说明

• 本文来自课本的学习内容整理，如果存在错误之处，欢迎指正！

设计目标及方案选择

• 设计目标：设计一种介于传统的关系型数据库和NoSQL之间的存储技术，尽可能达到高可用性和高可扩展性的统一。
  • 关系型数据库：高事务性和复杂数据查询
  • NoSQL数据库：扩展性和大数据处理能力
• 方法一：针对可用性的要求，实现了一个同步的、容错的、适合远距离传输的复制机制。——Paxos
• 方法二：针对可扩展性的要求，将整个大的数据分割成很多小的数据分区，每个数据分区连同它自身的日志存放在NoSQL数据库中，具体来说就是存放在Bigtable中。——子表（tablet） SSTable

数据的分区和复制

• 在Megastore中，小的数据分区被称为实体组集（Entity Groups）
• 每个实体组集包含若干的实体组，实体组相当于表的概念，多数情况下每个实体组仅有一个子表，分布在一台Bigtable的子表服务器上，若实体组比较大，导致子表分裂，会分布到多台子表服务器上
• 一个实体组中包含很多的实体（Entity，相当于表中记录的概念）
  

1. 同一个Entity Group的数据可以被划分到Bigtable表的同一个数据分区(子表，Tablet)中，这样，同一个Entity Group内的跨行事务是可以轻松支持的。
2. 同一个Entity Group中的数据是相邻存放的，这样可以将多表的关联查询转换为一个顺序的Scan，加速查询。同时，对于数据写入而言，同一个Entity Group中的多条数据在一起写入时，也可有效的降低随机IO数目来提升写入性能。
3. 跨集群数据复制时，一个Entity Group在不同的集群间的数据可保持ACID语义的
4. Entity Group可以理解为是比Bigtable Tablet（子表）更细粒度的分区，更细粒度意味着并发锁的范围可以更小，从而可以带来更高的并发度

---

• 实体组是一个实体和这个实体下的一系列实体。例如电商中，每个用户是一个实体组，用户的所有订单、消息等都挂载在这个用户下。这些东西都打包在一起就是一个实体组，对这个实体组数据进行操作时可能产生冲突。
• Megastore 在每个实体组内支持一阶段的数据库事务，当存在跨实体组的操作时：
  1. 使用2PC事务，代价昂贵，是一个阻塞的、有单点的解决方案
  2. 抛弃事务，Megastore提供了异步消息机制。

数据模型

• Google团队设计了一种能够提供细粒度控制的数据模型和模式语言。
• Megastore中关系型数据库的特征就集中体现在这种数据模型。同关系型数据库一样，Megastore的数据模型是在模式中定义的且是强类型的。
• 每个模式都由一系列的表构成，表又包含有一系列的实体，每个实体中又包含一系列的属性。
• 属性是命名的且具有类型，这些类型包括字符型、数字类型或者Google的Protocol Buffers。属性可以被设置成必需的（required）、可选的（optional）或者可重复（repeated）。

照片共享服务数据模型实例

• Megastore中，所有的表要么是实体组根表（Entity Group Root Table），要么是子表（Child Table）
• Megastore实例中可以有若干个不同的根表，表示不同类型的实体组集
• 所有的子表必须有一个参照根表的外键，该外键通过ENTITY GROUP KEY声明
  
• User是一个根表
• Photo就是一个子表，因为它声明了一个外键
• 三种不同属性设置，既有必须的（如user_id），也有可选的（如thumbnail_url），还有可重复的（如tag）

Megastore索引

索引分为两类：

• 局部索引：局部索引定义在单个实体组中，它的作用域仅限于单个实体组。例如，PhotosByTime就是一个局部索引
• 全局索引：横跨多个实体组集进行数据读取操作。例如，PhotosByTag则是一个全局索引

---

• STORING子句：通过在索引中增加STORING子句，可以存储一些额外的属性，在读取数据时可以更快地从基本表中得到所需内容。PhotosByTag这样一个索引中就对thumbnail_url使用了STORING子句。
• 可重复的索引：Megastore提供对可重复属性建立索引的能力。
• 内联索引（Inline Indexes）：任何一个有外键的表都能够创建一个内联索引。内联索引能够有效的从子实体中提取出信息片段并将这些片段存储在父实体中，以此加快读取速度。

Bigtable中存储情况

• 照片共享服务实例的数据在Bigtable中的存储情况。
  
• Bigtable的列名实际上是表名和属性名结合在一起得到，不同表中实体可存储在同一个Bigtable行中

事务及并发控制

