BigTable论文学习总结

一.bigtable是一个分布式存储系统，可以用来管理PB级别的结构化数据，且可以分布在大量的商业服务器上。

二.bigtable的目标是：广泛适用性，扩展性，高性能，高可用性。bigtable其类似一个数据库系统，和普通RDBMS数据库具有很多相同的策略，但是bigtable并不支持关联数据模型（bigtable是数据关系松散的），相反，它向客户端提供简单的/动态控制/模式自由的数据模型。可以通过row key和column name索引。客户端可以将任意字符串/字节数据存储与bigtable。Bigtable schema参数可以让客户端动态的控制数据是存储在memory中还是disk。

三.bigtable的数据模型是的一个松散的/分布式/持久存储/多维有序map，map通过row key/column key/timestamp进行排序，map的K-V可以为任意字符串。

四.row key（第一索引）可以为任意字符串，长度可以支持到64K，但是实际应用中，通常row key的值在100字节左右。可以通过row key获取当前行的任意数据。bigtable通过字节的字典顺序对数据进行存储，table将通过根据row key的区间进行分区，每个分区为一个“tablet”，tablet是bigtable进行分布式存储/负载均衡的基本数据单元。所以，读取一个小区间的数据将是高效的（只需要访问少数机器即可），所以对于row key值的设定将显得很重要，对于业务类型一样的数据，其row key值应该比较“接近”（字典顺序接近），可以让它们的存储更加集中，提高read的性能。

五.cloum family：简单来说，column key的集合，就是一个family，中文为列族(簇?)。列族是数据操作的基本单元。Column family必须在使用之前定义。不过bigtable的设计意图是希望用户的family尽量的少，且不能在操作是修改column family。。不过一个table可以有任意多个column。Column family的名字必须是可打印字符。存储层的控制（disk，memory）均是在column family层面。

六.timestamp:任何cell都可以包含多个版本的数据，这些版本数据将通过timestamp进行索引，bigtable中timestamp是64位的Long值，它可以被bigtable自动生成，也可以客户端指定。为了避免冲突，请制定唯一的timestamp。cell数据按照timestamp倒序存储，这样可以确保最新的值被优先取到。客户端可以指定（配置）任何cell需要保留version的个数，在bigtable 执行GC时，只有最新的version会被保留（同时支持最近n天内的version被保留）。

七.bigtable提供了对table/column family/column级别的修改/删除等API，同时还通过了权限控制。bigtable支持行级别事务，即单行数据的 read-modify-write的原子性（即单行数据，read之后，moidfy，然后再update，此3步为一个序列，可以确保数据的完整性）。但是bigtable尚不支持跨行事务操作（一个操作序列中，需要update多行数据，且执行过程是原子型的。），bigtable提供了多行批量操作的API。

八.bigtable是基于GFS存储log和数据文件的，bigtable依赖于分布式管理系统来执行scheduling jobs，管理资源，处理机器故障恢复，监控机器状态。Googe SSTable用来存储bigtable内部的数据，SSTable提供了持久/有序/稳定的map（K-V），可以用来查询特定的row kye获取k-v数据，也可以遍历row range数据序列。每个SSTable包括一序列blocks（一般尺寸为64KB，可配置），block索引（SSTable维护）可以帮助定位block位置，block索引会在SSTable打开时载入内存，一次查询可以通过一次disk seek执行完成：首先在内存中通过二进制查找（binary search）索引找到合适的block，然后把此block数据从disk中加载至内存，然后在内存中完成所需要的操作（row数据整合等）。此外，SSTable可以被完全映射如内存，这样可以允许client执行lookup/scan操作时，无需disk seek。
    Bigtable依赖一个高可用/持久的分布式锁服务，它称为chubby，在hadoop子项目中单独实现为zookeeper。Chubby服务会包含多个active replicas（副本），它们都有机会被选举位master，且子一个chubby服务中，只能有一个master，master是client请求服务的入口。Chubby使用Paxos算法来保持其replicas在遇到问题时状态/数据的一致性。Chubby 提供了一个namespace机制，namespace有目录和文件（files）组成，每个目录/文件都可以作为一个lock，并且对文件的都写操作是原子的，chubby client library对这写chubby files提供了一致性缓存，每个chubby客户端维护一个对chubby service的session，当chubby客户端session通话阻断或者重新获取session失败（在约定过期时间内，没有renew session），那么此session失效，此client失去chubby service的lock，同时意味着它将“离群”（失去服务提供能力）。Chubby client也能向chubby fiels/directories注册回调方式，当session过期或者更改可以通知client。
    bigtable使用chubby服务来做很多事情：确保任何时候有一个master可用；存储数据的bootstrap位置；检测tablet server的状态，以及确定tablet server的“离群”；存储bigtable schema信息（column family of every table）；存储access control lists（权限控制列表）。如果chubby service在较长的一段时间内不可用，那么bigtable也将不可用。

