前言
今天总结完基本背包问题后，准备复习一下一致性哈希的应用场景，阿里面试的时候讲了一下自己的理解感觉漏洞百出，这里分享一篇新浪架构师Tim Yang的文章：http://www.slideshare.net/iso1600/key-value-store，干货，收获很大
场景
假定场景为一IM系统，数据存储包括：
- 用户表（user）{id, nickname, avater, mood}
- 用户消息资料（vcard）{id, nickname, gender, age, location, ...}
- 好友表（roster）{[id1, subtype, nickname, avatar, remark], [id2, ...], ...}
单库单表时代
最初解决方案——单库单表，Mysql
随着用户增长，将会出现的问题——查询压力过大
通常的解决方案——Mysql replication及主从分离
用户数会继续增大，超出单表写的负载，单表数据库出现瓶颈，读写效率过低
分库分表时代
将用户按ID（或其它字段）分片到不同数据库
通常按取模算法 hash() mod n
解决了读写压力问题
Key value时代
我们需要的是一个分布式，自扩展的storage
web应用数据都非常适合key/value形式
User，vcard，roster数据
- {user_id:user_data}
问题
Range Select： 比如需删除一年未登录的用户
遍历： 比如需要重建索引
Search：广州，18-20
没有通用解决方法，依赖外部
Search：Lucene，Sphinx
非分布式key/value store
通过client hash来实现切分
通过replication来实现backup，load balance
Key store vs Mysql
性能：
- Key store读写速度几乎相同O(1),Mysql则为O(logN)
- 读写性能都比Mysql快上一个数量级以上
使用方式区别：
- Mysql：Relational <=> Object
- Key Store：Serialize <=> De-serialize
新需求
如何设计一个分布式的有状态的服务系统？
如IM Server， Game Server，用户分布在不同的服务器上，但彼此交互
CAP理论
分布式领域CAP理论：
- Consistency（一致性），Availability（可用性），Partition tolerance（分布）三部分在系统实现只可同时满足二点，无法三者兼顾
- 架构设计师不要精力浪费在如何设计能满足三者的完美分布式系统，而是应该进行取舍
Dynamo思想
淘宝译文：http://rdc.taobao.com/blog/cs/?cat=11 （ps：深入浅出，但是我更喜欢看一淘夜风师兄一致性哈希那篇blog）
The A.P. in CAP
- 牺牲部分consistency
- “Strong consistency reduce availability”
- Availability：规定响应时间(e.g. < 30ms)
Always writable
Decentralize
Consistent Hashing
传统的应用 如memcached，hash() mod n
问题：增删节点，节点失败引起所有数据重新分配
Consistent Hashing 如何解决这个问题？
Quorum NRW
NRW
- N：# of replicas
- R：min # of successful reads
- W：min # of successful write
只需要满足W+R > N