hbase（bigtable论文解读）
2023-10-11 23:54:29 0 举报AI智能生成
bigtable论文解读
作者其他创作
大纲/内容
可靠的处理PB级别的数据
适用性广泛、可扩展、高性能和高可用性
目标
动态控制数据的分布和格式
一切存储皆是字符串
存储
简介
Bigtable是一个稀疏的、分布式的、持久化存储的多维度排序Map
Key：Map的索引是行关键字、列关键字以及时间戳；
Value：都是一个未经解析的byte数组
定义
对同一个行关键字的读或者写操作都是原子的
行关键字是任意的字符串
Bigtable通过行关键字的字典顺序来组织数据
分区（Tablet）是数据分布和负载均衡调整的最小单位
动态分区
行
列关键字组成的集合叫做“列族“，列族是访问控制的基本单位
访问控制、磁盘和内存的使用统计都是在列族层面进行的
列族的名字必须是可打印的字符串，而限定词的名字可以是任意的字符串
列族：限定词
命名
列族
表的每一个数据项都可以包含同一份数据的不同版本；不同版本的数据通过时间戳来索引
64位整型
精确到毫秒的“实时”时间
类型
配置参数对废弃版本的数据自动进行垃圾收集。
时间戳
数据模型
支持单行上的事务处理
Bigtable可以作为MapReduce框架的输入和输出
API
使用Google的分布式文件系统(GFS)存储日志文件和数据文件
SSTable是一个持久化的、排序的、不可更改的Map结构，而Map是一个key-value映射的数据结构，key和value的值都是任意的Byte串
Google SSTable格式
SSTable是一系列的数据块
二分查找
SSTable使用块索引（通常存储在SSTable的最后）来定位数据块
存储数据的文件
GFS
集群管理系统（yar）
Chubby服务包括了5个活动的副本，其中的一个副本被选为Master，并且处理请求；
只有在大多数副本都是正常运行的，并且彼此之间能够互相通信的情况下，Chubby服务才是可用的；
当有副本失效的时候，Chubby使用Paxos算法来保证副本的一致性；
Chubby提供了一个名字空间，里面包括了目录和小文件。每个目录或者文件可以当成一个锁，读写文件的操作都是原子的。
Chubby客户程序库提供对Chubby文件的一致性缓存；
Chubby客户程序与服务端维持会话。如果客户程序不能在租约到期的时间内重新签订会话的租约，这个会话就过期失效了。当一个会话失效时，它拥有的锁和打开的文件句柄都失效了。
Chubby客户程序可以在文件和目录上注册回调函数，当文件或目录改变、或者会话过期时，回调函数会通知客户程序。
原理
确保在任何给定的时间内最多只有一个活动的Master副本；
存储BigTable数据的自引导指令的位置；
查找Tablet服务器，以及在Tablet服务器失效时进行善后；
存储BigTable的模式信息（每张表的列族信息）；
存储访问控制列表。
Bigtable使用Chubby的目的
只有在大多数副本都是正常运行的，并且彼此之间能够互相通信的情况下，Chubby服务才是可用的
Chubby（高可用的、序列化的分布式锁服务组件）
依赖集群管理系统来调度任务、管理共享的机器上的资源、处理机器的故障、以及监视机器的状态。
Bigtable构件
库函数：链接到每个客户端
为Tablet服务器分配Tablets
检测新加入的或者过期失效的Tablet服务器
对Tablet服务器进行负载均衡
对保存在GFS上的文件进行垃圾收集
处理对模式的相关修改操作，例如：建立表和列族
一个主服务器
负责处理它所加载的Tablet的读写操作，以及在Tablets过大时，对其进行分割。
每个Tablet服务器都管理一个Tablet的集合（通常每个服务器有大约数十个至上千个Tablet）
许多Tablet服务器
客户端读取的数据都不经过Master服务器：客户程序直接和Tablet服务器通信进行读写操作。
由于BigTable的客户程序不必通过Master服务器来获取Tablet的位置信息，因此，大多数客户程序甚至完全不需要和Master服务器通信。在实际应用中，Master服务器的负载是很轻的。
一个BigTable集群存储了很多表，每个表包含了一个Tablet的集合，而每个Tablet包含了某个范围内的行的所有相关数据。初始状态下，一个表只有一个Tablet。随着表中数据的增长，它被自动分割成多个Tablet，缺省情况下，每个Tablet的尺寸大约是100MB到200MB。
PS
组件
使用一个三层的、类似Ｂ+树[10]的结构存储Tablet的位置信息
包含了Root Tablet的位置信息。
第一层：Chubby file
存储Tablet的所有位置信息
METADATA表中存储了二级信息，包括一个日志，它记载了和每个tablet有关的所有事件，比如，一个服务器什么时候开始提供这个tablet服务。这些信息对于性能分析和程序调试是非常有用的。
METADATA表
Root Tablet是METADATA表当中的第一个Tablet，任何情况下都不会被拆分，从而保证Tablet位置层次结构不会超过三层。
第二层：Root Tablet
行键是由Tablet所在的表的标识符和Tablet的最后一行编码而成的
行键
存储行键的Tablet的位置信息
每个METADATA表都包含了一个user tablet集合的位置信息
第三层：METADATA表的其他Tablet
结构
客户端函数库会缓存Tablet位置信息
每次读取METADATA表时，都要读取至少两条以上的Tablet位置信息。
让客户端库函数预抓取tablet位置信息，来进一步减少代价
缓存
Tablet的位置
一个Tablet只能分配给一个Tablet服务器
Master服务器记录Tablet和Tablet服务器的状态，并进行分配
Tablet服务器启动时，它在Chubby的一个指定目录下建立一个有唯一性名字的文件，并且获取该文件的独占锁
Master服务器实时监控着这个目录（服务器目录），因此Master服务器能够知道有新的Tablet服务器加入了
比如由于网络断开导致Tablet服务器和Chubby的会话丢失
如果Tablet服务器丢失了Chubby上的独占锁它就停止对Tablet提供服务
只要文件还存在，Tablet服务器就会试图重新获得对该文件的独占锁；如果文件不存在了，那么Tablet服务器就不能再提供服务了，它会自行退出
当Tablet服务器终止时，它会尝试释放它持有的文件锁，这样一来，Master服务器就能尽快把Tablet分配到其它的Tablet服务器。
使用Chubby记录Tablet服务器状态
1. Master服务器从Chubby获取一个唯一的Master锁，用来阻止创建其它的Master服务器实例；
2. Master服务器扫描Chubby的服务器文件锁存储目录，获取当前正在运行的服务器列表；
3. Master服务器和所有的正在运行的Tablet表服务器通信，获取每个Tablet服务器上Tablet的分配信息；
4. Master服务器扫描METADATA表获取所有的Tablet的集合。在扫描的过程中，当Master服务器发现了一个还没有分配的Tablet，Master服务器就将这个Tablet加入未分配的Tablet集合等待合适的时机分配。
启动步骤
在METADATA tablets被分配之前，不能扫描METADATA表
在扫描METADATA表之前，如果在步骤3的扫描中发现root tablet未分配，主服务器把root tablet增加到待分配tablet集合
扫描METADATA表
建立了一个新表或者删除了一个旧表
两个Tablet被合并了
一个Tablet被分割成两个小的Tablet
Tablet的集合变化的情况
复杂情况
Master服务器在启动步骤
1. Master服务器通过轮询Tablet服务器文件锁的状态来检测何时Tablet服务器不再为Tablet提供服务；
2.如果Master检测到Tablet服务器异常，就会尝试获取该Tablet服务器文件的独占锁；并删除该Tablet服务器在Chubby上的服务器文件以确保它不再给Tablet提供服务；
3.Master服务器就把之前分配给它的所有的Tablet放入未分配的Tablet集合中。
维护
Master维护过程
Tablet分配
持久化存储，较早的更新存放在一系列SSTable中
更新操作提交到REDO日志中
REDO日志
一个排序缓存，存储最近提交的更新
memtable
Tablet的元数据包含了组成这个Tablet的SSTable的列表，以及一系列的Redo Point，这些Redo Point指向可能含有该Tablet数据的已提交的日 志记录
1. Tablet服务器首先从METADATA表中读取它的元数据
2. Tablet服务器把SSTable的索引读进内存，之后通过重复Redo Point之后提交的更新来重建memtable。
恢复Tablet
当对Tablet服务器进行写操作时，Tablet服务器首先要检查这个操作格式是否正确、操作发起者是否有执行这个操作的权限
权限验证的方法是通过从一个Chubby文件里读取出来的具有写权限的操作者列表来进行验证
成功的修改操作会记录在提交日志里
当一个写操作提交后，写的内容插入到memtable里面
当对Tablet服务器进行读操作时，Tablet服务器会作类似的完整性和权限检查
一个有效的读操作在一个由一系列SSTable和memtable合并的视图里执行。由于SSTable和memtable是按字典排序的数据结构，因此可以高效生成合并视图
当进行Tablet的合并和分割时，正在进行的读写操作能够继续进行。
验权
Tablet服务
当memtable的尺寸到达一个门限值的时候，这个memtable就会被冻结，然后创建一个新的memtable；
被冻结住memtable会被转换成SSTable，然后写入GFS；
在Compaction过程中，正在进行的读写操作仍能继续。
过程
收缩Tablet服务器使用的内存；
在服务器灾难恢复过程中，减少必须从提交日志里读取的数据量。
目的
Minor Compaction（次压缩）
Bigtable循环扫描它所有的Tablet，并且定期对它们执行Major Compaction；
读取一些SSTable和memtable的内容，合并成一个新的SSTable；
只要Merging Compaction过程完成了，输入的这些SSTable和memtable就可以删除了；
回收已经删除的数据占有的资源，并且确保BigTable能及时清除已经删除的数据。
Minor Compaction每次创建新的Tablet，读操作需要合并多个SSTable的更新；
合并SSTable
非主压缩所产生的SSTable可以包含特殊的删除入口（entry），它把被删除的数据压缩在仍然存活的比较老的SSTable当中。
回收资源
Major Compaction（主压缩）
Compactions（压缩）
实现
列族的组合，对Tablet中的每个局部性群组都会生成一个单独的SSTable。
将通常不会一起访问的列族分割成不同的局部性群组可以提高读取操作的效率。
比如，可以把一个局部性群组设定为全部存储在内存中。
以局部性群组为单位设定一些有用的调试参数
局部性群组（Locatity groups）
客户程序可以控制一个局部性群组的SSTable是否需要压缩；如果需要压缩，那么以什么格式来压缩；
分块压缩浪费了少量空间，但只读取SSTable的一小部分数据的时候不必解压整个文件
每个SSTable的块（块的大小由局部性群组的优化参数指定）都使用用户指定的压缩格式来压缩。
第一遍采用Bentley and McIlroy’s方式[6]，这种方式在一个很大的扫描窗口里对常见的长字符串进行压缩；
第二遍是采用快速压缩算法，即在一个16KB的小扫描窗口中寻找重复数据。
常用压缩算法：“两遍”的、可定制的压缩方式。
压缩（Compression）
对于经常要重复读取相同数据的应用程序来说，扫描缓存非常有效；
一级缓存：扫描缓存，主要缓存Tablet服务器通过SSTable接口获取的Key-Value对；
对于经常要读取刚刚读过的数据附近的数据的应用程序来说，Block缓存更有用
例如，顺序读，或者在一个热点的行的局部性群组中随机读取不同的列
二级缓存：Block缓存，缓存的是从GFS读取的SSTable的Block。
Tablet服务器二级缓存的策略
通过缓存提高读操作的性能
客户程序对特定局部性群组的SSTable指定Bloom过滤器
查询一个SSTable是否包含了特定行和列的数据，减少磁盘访问次数
Bloom过滤器
若每个Tablet一个文件，会产生对GFS的大量并发写请求，会有大量的磁盘Seek操作
单个Tablet批量提交的数量较少，批量提交本应具有的优化效果会弱化
必要性
显著提高了普通操作的性能
优点
每个Tablet服务器都装载很少的几个原来的服务器的Tablet
当一个Tablet服务器宕机时，它加载的Tablet将会被移到很多其它的Tablet服务器上
当恢复一个Tablet的状态的时候，新的Tablet服务器要从原来的Tablet服务器写的日志中提取修改操作的信息，并重新执行
然而，这些Tablet修改操作的日志记录都混合在同一个日志文件中的。
问题
为了避免多次读取日志文件，我们首先把日志按照关键字（table，row name，log sequence number）排序
排序之后，对同一个Tablet的修改操作的日志记录就连续存放在了一起，因此，我们只要一次磁盘Seek操作、之后顺序读取就可以了
为了并行排序，我们先将日志分割成64MB的段，之后在不同的Tablet服务器对段进行并行排序。
这个排序工作由Master服务器来协同处理，并且在一个Tablet服务器表明自己需要从Commit日志文件恢复Tablet时开始执行。
解决方案
数据恢复复杂
缺点
写操作正在进行的时候，一个GFS服务器宕机了；
或者连接三个GFS副本所在的服务器的网络拥塞或者过载了
GFS中写Commit日志的时候可能会引起系统颠簸
每个线程都写自己的日志文件，并且在任何时刻，只有一个线程是工作的
如果一个线程的在写入的时候效率很低，Tablet服务器就切换到另外一个线程，修改操作的日志记录就写入到这个线程对应的日志文件中
每个日志记录都有一个序列号，因此，在恢复的时候，Tablet服务器能够检测出并忽略掉那些由于线程切换而导致的重复的记录
双线程单活写入日志
方案
高可用
一个Tablet服务器一个Commit日志文件，其多个Tablet，修改操作的日志以追加方式写入同一个日志文件
Commit日志的实现
Tablet迁移Tablet服务器移时，源服务器会对这个Tablet做一次Minor Compaction
这个Compaction操作减少了Tablet服务器的日志文件中没有归并的记录，从而减少了恢复的时间。Compaction完成之后，该服务器就停止为该Tablet提供服务
在卸载Tablet之前，源Tablet服务器还会再做一次（通常会很快）Minor Compaction，以消除前面在一次压缩过程中又产生的未归并的记录
第二次Minor Compaction完成以后，Tablet就可以被装载到新的Tablet服务器上了，并且不需要从日志中进行恢复。
Tablet恢复提速
当从SSTable读取数据的时候，我们不必对文件系统访问操作进行同步。这样一来，就可以非常高效的实现对行的并行操作。
memtable是唯一一个能被读和写操作同时访问的可变数据结构。为了减少在读操作时的竞争，我们对内存表采用COW(Copy-on-write)机制，这样就允许读写操作并行执行。
每个Tablet的SSTable都在METADATA表中注册了。Master服务器采用“标记-删除”的垃圾回收方式删除SSTable集合中废弃的SSTable【25】，METADATA表则保存了Root SSTable的集合。
我们可以把永久删除被标记为“删除”的数据的问题，转换成对废弃的SSTable进行垃圾收集的问题了
SSTable的不变性使得分割Tablet的操作非常快捷。我们不必为每个分割出来的Tablet建立新的SSTable集合，而是共享原来的Tablet的SSTable集合。
Bigtable中除了SSTable缓存之外的其它部分产生的SSTable都是不变的，我们可以利用这一点对系统进行简化
利用不变性
优化（Refinements）
每个随机读操作都要通过网络从GFS传输64KB的SSTable到Tablet服务器，而我们只使用其中大小是1000 byte的一个value值。Tablet服务器每秒大约执行1200次读操作，也就是每秒大约从GFS读取75MB的数据。这个传输带宽足以占满Tablet服务器的CPU时间，因为其中包括了网络协议栈的消耗、SSTable解析、以及BigTable代码执行；这个带宽也足以占满我们系统中网络的链接带宽。大多数采用这种访问模式BigTable应用程序会减小Block的大小，通常会减到8KB。
随机读的性能比其它操作慢一个数量级或以上
原因是，所有1000-byte的读操作都是从Tablet服务器的本地内存中读取数据，不需要从GFS读取64KB的Block。
内存中的随机读操作速度快很多
原因是每个Tablet服务器直接把写入操作的内容追加到一个Commit日志文件的尾部，并且采用批量提交的方式，通过把数据以流的方式写入到GFS来提高性能。随机写和序列写在性能上没有太大的差异，这两种方式的写操作实际上都是把操作内容记录到同一个Tablet服务器的Commit日志文件中。
随机和序列写操作的性能比随机读要好些
因为每取出64KB的SSTable的Block后，这些数据会缓存到Block缓存中，后续的64次读操作直接从缓存读取数据。
序列读的性能好于随机读
这是由于客户程序每一次RPC调用都会返回大量的value的数据，所以，RPC调用的消耗基本抵消了。
扫描的性能更高
单个Tablet服务器的性能
随着Tablet服务器的数量增加了500倍，内存中的随机读操作的性能增加了300倍
内存随机读
这是因为每个1000-byte的读操作都会导致一个64KB大的Block在网络上传输。这样的网络传输量消耗了我们网络中各种共享的1GB的链路，结果导致随着我们增加服务器的数量，每台服务器上的吞吐量急剧下降。
随机读的性能随Tablet服务器数量增加的提升幅度最小（整体吞吐量只提升了100倍，而服务器的数量却增加了500倍）
随机读
Tablet服务器从1台增加到500台，性能非线性挺升
这是由于多台服务器间的负载不均衡造成的，大多数情况下是由于其它的程序抢占了CPU。
一个是尽量减少Tablet的移动导致重新负载均衡能力受限（如果Tablet被移动了，那么在短时间内 — 一般是1秒内 — 这个Tablet是不可用的）
另一个是我们的基准测试程序产生的负载会有波动
负载均衡的算法问题
每台Tablet服务器性能降低
性能提升
Google Analytics
Google Earth
个性化查询
实际应用
性能评估
经验教训（Lessons）
相关工作
结论
Bigtable论文
hbase
0 条评论
回复 删除
下一页