九.bigtable的实际应用中，有3个必要组件构成：一个类库，一个master，一些tablet server。Tablet server 能够根据负载量动态的增加/删除。  Master用来负责对tablet server中生成的tablet分配管理，检测tablet server的增加和过期；均衡tablet-server的负载,gc GFS的文件,此外还负责table/comlum family的schema修改/新增等.每个tablet server管理一部分tablets(一般为10~100个左右),tablet server处理client的数据都写操作(前提是tablet在此机器上),同时负责split尺寸过大(超过阀值)的tablet.
    在单master分布式存储系统中,client数据操作是不需要经过master:client直接与tablet server通信,进行数据交互.因为bigtable client不依赖master来确定tablet位置信息,大多数 bigtable client很少master通信,因此master的负载很低.
    bigtable分布式节点(DataNodes)中存储一定数量的tablets,每个tablet server包含一序列tablets,每个tablet包括一序列(row key range)所有的数据(即所有table的column family).初始时,每个table只有一个tablet,随着数据量的增加,tablet被spit成多个tablets,默认每个tablet的尺寸为100~200M左右(可配置).

十.bigtable使用三层B+结构来存储tablet的位置信息，第一层是root tablet，它存储在chubby中，root tablet将所有的tablets位置信息存储在 一个特殊的METADATA表中,每个METADATA表包含一系列user tablets位置，root tablet仅仅是METADATA表的第一个tablet，但是它从不会被split，以保证结构分层不超过3层。METADATA表存储tablet位置，基于编码之后的table标示和它们的结束行。每个METADATA row大概有1KB（内存存储）。客户端library会缓存tablet位置信息，如果client不知道tablet的位置或者发现缓存的位置信息有错，it recursively move up the tablet location hierarchy。

十一.每个tablet都会被分配到一个tablet server上，master跟踪每个live table server以及其上的已经分配和尚未分配的tablets。当一个tablet未被分配，且有一个tablet server有足够的空间，那么master将会分配此tablet通过向此tablet server发送一个tablet装载请求。

