根据网上公开资料整理的Twitter架构，主要是cache方面，加了作者自己的补充，跟实际的架构未必完全一致。
一些数据：
参考资料：
最近项目中一个分布式应用碰到一些设计问题，听过上次技术沙龙key value store漫谈的同学可能会比较容易理解以下说明。
场景
假定一个有状态的服务，可以理解成web或者socket服务器，每个用户在这个服务上登录后是有状态的，我们把它的状态连同其他加载到内存的用户数据统称用户session。由于session数据实时会变化，加上程序访问session频率大，几乎所有的操作都跟session数据相关，因此不适合放在远程memcached中
第一阶段
考虑到单服务器不能承载，因此使用了分布式架构，最初的算法为 hash() mod n, hash()通常取用户ID，n为节点数。此方法容易实现且能够满足运营要求。缺点是当单点发生故障时，系统无法自动恢复。
第二阶段
为了解决单点故障，使用 hash() mod (n/2), 这样任意一个用户都有2个服务器备选，可由client随机选取。由于不同服务器之间的用户需要彼此交互，所以所有的服务器需要确切的知道用户所在的位置。因此用户位置被保存到memcached中。
当一台发生故障，client可以自动切换到对应backup，由于切换前另外1台没有用户的session，因此需要client自行重新登录。
这个阶段的设计存在以下问题
第三阶段
打算去掉硬编码的hash() mod n 算法，改用一致性哈希(consistent hashing)分布
假如采用Dynamo中的strategy 1(可参看Dynamo: Amazon’s Highly Available Key-value Store, PDF, P216)
我们把每台server分成v个虚拟节点，再把所有虚拟节点(n*v)随机分配到一致性哈希的圆环上，这样所有的用户从自己圆环上的位置顺时针往下取到第一个vnode就是自己所属节点。当此节点存在故障时，再顺时针取下一个作为替代节点。
优点：发生单点故障时负载会均衡分散到其他所有节点，程序实现也比较优雅。
应用一致性哈希分布后若干问题
1.如何解决单点故障时候的session迁移？是否所有session都像Dynamo那样写入到多个节点(或双写)？如果双写所有的服务器需要消耗2倍的内存及更多CPU资源，所以优先不考虑双写方案。
2.如果不双写，则发生故障切换时，即使服务器内部自动帮用户切换节点不重新登录，都需要牵涉到大量session重建，会引起集群震荡。当然这里可以稍微优化，比如session按需建立，IDLE的用户可以先不重建。
3.当故障节点恢复时候如何处理？Dynamo的策略是故障期间所有的数据都属于hinted handoff, 就是备用机起业务代理作用，一旦故障机恢复就立即把所有临时数据从备用机拉回去，然后整个集群恢复正常流程。但由于本场景session数据比较笨重，而且牵涉到复制时存在并发变更，如果直接借鉴Dynamo的话则感觉切换成本过高，大部分开发人员倾向于继续用备用机处理该用户业务。如果恢复正常后不切换，则存在用户位置的不确定性，使用一致性哈希算出来的结果和用户实际所在的节点不同。需要顺着圆环往下找用户,效率很低。因此就有提议把所有用户所在的当前节点位置写入memcached。
5. 假如需要将位置写入memcached,那似乎一致性哈希算法又成了花瓶，完全可以由client在create session时候随机选取一个没有故障的节点, 然后把位置写入memcached, 某个节点发生故障时，client再另外选一个随机的，并把新的位置写入memcached, 所有用户所在节点的位置都通过memcached来存储，服务器之间实时的通讯也通过查询memcached来寻址。从实用的角度来看，这样似乎程序更简单。
因此，一致性哈希分布对于这个场景来说是无用的？
在分布式领域有个CAP理论(Brewer’s CAP Theorem) ，是说Consistency(一致性), Availability(可用性), Partition tolerance(分布) 三部分在系统实现只可同时满足二点，没法三者兼顾。所以架构设计师不要把精力浪费在如何设计能满足三者的完美分布式系统，而是应该进行取舍，选取最适合应用需求的其中之二。比如MySQL 5.1 cluster设计前显然不知道有CAP理论这样的经验, 所以MySQL cluster表面看来尽管可提供所有分布式特性，但实际大部分场合都无法提供稳定可靠的服务。
Yahoo!的PNUTS是一个分布式的数据存储平台，它是Yahoo!云计算平台重要的一部分。它的上层产品通常也称为Sherpa。按照官方的描述，”PNUTS, a massively parallel and geographically distributed database system for Yahoo!’s web applications.” PNUTS显然就深谙CAP之道，考虑到大部分web应用对一致性并不要求非常严格，在设计上放弃了对强一致性的追求。代替的是追求更高的availability，容错，更快速的响应调用请求等。
传统的数据库提供强一致性保证, 通常称为“serialization transaction”，保证调用时序的一致性。但在web应用中不是必须，比如用户A修改了自己的资料或上传了图片，他的好友B短时间不能立即看到并不是大的问题，通常的Web应用都可以接受。PNUTS像大部分分布式key/value系统类似，提供的是弱一致性的支持，也就是支持“最终一致性(eventually consistent)”。用户B最终会看到用户A的修改信息。
未够！但最终一致性并非可以适应所有场合，比如用户A修改了相册的访问权限，设置用户C不能访问，然后用户A又上传了新的图片，如果用户C处于另外一个IDC访问，如果图片数据先同步成功，而权限记录后同步的话，C实际上违反了A设置的权限而看到图片了。因此对于部分场合最终一致性是不够的。
每一条记录都有一个主记录。比如一个印度的用户保存的记录master在印度机房，通常修改都会调用印度。其他地方如美国用户看这个用户的资料调用的是美国数据中心的资料，有可能取到的是旧版的数据。非master机房也可对记录进行修改，但需要master来统一管理。每行数据都有自己的版本控制，如下图所示。
Write调用示意图
记录级别master的问题，比如master选取如何达到效率最佳，如何面对2个修改合并冲突?合并冲突据说是需要client自行来处理，
这篇Details on Yahoo’s distributed database提到的平均调用latency 100ms的问题。web应用通常对每次数据的访问最好在10ms之内完成，因为每个web页面实际上不止一个数据访问的调用，经常调用10次以上db的访问的页面并不少见，因此如果平均latency在100ms以上那势必影响页面加载速度。不过yahoo!的开发人员回复paper中的数据实际是一个老版本的测试，目前的版本，在实际生产环境的pnuts的latency会在10ms以下。
另外PNUTS为什么要用消息系统代替replication/undo log？有何优点？
Web应用使用通用的存储服务是大势所趋，类似BigTable, Amazon Dynamo/SimpleDB这样的方案，但是目前除非使用Amazon提供的商用SimpleDB之外几乎没有通用的解决方案，每个公司甚至每个项目需要面对及考虑数据规模增大的问题。比如初步统计下国内研究可扩展数据存储及访问的项目就有
当然上面几个只是冰山一角，大部分互联网公司都有自己的数据层分布及访问实现，只不过没有对外公开而已。架构师、DBA、程序员具备这方面的实践经验及技能当然是好事，但是如果业界能够有通用稳定的解决方案来解决大家的重复工作则对整个业界更佳。PNUTS虽然声称会开源，但是一直没有进一步消息。而且即使开源是是开放核心代码还是全部可用于部署的程序(比如YMB等)这也是一个问题。
当然，我不是第一个也不是最后一个考虑这个问题的，比如2006年Greg Linden就说I want a big, virtual database
What I want is a robust, high performance virtual relational database that runs transparently over a cluster, nodes dropping in an out of service at will, read-write replication and data migration all done automatically.
I want to be able to install a database on a server cloud and use it like it was all running on one machine.
参考资料
