这是一篇在阅读《大规模分布式存储系统：原理解析与架构实战》时的阅读笔记，由于长时间碎片阅读的关系导致在做这种读书笔记的时候接近复制粘贴。虽然其中会有一小部分自己的想法但都十分零碎，希望后续能改进。
Megastore在Bigtable系统之上提供呢有好的数据库功能支持，增强易用性。Megastore是介于传统的关系型数据库和NoSQL数据库之间的存储技术。
从Bigtable的单表应用向着传统数据库方向发展，使得一个分布式存储系统对外表现为传统的关系型数据库，不说是方便用户使用，应该是在功能上逐渐拥有传统数据的功能：跨表事务、多表联查等
互联网应用往往可以根据用户进行拆分，比如Email系统、相册系统、广告投放效果报表系统、购物网站商品存储系统等。同一用户内部的操作需要保证强一致性，比如要求支持食物，多个用户之间的操作往往只需要最终一致性，比如用户之间发Email不要求立刻收到。因此，可以根据用户将数据拆分为不同的子集分布到不同的机器上。
根据业务将系统进行拆分为独立的子系统，并将数据也随之拆分。这就是现在的微服务。
谷歌进一步从互联网应用特性中抽取实体组（Entity Group）概念，从而实现可扩展性和数据库语义之间的一种权衡，同时获得NoSQL和RDBMS的优点。
什么是实体组？用户定义了User和Photo两张表，主键分别为<user_id>和<user_id, photo_id>,每一个用户的所有数据构成一个实体组。其中User表是实体组根表，Photo表是实体组子表
对现实事物的抽象就是一个实体组？每一个用户的所有数据构成了这个用户本身。用户实体组当然要以用户为核心。
实体组根表中的一行成为根实体（Root Entity），对应Bigtable存储系统中的一行。根实体除了存放用户数据，还需要存放Megastore事物及复制操作所需的元数据，包括操作日志。
表6-1中有两个实体组分别是101和102:
从字段可以看到，实体组是一个抽象的概念，在数据库中并不会按照一个实体组一行数据这样的形式保存，而是将一个“用户”的概念拆分成多张表，并在逻辑层面将这些表的数据拼装成一个实体（Entity），证据就是101的用户，在实体组中记录了它多次对Photo进行操作的记录，同时并没有一张拥有name与time的表。
其中101,500是Photo的主键<user_id, photo_id>。
Bigtable通过单行事务保证根实体操作的原子性，而一个实体组就是一行，因此对同一个实体组的操作都会是原子性的。
又因为同一个实体组的数据都是连续存放，因此一个用户的数据往往会存在同一张子表中，分布在同一台Tablet Server上，从而提供较高的扫描性能和事务性能，当然，也能够将实体组分不到多台服务器上。
系统架构
Megastore由三个部分组成：
- 客户端库：提供Megastore到应用程序的接口，应用程序通过客户端操作Megastore的实体组。Megastore系统大部分功能集中在客户端，包括映射Megastore操作到Bigtable，事务及并发控制，基于Paxos的复制，将请求分送给复制服务器，通过协调者实现快速读等。
- 复制服务器：接受客户端的用户请求并转发到所在机房的Bigtable实例，用于解决跨机房连接数过多的问题。
- 协调者：存储每个机房本地的实体组是否处于最新状态的信息，用于实现快速读。
Megastore的功能主要分为三个部分：映射Megastore数据模型到Bigtable，事务及并发控制，跨机房数据复制及读写优化。
1. Megastore首先解析用户通过客户端传入的SQL请求
2. 接着根据用户定义的Megastore数据模型将SQL请求转化为对底层Bigtable的操作。
在上表中，假设用户（user_id = 101)往Photo表格中插入photo_id分别为500和502的两行数据。这就意味着需要向Bigtable写入主键分别为<101, 500>和<101, 502>这两行数据。这两行数据在Bigtable属于同一个版本，客户端要么读到全部行，要么一行也读不到。
同一个版本应该是属于同一次操作吧，即一次操作同时插入两行。这一次操作就是原子性的。
实体组
GFS在底层负责保存数据，并维持数据的高可用与高容错；Bigtable在GFS之上抽象出了“表格”，并保持表格数据的一致性，但对外只有对表格数据的增删改查这些简单的服务；Megastore在Bigtable之上又添加了事务与并发支持，并同时增加高度灵活的SQL语句解析器，将SQL语句解析为对Bigtable的增删改查
从图中看到，数据拆分成不同的实体组，每个实体组内的操作日志采用基于Paxos的方式同步到多个机房，保证强一致性。
实体组之间通过分布式队列的方式保证最终一致性或者两阶段提交协议的方式实现分布式事务。
单集群实体组内部：同一个实体组内部支持满足ACID特性的事务。数据库系统事务实现时总是会提到REDO日志和UNDO日志，在Megastore系统中通过REDO日志的方式实现事务。同一个实体组的REDO日志都写到这个实体组的根实体中，对应Bigtable系统中的一行，从而保证REDO日志操作的原子性。客户端写完REDO日志后，事务操作成功，接下来只需要回放REDO日志。如果回放REDO日志失败，比如某些行所在的子表服务器宕机，事务操作也可以成功返回客户端，后续的读操作如果要读取最新的数据，需要先回放REDO日志。
用户这一行数据包含他的REDO操作日志，通过这列可以获取到这行数据所表示的实体执行的REDO操作。
REDO日志：记录事务修改后的状态。
Bigtable保证单行数据的原子性
单集群实体组之间：实体组之间一般采用分布式队列的方式提供最终一致性，子表服务器上又定时扫描线程，发送跨实体组的操作到目标实体组。如果需要保证多个实体组之间的强一致性，即实现分布式事务，只能通过两阶段提交协议加锁协调。
并发控制
读事务
Megastore提供了三种读模式：最新读取（current read）、快照读取（snapshot read）、非一致性读取（inconsistent read）。
最新读取和快照读取总是在单个实体组内完成。
在开始最新读取前，要确保之前的所有写操作都已经提交并全部生效，然后读取最后一个版本的数据。
对于快照读取，系统取出一个已知的已经完全生效的最新版本并读取。与最新读取不同，他在读取时不要求之前的写操作是否全部生效，即快照读取只读取当前时间点最新的一个已经完全提交并生效的版本数据。（REDO日志同步成功但没有回放完成）。
非一致性读取忽略日志的状态而直接读取Bigtable中最新的值，可能读取到不完整的事务。
最新读取之后 ，如果没有最新的写入，则之后的最新读取与快照读取的结果都将是同一个版本的数据
提交：同步REDO日志
生效：回放REDO日志
写事务
Megastore事务中的写操作采用了预写式日志（REDO日志），只有当所有操作都在日志中记录下来后，写操作才会对数据执行修改。
在写事务开始前，要执行一个最新读取，用于将之前提交的写事务生效并获取下一个可用的日志位置，将用户操作聚集到日志缓冲区，分配一个更高的时间戳，最后通过Paxos复制协议提交到下一个可用的日志位置。
Paxos协议使用了乐观锁机制：尽管可能有多个写操作同时试图写同一个日志位置，但最后只有一个会成功。其他失败的写操作都会观察到成功的写操作，然后终止并重试。
同一时间针对同一个id的多个提案，最终只会有一个提案被通过。
写事务大致流程如下：
1. 读取：获取最后一次提交的事务的时间戳和日志位置（最新读取）
2. 应用逻辑：从Bigtable读取并且将写操作聚集到日志缓冲区
3. 提交：将缓冲区中的操作日志追加到多个机房的Bigtable集群，通过Paxos协议保证一致性
4. 生效：应用操作日志，更新Bigtable中的实体和索引
5. 清理：删除不在需要的数据
执行方式如下:
事务从Megastore的SQL语句，会被解析成针对BIgtable每个子表的操作，并生成针对每个子表的REDO日志，将这些日志提交到对应子表所在的Tablet Server上后由Tablet Server进行回放操作。如果有一张子表回放失败，则所有子表的回放都判定为失败，并将数据恢复成REDO日志之前的数据。
有这样两个操作：1
2T1: Read a; Read b; Set c = a + b;
T2: Read a; Read d; Set c = a + d;
假设事务T1和T2对同一个实体组并发执行，T1执行时读取a和b，T2读取a和d，接着T1和T2同时提交。Paxos协议保证T1和T2中有且只有一个事务提交成功。
假如T1提交成功，T2将重新读取a和b后再次通过Paxos协议提交。对同一个实体组的多个事务被串行化，Megastore之所以能够提供可串行化的隔离级别，得益于定义的实体组数据模型，由于同一个实体组同时进行更新往往很少，事务冲突导致重试的概率很低。
为什么定义的数据模型能够提供可串行化的隔离级别呢？是因为Bigtable保证了对一行的操作只能是原子性吗？但是这已经涉及到生效步骤了，如果是事务提交阶段保证串行化的话只是通过Paxos来保证同一时间针对同一个实体组只有一个事务提案能够被通过。
复制
对于多个集群之间的操作日志同步，主要有两个方案：基于中心节点的强一致性同步、基于Paxos的同步。
基于中心节点：保证了日志同步的强一致性。但是当中心节点宕机时，Slave需要确认中心节点宕机后才能够切换为Master继续提供服务，在这一时间段内是需要停止写服务的。
基于Paxos：Slave可以在假设Master宕机的情况下作为Master发起同步操作，虽然会出现多个节点同时操作的情况，但是Paxos通过选举机制保证了同一时间针对同一个id的提案只能通过一个。
Megastore通过Paxos协议将数据复制到多个数据中心，而且机器故障自动切换不停写服务，保证了高可靠与高可用性。
索引
Megastore的索引分为两大类：
- 局部索引（local index）：局部索引是单个实体组内部的，用于加速单个实体组内部的查找。也就是子表的索引。实体组内，数据和局部索引的更新操作是原子的。
在某个实体组上执行事务操作时，先记录REDO日志，回放REDO日志时，原子地更新实体组内部的数据和局部索引。PhotosByTime就是一个局部索引，映射到Photo表中的(user_id, time)主键 - 全局索引（global index）：全局索引横跨多个实体组。在Bigtable中相当于一张索引表。PhotosByTag就是一个全局索引。映射到Bigtable就是一张新的索引表，主键为(tag, user_id, photo_id)，即索引字段+Photo数据表主键。
横跨多个实体组，那也可能横跨多个存储节点？甚至横跨数据中心
除了这两类之外，Megastore还有其他一些额外的索引特性：
- STORING子句：通过在索引中增加STORING子句，系统可以在索引中荣誉一些常用的列字段，从而不需要查询基本表，减少一次查询操作。PhotosByTag索引表中冗余了thumbnail_url字段。
全局索引会创建一个新的索引表，查询时先从索引表中查询到数据的主键，然后根据主键查询基本表。如果在这个索引表中添加一些列，可以在根据索引查询这些列的时候减少一次查询基本表的过程，但是要注意不能太多，且冗余的列必须属于热点数据。
- 可重复索引：Megastore数据某些中某些字段是可重复的，相应的索引就是可重复索引。这就意味着，一行数据可能对应多行索引。PhotosByTag就是重复索引，每个photo可能有不同呢的tag，分别对应不同的索引行。
即tag的部分一行会有多个tag，每个tag都在索引表中有一行，所以一行tag会对应多行索引表。
协调者
快速读
Paxos协议要求读取最新的数据至少需要经过一半以上的副本，然而，如果不出现故障，每个副本基本都是最新的。也就是说，能够利用你本地读取实现快速读取，减少读取延时和跨机房操作。
Megastore引入协调者来记录每个本机房Bigtable实例中的每个实体组的数据是否最新。如果实体组的数据最新，读取操作只需要本地读取，没有跨机房操作。
实体组有更新操作时，写操作需要将协调者记录的实体组状态更新为无效，如果某个机房的Bigtable集群写入失败，需要首先使得相应的协调者记录的实体组状态是无效后写操作才可以成功返回客户端。
有点像Learner，即paxos提案通过之后将这部分信息发送给Learner。协调者作为一个全局的数据版本保存节点，保存的是当前集群中数据的最新版本编号，由于只保留版本号而不保存数据值，因此协调者的IO压力不会很大。
协调者的可用性
每次写操作都涉及协调者，如果协调者出现故障就会导致整个系统不可用。因此当协调者不可用时，需要检测到他的故障并且将其隔离。
通常的故障检测都是心跳，但是在Bigtable中对Tablet Server的故障检测使用的Chubby的互斥锁机制。因此Megastore采用的也是这个方法。
协调者在启动时从数据中心内获取Chubby锁。为了处理请求，协调者必须持有Chubby所。一旦因为出现问题导致锁失效，协调者就会恢复到一个默认的保守状态：认为所有它能看到的实体组都是失效的。
如果协调者的锁失效，写操作可以安全地将其忽略；但是从协调者失效到检测到锁释放有一个短暂的过期时间，这个时间段写操作都会失败，所有的写操作都必须等待协调者的Chubby锁锁过期。
心跳与Chubby互斥锁的使用：心跳主要用于检测服务器节点是否生效，但是Chubby在检测节点是否失效的同时还有一个同一类节点的单一权限问题。因此，Chubby通常用于那些接收处理没有备份数据的节点，即所有的数据都发往这一个节点，它的备节点只是用来提供服务的高可用，而不是用于提高数据的可靠性。
例子：Chunk Server通过心跳告知Master自己的存活状态，因为当GFS在写入时，同一份数据能够发往Chunk Server的备节点，并不会都发给他一个。而Tablet Server通过Chubby来告知Master存活状态，因为每个Tablet Server中的子表在整个Bigtabl集群中是唯一的，Tablet Server拥有对子表的完全操作权限，因此当Tablet Server宕机时Master需要获取到这个Tablet Server的互斥锁用于解除它对子表的操作权限，否则就会出现数据不一致性。
简单地说：心跳不涉及对数据的任何操作权限，只用于提供存活检测。而互斥锁与租约，在提供存活检测的同时还有对这个节点的权限控制。因为GFS在写入的时候数据不是非得写入到这个Chunk Server上。而Bigtable对子表的操作时只能在对应的Tablet Server上操作。
竞争条件
除了可用性之外，对于协调者的读写协议必须满足一系列的竞争条件。
失效操作总是安全的，但是生效操作必须谨慎处理。
在异步的网络环境中，消息可能乱序到达协调者。每条生效消息和失效消息都带有日志位置。如果协调者先收到较晚的失效操作再收到较早的生效操作，生效操作将被忽略。
协调者从你启动到退出为一个生命周期，每个生命周期用一个唯一的序号标识。生效操作只允许在最近一次对协调者进行读取操作依赖序号没有发生变化的情况下修改协调者的状态。
提交数据最频繁的节点成为Leader。
读取流程
Megastore的读取流程如下：
1.本地查询。查询本地副本的协调者来决定这个实体组上数据是否已经最新。
2.发现位置。确认一个最高的已经提交的操作日志位置，并选择最新的副本，具体操作如下：
a. 本地读取：如果本地查询确认本地副本已经是最新的，直接读取本地副本已经提交的最高日志位置和响应的时间戳，即快速读取。
b. 多数派读取：如果本地副本不是最新的（或者本地查询、本地读取超时），从多数派副本中读取最大的日志位置，然后从中选取一个响应最快或者最新的副本。
3.追赶。一旦某个副本被选中，就采用如下方式使其追赶到已知的最大位置处：
a. 获取操作日志：对于所选副本中所有不知道Paxos共识值的日志位置，从其他副本中读取。对于所有不确定共识值的日志位置，利用Paxos发起一次误操作的写（Paxos中的no-op）。Paxos协议将会促使大多数副本达成一个共识值：要么是无操作写，要么是以前已提交的一次写操作。
b. 应用操作日志：顺序地应用所有已经提交但还没有生效的操作日志，更新实体组的数据和索引信息。
4.使实体组生效。如果选取了本地副本且原来不是最新的，需要发送一个生效消息以通知协调者本地副本中这次读取的实体组已经最新。生效消息不需要等待应答，如果请求失败，下一个读取操作会重试。
5.查询数据。在所选副本中通过日志中记录的时间戳读取指定版本数据。如果所选副本不可用了，重新选去一个替代副本，执行追赶操作，然后从中读取数据。
什么是共识值？写事务的操作日志。
追赶：将多数派读取中那些没有达到最新值的副本的操作日志更新对最新。
第五步之前的查询都是查询Bigtable中的操作日志，只有到第五步确定了所要查询实体组的时间戳后才会从Bigtable中查询子表数据。因为Bigtable保存的数据是带有时间戳的，只用通过前4步获取到所要查询数据的最新提交生效的时间戳才能获取的正确的数据。
写入流程
执行完一次完整的读流程后，下一个可用的日志位置，最后一次写操作的时间戳，以及下一次的主副本（Leader）都知道了。在提交时刻所有的修改操作都被打包，同时还包含一个时间戳、下一次主副本提名，作为提议的下一个日志位置的共识值。如果该值被大多数副本通过，它将被应用到所有的副本中，否则整个事务将中止从读操作开始重试。
为什么要重试？此时采用的paxos算法是改进后的multi-paxos，该算法的核心在于第一次accept之后如果成功，则下一次不需要执行prepaer阶段。而在这里，直接进入accept，这个过程中会出现数据不一致，但是只有当协调者的数据更新后，这次修改才会对客户可见
写入过程包括如下几个步骤：
1.请求主副本接受：请求主副本将提议的共识值（写事务的操作日志）作为0号提案。如果想成功，跳转到步骤3.
2.准备：对于所有的副本，运行Paxos协议准备节点，即在当前的日志位置上，用一个比以前所有提议都更高的提议号进行选举。将提议的共识值替换为已知的拥有最高提议号的副本的提议值。
3.接收：请求剩余的副本接受主副本的提议，如果大多数副本拒绝这个值，返回步骤2。Paxos协议大多数情况下主副本不会变化，可以忽略准备阶段直接执行这个阶段，这就是Megastore的快速写。
4.使实体组失效：如果某些副本不接受多数派达成共识，将协调者记录的实体组状态标记为失效。协调者失效操作返回前写操作不能返回客户端呢，从而防止用户的最新读取得到不正确的结果。
5.应用操作日志：将共识值在尽可能多的副本上应用生效，更新实体组的数据和索引信息。
这里既然提到将共识值尽可能多的在副本上应用生效，则共识值就是REDO日志记录了。
讨论
分布式存储系统有两个目标：一个是可扩展性，最终目标是线性可扩展；另外一个是功能，最终目标是支持全功能SQL。Megastore是一个介于传统的关系型数据库和分布式NoSQL系统之间的存储系统呢，融合了SQL和NoSQL两者的优势。
Megastore的主要创新点在于：
- 提出实体组的数据模型。通过实体组划分数据，实体组内部位置关系数据库的ACID特征，实体组之间维持类似NoSQL的弱一致性，有效地融合了SQL和NoSQL两者的优势。另外，实体组的定义方式也在很大程度上规避了影响性能和可扩展性的Join操作。
- 通过Paxos协议同时保证高可靠性和高可用性，即把数据强同步到多个机房，又能做到发生故障时自动切换不影响读写服务。另外，通过协调者和优化Paxos协议是的读写操作都比较高效。
但是Megastore也有一些问题：来源于Bigtable的单副本服务，SSD支持较弱，整体架构过于复杂，协调者对读写服务和韵味复杂度的影响。因此后续又有一套Spanner架构用于解决这些问题。
以用户作为分组的方式，如果某个查询需要查询所有用户的用户信息，则这个查询会横跨多个实体组，甚至是多个网络集群。