十二.bigtable借助chubby来跟踪tablet servers，当一个tablet server启动，它将会在chubby的一个特殊文件目录下，对一个唯一名称的文件获取排他锁；master会监控此目录来观察tablet server。一个tablet server如果失去对chubby file的排他锁，那么它就停止对tablet的服务。因为网络的不稳定因素可能导致tablet server失去chubby session。（chubby提供了一种高效的机制让tablet server自主检测自己是否仍然持有lock，此机制之需要较少的网络流量）。Tablet server将尝试重新获取排他锁（假如文件仍存在），如果文件不存在，tablet server将永远再不能继续服务，最终server将kill itself（终止进程）。当一个tablet server终止了（分布式管理系统从环境中移除此server节点，比如通过安全终止指令，而不是直接断电），它将会尝试释放chubby file lock，同时master将会把此上的tablets重新分配（分配，均衡）。
     Master检测到tablet server不能继续serving its tablets，那么它就会立即重新分配此tablet server上的tablets。Master为了检测tablet server的状态，master会间歇性的问询每个tablet server对chubby file block的持有状态。当tablet server报告其失去了lock，或者master无法访问到tablet server，那么此时master将尝试去获取此tablet server file（chubby 下）的排他锁，一旦master获取此锁，并且接下来chubby服务正常并且tablet server宕机或者与chubby通信遇到问题，master会确认tablet server真的无法提供服务了，然后将果断删除chubby server file。一旦server file被删除，那么就意味着此tablet server“离群”了，master将在tablet server已经分配的tablet转移到未注册状态。
    请确保bigtable发分布式环境中，master和chubby之间的网络状况是良好的，如果master和chubby的链接session过期/失效，那么master也会kill itself。不过master的失效，不会改变tablet的分配状况。当master被分布式管理系统启动，它首先去检查当前tablet的分配情况，然后才能去做改变tablet分配的操作。如下是一个master的启动的步骤：1）master首先在chubby service中grab（捕获）一个唯一master lock，用来阻止其他master进行同样的操作，确保master群组中只有一个主master 2）master扫描chubby下服务器注册表目录（server directory，server file），来获取所有现存的server信息。 3）master与每个tablet server通信，来检测其上已经分配的tablet。4）master 扫描 METADATA 表，来获知tablet集合，无论何时，一旦在扫描时获知一个tablet尚未被分配，那么master就会把此tablet信息添加在“未分配”的集合中，以保证这些未分配的tablet有被分配的机会。

    其中需要提醒的是，master扫描METADATA的动作只有在METADATA标已经被分配时才会发生，所以在开始扫描时（第4步），如果在第三步操作时未发现root tablet，那么master也会将root tablet添加至“未分配”集合中，最终以确保root tablet是存在且已经分配。因为root tablet保存了所有METADATA tablets的名称信息，master通过扫描root tablet可以获取它们（METADATA）的所有信息。

    一些现存的tablets只有在table创建或者删除时才会发生变化（变化的前提是，表必须存在），2个现存的tablets可以合并成一个更大的tablet，当然可以可以分裂成2个更小的。master能跟踪这些变化。Tablet server对于tablet分裂是特殊对待的，分裂开始时tablet server会提交分裂信息通过在METADATA 表中记录新/旧tablet信息。当分裂被提交后，它会通知master。万一分裂通知消息丢失（或许是因为tablet server或者master以及died），master会通过问询tablet server其上已经分裂（可能部分未分配）的tablet来检测那些新的tablet（已经分裂但是尚未分配的）。Tablet server在分裂时会通知master，因为METADATA表中找到的tablet数据会指定为“master要求tablet server装载的tablet”的一部分。（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.）。估计意思是：master中持有的tablet分区情况可能是分裂之前，但是METADATA表中已经记录了分裂的情况，client请求tablet server中tablet的信息，master只知道是分裂之后的一部分tablet信息（非数据），如果不通知master，master可能在一段时间内仅持有分裂前的tablet情况。（不过master会间歇性的问询tablet server，避免这写通知消息丢失等不同步情况）。其通知的目的，是master掌握的spit信息和METADATA table一致。

十三.持久状态的tablet是存储GFS中，对于更新操作，将会首先提交至commit log文件中。最新更新的数据，是保存在内存中，称为memtable，较旧的更新数据保存在一系列的SSTables中。为了恢复一个tablet，tablet server会从METADATA表中读取它的metadata信息，这个metadata中包含组成这个tablet的SSTables列表，以及一些redo points，这些point指向包含此tablet数据的相应的commit log，tablet server把这写SSTable的indices（指数？？）读取到内存，通过应用redo points之后提交的更新操作，重建memtable。【一个tablet的恢复，包括SSTables恢复（已持久）和memtable（已提交的更新，单尚未被flush成文件，这写数据只能通过commit log恢复）】
    当一个“写”操作请求tablet server，server会检测其数据是否是格式良好的，并且请求者具有相应的更改权限。授权操作是chubby来做，它通过读取一个chubby file（可以被缓存在内存中）来获取所有许可用户列表，只有合法的修改操作才会被记录在commit log中。Group commit可以提高并发量。当write请求被提交后，它的数据内容将会被插入到memtable中。

    当一个read请求tablet server，它和write操作类似：检查格式良好和授权。一个有效的read操作被执行，会在一个merged view上执行（一序列SSTables和memtable）。因为SSTable和memtable中的数据都是row key的字典顺序存储，所以，merge view能被高效的整合。【从SSTable和memtable中读取相应row key的数据，然后整合成一个view，这个view中包含read所需要的数据】当tablets分裂和整合时（spit/merged），仍然可以进行读写操作。

