Design of a tinyurl service

A tinyurl service compresses a long url into a short one. This saves space, and is useful for scenarios such as twitter or weibo, where each character counts.  The down side is possible spam use.  Concerns include longevity of a short url.

== Single Server ==

What a tinyurl service does is essentially: long-url <==> short_url. The conversion is double-sided, i.e., a two-way function. A site registers its url at the service, and then provides the short url to visitors. The visitors visit the short url, which then redirects them to the original (mostly longer) url.

A common way of thinking is to hash the long url into a short one. However this is not correct, because hash is a one-way function.

Many ways can be used to do the compression. One of the most simple but also effective one, is to have a database table set up this way:

Table T_Url_Conversion (
    ID : int PRIMARY_KEY AUTO_INC,
    Original_url : varchar,
    Short_url : varchar
)

Then the auto-incremental primary key ID is used to do the conversion: (ID, 10) <==> (short_url, BASE). Whenever you insert a new original_url, the query can return the new inserted ID, and use it to derive the short_url, save this short_url and send it to cilent.

Here the BASE can be 62 for a-zA-Z0-9, or 36 for a-z0-9. So this is a conversion of numbers between base-10 and base-62 or base-36. If use base-62, and with a short_url length of 6 characters, that's a space of 62^6 =~ 57 billion short urls to use.

One concern is some short url strings will be reserved, say for at least 2 reasons: 1) urls reserved by certain clients for branding purpose, 2) dirty words that are avoided by clients. Such reserved strings can be stored in another table, and do a check upon new short_url generation.

Follow this design, one can easily setup a website providing short url service. This idea is not new, other people already came up with it [1][2][3].

== Multiple Servers ==

[1] also discussed the case of distributed design. However the scheme to do the assignment is not clear: when receiving a long url it can be hashed to a value and choose a target storage server according to this value.  This may work if the fictitious universal hashing function can evenly dispatch the requests to different servers.  But a more serious issue is, when receiving a short url, how can you know which server it belongs to?

I think one solution can be like this:

-- Solution I --
Say there are 3 servers, and a load-balancing machine that does the assignment in a round-robin fashion: for insertion requests 3k, 3k+1, 3k+2, assign them to servers 1, 2 and 3 respectively. On each server, the ID starts at 1, 2 and 3, and all increment by 3. This way, the first server stores ID 1, 4, 7 .., the second server stores ID 2, 5, 8 ..., the third server stores ID 3, 6, 9.. So when you receive a short url and converts it back to N, then you can go to server N%3.

The potential shortcoming of this method, is when you need to add a fourth server, then the split method is broken. A possible solution can be dividing 3k to 6k' and 6k' + 3. Here is another solution that can be better:

-- Solution II --
Since we already know that by only using 6 characters, the short_url space is about 57 billion, so this distributed scenario comes up only because of heavy load, not for lack of short_url space. So we may have the luxury to use an extra character to specify which server to go: say the short_url is abc, then we append a last digit to specify the server to go. For example, if it goes to server 2, then we make the short_url abc2. This way, the load-balancer continues with the round-robin modulo assignment algorithm when new servers are added, and short_urls can easily find their way. Also, now each server does not have to increment their ID by server_count now, and can use continuous ID.  Seems now everyone can live happily ever after.

It is further easy to see that, using this method, with one appended digit, one can have up to 62 servers on a base-62 system. This should be enough for such a simple service.

It is also easy to see that the initial long_url assignment approach of load-balancer is independent from the short_url assignment method.The long_url assignment now can actually use a universal-hashing method, but a round-robin method still works well and is indeed more simple with just a counter, and is fault-tolerant: losing the counter for a while does not actually matter.

References:
[1] System Design for Big Data [tinyurl]
[2] URL Shortening: Hashes In Practice, 21 Aug 2007
[3] How to code a URL shortener?

Memcached

Today start to look at Memcached.

