Dynamo学习

      看了介绍Dynamo的论文，虽然英文不济，理解可能有误，但还是交流一下学习心得。Dynamo是亚马逊的key-value模式的存储平台，可用性和扩展性都很好，性能也不错：读写访问中99.9%的响应时间都在300ms内。

数据划分
      按分布式系统常用的哈希算法切分数据，分放在不同的node上。Read操作时，也是根 据key的哈希值寻找对应的node。Dynamo使用了Consistent Hashing算法【参考 http://tech.idv2.com/2008/07/24/memcached-004/】，node对应的不再是一个确定的hash值，而是一 个hash值范围，key的hash值落在这个范围内，则顺时针沿ring找，碰到的第一个node即为所需。
      Dynamo对Consistent Hashing算法的改进在于：它放在环上作为一个node的是一组机器（而不是memcached把一台机器作为node），这一组机器是通过同步机制保证数据一致的。
以上图为例，node1其实包含了多台机器，在一个node里宕了一台机或增加一台机，并不影响整个Dynamo对key的寻找。
      如果一个ring内的访问量大了，则可以在两个node间加入一个新node以缓解压力，这时会影响到其后继node的hash范围，需要调整数据。假设一 个ring中原本只有node2、node3、node4，在加入新的node1之后，原先从node2查询的部分key将改为从node1查 询，node1和node2中的数据就需要调整，主要是node1从node2中提取出属于它的数据，这样做需要选取性能压力不高的时候。（至于具体的调 整方法，从论文中没找到 -_-b）

数据同步
      Dynamo的一个node中的同步是由client端来“解决”的，使用所谓的（N, R, W）模型，其中，N表示node中机器的总数，R表示一个读请求需要的机器参与总数，W代表一个写请求需要的机器参与总数，这些值由client端配置。
      例如，一个node有5台机器（N=5），client发出写请求——广播到5台机，如果收到3个“写完成”的返回消息，即认为写成功 （W=3）；client发出读请求——还是广播到5台机，如果收到2个“读完成”的返回消息，即认为读成功（R=2）。对于数据十分重要的应用（如金融），配置可以为(5, 5, 5)，即要求node中所有机器的写都成功；而对于数据读写访问量极高的应用，配置可以为（5, 1, 1）。
      通常W不等于N，于是，在某些情况下一个node内的机器上的数据可能会有不一致，这时Dynamo是通过将多个Read的返回结果“合并”来得出最终结果 的，使用了所谓Object Version和Vector clock的技术，即跟踪一个Object在不同机器上的版本变化，以确保当多个Read请求结果返回不一致时，能够更具其版本信息得出正确的结果。 Dynamo的这种做法是一种折衷，即为了同时保证读和写的效率，写操作不要求绝对同步，而把不同步可能产生的后果推给了读操作。

数据恢复
      Dynamo的一个node中一台机器建有一个Merkle Tree，当两台机器不一致时（如一台机器宕机一段时间），通过这个tree结构，可以快速定位不一致的Object来恢复数据。Merkle Tree又叫Hash Tree，它把key分成几个range，每个range算出一个hash值，作为叶子，再一层层合并计算上去，这样，从root开始比较hash值，就可以快速找到哪几段range中的hash值变化了。

      个人感觉Dynamo的同步策略有点别扭，读采用广播，怎么保证读的效率呢？当然，也许人家有高招。