这是一篇在阅读《大规模分布式存储系统：原理解析与架构实战》时的阅读笔记，由于长时间碎片阅读的关系导致在做这种读书笔记的时候接近复制粘贴。虽然其中会有一小部分自己的想法但都十分零碎，希望后续能改进。
分布式表格系统对外提供表格模型，每个表格由很多行组成，通过主键唯一标识，每一行包含很多列。整个表格在系统中全局有序。
GFS+Bigtable双层架构是一种里程碑式的架构，但是Bigtable对外结构不够丰富，因此后续又推出了构建在Bigtable上的Megastore以及支持跨多个数据中心的数据库事务的Spanner。
Google Bigtable
Bigtable是Google开发的基于GFS和Chubby的分布式表格系统。他存储了大量结构化和半结构化数据。
Bigtable系统由很多表格组成，每个表格包含很多行，每行通过一个主键（Row Key）唯一标识，每行又包含很多列（Column）。某一行的某一列构成一个单元（Cell），每个单元包含多个版本的数据。
需要和常用的关系型数据库区分，在关系型数据库中“某一行的某一列”表示的是数据的值，而在Bigtable中则表示某个值的多个版本对象。
整体上看，Bigtable是一个分布式多维映射表。
其中的时间戳就是某一行某一列的各个版本号，通过版本号获取这个值当时的信息。即通过<行，列>确定数据的对象，通过时间戳确定数据的版本。
Bigtable将多个列组织成列族（column family），这样，列由两个部分组成：（column family，qualifier）。列族是Bigtable中访问控制的基本单元，也就是说，访问权限的设置是在列族这一级别上进行的。
Bigtable中的列族在创建表格的时候需要预先定义好，个数不允许过多；但是列族中包含哪些qualifier是不需要预先定义的，qualifier可以任意多个，适合表示半结构化数据。
- 结构化数据：结构化数据可以使用关系型数据库来表示和存储，如MySQL、Oracle、SQL Server等，表现二维形式的数据。可以通过固有键值获取相应信息。一般特点是：数据以行为单位，一行数据表示一个实体的信息，每一行数据的属性是相同的。结构化的数据的存储和排列是很有规律的，这对查询和修改等操作很有帮助。但是，显然，它的扩展性不好（比如，我希望增加一个字段）。
- 非结构化数据：非结构化数据,就是没有固定结构的数据，包含全部格式的办公文档、文本、图片、XML、HTML、各类报表、图像和音频/视频信息等等。一般直接整体进行存储，而且一般存储为二进制的数据格式
- 半结构化数据：半结构化数据可以通过灵活的键值调整获取相应信息，且数据的格式不固定，如json，同一键值下存储的信息可能是数值型的，可能是文本型的，也可能是字典或者列表。半结构化数据，属于同一类实体可以有不同的属性，即使他们被组合在一起，这些属性的顺序并不重要。常见的半结构数据有XML和JSON。
Bigtable中的行主键可以是任意的字符，最大不超过64KB。Bigtable表中的数据按照行主键进行排序，排序使用的是字典序。
对于域名www.cnn.com，在存储的时候将其域名修改为com.cnn.www，这样的好处是使得所有www.cnn.com下的子域名在系统中连续存放。
即com.cnn.www、com.cnn.A.www、com.cnn.B.www这样的排布方式，使得主域名作为排序的前缀，由于主域名不会重复，因此在字典序下主域名下所有的子域名都连续存放。
这一行包含两个列族：“contents”和“anchor”，其中，列族“anchor”又包含两个列，qualifier分别为“cnnsi.com”和“my:look.ca”。
谷歌的很多服务，比如Web检索和用户的个性化设置，都需要保存不同时间的数据，这些不同的数据版本必须通过时间戳来区分。
那应该会有一个时间戳列表或者索引，不然怎么知道是哪个时间戳才保存了数据。
途中contents的t1、t2、t3分别保存了三个时间点获取的网页。为了简化不同版本呢的数据管理，Bigtable提供了两种设置：一种是保留最近的N个不同版本，另一种是保留限定时间内的所有不同版本，比如可以保存最近10天的所有不同版本的数据。失效的版本将会由Bigtable的垃圾回收机制自动删除。
架构
Bigtable构建在GFS之上，为文件系统增加一层分布式索引层。另外，Bigtable依赖Google的Chubby（分布式锁服务）进行服务器选举及全局信息维护。
Bigtable将大表划分为大小在100～200MB的子表（tabler），每个子表对应一个连续的数据范围。
Bigtable主要由三个部分组成：客户端程序库（Client）、一个主控服务器（Master）、多个子表服务器（Tablet Server）
- Client：提供Bigtable到应用程序的接口，应用程序通过客户端程序库对表格的数据单元进行增、删、查、改等操作。客户端通过Chubby锁服务获取一些控制信息，但所有表格的数据内容都在客户端与子表服务器之间传送。
- Master：管理所有子表服务器，包括分配子表给子表服务器，指导子表服务器实现子表的合并，接受来自子表服务器的子表分裂消息，监控子表服务器，在子表服务器之间进行负载均衡并实现子表服务器的故障恢复等。
- Tablet Server：实现子表的装载/卸出、表格内容的读和写，子表的合并和分裂。Tablet Server服务的数据包括操作日志以及每个子表上的sstable数据，这些数据存储在底层的GFS中。
Bigtable依赖于Chubby锁服务完成如下功能：
1. 选取并保证同一时间内只有一个主控服务器
2. 存储Bigtable系统引导信息
3. 用于配合主控服务器发现子表服务器加入和下线
4. 获取Bigtable表格的schema信息及访问控制信息
1可以理解，通过锁服务进行选举得到唯一的Master；但是2，锁服务是如何配合Bigtable存储Bigtable系统的引导信息的呢？；3，Tablet Server不是通过心跳与Master维持通信来告知存活的吗？这个节点Chubby是如何加入进来的呢？难道是在Chubby存储当前主Master的信息，而Tablet Server的心跳信息是直接发放Chubby然后再由Chubby转发到当前生效的主Master中的吗？；4，锁服务可以执行访问控制。
PS:2、在Chubby服务器上存储元数据服务器的元数据信息。3、TabetServer通过持有互斥锁来告知Master是否在线。4、同2
为什么不用心跳。因为互斥锁比心跳更能判断是否存活，心跳如果接收不到可能是网络原因，如果Master将其判断为下线并执行表的复制，但实际上该TabletServer并没有下线，因此会导致有两张相同的子表同时对外提供服务，会造成数据的不一致性
Chubby是一个分布式锁服务，底层的核心算法为Paxos。Paxos算法的实现过程需要一个“多数派”就某个值达成一致，进而才能得到一个分布式一致状态。只要半数以上的节点不发生故障，Chubby就能够正常提供服务。
Bigtable包含三种类型的表格：用户表（User Table）、元数据表（Meta Table）和根表（Root Table）。
- 用户表：存储用户实际数据
- 元数据表：存储用户表的元数据，如子表位置信息、SSTable及操作日志文件编号、日志回放点等
- 根表：用来存储元数据表的元数据
根表的元数据，也就是根表的位置信息，又称为Bigtable引导信息，存放在Chubby中。客户端、主控服务器以及子表服务器执行过程中都需要依赖Chubby服务，如果Chubby发生故障，Bigtable系统整体不可用。
数据分布
客户端在查询时先查询Chubby获取根表信息，然后从根表获取元数据表最后查询到用户表获取数据。为了加快查询速度使用了缓存和预取技术。子表的位置信息被缓存在客户端，客户端在寻址时首先查找缓存，如果不存在则向上请求元数据表的缓存，如果也不存在则继续向上请求根表的缓存，还是不存在的话就按照原先顺序冲Chubby中开始向下查询。
复制与一致性
Bigtable系统保证强一致性，同一时刻同一子表只能被一台Tablet Server服务，也就是说，Master将子表分配给某个Tablet Server服务时需要确保没有其他Tablet Server正在服务这个子表。这一过程可以通过互斥锁来实现，且为了防止死锁，互斥锁也会有一个过期时间
这点就类似于租约机制，同一时刻只能有一台Chunk Server提供服务，当拥有租约的服务器宕机后，Master会在租约过期后重新进行选举
Bigtable写入GFS的数据分为两种：
- 操作日志：当Tablet Server发生故障时，它上面服务的子表会被集群中的其他Tablet Server加载继续提供服务。加载子表可能需要回放操作日志，每条操作日志都有唯一的序号，通过它可以去除重复的操作日志。
- 每个子表包含的SSTable数据。如果写入GFS失败可以重试并产生多条重复记录，但是Bigtable只会索引最后一条成功写入的数据。
第二条解决了GFS遗留的一致性问题，它只会获取一致性写入后的一条数据，将那些重复与填充数据全部排除。
容错
Bigtable中Master对Tablet Server的监控是通过Chubby完成的，Tablet Server在初始化时都会从Chubby中获取一个独占锁。通过这种方式所有的Tablet Server基本信息被保存在Chubby中一个成为服务器目录（Server Director）的特殊目录之中。Master通过检测这个目录随时获取最新的Tablet Server信息，包括目前正在活跃的Tablet Server，以及每个Tablet Server上现已经分配的子表。
这个独占锁也和租约很像，为了防止死锁，Tablet Server的独占锁肯定会有一个过期时间，而为了减少Chubby的工作开销，肯定是要快过期的时候Tablet Server往Chubby请求申请续租。
Master通过定期往Chubby检查Tablet Server独占锁的状态来判断Tablet Server的存活状态，这时会有两种情况：Chubby出问题、Tablet Server出问题。Master首先会尝试获取这个锁，如果获取失败则表示Chubby出问题，否则就是Tablet Server出问题。Chubby 出问题表示整个Bigtable都无法提供服务所以只能由人工维护；Tablet Server出问题的话，Master将终止这个Tablet Server并将其上的子表全部迁移到其他Tablet Server。
每个子表持久化的数据包含两部分：操作日志以及SSTable。
为了提高性能，Tablet Server不会为每一份子表都维护一份独立的操作日志，而是将所有子表的操作都写进GFS中，每条日志通过〈表格编号，行主键，日志序列号〉来唯一表示。
当某个Tablet Server宕机后，Master将该Tablet Server服务的子表分配给其他Tablet Server。为了减少Tablet Server从GFS读取的日志数据量，Master 将选择一些Tablet Server对日志进行分段排序。排好序后，同一个子表的操作日志连续存放，Tablet Server恢复某个子表时只需要读取该子表对应的操作日志即可。Master需要尽可能选择负载低的Tablet Server执行排序，并且需要处理排序任务失败的情况。
Tablet Server在写入操作日志的时候为了性能可以一股脑一起写入，但是在恢复Tablet Server数据并写需要重现日志的时候是按照子表来恢复的，因此需要将写入的混合日志分离出来并排序，并且以子表为单位进行恢复。这样做的原因是进行子表转移分配的时候它的基本单位也是子表，而不是多条操作日志。同时这是对追求写入所产生的后果进行的填补。
如何排序？在GFS中是没有排序逻辑的，因此需要将操作日志全部取出来并且分配到各个空闲的Tablet Server来为这部分数据排序，这里要求排序要将数据拆分后排序，可以在排好序后建立一个子表与排序集合的映射表方便组合最终的结果。
Master也会和Tablet Server一样，在启动时获取一个独占锁，如果锁过期则表示Master宕机，那么Chubby将会选择备Master恢复服务。
Master如Chubby的不同：
- Chubby主要用于保存元数据表的元数据，分布式锁服务，检测各个成员状态等功能。
- Master主要用于执行在分布式存储系统中遇到的各种问题，比如数据备份、容错恢复等操作。
一个偏向于存储与管理生命周期，一个偏向于管理集群日常事务。
负载均衡
子表是Bigtable负载均衡的基本单位，与GFS的chunk一样。
Tablet Server定期向Master汇报状态。
当Master的状态检测时发现某个Tablet Server上的负载过重时，Master会自动对其进行负载均衡，即执行子表迁移工作。
子表迁移分两步：
1. 请求原有的Tablet Server卸载子表；
2. 选择一台负载较低的Tablet Server加载子表。
由于所有的数据都是构建在GFS之上的，所有Bigtable对子表的迁移实际上迁移的就是表结构以及GFS中数据索引与偏移量相关的数据，并不会执行普通数据库一样的大量数据迁移。
Master发送命令请求原有的Tablet Server卸载子表时需要首先获取互斥锁。如果原有Tablet Server发生故障，新的Tablet Server需要等待原有Tablet Server加载子表上的互斥锁过期。
这样来看Bigtable中的互斥锁有两种，一种就是锁定整个节点的锁，Master用这种互斥锁来确认Tablet Server是否存活；另一种就是锁住整个子表，Tablet Server通过这种锁来获取对子表操作的唯一权限。
在迁移前会对原有Tablet Server执行Minor Compaction操作，将内存中的更新操作以SSTable文件的形式转出到GFS中
Tablet Server不需要回放操作日志。
由于不需要回放操作日志，因此在子表的迁移过程中将会停止该子表的服务，为了尽可能减少停服务的时间，Bigtable内部采用两次Minor Compaction的策略：
1. 原有Tablet Server对子表执行一次Minor Compaction操作，操作过程仍然允许写操作
2. 停止子表的写服务，对子表再执行一次Minor Compaction操作。由于第一次Minor Compaction过程中写入的数据一般比较少，第二次Minor Compaction的时间会比较短。
从“暂停并将内存中的所有数据写入”简化为了“暂停服务，并将上一次Minor Compaction执行期间的操作日志写入”。明显是后者的时间短。
由于子表迁移过程会停止一段时间的服务，因此负载均衡策略不宜过于激进。涉及的因素有：TabletServer读、写个数、磁盘、内存负载等信息。
分裂与合并
随着数据的写入与删除，某些子表可能太大，某些子表可能太小，需要执行子表 分裂与合并操作。
又不改动GFS中的数据，应该就是对Tablet Server中保存的子表的元数据进行一个分裂。
顺序分布与哈希分布的区别在于哈希分布往往是静态的，而顺序分布是动态的，需要同构分裂与合并操作动态调整。
哈希分布很难排序与遍历，因此不方便对数据进行分裂
Bigtable每个子表的数据分为内存中的MemTable和GFS中的SSTable。
同一个子表只能被一台TabletServer服务，因此不会存在子表的备份。如果子表宕机，将会从元数据节点中查询子表的元数据并从GFS中读取恢复。
Bigtable上执行分裂操作不需要进行实际的数据拷贝工作，只需要将内存中你的索引信息分为两份，比如分裂前子表的范围为（起始主键，结束主键]，在内存中将索引分为（起始主键，分裂主键]和（分裂主键，结束主键]两个返回。
分裂以后两个子表各自写不同的MemTable，等到执行Compaction操作时再根据分裂后的子表范围生成不同的SSTable，无用的数据被回收。
分裂操作由Tablet Server发起，需要修改元数据（包括元数据表、根表）。Bigtable保证在元数据中添加一行为原子性事物。只要修改元数据成功，分裂操作就算成功。
分裂成功后Tablet Server向Master报告，如果出现Tablet Server故障，Master可能会丢失汇报分裂的消息。但是当Tablet Server重新上线并从磁盘与元数据表中重新构建子表元数据时会通过定时的汇报将这个修改告知Master。
合并由Master发起，比起分裂要更加复杂，因为可能涉及到多个Tablet Server。所以合并的第一步需要将待合并的子表迁移到同一台Tablet Server上，然后通知Tablet Server执行子表合并。
子表合并一个最大的问题就是主键不连续。而随着子表的合并，在元数据表中按道理说要删除n-1行数据，由此，如何分配并管理合并后的子表主键就是一个问题。
论文原文
2021/03/25追加：合并或许不需要修改根表，只需要修改根表到子表的映射即可，跟Facebook Haystack一样，修改的是映射关系，即一张子表由两段不相交的连续的主键组成，在根表中有两个引用指向该表。
单机存储
Bigtable采用Merge-dump存储引擎。数据写入是需要先写操作日志，成功后应用到内存中的MemTable中，写操作日志是往磁盘中的日志文件追加数据，很好地利用了磁盘设备的特性。
写日志也是往GFS中写，这样可以方式Tablet Server永久下线导致的数据丢失，实际上在Tablet Server中已经不会有独属于它自身的持久化数据，MemTable与SSTable的数据都通过操作日志的形式在GFS中留有备份，他的元数据信息也是存在GFS中，而元数据的索引保存在上级元数据节点中。
类似于LevelDB的写入方法。当内存中的MemTable过大时，将MemTable转储（Dump）成SSTable文件保存到GFS中。
由于数据同时存在MemTable与多个SSTable中，读取操作需要按从旧到新的时间顺序合并SSTable和内存中的MemTable数据。数据在SSTable中连续存放，硬刺可以同时满足随机读取和顺序读取两种需求。
为了方式SSTable数量过多，需要通过compaction过程将其合并为一个SSTable，从而减少后续读操作需要读取的文件个数。
这个SSTable是保存在GFS中，但是在保存的时候GFS会将数据的副本放置在tabletserver本地磁盘中，因此这种合并操作可以是在Tablet Server本地执行完成后统一写入到GFS中。通过Compaction直接在GFS中合并SSTable。
增删改查插入等操作在Merge-dump引擎中都看成一回事，除了最早生成的SSTable外，SSTable中记录的只是操作，而不是最终的结果，需要等到读取时才合并得到最终结果。
Bigtable中包含三种Compaction策略：Minor Compaction、Merging Compaction、Major Compaction。
- Minor Compaction：把内存中的MemTable转储到GFS中
- Merging Compaction：合并GFS中的多个SSTable文件生成一个更大的SSTable。
- Major Compaction：与Merging Compaction执行的操作一样都是将GFS中的多个SSTable合并成一个，但是不同的是他会合并所有的SSTable文件和内存中的MemTable，生成最终结果，而Merging Conpaction生成的SSTable文件可能包含一些操作，比如删除、增加等。
经过Major Compaction之后，Tablet Server中的数据会按照主键有序存储。每个SSTable由若干个大小相近的数据块（Block）组成，每个数据块包含若干行。
数据块的大小一般在8 ～ 64KB之间，可以后期配置。
Tablet Server的缓存包含两种：块缓存（Block Cache）和行缓存（Row Cache）。其中，块缓存的单位为SSTable中的数据块，行缓存的单位为一行记录。
随机读取时，首先查找行缓存；如果读取的数据行在SSTable中不存在，可以通过布隆过滤器发现，从而避免一次读取GFS文件的操作。
垃圾回收
Compaction后生成新的SSTable，原有的SSTable成为了垃圾需要被回收掉。每个子表正在引用的SSTable文件保存在元数据中。因此这个任务需要由Master执行或者参与。
Master定期执行垃圾回收任务，这是一个标记删除的过程。首先扫描GFS获取所有的SSTable文件，接着扫描所有子表与元数据获取他们正在引用的SSTable文件，如果GFS中的SSTable没被任何一个子表使用，说明可以被回收掉。
如果刚好遇到Tablet Server下线并且Master还没有获知这一情况下，此时一部分有效SSTable将没有被任何子表引用。这个问题的解决办法在于子表对SSTable的引用需要有一个过期时间，而不是实时引用，这个过期时间需要设置的比Tablet Server持有的互斥锁所过期的时候要长或者相同。这样，发生这种情况的时候这部分SSTable的引用依旧存在，而当引用过期的时候Tablet Server已经下线的情况早就被Master所得知了，也不会随便开启垃圾回收，或者在开启垃圾回收的时候将这部分SSTable判断为非垃圾数据。
由于Tablet Server执行Compaction操作生成一个全新的SSTable与修改元数据这两个操作不是原子的，垃圾回收需要避免删除刚刚生成但还没有记录到元数据中的SSTable文件。一种简单的做法就是垃圾回收只删除至少一段时间，比如1小时没有被使用的SSTable文件，这样上面的那个问题也同时被解决了。
讨论
GFS+Bigtable两层架构以一种很优雅的方式兼顾系统的强一致性和可用性。
底层文件系统GFS是弱一致性，可用性和性能好，但是多客户端追加可能出现重复记录等数据不一致问题；
表格系统Bigtable通过多级分布式索引的方式使得系统对外整体表现为强一致性。
Bigtable最大的优势在于线性可扩展，单台机器出现故障可以将服务迅速迁移到整个集群。但同时Bigtable也面临一些问题：
- 单副本服务。Bigtable架构非常适合离线或者半线上应用，然而，TabletServer节点出现故障时部分数据短时间内无法提供读写服务，不适合实时性要求特别高的业务，比如交易类业务
- 不过谷歌最开始用Bigtable就是为了存储网页信息
- SSD使用。谷歌整体架构的设计理念为通过廉价机器构建自动容错的大集群，然而，随着SSD等硬件技术的发展，机器宕机的概率变得更小，SSD和SAS混合存储也变得比较常见，存储和服务分离的架构已经不太适应当前时代
- 架构的复杂性导致BUG定位难。Bigtable依赖GFS和Chubby，这些依赖系统本身比较复杂，另外，Bigtable多级分布式索引和容错等机制内部实现都非常复杂，工程量巨大，使用的过程中如果发现问题很难定位。