Memcached [1][7] is a distributed in-memory key/value cache system. It is open source under the BSD license.  The first version was written in Perl by Brad Fitzpatrick in May, 2003 for his website Live Journal (as one can notice, this site runs very fast).  Then it was re-written in C by Anatoly Vorobey.  It uses server-client architecture. Multiple servers don't talk to each other, the client hashes the key and chooses a target server to store the data. It's designed for unix/linux, but was ported to windows too. That's all about it.

Memcached homepage is at [1]. Here you can understand what it's about, and download it. There is a small wiki [6] that contains basic information about it. The current version is 1.4.20 as of July 2014.

== Install ==

1) To install from package (recommended, especially if you are deploying to multiple servers):

Ubuntu & Debian: apt-get install memcached
Redhat/Fedora: yum install memcached
FreeBSD/(Mac ?): portmaster databases/memcached

2) Although less recommended, you can install from source too:

First you will need libevent as pre-requisite:
Ubuntu: apt-get install libevent-dev
Redhat/Fedora: yum install libevent-devel

Then install memcached:
wget http://memcached.org/latest
tar -zxvf memcached-1.x.x.tar.gz
cd memcached-1.x.x
./configure [--prefix=/usr/local/memcached]
make && make test
sudo make install

== Run from console ==

memcached [-m 64] -p 11211

Here -m specifies the memory allocated, unit is MB. -p is the port used, and 11211 is the default.

-- Test --

You can test memcached using the telnet interface: telnet localhost 11211
Then these commands can be used [2][3][4]:

get [key]
set [key flag timeout size]
add [key flag timeout size]
replace [key flag timeout size]
append [key flag timeout size]
prepend [key flag timeout size]
incr [key int_value]
decr [key int_value]
delete [key]
flush_all [ |timeout]
stats [ |slabs|malloc|items|detail|sizes|reset]
version
verbosity
quit

An example console session is:

> telnet localhost 11211
Trying ::1...
Connected to localhost.
Escape character is '^]'.
version
VERSION 1.4.20  
verbosity 10   # this will cause the server side echo telnet client input.
OK
stats
...                  
stats slabs
...
stats items
...
add mykey1 0 3600 5  # "mykey1" is the key, "0" is a 32-bit unsigne int  flag, "3600" is expiration (seconds), "5" is data size.
12345            # this is the data you store at key "mykey1".
STORED      
get mykey1
12345
END
quit
Connection closed by foreign host.

== Run as daemon ==

memcached -d

Or:
sudo service memcached stop
sudo service memcached start
sudo service memcached restart

Or:
sudo /etc/init.d/memcached start
sudo /etc/init.d/memcached stop
sudo /etc/init.d/memcached restart

Now if you run "top" command, you can see "memcached" in list of processes. You can run multiple versions of memcached using different ports. For more details, refer to [5] etc.

== Configuration of server, client and cluster ==

See [6].

== More things about using memcached, maintenance and development ==

See [6].

== Source code ==

The source code is available by instruction at [8] on its homepage [1]. A count of LOC on the current version is:

[./memcached/assoc.c] Lines: 293
[./memcached/assoc.h] Lines: 9
[./memcached/cache.c] Lines: 148
[./memcached/cache.h] Lines: 116
[./memcached/daemon.c] Lines: 89
[./memcached/globals.c] Lines: 25
[./memcached/hash.c] Lines: 21
[./memcached/hash.h] Lines: 14
[./memcached/items.c] Lines: 936
[./memcached/items.h] Lines: 37
[./memcached/jenkins_hash.c] Lines: 431
[./memcached/jenkins_hash.h] Lines: 15
[./memcached/memcached.c] Lines: 5646
[./memcached/memcached.h] Lines: 610
[./memcached/murmur3_hash.c] Lines: 124
[./memcached/murmur3_hash.h] Lines: 19
[./memcached/protocol_binary.h] Lines: 470
[./memcached/sasl_defs.c] Lines: 190
[./memcached/sasl_defs.h] Lines: 31
[./memcached/sizes.c] Lines: 29
[./memcached/slabs.c] Lines: 882
[./memcached/slabs.h] Lines: 49
[./memcached/solaris_priv.c] Lines: 44
[./memcached/stats.c] Lines: 375
[./memcached/stats.h] Lines: 8
[./memcached/testapp.c] Lines: 1967
[./memcached/thread.c] Lines: 854
[./memcached/timedrun.c] Lines: 102
[./memcached/trace.h] Lines: 71
[./memcached/util.c] Lines: 144
[./memcached/util.h] Lines: 33

