Dynamo: Amazon’s Highly Available Key-value Store

参考：http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html

 

所谓key-value存储系统就是，系统提供两个提口，一是put,一是get，put的时候，传进key与value，就可以把数据写到系统里，get的时候，传进key，就可以获得相应的value。

key-value存储系统可以认为是从传统的关系数据库系统演化而成。传统的关系数据库在WEB应用中，存在性能、可扩展性、容灾等方面的问题，而观察发现，WEB应用中，大部分情况下不需要作关系查询，可以只支持key-value查询，以提高性能，可扩展性等

简 单来说，只需要维护一个HASH表或者B树一类的索引结构，然后把value存在硬盘上，就是一个简单的key-value存储系统了。但是如果数据量大 了，单机就存不下来了，或者能存下来，但是查询速度会比较慢，这时候就需要分多台机器储存了。这时候就进化成一个分布式的key-value存储系统了。 我想国内很多公司山寨的KEY-VALUE存储系统就只做到这一步。

一般的做法是对key取模，然后分到相应的机器上。但是这样新增机器或者减少机器的时候会很麻烦，所以Dynamo用的是consistent hash（http://hi.baidu.com/rodimus/blog/item/6f23a9c4512b2dc638db4928.html ），用的时候，是把一台机器映射成多个节点，一方面是使数据分布更均匀，另一方面性能好的机器映射成更多的节点，从而充分利用机器性能

至 此数据已经可以存下来了，但是如果有机器坏了怎么办？需要作备份，一般认为两个备份不够，需要三个备份。最简单的备份方式是有几台完全相同的机器互为备 分，但是这样修改备份数的话，会比较麻烦。可能还有别的考虑吧，Dynamo的做法是，一台机器是部分数据的首选，同时是多台机器的备分。

作 备份容易，难的是作了备份之后，每次作写操作都需要写多台机器，性能下降了，极端情况下，有一台坏了，就是写不成功。所以写的时候，可以在部分机器写成功 后就返回，剩下的后台再继续写。这样写简单了，读就麻烦了。读的时候如果只读一台机器，可能会读到旧的数据，如果读多台机器，可能会读到不同的数据，一般 情况下，如果有N个备份，写W台，读R台，保证W+R>N，则至少可以读到一份新的数据。读到的R份数据可能会不同，Vector clocks（http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.142.3682&rep=rep1&type=pdf ）理清各个版本的关系，具体的merge逻辑，由上层应用决定(在并发写的情况下，可能会有两份并行的数据，底层很难知道应该保留哪个)，把merge后的数据，再回写到存储系统里。

作为长期运行的系统，迟早会有机器出故障的。系统小的时候，故障的频率低，可以手工修复。系统大了，就不行了。故障要分两种，一种是临时性的，一种是永久性的。

对 于临时性错误，每个key对于所有的机器有个优先级考虑，之前是选前N个来存储，现在改为前N个健康的机器存储，当A机器故障，而被迫把A的数据写往D的 时候，数据里带一个信息告诉D，这部分数据是属于A的，D会把这部分数据与原来属于它的数据分开存储，然后在A恢复后（需要周期性地探测），再把数据拷回 去。在A已经恢复，正在把数据拷回去的时候，读写会比较复杂。

有一种情况是，D也出问题了或者别的情况，反正现在没办法把D帮A存的数据搬到A上面去了。这种情况下，A复活后，需要从别备份机上拷贴贝数据。为了减少数量拷贝量，采用hash tree（http://hi.baidu.com/rodimus/blog/item/5787a5c84983691d7f3e6f3a.html ）。hass tree可以使得同步的数据很少，但是维护的代价比较大。

至此系统已经可以运行了。但是随着数据的数据的变化，可能会增加或者移除机器，consisten hash可以保证冲击会很小，系统会自动地进行数据的迁移。

 

一般的所谓分布式系统，都会有一个中控机。但是Dynamo是没有的，这是一个P2P的系统，所有的机器之间用gossip-based protocol通信