Bigtable: A Distributed Storage System for Structured Data

• The row keys in a table are arbitrary strings (currently up to 64KB in size, although 10-100 bytes is a typical size for most of our users). (rowkey范围限制在64KB，但是10-100bytes是一个典型值)
• Every read or write of data under a single row key is atomic (regardless of the number of different columns being read or written in the row), a design decision that makes it easier for clients to reason about the system’s behavior in the presence of concurrent updates to the same row.（对于每一行的读写都是原子操作的，这样对于concurrent更新的话比较好reason）
• Bigtable maintains data in lexicographic order by row key. The row range for a table is dynamically partitioned. Each row range is called a tablet, which is the unit of dis-tribution and load balancing.（对于row-key都是按照字典序排列的，并且每个row range都会动态划分。划分出来的row range对应的数据成为tablet，其实就是table里面一个连续的小部分，非常类似于chunk，作为分布以及负载均衡的最小单元）

• Column keys are grouped into sets called column fami-lies, which form the basic unit of access control （所有的column都放在某一个column family下面进行管理）
• All data stored in a column family is usually of the same type (we compress data in the same column family together).（通常在一个column family下面的column都是相同类型的，这样方便进行压缩）
• A column family must be created before data can be stored under any column key in that family; after a family has been created, any column key within the family can be used. （首先需要创建cf，之后可以在cf下面创建任意的column）
• It is our intent that the number of distinct column families in a table be small (in the hundreds at most), and that families rarely change during operation. In contrast, a table may have an unbounded number of columns.（设计假设cf非常少最多100个左右，并且不会经常变化。而对于里面的column来说没有上限）
• Access control and both disk and memory account-ing are performed at the column-family level（底层访问操作通常都是针对cf进行的。使用cf聚合的话，一方面可以减少访问多个字段的代价，另外在存储方面也可以进行压缩）

• Each cell in a Bigtable can contain multiple versions of the same data; these versions are indexed by timestamp. Bigtable timestamps are 64-bit integers. They can be as-signed by Bigtable, in which case they represent “real time” in microseconds, or be explicitly assigned by client applications. Applications that need to avoid collisions must generate unique timestamps themselves. Different versions of a cell are stored in decreasing timestamp or-der, so that the most recent versions can be read first.（timestamp用来区分多个版本，timestamp是一个64bit整数，这个可以由bigtable产生也可以用户指定。主要功能就是为了区分版本。所有的版本都是存放在一起并且按照降序排列，因为首先读取是最新的版本）
• To make the management of versioned data less oner-ous, we support two per-column-family settings that tell Bigtable to garbage-collect cell versions automatically. The client can specify either that only the last n versions of a cell be kept, or that only new-enough versions be kept (e.g., only keep values that were written in the last seven days).（支持针对每个cf设置使用最近几个版本）

• root tablet是比较特殊的METADATA tablet从来不进行分裂
• METADATA tablet是kv结构并且是有序的。其中k是table identifier+end row key，v则是对应志向的位置（位置信息应该都是GFS的地址）
  • 查找的时候首先在root tablet上面做二分查找，找到对应的METADATA tablet。
  • 然后在METADATA tablet上面做二分找着，找到对应的user tablet。
  • 然后在user tablet上面找到对应的值。
• meta tablet server每行存储大概1KB数据，一个大约使用128MB内存，这样对于三级结构来说允许存储大约我2^34个tablets。
• client会cache tablet位置，但是如果位置信息错误的话，那么需要逐层向上查询。因为对于cache empty情况需要3个roundtrip，而对于stale情况需要6个roundtrip
• Although tablet locations are stored in memory, so no GFS accesses are required, we further reduce this cost in the common case by having the client library prefetch tablet locations: it reads the metadata for more than one tablet whenever it reads the METADATA table. #todo: 预取可以减少什么开销呢?

assignment这个信息应该是维护在master上面的，且没有必要进行持久化。

如何处理tablet server挂掉：

• 所有的tablet server都在chubby上面注册节点并且加锁。如果和chubby节点断开的话，那么重新连接并且获取锁。如果文件已经删除的话，那么就自动退出。
• master会定时询问tablet server是否存活。如果没有查询到存活的话，那么会尝试lock tablet server创建的节点。如果lock成功的话，那么删除这个文件。这样确保tablet server之后不会继续服务。
• 如果master认为某个ts挂掉的话，那么会重新assign原来分配所有的tablet出去。
• 如果master和chubby断开的话，那么也会自己直接退出。