[.] Total Lines: 13782

== Windows version ==

Memcached was designed for unix/linux. However, windows version is also available due to community support [9][10]. [11] is an example that seems no longer available.  One major vendor seems to be North Scale labs, they first provide memcached for windows as a stand-alone application, then combines it into their NoSQL product MemBase, and finally combines into CouchBase [12].


References:

[1] http://memcached.org
[2] Memcached telnet command summary
[3] Memcache Telnet Interface
[4] github: memcached / doc / protocol.txt 
[5] stackoverflow: stop and restart memcached server
[6] Memcached wiki 
[7] Wiki: memcached
[8] Obtain memcached source 
[9] memcached 1.4.4 Windows 32-bit binary now available!
[10] Memcached on Windows (x64)
[11] Installing Memcache on Windows
[12] http://www.couchbase.com/

What JavaScript can do in browser for game programming

This is what javascript can do in browser for game programming now:

http://www.babylonjs.com/

This is from Microsoft developer, and features engine for many 3D effects that used to be available on desktop applications only. Note you will need a browser that supports WebGL, such as Chome.

WebGL [1][2] makes use of GPU (Graphics Processing Unit) to render 2D and 3D graphics in browser.

References:
[1] Wiki: WebGL
[2] Compatibility table for support of WebGL in desktop and mobile browsers

The Mandelbrot Set and Fractals

The Mandelbrot set and associated Julia set are examples of beautiful fractal graphics derived from mathematics. Here is Wolfram Mathworld's introduction to the Mandelbrot set. Some relevant books are:

[1] Amazon: The Fractal Geometry of Nature, by Benoit B. Mandelbrot, 1982.

This books, however, does not have good review as the writing is said to be not so good. A review on Amazon is: "It is not an easily readable book. 1. It is not well-organized 2. It does not cover necessary things in detail 3. Frustratingly long in some parts." Books on this topic that are said better by Amazon reviewers:

[2] Feder, Fractals; Turcotte, Fractals and Chaos in Geology and Geophysics.
[3] The Science of Fractal Images, edited by Peitgen and Saupe. The math is clear; the algorithms are plainly stated for the PC enthusiast with some simple programming skills; and the color plates are astounding.

The first Mandelbrot set image was created in 1978. The Python program below from [4] will draw such an image. Note to run the Python program you need Numpy, which stands for Numerical Python, and is a scientific computation module of Python. You can download the win32 installation package from [6], or amd64 version from [7]. On my system, I have Python 2.7.1 and use Numpy 1.8.1. 

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Copyright (c) 2013, P. Lutus http://arachnoid.com
# Released under the GPL http://www.gnu.org/licenses/gpl.html

from numpy import arange

# dimensional parameters for the set

yl = -1.2
yh = 1.2
ys = .05

xl = -2.05
xh = 0.55
xs = 0.03

def mandelbrot(c):
  z = 0
  for n in range(10):
    z = z*z + c
    if(abs(z) > 2):
      return '.'
  return '*'
 
s = ''
for y in arange(yl,yh,ys):
  for x in arange(xl,xh,xs):
    s += mandelbrot(complex(x,y))
  s += '\n'
 
print(s)

[5] contains an example program to draw the Mandelbrot set image in iPhone.

