Ssystem|分布式|Bigtable
Ssystem|分布式|Bigtable
Bigtable被称为谷歌的三驾马车之一，主要面向谷歌的结构化数据存储,其思想被许多nosql数据库继承。Bigtable建立于GFS和Chubby之上，而为MapReduce服务,可以说是承上启下。
A Bigtable is a sparse, distributed, persistent multidimensional sorted map.
Bigtable基于行名、列名、时间戳进行索引。存储的内容仅仅是无类型字节，由应用解释。谷歌常常用URL作为行，页的某方面作为列，内容作为值。
行
对行的读写具有原子性，按照字典序排列。行的范围是动态切分的，称为tablet，是数据的分配和负载均衡的基本单元。因此客户端应该注意范围尽可能小，保证局部性。
e.g. URL并没有按照浏览器输入顺序，而是按照com.cnn.www这样的方式进行的，这种方式实际上就是DNS解析域名的顺序，因此相同DNS域名的网页会被放得连续，查询效率高。
列
列也进行了分组，为col family，是访问控制的基本单元。同组的内容一般是相同类型。必须先创建col family才能新建列，但是family本身通常很少变动。
如上图，列名为{family}:{qualifier}，family必须可打印，qualifier则任意。例如在这里anchor就是一个family，qulifier是引用网站，内容则是链接。
时间戳
时间戳由Bigtable自动生成或者Client指定，不同版本按照增序排列，便于取出新数据。按照版本数和距今的时间戳两种机制GC
API
// Open the table
Table *T = OpenOrDie("/bigtable/web/webtable");
// Write a new anchor and delete an old anchor
RowMutation r1(T, "com.cnn.www");
r1.Set("anchor:www.c-span.org", "CNN");
r1.Delete("anchor:www.abc.com");
Operation op;
Apply(&op, &r1);
//Read
Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily("anchor");
stream->SetReturnAllVersions();
scanner.Lookup("com.cnn.www");
for (; !stream->Done(); stream->Next()) {
printf("%s %s %lld %s\n",
scanner.RowName(),
stream->ColumnName(),
stream->MicroTimestamp(),
stream->Value());
}支持单行事务但不支持跨行事务，还有谷歌自己的脚本语言用于变换数据。
在上个文章中我们提到了MapReduce的输入输出基于GFS，这次谷歌改成了基于Bigtable，又是著名的所有问题增加一个间接层来解决。不过最关键的中间文件存在哪里谷歌还是没有动刀子，存在Mapper本地文件。所以后来Spark一个重要的优化就是中间结果存在消息队列里面，in-memory存储。
- GFS - 数据和log存储
- 集群管理系统 - 监控状态分配任务处理故障管理资源
- SSTable文件格式 - 持久化有序不可变map，由一系列block构成，有一个索引用于定位，SSTable打开时block的索引放入内存，因此查找的时候内存查索引，然后磁盘查数据。
- Chubby - OSDI，类似于Zookeeper的注册中心，提供高可用持久化的分布式锁，有时间再写，反正和zookeeper长得差不多，理解为专门放metadata的地方就好。
谷歌在实现里说明了架构细节，不过没配图，我自己画张。经典的数据流控制流解耦，Master通过Chubby实现所有Tablet的控制，Client通过Chubby实现所有Tablet的读写。
Bigtable由Client链接库、单Master、多Tablet Server组成
- Library 提供访问API
- Master 分配Tablet数据，监测Tablet服务器数目变化，负载均衡，对GFSGC，处理table和col family等schema
- Tablet Server 通过GFS远程存储若干Tablets,处理读写,同时tablet过大时进行分裂
和其他单Master集群思路一样，数据同样不流经Master（所以多Master就可以流经咯）,而且Tablet的定位甚至也不需要master，因此master低负载。
最初的Tablet Server仅仅持有一个Tablet,大的时候再分裂。(相当于数据库自动垂直分表）
Tablet寻址
这里相当于利用Chubby做了服务发现，按照Chubby->Root->METADATA->Data层次化定位。机制和页表类似，Client的缓存相当于TLB，Chubby相当于ttbr或者cr3。
- Root 是特殊的METADATA,从不分裂，存储所有tablet的位置。
- METADATA 把tablet的位置以及事件的log存在(tablet id,末尾行）编码后对应的行,1KB。
- Client 会缓存tablet位置。如果cache hit最好，如果cache miss则要三次寻址，如果cache错误则需要六次，先miss原地址然后再miss新地址才能获得正确地址。Prefetch优化。
Tablet分配
当tablet服务器运行后，在服务器目录创建独一无二的文件申请互斥锁，然后用于master服务发现。如果tablet服务器发现文件不在了也就是失去了互斥锁，那么它就停止服务(例如和Chubby断连)并且尝试放锁从而方便master再分配。
(Chubby provides an efficient mechanism that allows a tablet server to check whether it still holds its lock without incurring network traffic.)
master会通过Chubby跟踪活着的tablet服务器，以及存储目前的分配情况, 对未分配且空间充足的服务器发出load请求要求他们通过Chubby获取指定的tablet，load通过Chubby进行。
master定期轮询tablet服务器锁状态，监测到tablet服务器停止服务或者和master断连后,master立即尝试向Chubby请求对应文件的互斥锁。
如果能请求到，那么说明tablet服务器大约的确是挂了，并且删除对应的server文件，然后把之前分配的tablet转移到没分配的tablet。这里为了保证Master和Chubby的P,一旦断连Master就kill自己牺牲一定的A, 但是却无法assign，因此需要重启的master擦屁股。
master重启后
- 申请master锁
- 找到live服务器
- 问他们已经分配了什么tablet
- 如果找到了ROOT，扫描METADATA遍历所有tablet并从中找到没有分配的tablet
- 如果没找到ROOT，把ROOT加到未分配中，然后执行上面的操作。
tablet创建或者摧毁master都知情，但是tablet分裂则是tablet server干的。因此tablet server需要commit自己的分表信息到METADATA里面的新表，并且通知master。如果通知失败，下次master要求load分裂前的表时，tablet server又会通知master新表的存在。
Tablet 服务
Write-ahead-log 写操作会先放进log中，这个log是REDO log。最近的一些commit会放在memtable中，一个in-memory有序缓存。
Recover 恢复Tablet Server时，从METADATA中读取自己的metadata，例如一系列的SSTable和REDO point，也就是那些可能存储着数据的log。然后根据log更新SSTable。
Write 首先检验格式是否正确，从Chubby中读取白名单确认访问权限，然后log
Read 首先检验格式是否正确，从Chubby中读取白名单确认访问权限，然后从memtable和SSTable两者结合(因为都是有序表所以容易合并)获取数据。
Tablet分裂与合并的时候，读写依然能够继续(因为真正持有数据的是SST和Log)
Tablet Compaction(这玩意儿不好翻译啊，压缩和Compress混淆，姑且翻译成夯实）
当memtable达到阈值时，新memtable被创建，而旧的则放进SST。(minor compaction)
这里是实际的持久化阶段，也就是把内存持久化成SST。
夯实的目的有二:
- 减少内存占用
- 减少崩溃后需要读取log的数目
夯实同样不影响读写(同上理)
如果每次夯实都创建新的SST，那么显然容易数目过多，因此有个专门的merge进程用来把SST和memtable进行合并(merging compaction)。这里的合并指的是先把数据读出来，再创建新的SST，原本的SST是不可变的
如果把所有的SST都进行合并到一个SST，则成为major compaction。
非majar夯实产生的SST会保存被删除的特殊条目(can contain special deletion entries that suppress deleted data in older SSTables that are still live)，而major则不会。Bigtable会定期地进行major compaction彻底抹杀这些数据。
优化
本地化组 - 几个col family构成locality group，专门放一个SSTable
压缩(Compression) - 选择某些不经常访问的SST压缩，经典时空交换
Cache - 高层Scan Cache缓存键值对，底层Block Cache缓存SST blocks
Bloom Filter - 便于询问制定指定行列数据是否存在于SST中，而不需要从磁盘取出读
Commit Log实现 - 为了减少磁盘寻道，使得同tablet server的log写在同一个文件，不同tablet的log混合。
问题是如果这些tablet分别被不同的server给load的话，读的效率不高，因此log entry按照<table, row name, log sequence number>排序，这样每个tablet可以连续读了。log被分成64mb的段，不同段可以并发排序。
另一个问题是写可能性能受挫s (e.g., a GFS server machine involved in the write crashes, or the network paths traversed to reach the particular set of three GFS servers is suffering network congestion, or is heavily loaded)，所以有两个写线程，如果一个堵住了就切换另一个，通过log的序列号保证切换不会出错。
加速Recovery - 一旦发生tablet移动，source立即minor compaction减少未被夯实的log，之后unload停止服务，然后执行第二次快速的minor compaction处理期间，最后再load。
利用不变性 - 在读时我们不需要考虑同步SST，可变的仅有memtable，因此对memtable执行COW，保证并发读写。
在分裂时，只需要使得两个子tablet共享同一个SSTable即可
在删除时，变成了GC淘汰的SSTable，因此用标记清扫法，删除时标记即可
LSM Tree
后来业界专门给谷歌这种数据结构取了名字叫做Log Structured-Merge Tree, 谷歌的实现只有L0，又新增了层次化处理新旧关系,优先查上层的数据，还有个immutable table作为专有名词表示compact的中间状态，这里的immutable就是旧，mutable就是新。这个算法最后成为了nosql的存储引擎
当memtable达到阈值时，新memtable被创建，而旧的则放进SST。(minor compaction)
LSM Tree的问题在于写入快（写Log)，读取慢（分层多的时候)，因此优化用了两级Cache。
云时代下的Bigtable
估计指的是后来2012OSDI的Spanner。因为谷歌这三架马车都没开源，目前的开源项目都是对着论文实现的（比如HDFS之于GFS,Hadoop之于MapReduce），看看就好。
参考: Bigtable: A Distributed Storage System for Structured Data
Problem: 提供大规模结构化的分布式存储
Related work: 维护过于复杂的关系模型
Observation: 获取数据通过Chubby不经过Master + LSM Tree + 无意义数据
Solution: Chubby利用页表机制寻址, 数据通过WAL持久化然后逐渐转移到SSTable
Evaluation: 不支持复杂的分布式事务, 数据无意义由应用处理更domain specific
Comments: SST全放到GFS的话，Bigtable本身的磁盘空间是不是没法充分利用了