三、分布式锁服务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()返回一个sequencerSetSequencer()将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年提出的，实际上它是一个很长的二进制向量和一系列随机映射函数，在读利用中确定子表的位置时非常有用。
优点：
- 布隆过滤器的速度快，省空间
- 不会将一个存在的子表判定为不存在
缺点：
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