master启动时候需要重新获得assignment信息：

• master重启的话不会影响assignment
• master在chubby上面创建一个文件并且lock
• 和当前所有的tablet server进行通信，获得所有的tablet server。
• 如果METADATA tablet server没有被assign的话，那么assign META ts
• 扫描所有的META ts，看哪些tablet server没有被assign出去，如果没有assign的话那么发起assign

如果tablet server上面的tablet发起变化的话，那么也会有assign行为：

• table创建删除
• 两个tablet进行merge成为一个大的tablet（这个master才能够看到）
• tablet split（这个单个tablet server就能够感知到自己的tablet过大从而需要split）

对于前面两个行为的话是master发起的话能够追踪所有的变化。

对于tablet server发起操作导致tablet变化的话，完成之后写入METADATA tablet，通知master。

In case the split notification is lost (either because the tablet server or the master died), the master detects the new tablet when it asks a tablet server to load the tablet that has now split. The tablet server will notify the master of the split, because the tablet entry it finds in the METADATA table will specify only a portion of the tablet that the master asked it to load.

compaction分为三种：

• minor compaction. memtable -> sstable
• merging compaction. sstable + memtable -> sstable(s)
• major compaction. sstable -> one sstable

其中leveldb里面实现只有前面两种。merging compaction就是几个sstable合并（合并的sstable里面没有deletion），而major compaction回将所有的sstable合并成为一个sstable（里面没有任何deletion）

通过将多个cf合并成为一个locality group，然后为这个locality group分配单独的一个sstable。通过将不同属性的cf区分开，并且将相同属性的cf进行聚合，这样可以提高读效率。允许指定参数来说明那些locality group需要放在memory里面。

• The first pass uses Bentley and McIlroy’s scheme , which compresses long common strings across a large window.
• The second pass uses a fast compression algorithm that looks for repetitions in a small 16 KB window of the data.
• Both compression passes are very fast—they encode at 100–200 MB/s, and decode at 400–1000 MB/s on modern machines.

• Scan Cache在高层缓存读取到的k/v。比较适合重复读取相同数据（相对与Block Cache效率更好）
• Block Cache在底层缓存读取到的block。比较适合遍历或者是反复读取附近数据。（leveldb实现里面只是提供了block cache）

新版本的leveldb里面也实现了bloom filter，可以屏蔽掉很多无用的disk seek

如果每个tablet的操作都写单独的redo文件的话，那么会对gfs造成很大的压力。因此解决办法就是，对于一个tablet server上面所有的tablet的commit log，都记录在同一个文件里面。

但是这样会对recovery造成一定的问题：假设这个tablet server上面有100 tablet的话，如果down掉，那么100 tablet重新assign之后每个tablet server都需要读取这个文件， 然后根据log里面的内容判断除外哪些log是自己需要的。

这个问题的解决是通过将这个log进行排序。如果有一个tablet server需要读取这个log的话，那么会通知master，master发起排序操作。按照 （table, row name, log sequence number ） 这个复合键进行排序。排序之后每个tablet server只需要找到相应的偏移就可以开始顺序读取了。

另外写gfs的时候也可能因为很多原因造成perfor-mance hiccups(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).，为了减少latency spike，对于tablet server写commit log是采用两个线程完成的，但是只有一个线程在执行。如果一个线程写入比较慢的话，那么就会切换到另外一个线程写入。因为log里面都带了sequence number，所以在读取的时候可以进行判重避免读取重复数据。

这个主要发生在tablet主动迁移的时候。因为迁移的时候memtable内容没有存放到gfs上面，因此如果直接unload的话，那么在另外一台机器上面就需要重新从gfs读取log并且进行recovery。 为了加快这个过程，source tablet server在主动迁移时候发生如下行为：

• 将memtable使用minor compaction将内容写入sstable
• 停止对这个tablet的服务
• 将上面时间内所有的memtable操作重新做一个minor compaction(very fast)

这样另外一台机器load tablet的时候就可以直接使用了。

对于obsolete tablet sstable的回收过程是这样的：

• 从root里面可以获得所有的tablet对应的sstable（tablet管理的sstable都在METADATA tablet上面注册了）
• master可以查询每个tablet server所管理的sstable
• 对比master就可以发现那些sstable是可以被GC的。