Massive-Data-Process-Homework-3

Key-Value对存储

在BigTable系统中,如果有一个TabletServer出现了错误,不能继续进行工作,这样对应的Tablet将不能够提供服务。在系统中,数据表格中的数据形式就是URLContent的Key-Value对的形式。

  1. 磁盘中的元数据表中包含的内容,内存中的元数据表中包含的内容?(只需要描述必要的数据结构帮助恢复过程即可)
  2. 简要描述系统恢复的流程。

磁盘中的元数据表中包含的内容,内存中的元数据表中包含的内容?(只需要描述必要的数据结构帮助恢复过程即可)

  1. 磁盘中的元数据表包含的内容

Tablet的位置信息及数据范围,数据片的所有事件的日志信息,SSTable文件列表信息,Redo Point

其数据结构:

encoding(table_id + end_row_key): tablet_location(SSTable file list), log

  1. 内存中的元数据表包含的内容:

内存中的元数据表是已经分配给对应tablet server 管理的Tablet位置信息,因此其value为:ip:port,即保存的Tablet的服务器的进程位置。

简要描述系统恢复的流程。

BigTable 使用 Chubby 跟踪记录 Tablet 服务器的状态。当一个 Tablet 服务器启动时,它在 Chubby 的一个指定目录下建立一个有唯一性名字的文件,并且获取该文件的独占锁。

Master 服务器实时监控着这个目录(服务器目录),Master 服务器通过轮询 Tablet 服务器文件锁的状态来检测何时 Tablet 服务器不再为 Tablet 提供服务。当Tablet Server宕机之后,Master尝试与之通信多次得不到响应,Master 服务器就会尝试获取该 Tablet 服务器文件的独占锁;如果 Master 服务器成功获取了独占锁,则Master服务器判断该Tablet Server宕机了,于是Master服务器删除该tablet server在chubby中的服务器文件,然后Master将该Tablet Server 管理的所有数据片置为未分配状态。

随后,该宕机的Tablet Server管理的Tablet将被分散到多个Server上,每个服务器只会加载该服务器上很少量的数据片,这些server为了恢复原来tablet server上的修改,需要从commit log文件中读取log信息。在BigTable中,每个数据片服务器记录一个commit-log文件,在恢复时,这些服务器先向Master发出请求表明自己需要从该数据片服务器的提交日志文件中恢复数据片的修改操作时,Master首先将该提交日志文件按照关键字<表、行名、日志序列号>的顺序,对提交日志的条目进行排序。在排序输出中,某个特定数据片的所有修改操作信息都会连续存放在一起。因此,只需要一次磁盘寻道,然后再执行一次连续的读取操作,就可以读取日志文件并将不同的数据片的提交日志分发给对应的新分配数据片服务器,新分配的数据片服务器收到提交日志时redo该日志恢复数据片信息,至此,这些数据片可以开始提供服务了。

在DHT上实现Query

如果直接使用dht来实现key到host的对应,难点在于实现一个range query。一个range query可能需要涉及到所有的节点。有没有办法能够在仍然使用dht的情况下减少所涉及到的节点的数目?

算法基于如下hash实现;

  • 假定hash(key)均匀的分布在一个环上
  • 所有的节点也都分布在同一环上(节点加入时通过随机数的方式确定其位置)
  • 每个节点只负责一部分Key,当节点加入、退出时只影响加入退出的节点和其邻居节点或者其他节点只有少量的Key受影响

为了优化range query, 使用order-preserving hash function(保序散列函数)实现对key的hash, 这样某一个范围的(key, value)对会集中分布在相邻几个节点中,这样range query 时只需要访问这部分相邻节点即可。但是这有可能会导致负载不均衡。

每一个节点加入时需要为其构建Route Table

参考:

打赏