５．实现
ＢＴ 的实现有三个主要组件：客户程序库，一个主服务器和多个子表服务器．针对负载的变化，可以动态的从服务器群中添加（或者去除）子表服务器．主服务器的任务 是：给子表服务器指定子表，检测加入或者失效的子表服务器，子表服务器负载均衡，以及对google文件系统的文件进行垃圾收集．除此之外，它还处理诸如 建立表和列族之类的表模式改变工作．
每个子表服务器管理一个子表集合（通常每个服务器处理数十乃至上千个子表）．子表服务器负责处理对它管理的子表进行的读写操作，当子表变的太大时， 服务器会将子表分割．和很多单个主服务器分布式系统［17.21］一样，客户数据不经过主服务器．客户的读写操作是通过直接和子表服务器通信完成的．由于 ＢＴ的客户不必通过主服务器获取子表位置信息，大多数客户完全不和主服务器通信．因此，实际使用中主服务器的负载很轻．
一个ＢＴ集群存储多个表．每个表由一些子表组成，每个子表包含一个行域内的所有数据．在起始状态下，一个表只有一个子表．当一个表长大以后，它自动的分割成多个子表，每个子表的缺省大小是100到200MB.
5.1 子表的地址
子表地址信息是存储在一个三层类似Ｂ＋树[10]的结构中的(图4)．
图4:子表地址结构
第一层是Chubby中的一个文件，它存储根子表的地址．根子表里存储一个特殊的表里的所有子表的地址，地址这个特殊的表是元数据表．每个元数据子 表里存储一组用户子表的地址．根子表其实是元数据表里的第一个子表，但是对它的处理比较特殊：根子表永远不会被分割，这样一来保证了子表地址结构不会超过 三层．
元数据表里面，每个子表的地址都对应一个行关键字，这个关键字是由子表所在的表的标识符，和子表的最后一行编码而成的．每个元数据行在内存里存储大 约1kb的数据．元数据子表的大小限制是128MB，限制看似不大,不过已经可以让这个三层的地址树足够表示2^34个子表了（如果每个子表存储 128MB数据，一共是2^61字节数据）．
客户程序库缓存了子表地址．如果客户没有一个子表的地址，或者它发现地址不正确，客户就递归的查询子表地址树．如果缓存是空的，那么寻址算法需要三 次网络来回通信来寻址，其中包括一次Chubby读操作．如果缓存数据过期，那么寻址算法可能最多需要６次网络来回通信才能更新数据，因为只有在缓存不命 中的时候才能发现数据过期｛三次通信发现过期，另外三次更新数据｝（这里的假定是，元数据子表没有频繁的移动）．子表的地址是放在内存里的，所以不必访问google文件系统ＧＦＳ，我们通过预取子表地址来进一步的减少了访问开销｛体系结构里的老花招：缓存，预取｝：每次读取子表的元数据的时候，都读取几个子表的元数据｛为什么不说预取几个子表地址？俩？四个？这里就是有价值的东西了，需要时间去积累经验｝．
在元数据表中还存储了次要信息，包括每个子表的事件日志（例如，什么时候一个服务器开始服务该子表）．这些信息有助于排错和性能分析｛一笔代过重要信息，比如都存了什么事件，事件属性是什么等｝．
5.2子表分配
在任一时刻，一个子表只会分配给一个子表服务器．主服务器知道当前有哪些活跃的子表服务器，还知道哪些子表分配到哪些子表服务器，哪些以及哪些子表 没有被分配．当一个子表没有被分配到服务器，同时又有一个服务器的空闲空间足够装载该子表，主服务器就给这个子表服务器材发送一个装载请求，把子表分配给 这个服务器．
｛这里是协议描述｝ＢＴ使用Chubby来追踪子表服务器．当一个子表服务器启动时，它在一个特定的Chubby目录里建立一个有唯一名字的文件，并获取该文件的独占的锁．主服务器监视这个目录{服务器目录}，就可以发现新的子表服务器．一个子表服务器如果丧失了对文件的锁，就停止对它的子表们的服务．服务器可能丧失锁的原因很多，例如：网络断开导致服务器丢失了Chubby会话?hubby提供一种有效的服务，使子表服务器不必通过网络就能查询它是否还拥有文件锁｛这个比较神，难道是tablet server自己只查本地文件，chubby server来帮它在本地建立文件？要认真看看chubby的协议才知道｝）． 如果文件依然存在，子表服务器会试图重新获得对文件的独占锁．如果文件不存在了，那么子表服务器就不能服务了，它就退出．当子表服务器终止时（例如，集群 管理系统将子表服务器的机器从集群中移除），它会试图释放文件锁，这样一来主服务器就能更快的把子表分配给其他服务器．
当一个子表服务器不再服务它的子表的时候，主服务器有责任发现问题，并把子表尽快重新分配．主服务器发现问题的方法是定期询问子表服务器的文件锁状 态．如果一个子表服务器报告丢失了文件锁，或者过去几次询问都没有反应，主服务器就会试图获取子表服务器的文件锁．如果主服务器能够获取锁，说明 Chubby是好的，子表服务器或者是死了，或者不能和Chubby通信，主服务器就删除子表服务器的文件，以确保子表服务器不再服务子表．一旦一个服务 器的文件被删除，主服务器就可以把它的子表都放入未分配的子表集合中．为了保证在主服务器和Chubby之间有网络故障的时候ＢＴ仍然可以使用，主服务器 的Chubby会话一旦过期，主服务器就退出．但是，如前所述，主服务器故障不影响子表到子表服务器的分配．
当一个集群管理系统启动一个主服务器时，它需要发现当前的子表分配状态，然后才能修改分配状态｛设计思想：永远考虑失效＋恢复｝．主服务器执行以下启动步骤：(１)主服务器在Chubby中获取唯一的主文件锁，来阻止其他主服务器实例｛singlton｝．(2)主服务器材扫描Chubby服务器目录,获取当前活跃服务器列表.(3)主服务器和活跃子表服务器通信，获取子表分配状态｛注意子表分配不是主服务器存储的，保证了失效时主服务器不会成为性能瓶颈｝．（４）主服务器扫描元数据表，每次遇到一个没有分配的子表，就加入未分配子表集合，这个子表就可以被分配了．
这里有一个复杂的情况：在元数据表没有被分配之前，是不能扫描元数据表的｛鸡和蛋｝．因此，在开始第四步的扫描之前，如果第三步的扫描没有发现根子表没分配，主服务器就把根子表加入未分配的子表集合．这一附加步骤保证了根子表肯定会被分配．由于根子表包括了所有元数据子表的名字，主服务器在扫描过根子表以后，就知道了所有的元数据子表．
现存子表集合仅在以下事件中才会改变：一个子表被建立或者删除，两个子表被合并，或者一个子表被分割成两个．主服务器可以监控所有这些事件，因为前 三个事件都是主服务器启动的．最后一个事件：分割子表，是由子表服务器启动的．这个事件是特别处理的．子表服务器在分割完毕时，在元数据表中记录新的子表 的信息．当分割完成时，子表服务器通知主服务器．如果分割的通知没有到达（两个服务器中间死了一个），主服务器在请求子表服务器装载已经分割的子表的时 候，就会发现这个没有通知的分割操作｛设计的时候一定要考虑到错误和失败的恢复．古人云，未思进,先思退｝．子表服务器就会重新通知主服务器，因为在元数据表中找到的子表入口只包含要求装载的子表的部分信息｛细节，细节呢？｝．
//今天比较忙,只有这些了.抱歉.
//更新:彼岸翻译了第5章的剩余部分,贴在这里:
5.3 子表服务
子表的状态存放在GFS里，如图5所示。更新内容提交到存放redo记录的提交日志里｛比较绕，看原文可能清楚点｝。在这些更新中，最近提交的那些存放在内存里一个叫memtable的有序缓冲里；老一点的更新则存放在一系列SSTable里。若要恢复一个子表，子表服务器从METADATA表中读取元数据。元数据包括了由一个子表和一系列redo点｛redo怎么翻好？｝组成的SSTable列表，这些是指向可能含有该子表数据的提交日志的指针｛烦死定语从句了｝。 该服务器把这些SSTable的索引读进内存，并通过重复redo点之后提交的更新来重建memtable。
当一个写操作到达子表服务器时，该服务器检查确信这个操作完整无误，而且发送方有权执行所描述的变换。授权是通过从一个Chubby文件里读取具有 写权限的操作者列表来进行的（几乎一定会存放在Chubby客户缓存里）。合法的变换会写到提交日志里。可以用成组提交来提高大量小变换的吞吐量 ［13，16］。写操作提交后，写的内容就插入到memtable里。
当一个读操作到达子表服务器时，会作类似的完整性和授权检查。合法的读操作在一个由SSTable系列和memtable合并的视图里执行。由于SSTable和memtable是字典序的数据结构，合并视图可以很有效地形成。
进来方向的｛incoming｝读写操作在子表分拆和合并时仍能继续。
5.4 紧缩｛compaction｝
在执行写操作时，memtable的大小不断增加。当memtable大小达到一定阈值时，memtable就会被冻结，然后创建一个新的memtable，冻结住的memtable则被转换成SSTable并写到GFS里。这种次要紧缩过程有两个目的：缩小了子表服务器的内存用度，以及减少了在服务器当机后恢复过程中必须从提交日志里读取的数据量。 进来方向的读写操作在紧缩进行当中仍能继续。
每一个次要紧缩会创建一个新的SSTable。如果这种行为一直继续没有停止的迹象，读操作可能需要合并来自任意多SSTable的更新。相反，我们通过定期在后台执行合并紧缩来限定这类文件的数量。合并紧缩读取一些SSTable和memtable的内容，并写成一个新的SSTable。一旦紧缩完成，作为输入的这些个SSTable和memtable就可以扔掉了。
把所有SSTable重写成唯一一个SSTable的合并紧缩叫作主要紧缩。 由非主要紧缩产生的SSTable可以含有特殊的删除条目，它们使得老一点但仍活跃的SSTable中已删除的数据不再出现。而主要紧缩则产生不包含删除 信息或删除数据的SSTable。Bigtable在它所有的子表中循环，并且定期对它们执行主要紧缩。这些主要紧缩使得Bigtable可以回收已删除 数据占有的资源，并且还能保证已删除数据及时从系统里小时，这对存放敏感数据的服务很重要。