k. To handle millions of users. Explain the following transactions
1) Adding/Deleting a friend
2) Friend suggestions
What if you cannot store all users on one server
一些大规模网站会用到的常用组件和技术。
参见http://tech.idv2.com/2008/08/17/memcached-pdf/
一些要点如下
一个典型的用例：
初始化一个Memcache的对象：
$mem = new Memcache;
连接到我们的Memcache服务器端，第一个参数是服务器的IP地址，也可以是主机名，第二个参数是Memcache的开放的端口：
$mem->connect(“192.168.0.200″, 12000);
保存一个数据到Memcache服务器上，第一个参数是数据的key，用来定位一个数据，第二个参数是需要保存的数据内容，这里是一个字符串，第三个参数是一个标记，一般设置为0或者MEMCACHE_COMPRESSED就行了，第四个参数是数据的有效期，就是说数据在这个时间内是有效的，如果过去这个时间，那么会被Memcache服务器端清除掉这个数据，单位是秒，如果设置为0，则是永远有效，我们这里设置了60，就是一分钟有效时间：
$mem->set(‘key1′, ’This is first value’, 0, 60);
从Memcache服务器端获取一条数据，它只有一个参数，就是需要获取数据的key，我们这里是上一步设置的key1，现在获取这个数据后输出输出：
$val = $mem->get(‘key1′);
echo ”Get key1 value: “ . $val;
现在是使用replace方法来替换掉上面key1的值，replace方法的参数跟set是一样的，不过第一个参数key1是必须是要替换数据内容的key，最后输出了：
$mem->replace(‘key1′, ’This is replace value’, 0, 60);
$val = $mem->get(‘key1′);
echo “Get key1 value: ” . $val;
同样的，Memcache也是可以保存数组的，下面是在Memcache上面保存了一个数组，然后获取回来并输出
$arr = array(‘aaa’, ’bbb’, ’ccc’, ’ddd’);
$mem->set(‘key2′, $arr, 0, 60);
$val2 = $mem->get(‘key2′);
print_r($val2);
现在删除一个数据，使用delte接口，参数就是一个key，然后就能够把Memcache服务器这个key的数据删除，最后输出的时候没有结果
$mem->delete(‘key1′);
$val = $mem->get(‘key1′);
echo “Get key1 value: ” . $val . ”
”;
最后我们把所有的保存在Memcache服务器上的数据都清除，会发现数据都没有了，最后输出key2的数据为空，最后关闭连接
$mem->flush();
$val2 = $mem->get(‘key2′);
echo “Get key2 value: ”;
print_r($val2);
echo ”
”;
在多机并行的时候，有一个严重的问题是在增减机器后，会出现大范围的缓存失效（key被映射到不同的机器上），解决方法是使用consistent hashing, 介绍在：
http://tech.idv2.com/2008/07/24/memcached-004/#content_2_6
Consistent Hashing的简单说明
Consistent Hashing如下所示：首先求出memcached服务器（节点）的哈希值， 并将其配置到0～2^32的圆（continuum）上。 然后用同样的方法求出存储数据的键的哈希值，并映射到圆上。 然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。 如果超过2^32仍然找不到服务器，就会保存到第一台memcached服务器上。
图4 Consistent Hashing：基本原理
从上图的状态中添加一台memcached服务器。余数分布式算法由于保存键的服务器会发生巨大变化 而影响缓存的命中率，但Consistent Hashing中，只有在continuum上增加服务器的地点逆时针方向的 第一台服务器上的键会受到影响。
图5 Consistent Hashing：添加服务器
因此，Consistent Hashing最大限度地抑制了键的重新分布。 而且，有的Consistent Hashing的实现方法还采用了虚拟节点的思想。 使用一般的hash函数的话，服务器的映射地点的分布非常不均匀。 因此，使用虚拟节点的思想，为每个物理节点（服务器） 在continuum上分配100～200个点。这样就能抑制分布不均匀， 最大限度地减小服务器增减时的缓存重新分布。
通过下文中介绍的使用Consistent Hashing算法的memcached客户端函数库进行测试的结果是， 由服务器台数（n）和增加的服务器台数（m）计算增加服务器后的命中率计算公式如下：
(1 – n/(n+m)) * 100
另外还有一个需求是将memcache中的数据持久化，可以考虑定期持久化。
关于NoSQL的文章
http://sebug.net/paper/databases/nosql/Nosql.html