作者：刘旭晖 Raymond 转载请注明出处
Email：colorant at 163.com
BLOG：http://blog.csdn.net/colorant/
更多论文阅读笔记 http://blog.csdn.net/colorant/article/details/8256145
关键字
跨机房，数据同步，paxos，一致性，Google
Megastore
==
目标问题 ==
提供一个可伸缩的，高可靠，一致性好，跨地域，低延迟，易用性好的数据库存储方案
==
核心思想 ==
以上目标（本质需求上相冲突）很难做到面面俱到，需要在不同的方面进行取舍。Megastore的核心思想是将数据分割成不同的EntityGroup，EntityGroup的数据备份是跨Datacenter存放的，在EntityGroup内部提供完整的ACID支持，保证数据写操作在所有数据中心的同步备份。在EntityGroup之间只提供受限的ACID，例如不保证数据的强一致性等。
这种数据划分的思想主要是基于多数的数据内在的都可以按照一定的原则分组（如按用户划分），组内的操作的对一致性，实时性的要求比较高，但是因为多方同时操作同一个组的概率比较低，数据冲突发生的可能性较小，所以满足一致性等指标所带来的代价也比较小，而跨组的操作可以对数据一致性和更新延迟的容忍程度较高。可以降低这方面的指标。
如何在保证一致性的基础上做到高可靠性和高可用性的数据备份，是整个系统的关键。常见的广域数据备份方案各有优缺点：
- 异步的主从节点：主节点异步的将log写到从节点，不等待从节点的确认。这样的优点是延迟小，缺点是主节点失败时可能导致部分数据丢失，也难以保证高可用性。
- 同步的主从节点：主节点将log同步的写到从节点，只有得到确认后才允许完成当前操作，这样的优点是可以保证数据的可靠性，缺点是延迟大，主从节点的监控和切换需要有效的机制
- 乐观的平等主节点：没有主从节点之分，各个节点都可以接受数据修改，再异步的派发，优点是延迟小，高可用性，但是数据一致性得不到保障。
Megastore的方案有点类似平等的节点方案，没有主从节点之分，任何节点都可以发起写操作，但是通过Paxos机制来决定哪个写操作最终被采纳并分发，从而保证数据的一致性。
每个EntityGroup有自己的多备份的操作Log，保证高可用性，也可以最大并行化不同EntityGroup的操作。
跨EntityGroup的操作通过消息队列来实现，因而是弱一致性的。不过对于一致性要求高的应用，也可以使用两阶段提交的方式保证强一致性。
如何合理的划分EntityGroup，达到最佳性能则是用户需要考虑的。
==
实现细节 ==
- 提供了一个可完全串行化ACID的低延迟远程数据备份环境。
- 为了保证数据操作的低延迟，megastore允许用户指定EntityGroup的主数据中心，它的Schema的设计也保证EntityGroup内部数据的连续存储。
- 一个EntityGroup的数据可能存放在不同的表里（Entity
Root Table和child Table），而不同EntityGroup的相同字段的数据则是存放在同一个表里 - 由于BigTable这样的key-value类数据库本身是适合于存储稀疏结构化的数据的，在Read为主的应用环境下，尽量使用denormalization的Schema设计和存储方式，减少Join的开销
- 使用了BigTable的一个单元格可以存储多个Version的数据的特性来实现基于MVCC的ACID
- 读操作分为current/snapshot/inconsistant三类，由于采用MVCC，读写可以并行，不同的读操作针对不同的应用场合，current保证当前所有写操作已经完成，来读取最新数据，snapshot可以指定特定版本，inconsistant不保证数据的一致性，立刻读取当前数据
- 写操作通过Paxos机制决定下一个Log位置，任何replica都可以发起写操作，只有竞争获得下一个Log位置的进程，可以真正执行写操作，先写log，再Apply
change。类似乐观锁机制，竞争失败的写操作自己重试。 - Paxos模型的通讯开销是实现Paxos的系统或多或少都要面临的问题，Megastore使用了一个coordinator服务进程来跟踪本地数据备份replica中，哪些EntityGroup的数据是最新的，对这些数据，规避Paxos过程来直接读取本地数据。而coordinator的状态要由应用层在写操作是负责同步更新
- 除了完整的Replica Server，Megastore还使用了两种简化的Replica
Server角色，一种只保存Log不保存数据，另一种只保存数据不保存Log，分别用于Paxos仲裁和提供只读服务（可能不是最新版本的数据） - 如果coordinator实效了，写操作会被Block，这也就要求有一个机制检测coordinator的实效，megastore使用Chubby
Lock服务检测coordinator失效，对于coordinator自己来说，如果更新chubby
lock失败，就认为本地的数据都不是最新的，Read操作都要走Paxos流程，对于写操作，在检测到coordinator失效时就不等待他的invalidate操作返回，在失效被发现前，大概有10秒的时间write会被block，但是，实效的coordinator的恢复期间，读写操作都不会被block，依然可以正常进行。
==
数据 ==
平均读延迟10ms，平均写延迟100-400ms，取决于读写数据量的大小，数据备份replica的数量和数据中心的分布距离。可用性方面，基于多年100+的实际上线应用的数据统计多数可以达到99.999%以上的读写可用性。
==
相关研究，项目等 ==
项目相关的首先当然是底层的BigTable，其次是Chubby。理论相关如Paxos，和各种Fast
Paxos的优化方案研究等
类似的项目：阿里的Wasp，大概是基于Megastore的理论，在HBase上的一个仿照实现。
==
其它 ==
个人理解简单总结：
megastore本身不是数据库，更像一个基于Bigtable数据库的多数据中心数据备份读写解决方案，采用了各式各样的最佳实践来达到它的目的。使用Paxos来同步和保证数据Replica的读写一致性，采用划分EntityGroup的方式来减少Paxos过程的冲突，使用Coordinator/localread/chubby
lock以及其它各种机制来提高效率，减少延迟，检测失效。使用megastore client Library屏蔽底层实现复杂性的同时，也提供给用户足够的灵活性来指导数据的存放和读写以提高效率。同时提供了Index，schema，queue等以提高底层BigTable数据库的易用性。