• 同一实体组下的所有数据行可看成一个抽象的小数据库，在之上Megastore也支持“可串行化”的ACID语义。采用MVCC（Multiversion Concurrency Control 多版本并发控制）实现隔离性。
• 数据库有多个历史版本，每次请求那最新的快照，整个事务提交时会检查当前数据库里数据的最新版本，是否和拿到的快照版本一致。如果一致则提交成功并更新版本。当有两个并发的数据库事务读写同一份数据时，先提交的事务会成功，后提交的会因为最新版本数据变了而失败。当有一个事务正在提交或写入到一半，另一个读取事务的请求不会读到已经写的一般数据，而是读到上一个最新版本的快照。
• 单条记录有多个版本，可线性化要求提交时检查是否有其他事务已经更新过当前事务读写的数据
  
• Bigtable天然会存储多个版本的数据，每次写入都是添加新版本，这和MVCC很匹配。Megastore的一个实体组可能包含多行数据，使用时间戳实现基于MVCC的事务和隔离。提交事务时只要指定时间戳，读取时直接读最新的。
• 如果事务执行一般，一个实体组中部分数据更新，此时不会读到更新一半的数据。根据时间戳，提供了 current、snapshot、inconsistent 三种模式：

Megastore提供的三种读

• 实体组相当于表的概念，每个实体组一般只有一个子表
• current：总是在单个实体组中完成
  • 在开始某次current读之前，需要确保已提交的写操作已经全部生效，然后应用程序再从最后一个成功提交的事务时间戳位置读数据
• snapshot：总是在单个实体组中完成
  • 系统取出已知的最后一个完整提交的事务的时间戳，接着从这个位置读数据。
  • 读的时候可能还有部分事务提交了但还未生效
• inconsistent：
  • 忽略日志的状态直接读取最新的值
  • 适用于要求低延迟并能忍受数据过期或不完整的读操作

Megastore的写操作

• Megastore事务中的写操作采用预写式日志（Write-ahead Log）。
• 只有当所有的操作都在日志中记录下后写操作才会对数据执行修改。
• 一个写事务总是开始于一个current读以便确认下一个可用的日志位置。
• 提交操作将数据变更聚集到日志，接着分配一个比之前任意一个都高的时间戳，然后使用Paxos将数据变更加入到日志中。该协议使用乐观并发（Optimistic Concurrency）：尽管可能有多个写操作同时试图写同一个日志位置，但只会有1个成功。所有失败的写都会观察到成功的写操作，然后中止并重试它们的操作。

完整的事务周期

• Megastore中事务间的消息传递通过队列（Queue）实现。
• Megastore 支持跨实体组的事务的两阶段提交：请求阶段和提交阶段
• Megastore中的消息能够横跨实体组，在一个事务中分批执行多个更新或者延缓作业；在单个实体组上执行的事务除了更新它自己的实体外，还能够发送或收到多个信息；
• 每个消息都有一个发送和接收的实体组；如果这两个实体组是不同的，那么传输将会是异步的
  
• 异步消息机制如下：需要同时操作实体组A和B时，对一个实体组通过一阶段事务完成，然后通过Megastore提供的一个队列像实体组B发送一个消息。实体组B接收到消息后，可以原子地执行这个消息所做地改动。所以AB两边地改动都是事务性的，但两个操作没有共同组成同一个分布式事务。所以Megastore本质上没有实现数据库事务，而是实现了最终一致性。
  以微信作为例子：

1. 将每个微信号作为一个实体组
2. 账号里收发地消息都挂载在这个实体组
3. 发一条消息会影响两个实体组
4. 但不需要保证发出消息和对方收到消息同时发生，所以可以使用Megastore的异步消息机制
5. 先用一个一阶段事务，在发送者账号的实体组写入消息，再通过Megastore的异步消息机制向收件人的账号中发送一条写入消息请求。他的实体组收到异步消息后将消息事务性地写入自己的实体组。

Megastore基本架构

• Megastore基本架构中，最底层的数据是存储在Bigtable中的，不同类型的副本存储不同的数据。
• 在Megastore中共有三种副本，分别是完整副本、见证者副本和只读副本
  
• 完整副本：可投票，存储数据和日志
• 见证者副本：可投票，只存储日志
• 只读副本：不可投票，读取最近过去某个时间点的一致性数据，数据不是最新的

---

横向看：

1. 每个数据中心都有一个应用服务器，所有外部请求都先到应用服务器在有它代理进行数据库操作
2. 事务日志和数据等都是存储在底层的Bigtable中
3. 在中间层，Megastore有两类服务器：协同服务器，维护本地数据是否最新版本；复制服务器（Replication Server）。当有数据写入请求时，写到本地数据中心的直接写Bigtable，如果是写远端其他数据中心，则是发送给那个数据中心的复制服务器。其本质上是一个代理。此外复制服务器还定期扫描本地副本，将因网络或硬件故障而没完整写入的数据库事务同步到最新

快速读与快速写

---

快速读