十四.当write操作不断执行，memtable的size也会不断增加。当memtable的size达到阀值，memtable会被frozen，同时一个新memtable会被创建，被“冻结”的memtable会被转换成SSTable存入GFS中。Minor compaction有2个目的：减少tablet server中内存的使用量；在server宕机时恢复数据时，减少从commit log中读取数据的总量。compaction时仍然可以接受read/write操作。

    Minor compaction执行的结果是产生一个新的SSTable。随着minor的执行，将会产生大量的SSTable，所以会导致read操作将“跨越”多个SSTable（merge结果）。相反，我们约束这些文件的数量（SSTable）通过后台程序间断的去执行一个merging compaction。Merging compaction从一些SSTable和memtable中读取数据内容，然后写入到一个新的SSTable。作为输入源的SSTable和memtable将会在compaction之后删除。

    一个重写所有SSTables到一个SSTable的merging compaction称为major compaction。非major compaction产生的SSTable会包含一些特殊的删除的数据。Major compaction创建一个不包含任何删除信息和删除数据的SSTable，bigtable在所有的tablet中循环定期执行major compaction。Major compaction允许bigtable来回收再利用这些删除数据占用的资源，同时也确保这些删除的数据能够及时的从文件系统中消失，这对于存储一些敏感数据很重要。

    客户端能把多个column family聚集在一起成为一个locality group。一个SSTable对应locality groups（概念上对应，非数据，原句：A separate SSTable is generated for each locality group in each tablet.）。不同的column family分离存储在不同的locality group中能够使read更加高效。例如：webtable中的page metadata（language，checksums）可以为一个locality group,page内容在另外一个group中：应用程序仅需要获取page metadata，将不会对page内容进行多余的read。此外，可以对每个locality group指定一些有用的调节参数，例如，一个locality group能被声明存储在内存中，针对存储在内存中的locality group，SSTable将延迟加载它们到内存。一旦加载，属于这个locality group的cloumn families能够直接在内存读取而无需进行硬盘操作，这种特性，对于那些存取频繁的小数据比较有用：METADA表中使用这个特性来定位column family。

十五.客户端能够控制SSTable for a locality group的压缩与否，以及其压缩的方式。用户指定的压缩格式可以应用在每个SSTable block（block的大小可以通过配置指定）。虽然压缩每个block将会消耗一定的空间，但是读取SSTable的一小部分无需解压整个file，我们可以从中获益。压缩算法，更注重速度而非减少空间。

十六.为了提高read性能，tablet提供了2个级别的缓存。Scan cache是个hight level的缓存，用来缓存SSTable查询返回的K-V对。Block cache是一个lower level的缓存，用来缓存从GFS中读取的SSTable blocks。Scan cache在读取多次重复读取相同数据非常有用，block cache对于依次读取一序列（row 序列）数据比较有利（顺序读取，或者随即读取locality group中一个hot row中不同的列）。

