三、分布式锁服务Chubby
Chubby 是 Google 设计的提供粗粒度锁服务的一个文件系统，它基于松耦合分布式系统，解决了分布的一致性问题。通过使用 Chubby 的锁服务，用户可以确保数据操作过程中的一致性。不过值得注意的是，这种锁只是一种建议性的锁（Advisory Lock）而不是强制性的锁（Mandatory Lock），这种选择使系统具有更大的灵活性。
GFS 使用 Chubby 选取一个 GFS 主服务器，Bigtable 使用 Chubby 指定一个主服务器并发现、控制与其相关的子表服务器。除了最常用的锁服务之外，Chubby 还可以作为一个稳定的存储系统存储包括元数据在内的小数据。同时 Google 内部还使用 Chubby 进行名字服务（Name Server）。
（一）Paxos算法
Paxos 算法是 Leslie Lamport 最先提出的一种基于消息传递（Messages Passing）的一致性算法，用于解决分布式系统中的一致性问题。在目前所有的一致性算法中，该算法最常用且被认为是最有效的。
系统的约束条件：
- p1：每个acceptor只接受它得到的第一个决议。
- p2：一旦某个决议得到通过，之后通过的决议必须和该决议保持一致。
- p2a：一旦某个决议v得到通过，之后任何acceptor再批准的决议必须是v。
- p2b：一旦某个决议v得到通过，之后任何proposer再提出的决议必须是v。
- p2c：如果一个编号为n的提案具有值v，那么存在一个 “多数派” ，要么它们中没有谁批准过编号小于n的任何提案，要么它们进行的最近一次批准具有值v。
为了保证决议的唯一性，acceptors 也要满足一个约束条件：当且仅当 acceptors 没有收到编号大于n的请求时，acceptors 才批准编号为n的提案。
一个决议分为两个阶段：
（1）准备阶段：proposers 选择一个提案并将它的编号设为n，将它发送给 acceptors 中的一个 “多数派”，acceptors 收到后，如果提案的编号大于它已经回复的所有消息，则 acceptors 将自己上次的批准回复给 proposers，并不再批准小于n的提案。
（2）批准阶段：当 proposers 接收到 acceptors 中的这个 “多数派” 的回复后，就向回复请求的 acceptors 发送 accept 请求，在符合 acceptors 一方的约束条件下，acceptors 收到 accept 请求后即批准这个请求。
（二）Chubby系统设计
Chubby的设计目标主要有以下几点：
（1）高可用性和高可靠性
（2）高扩展性
（3）支持粗粒度的建议性锁服务
（4）服务信息的直接存储
（5）支持缓存机制
（6）支持通报机制
Chubby的基本架构：
1、客户端
在客户这一端每个客户应用程序都有一个Chubby程序库（Chubby Library），客户端的所有应用都是通过调用这个库中的相关函数来完成的。
2、服务器端
服务器一端称为Chubby单元，一般是由五个称为副本（Replica）的服务器组成的，这五个副本在配置上完全一致，并且在系统刚开始时处于对等地位。
（三）Chubby中的Paxos
单个Chubby副本结构：
从图中可以看出，单个副本主要由以下三个层次组成。
（1）最底层是一个容错的日志，该日志对于数据库的正确性提供了重要的支持。不同副本上日志的一致性正是通过 Paxos 算法来保证的。副本之间通过特定的 Paxos 协议进行通信，同时本地文件中还保存有一份同 Chubby 中相同的日志数据。
（2）最底层之上是一个容错的数据库，这个数据库主要包括一个快照（Snapshot）和一个记录数据库操作的重播日志（Replay-log），每一次的数据库操作最终都将提交至日志中。和容错的日志类似的是，本地文件中也保存着一份数据库数据副本。
（3）Chubby 构建在这个容错的数据库之上，Chubby 利用这个数据库存储所有的数据。Chubby 的客户端通过特定的 Chubby 协议和单个的 Chubby 副本进行通信。
由于副本之间的一致性问题，客户端每次向容错的日志中提交新的值（value）时，Chubby 就会自动调用 Paxos 构架保证不同副本之间数据的一致性。下图就显示了这个过程。
容错日志的API：
结合上图来看，在 Chubby 中 Paxos 算法的实际作用为如下三个过程。
（1）选择一个副本成为协调者（Coordinator）。
（2）协调者从客户提交的值中选择一个，然后通过一种被称为 accept 的消息广播给所有的副本，其他的副本收到广播之后，可以选择接受或者拒绝这个值，并将决定结果反馈给协调者。
（3）一旦协调者收到大多数副本的接受信息后，就认为达到了一致性，接着协调者向相关的副本发送一个 commit 消息。
上述三个过程实际上跟 Paxos 的核心思想是完全一致的，这些过程保证提交到不同副本上容错日志中的数据是完全一致的，进而保证 Chubby 中数据的一致性。
（四）Chubby文件系统
Chubby 系统本质上就是一个分布式的、存储大量小文件的文件系统，它所有的操作都是在文件的基础上完成的。例如在 Chubby 最常用的锁服务中，每一个文件就代表了一个锁，用户通过打开、关闭和读取文件，获取共享（Shared）锁或独占（Exclusive）锁。选举主服务器的过程中，符合条件的服务器都同时申请打开某个文件并请求锁住该文件。成功获得锁的服务器自动成为主服务器并将其地址写入这个文件夹，以便其他服务器和用户可以获知主服务器的地址信息。
单调递增的64位编号：
（1）实例号(Instance Number)：新节点实例号必定大于旧节点的实例号。
（2）内容生成号(Content Generation Number)：文件内容修改时该号增加。
（3）锁生成号(Lock Generation Number)：锁被用户持有时该号增加。
（4）ACL生成号(ACL Generation Number)：ACL名被覆写时该号增加。
常用的句柄函数及作用：
| 函 数 名 称 | 作用 |
| Open() | 打开某个文件或者目录来创建句柄 |
| Close() | 关闭打开的句柄，后续的任何操作都将中止 |
| Poison() | 中止当前未完成及后续的操作，但不关闭句柄 |
| GetContentsAndStat() | 返回文件内容及元数据 |
| GetStat() | 只返回文件元数据 |
| ReadDir() | 返回子目录名称及其元数据 |
| SetContents() | 向文件中写入内容 |
| SetACL() | 设置ACL名称 |
| Delete() | 如果该节点没有子节点的话则执行删除操作 |
| Acquire() | 获取锁 |
| Release() | 释放锁 |
| GetSequencer() | 返回一个sequencer |
| SetSequencer() | 将sequencer和某个句柄进行关联 |
| CheckSequencer() | 检查某个sequencer是否有效 |
（五）通信协议
Chubby客户端与服务器端的通信过程：
可能出现的两种故障：
（六）正确性与性能
1、一致性
每个 Chubby 单元是由五个副本组成的，这五个副本中需要选举产生一个主服务器，这种选举本质上就是一个一致性问题。
2、安全性
采用的是 ACL 形式的安全保障措施。只要不被覆写，子节点都是直接继承父节点的 ACL 名。
Chubby 的 ACL 机制：
用户 chinacloud 提出向文件 CLOUD 中写入内容的请求。CLOUD 首先读取自身的写 ACL 名 fun，接着在 fun 中查到了 chinacloud 这一行记录，于是返回信息允许 chinacloud 对文件进行写操作，此时 chinacloud 才被允许向 CLOUD 写入内容。其他的操作和写操作类似。
3、性能优化
提高主服务器默认的租约期、使用协议转换服务将 Chubby 协议转换成较简单的协议、客户端一致性缓存等。
四、分布式结构化数据表Bigtable
Bigtable 是 Google 开发的基于 GFS 和 Chubby 的分布式存储系统。Google 的很多数据，包括 Web 索引、卫星图像数据等在内的海量结构化和半结构化数据，都存储在 Bigtable 中。从实现上看，Bigtable 并没有什么全新的技术，但是如何选择合适的技术并将这些技术高效、巧妙地结合在一起恰恰是最大的难点。Bigtable 在很多方面和数据库类似，但它并不是真正意义上的数据库。通过本节的学习，读者将会对 Bigtable 的数据模型、系统架构、实现以及它使用的一些数据库技术有一个全面的认识。
（一）设计动机与目标
Bigtable 的设计动机：
（1）需要存储的数据种类繁多。包括URL、网页内容、用户的个性化设置在内的数据都是Google需要经常处理的。
（2）海量的服务请求。Google运行着目前世界上最繁忙的系统，它每时每刻处理的客户服务请求数量是普通的系统根本无法承受的。
（3）商用数据库无法满足需求。一方面现有商用数据库的设计着眼点在于其通用性。另一方面对于底层系统的完全掌控会给后期的系统维护、升级带来极大的便利。
Bigtable 应达到的基本目标：
（1）广泛的适用性。Bigtable是为了满足一系列Google产品而并非特定产品的存储要求。
（2）很强的可扩展性。根据需要随时可以加入或撤销服务器。
（3）高可用性。确保几乎所有的情况下系统都可用。
（4）简单性。底层系统的简单性既可以减少系统出错的概率，也为上层应用的开发带来便利。
（二）数据模型
Bigtable数据的存储格式：
Bigtable 是一个分布式多维映射表，表中的数据通过一个行关键字（Row Key）、一个列关键字（Column Key）以及一个时间戳（Time Stamp）进行索引。
Bigtable 的存储逻辑可以表示为：
(row:string, column:string, time:int64)→string
1、行
- Bigtable的行关键字可以是任意的字符串，但是大小不能够超过64KB。
- 表中数据都是根据行关键字进行排序的，排序使用的是词典序。
- 同一地址域的网页会被存储在表中的连续位置。
- 倒排便于数据压缩，可以大幅提高压缩率。
2、列
- 将其组织成所谓的列族（Column Family）
- 族名必须有意义，限定词则可以任意选定。
- 组织的数据结构清晰明了，含义也很清楚。
- 族同时也是Bigtable中访问控制（Access Control）的基本单元。
3、时间戳
- Google 的很多服务比如网页检索和用户的个性化设置等都需要保存不同时间的数据，这些不同的数据版本必须通过时间戳来区分。
- Bigtable 中的时间戳是64位整型数，具体的赋值方式可以用户自行定义。
（三）系统架构
Bigtable 基本架构：
Bigtable 中 Chubby 的主要作用：
（1）选取并保证同一时间内只有一个主服务器（Master Server）。
（2）获取子表的位置信息。
（3）保存Bigtable的模式信息及访问控制列表。
（四）主服务器
- 当一个新的子表产生时，主服务器通过一个加载命令将其分配给一个空间足够的子表服务器。
- 创建新表、表合并以及较大子表的分裂都会产生一个或多个新子表。
- 分割完成之后子服务器需要向主服务发出一个通知。
- 主服务器必须对子表服务器的状态进行监控，以便及时检测到服务器的加入或撤销。
Bigtable 中 Chubby 的主要作用：
步骤 1：从Chubby中获取一个独占锁，确保同一时间只有一个主服务器
步骤 2：扫描服务器目录，发现目前活跃的子表服务器
步骤 3：与所有的活跃子表服务器取得联系以便了解所有子表的分配情况
步骤 4：通过扫描元数据表（Metadata Table），发现未分配的子表并将其分配到合适的子表服务器
（五）子表服务器
1、SSTable 格式的基本结构
SSTable是Google为Bigtable设计的内部数据存储格式。所有的SSTable文件都存储在GFS上，用户可以通过键来查询相应的值。
子表实际组成：
- 不同子表的SSTable可以共享
- 每个子表服务器上仅保存一个日志文件
- Bigtable规定将日志的内容按照键值进行排序
- 每个子表服务器上保存的子表数量可以从几十到上千不等，通常情况下是100个左右
2、子表地址
Bigtable系统的内部采用的是一种类似B+树的三层查询体系。
3、Bigtable 数据存储及读/写操作
较新的数据存储在内存中一个称为内存表（Memtable）的有序缓冲里，较早的数据则以 SSTable 格式保存在 GFS 中。
三种形式压缩之间的关系：
（六）性能优化
1、局部性群组
Bigtable允许用户将原本并不存储在一起的数据以列族为单位，根据需要组织在一个单独的SSTable中，以构成一个局部性群组。
用户可以只看自己感兴趣的内容。对于一些较小的且会被经常读取的局部性群组，明显地改善读取效率。
2、压缩
压缩可以有效地节省空间，Bigtable中的压缩被应用于很多场合。首先压缩可以被用在构成局部性群组的SSTable中，可以选择是否对个人的局部性群组的SSTable进行压缩。
- 利用Bentley & McIlroy方式（BMDiff）在大的扫描窗口将常见的长串进行压缩
- 采取Zippy技术进行快速压缩，它在一个16KB大小的扫描窗口内寻找重复数据，这个过程非常快
3、布隆过滤器
Bigtable向用户提供了一种称为布隆过滤器的数学工具。布隆过滤器是巴顿•布隆在1970年提出的，实际上它是一个很长的二进制向量和一系列随机映射函数，在读操作中确定子表的位置时非常有用。
优点：
- 布隆过滤器的速度快，省空间不会将一个存在的子表判定为不存在
缺点：
- 在某些情况下它会将不存在的子表判断为存在