• 由于写操作基本上能在所有副本上成功，一旦成功认为该副本上的数据都是相同的且是最新的，就能利用本地读取实现快速读，带来更好的用户体验及更低的延迟
• 关键是保证选择的副本上数据是最新的
• 协调者是一个服务，该服务分布在每个副本的数据中心里面。它的主要作用就是跟踪一个实体组集合，集合里的实体组的副本已经观察到所有的Paxos写。
• 协调者的状态是由写算法来保证

---

快速写

• 如果一次写成功，那么下一次写的时候就跳过准备过程，直接进入接受阶段
• Megastore没有使用专门的主服务器，而是使用leaders
• leader主要是来裁决哪个写入的值可以获取0号提议
• 复制服务器会定期扫描未完成的写入并通过Paxos算法提议没有操作的值来让写入完成。

核心技术之复制

• 复制可以说是Megastore最核心的技术，如何实现一个高效、实时的复制方案对于整个系统的性能起着决定性的作用。通过复制保证所有最新的数据都保存有一定数量副本，能够很好地提高系统的可用性。

复制的日志

• 每个副本都存有记录所有更新的数据。即使是它正从一个之前的故障中恢复数据，副本也要保证其能够参与到写操作中的Paxos算法，因此Megastore允许副本不按顺序接受日志，这些日志将独立的存储在Bigtable中。
• 当日志有不完整的前缀时就称一个日志副本有“缺失”（Holes）。在图2-25中0～99的日志位置已经被全部清除，100的日志位置被部分清除，因为每个副本都会被通知到其他副本已经不再需要这个日志。
• 101的日志位置被全部副本接受。102的日志位置被γ获得，这是一种有争议的一致性。103的日志位置被副本A和副本C接受，副本B则留下了一个“缺失”。104的日志位置则未达到一致性，因为副本A和副本B存在争议。

数据读取

1. 本地查询：查询本地副本的协调者确认该实体组上数据是否是最新的。
2. 发现位置：获取已Commit的最大的Log Position，而后基于该Log Position选择最合适的副本。
   • 【本地读取】如果第1步中Local Replica的数据是最新的，则直接读取Local Replica中已接收的最大的Log Position以及Timestamp信息；
   • 【多数派读取】如果Local Replica中的数据不是最新的，则从大多数副本中获取已被接收的最大的Log Position信息以及Timestamp信息，然后选择一个通常能快速响应的Replica或者是数据最新的Replica。
3. 追赶：进行数据追赶，需要补齐所有的缺失的数据。

• 追赶：在一次Current读之前，要保证至少有一个副本上的数据是最新的，所有之前提交到日志中的更新必须复制到该副本上并确保在该副本上生效

- 对于所选副本中所有不知道共识值的日志位置，从其他的副本中读取值。对于任意的没有任何可用的已提交的值的日志位置，将会利用Paxos算法发起一次无操作的写。Paxos将会促使绝大多数副本达成一个共识值——可能是无操作的写也可能是以前的一次写操作。
- 接下来就所有未生效的日志位置生效成上面达成的共识值，以此来达到分布式一致状态。

4. 验证：如果Local Replica被选中，且Local Replica的数据并不是最新的，这个时候需要给Coordinator发送一个验证信息（validate）来确认要读取的Entity Group在该Replica中的数据是完整的。
5. 查询数据：基于第2步获取到的Timestamp信息开始读取数据。如果读取过程中，所选择的Replica变得不可用，则需要重新更换一个Replica，然后同样需要执行数据追赶操作。

数据写入

1. 接受leader：请求leader接受值作为0号提议。实际上就是快速写方法。如果成功，跳至步骤3。
2. 准备：在所有的副本上使用一个比其当前所见的日志位置更高的提议号进行Paxos准备阶段。将值替换成拥有最高提议号的那个值。
3. 接受：请求剩余的副本接受该值，如果大多数副本拒绝这个值，返回步骤2。
4. 失效：将不接受值的副本上的协调者进行失效操作。
5. 生效：将值的更新在尽可能多的副本上生效。如果选择的值和原来提议的有冲突，返回一个冲突错误。

• 失效：如果一次写操作不是被所有的副本接受，必须要将这些未接受写操作的副本中相关的实体组从协调者中移去，这个过程称为失效。
• 失效是为了保证协调者所看到的的副本上的数据都是接受了写操作的最新数据。

协调者的可用性

• 协调者的进程运行在每个数据中心。每次的写操作中都要涉及协调者，因此协调者的故障将会导致系统的不可用
• **Megastore使用Chubby锁服务，为处理请求，一个协调者必须持有多数锁。**一旦因为出现问题导致它丢失大部分锁，协调者就会恢复到一个默认保守状态——认为所有它能看到的实体组都是失效的。
• 除可用性问题，对于协调者的读写协议必须满足一系列的竞争条件