十七.如果每个tablet的commit log分别存储，那么将会导致大量的log文件并发写入GFS。依据GFS 底层文件系统的实现，这种不同物理log文件的写入能导致大量的disk seeks，此外，每个tablet一个commit log还降低了group commit的性能优势，因为groups可能会小很多。为了解决这个问题，我们提交这写数据变更信息到一个单一的commit log文件中。

    对于普通的操作，单一log文件能够显著的提高性能，但是增加了数据恢复的复杂性。当tablet server宕机，此server上服务的tablet将会被“moved”（迁移）到其他servers上：每个server会承担原来server上一些数量的tablets。为了恢复tablet，新的tablet server需要回放原来server上的commit log上数据的更改。

    所有tablets的commit log信息混合在一个log 文件中。每个新的tablet server需要读取原server上commit log，获取其需要恢复的tablet的相应的操作。但是在这种schema下，如果100个机器被分配了一个failt server上的tablet，那么这个log file将会被全量读取100次。

    为了避免这种log文件重复读取，对commit log数据条目中的按照key(table,row name,log sequence number)进行第一排序.在这个有序的输出中，对一个特定的tablet的所有更改都是连续存储的，所以能够通过一次disk seek顺序read这写日志，而且比较高效。为了能够并行排序，我们对log文件进行分区，每64M一个segement（片段），在不同的tablet servers上并行排序每个片段。排序处理可以通过master来协调（应该是master决定写入那个segment），当tablet server需要从某个commit log文件恢复这写变更的数据时，会发起这个排序处理（这个处理thread或许能有定位恢复数据的log/以及其他功能）。

    把commit log写入GFS，偶尔会带来性能上的波动（可能是网络原因）。为了保护操作GFS中数据延迟不会太大，每个tablet server都有2个日志写入线程，但是同一时间知会有一个线程运行。如果写入日志运行的不够良好，那么线程将会被切换成另一个。每个log数据条目都包含一个sequence数字，让恢复处理程序无需读取因线程切换造成的重复的log条目数据。

十八.如果master从一个tablet server上迁移一个tablet到另外的server上，原server首先会对tablet进行一次minor compaction。此次compaction减少commit log中记录的uncompacted的数据的总量，以此降低恢复数据的时间。compaction结束之后，tablet server停止此tablet的服务能力。不过在tablet server卸载此tablet之前，会补充执行一次minor compaction，主要是用来清除（数据恢复到ablet文件中，清除log内容）在第先前minor compaction执行过程中新增的commit log信息，执行时间会非常短。在这次compation执行结束后，日志中也。有了此tablet的恢复信息，同时此tablet也被装载到了其他server上。（清除恢复日志，形成比较稳定的tablet文件，同时数据迁移到其他机器上去）

十九.除了SSTable cache之外，bigtable的其他部分系统都被简化，事实上产生的SSTables都是“一成不变的“。例如，读取SSTables数据时，我们不需要文件系统的任何同步操作。所以row层面的并发控制，能够被高效的实现。仅有的一个可read/write的易变数据的结构就是memtable，每个memtable row使用copy-on-write方式，来支持read/write的并发处理。

    因为SSTable是不可变的，永久移除那些“被删除”数据的问题，被转换成通过垃圾回收过去的SSTable。每个tablet的SSTables信息都是在METADATA表中注册的。Master使用mark-and-sweep的gc方式删除过期的SST   able。

    最后，SSTables的不变性能够使我们更快的spit tablets。我们让每个子tablet共享父tablet的SSTables，而不是为每个子tablet生成一堆新的SSTables。

二十.随机写入和顺序写入（依据row key排序）表现的要比随即读取性能要好（吞吐量），因为每个tablet server把write操作追加到一个单一的commit log文件中，并且使用group commit这些write到GFS中。在随机写入和顺序写入之间，并没有太大的性能差距，因为它们的操作（write）终究是写入到了同一个commit log中，而且采用了相同的提交方式。

    顺序读取，要比随即读取，更加高效；因为每次读取，都将会从GFS中获取一个64KB的SSTable block（可配置尺寸），并且此block的数据被存储在block cache中，这个block cache对于顺序读取非常有用（无需再次从GFS中读取，而是直接从cache中获得即可）。

    Scans也是更加迅速，因为tablet server能够在一次client RPC中，返回一个较大数量的数据（缓存起来，模块为Scan cache），这样接下来的RPC可以使用这些数据，事实上，是减少了GFS文件检索的次数，scan可以认为是顺序的批量数据读取操作。

备注:如有错误,请多多指教;如需转发,请标记出处.谢谢.