[8] is about doing the drawing in JavaScript. It includes the formula of Linas Vepstas algorithm to draw a smoothed-color version of the image:




References:

[4] Mandelbrot Set - An exploration in pure mathematics
[5] A Mandelbrot Set Visualization on the iPhone
[6] Sourceforge: Numerical Python
[7] Unofficial Windows Binaries for Python Extension Packages
[8] Visualizing the Mandelbrot set with JavaScript

A Game of M.C. Escher style

Monument Valley - very nice game on geometries like in the paintings of M.C. Escher. Only shortcoming as many reviewers complain, is the game is too short, only 10 levels and can be finished in 1 hour. Guess they need to put in more levels later.

It proves again that fine combination of computer programming with arts will make a good product.

Youtube: Monument Valley - Gameplay Walkthrough ALL Levels 1 - 10 (1080p) (59m 36s)

Estimate size of MSSQL Table with indices

How to estimate the size of a MSSQL table with indices?

It's not enough to just multiply number of rows with the size of each row, because there are other entities involved, mostly the index. Relevant concepts are clustered/non-clustered index, unique/non-unique index, fill factor of an index, fix/variable length column, page size (8192 or 8K bytes), Null bitmap etc.

For MSSQL 2008, see MSDN articles [1][2][3]. For other versions of MSSQL, relevant links are in articles [1][2].

[1] Estimating the Size of a Clustered Index (MSSQL 2008)
[2] Estimating the Size of a Nonclustered Index (MSSQL 2008)
[3] Estimating the Size of a Table with a Clustered Index (MSSQL 2000)

Note that "Step 1. Calculate the Space Used to Store Data in the Leaf Level" in [1] is basically copied from [3], the only difference in [1] is the addition of "3. If the clustered index is nonunique, account for the uniqueifier column:". This actually calculates the combined size of both data and index in the leaf level nodes. In that the title of article [1] is inaccurate.

A query that directly read data and index information from the database is below (from here):

with pages as (
    SELECT object_id, SUM (reserved_page_count) as reserved_pages, SUM (used_page_count) as used_pages,
            SUM (case 
                    when (index_id < 2) then (in_row_data_page_count + lob_used_page_count + row_overflow_used_page_count)
                    else lob_used_page_count + row_overflow_used_page_count
                 end) as pages
    FROM sys.dm_db_partition_stats
    group by object_id
), extra as (
    SELECT p.object_id, sum(reserved_page_count) as reserved_pages, sum(used_page_count) as used_pages
    FROM sys.dm_db_partition_stats p, sys.internal_tables it
    WHERE it.internal_type IN (202,204,211,212,213,214,215,216) AND p.object_id = it.object_id
    group by p.object_id
)
SELECT object_schema_name(p.object_id) + '.' + object_name(p.object_id) as TableName,  

       (p.reserved_pages + isnull(e.reserved_pages, 0)) * 8 as reserved_kb,
        pages * 8 as data_kb,
        (CASE WHEN p.used_pages + isnull(e.used_pages, 0) > pages 

              THEN (p.used_pages + isnull(e.used_pages, 0) - pages) ELSE 0 END) * 8 as index_kb,
        (CASE WHEN p.reserved_pages + isnull(e.reserved_pages, 0) > p.used_pages + isnull(e.used_pages, 0) 

         THEN (p.reserved_pages + isnull(e.reserved_pages, 0) - p.used_pages + isnull(e.used_pages, 0)) else 0 end) * 8 as unused_kb
from pages p
left outer join extra e on p.object_id = e.object_id

Largest collection of FREE Microsoft eBooks ever

Largest collection of FREE Microsoft eBooks ever, including: Windows 8.1, Windows 8, Windows 7, Office 2013, Office 365, Office 2010, SharePoint 2013, Dynamics CRM, PowerShell, Exchange Server, Lync 2013, System Center, Azure, Cloud, SQL Server, and much more ...