免费网站源码模板下载,wordpress通过微信投稿,福州快速网站建设,模板网简历2003年USENIX#xff0c;出自谷歌#xff0c;开启分布式大数据时代的三篇论文之一#xff0c;底层依赖 GFS 存储#xff0c;上层供 MapReduce 查询使用
Abstract
是一种分布式结构化数据存储管理系统#xff0c;存储量级是PB级别。存储的数据类型和延时要求差异都很大。…2003年USENIX出自谷歌开启分布式大数据时代的三篇论文之一底层依赖 GFS 存储上层供 MapReduce 查询使用
Abstract
是一种分布式结构化数据存储管理系统存储量级是PB级别。存储的数据类型和延时要求差异都很大。论文介绍数 bigtable 的数据模型。
Introduction
BigTable 达成了几个目标适用面广、伸缩性好、高性能、高可用。即可以满足吞吐导向的批处理的需求也满足延迟敏感服务的需求。很多时候 BigTable 看起来像数据库但又有不同的接口层。不支持全部关系数据模型、支持动态控制数据布局和格式。支持数据再底层存储时候的属性推断。数据用字符串作为行列名建索引。BigTable 把数据当字符串。
Data Model
BigTable 是一个稀疏、分布式、持久化、多维存储的字典(map)。map 由一个 row key、column key、timestamp 组合建索引map 的值是字节流(array of bytes)。(row:string, column:string, time:int64) → string以下是一个具体的例子 这个 Webtable 表存储了网页内容和引用该网页的网页地址。
Rows
对一个 row key 的读写都是原子的不管里面包含了多少列。这个设计使得客户端使用的时候更好做并发控制。
BigTable按照字典序存储 row key。行范围动态划分一个范围称为一个 tablet其作为分布式存储平衡的单元。这个性质帮助客户端探索数据的局部性存储得到更高的效率。比如对于 webtable 来说同一个网站的页面因为 url 的倒序排列而聚集到一起。
Column Families
column keys 聚集到 column families 里面column families 作为访问控制的基本单元。同一个 column families 的数据通常来说有相同的数据类型并且系统会把数据放一起压缩。column family 先创建再使用。系统的用意就是 column family 的数量比较少并且不经常变动。相反column 的数量不做限制。
一个 column key 的格式 family:qualifier例如对于 webtable 来说一个 column family是 language family。里面只有一个 column key存储网页的 language ID。另一个 column family 是 anchor如图一所示。
Timestamps
每个 BigTable 的单元格可以存储同一份数据的多个版本版本号就是 timestamp。并且从大到小倒序排列。为了高效管理系统支持设置保留最近几个版本或者回收多久以前的旧版本。
API
提供了基本的API来控制 BigTable比如创建表改变列访问控制等。一个简单的例子
// Open the table
Table *T OpenOrDie(/bigtable/web/webtable);
// Write a new anchor and delete an old anchor
RowMutation r1(T, com.cnn.www);
r1.Set(anchor:www.c-span.org, CNN);
r1.Delete(anchor:www.abc.com);
Operation op; // 原子的将这些改变落地
Apply(op, r1)还有一个用 Scanner 来扫描特定行列的例子
Scanner scanner(T);
ScanStream *stream;
stream scanner.FetchColumnFamily(anchor);
stream-SetReturnAllVersions();
scanner.Lookup(com.cnn.www);
for (; !stream-Done(); stream-Next()) {printf(%s %s %lld %s\n,scanner.RowName(),stream-ColumnName(),stream-MicroTimestamp(),stream-Value());
}BigTable 支持单行的事务用 read-modify-write 模式保证原子性。支持单元格计数。支持服务器上执行客户端提供的脚本脚本功能是对数据进行转化过滤统计等操作。
Building Blocks
BigTable 依赖几个谷歌内部的基础服务第一个就是GFS。
存储文件格式是 Google SSTable 文件格式。这个格式是一种持久化有序、不可变的 key - value 映射格式key 和 value 都是字符串的二进制数组形式。每一个 SSTable 包括连续的 blocks一个 block 64KB。block index 用于查找 block。当 SSTable 打开的时候block index 载入内存通过二分查找找到合适的索引。然后从磁盘读取合适的 block。此外 SSTable 还可以映射到内存中这样可以完全避免磁盘操作。
BigTable 还依赖一个高可用的分布式锁服务 Chubby。Chubby 有5个服务组成其中一个是 master用来处理请求。当超过一半副本存活的时候集群可用。Chubby 使用 Paxos 算法来保持副本间的一致性。Chubby 基本可以看作是 zookeeper 的谷歌版。客户端和 Chubby 保持session能一致性的读写小文件文件带锁Chubby 支持对保存文件注册回调函数。
BigTable 用 Chubby 有几个不同用处确保任何时刻只有最多一个 master存储 bootstrap 文件地址tablet 服务发现和死亡摘除存储表的 schema 信息(每张表的 column family)保存存储权限列表。Chubby 不可用了BigTable 也就不可用了。
5 Implementation
整体有三大组件客户端需要链接的依赖库一个 master Server一堆 tablet Servers。tablet server 可以动态加入或者移除集群。
master 的职责是分配 tablets 给 tablet servers发现并加入 tablet server删除过期的 tablet server平衡 tablet servers 之间的负载垃圾回收无效的文件表格 schema 的变化。
tablet Server 负责一系列的 tablet包括读写请求对于增长过大的 tablet 负责分裂。
client 也是直接和 tablet Server 进行读写数据通信。client 不依赖 master 获取 tablet 的定位信息绝大多数 client 不会和 master进行通讯。
一个 BigTable 集群储存多张 table每个 table 由多个 tablet 组成每个 tablet 里面存储 row range 里面的全部数据。一开始一张 table 只有一个 tablet随着 table 数据增长会自动分裂成多个 tablet每一个 tablet 大约100~200M
5.1 Tablet Location
三层结构存储 tablet 位置信息的 B 树 Chubby 里面保存 root tablet 的地址root tablet 不会分裂里面保存其他所有 MetaData 里的 tablet而MetaData 里面的 tablet 里保存 user tablet 的位置信息。
MetaData table 保存一个 row key 存储在 tablet 的位置信息这个位置信息是 tablet 对其所属 table 标识符和row key的开始行和结束行的 encoding。其中存储的是以开始和结尾的Row Key作为键tablet位置作为值的映射。每一个 MetaData row 差不多1KB通常128MB的大小的 MetaData tablet 限制三层的 location schema 能存储2^34 个 tablets。
client 会 cache tablet 的位置信息如果 cache 中没有或者不正确就递归的向上查找。这个位置信息存储在内存中客户端在读取时也会采取“预取”策略一次读取多个 tablet 位置信息。
MetaData 里面还存储一些二级信息例如事件日志用于调试。
5.2 Tablet Assignment
master 追踪所有 tablet Server一个 tablet 一个时刻也只能分配给一个 tablet Server。 当一个 tablet 没有被分配如果出现足够资源的 tablet Servermaster 就会将其分配给这个 tablet Server。
BigTable 用 Chubby 来追踪 tablet Server。当 tablet Server 启动的时候在 Chubby 的一个特定目录下申请一个排它锁一个唯一文件名的文件。master 会一直监控这个目录以感知 tablet Server 的变化。当 tablet Server 不服务的时候就会释放 Chubby 上的锁。
master 会周期性的询问 tablet Server 是否还持有 Chubby 上的锁。如果 tablet 不持有或者无法应答 master 的请求master 会尝试获取这个 tablet Server 的锁并删除这个文件对应的锁。之后 master 会标记 tablets 为不可用。当 master 和 Chubby 断链master 会自动退出并不改变 tablet 的分配。
当 master 启动时执行一下操作1获取 Chubby 上的 mater 锁确保只有一个 master2master 扫描 Chubby 上的 server 目录发现活着的 tablet Server。3和每个 tablet Server 通讯查询被分配的 tablet4扫描 MetaData 表如果遇到 tablet 没有被分配标记为未分配。后续会对未分配的 tablet 做分配。
一个复杂的情况是扫描 MetaData 表的时候MetaData tablet 本身就还未分配。因此在执行步骤4之前如果 root table 没有 分配master 把 root tablet 标记为未分配。因为 root table 包含所有 MetaData 的 tablets所以 master 扫描 root table 之后就能扫描全部的 MetaData。
一个已有的 tablet 只有创建/删除、合并、分裂的时候才会改变。当 tablet 分裂时tablet Server 往 MetaData 中记录新的 tablet之后会通知 master。
5.3 Tablet Serving
更新操作提交到 commit log 中作为重做记录redo log。整体这块的顺序是WALwrite after log。最近的一些更新提交存储在内存中有序存储这块儿叫做 memtable老一些的更新提交存储在磁盘上的 sequence SSTable 上。所以可以看出来一个 tablet 由三部分组成磁盘上的 tablet log一系列的 SSTable 文件以及内存上的 memtable。这种操作在后续的 ElasticSearch 上也有体现。
为了恢复一个 tablet Servertablet Server 会先读取其 MetaData 知道包含哪些 SSTable并且 MetaData 里有一系列的重做指针指向 commit log。tablet Server 读取 SSTable 索引并通过重做指针指向的更新提交重建 memtable。
新来一个写操作的时候先校验格式、鉴权。通过之后先写都 commit log 里。多个 commit 聚合起来写提升吞吐写完之后再把内容写入到 memtable。
读操作也是先校验鉴权然后在 memtable 和 SSTable 里面查询并将结果合并。
5.4 Compactions
随着 memtable 越来越大达到阈值之后冻结转化成 SSTable写入GFS同时创建一个新的 memtable。这个操作叫 minor compaction能较少内存使用也能较少 commit log 的大小。
minor compaction 每次都会创建一个 SSTable放任不管小文件会越来越多。因此还需要控制文件数量 BigTable 通过一个默认的线程执行 major compaction 来达成。这个操作读取新生成的小碎 SSTable然后合并写入一个新的大的 SSTable 里。
在 major compaction 会删除之前 SSTable 里面标记软删除的数据。
6 Refinements
Locality groups存储位置分组
Compression数据压缩
Caching for read performance读时缓存
Bloom filters布隆过滤器
例如5.3节里的图例表示需要读取 tablet Server 下所有的 tablet 来获取最新的数据这会有比较多的磁盘读取操作。在 tablet Server 上建立 bloom filter验真查找的 row-cloumn 对是否在某个 SSTable 上减少磁盘操作。
Speeding up tablet recovery恢复加速
master 移动一个 tablet 的时候原来的 tablet Server 对这个 tablet 先做一次 minor compaction这样能减少 commit log从而加速恢复。然后该 tablet Server 停止对这个 tablet 服务。在确保卸载完全之前还会在做一次 minor compaction彻底干掉内存里的 commit log。
Exploiting immutability不可变性
除了SSTable缓存之外Bigtable 系统的其他各个部分都被简化了因为我们生成的所有 SSTable 都是不可变的。例如当从SSTables 读取时我们不需要同步访问文件系统。因此可以非常有效地实现对行的并发控制。读写都可以访问的唯一可变数据结构是 memtable。为了减少读取 memtable 时的争用我们在写时复制每个memtable 行并允许读和写并行进行。
由于 SSTables 是不可变的永久删除已删除数据的问题转化为垃圾收集过时的 SSTables。每个 tablet Server 的 SSTable 都注册在 MetaData 中。主进程删除过时的 SSTables作为对 SSTables 集的标记和清除垃圾回收其中元数据表包含根集。
最后SSTables 的不变性使得能够快速分割 tablet。我们不为每个子 tablet 生成一组新的 SSTable而是让子 tablet 共享父tablet 的 SSTables。
9 Lessons
作者总结了大型分布式系统的一些经验
第一条经验大型分布式系统容易受到多种失败类型的困扰不仅仅是标准的网络不通故障停止(fail-stop)等。例如内存和网络崩溃、锁倾斜、机器宕机、非对称的网络分裂、依赖系统的 bug、GFS配额超限、硬件过保等等。作者通过修改协议来缓解。例如在 RPC 里面增加校验和去掉对依赖系统的一些假设。
第二大经验除非清楚新功能有什么用否则延迟增加新需求很重要。例如作者想实现【事务】的时候等实际使用了来才发现只需要实现单行级别的事务就可以了。
第三大经验系统级的监控非常重要例如监控 BigTable 本身和使用 BigTable 的客户端。例如扩展了RPC系统用于追踪系统通过RPC做的重要动作。这个特性帮助排查解决了很多问题。
最重要的经验设计简单的价值。考虑到我们系统的规模以及代码随着时间的推移以意想不到的方式演变的事实我们发现代码和设计的清晰性对代码维护和调试有着巨大的帮助。其中一个例子就是我们的tablet服务器成员协议。我们的第一个协议很简单主机定期向tablet服务器发出租约如果租约到期tablet服务器就会自杀。不幸的是这种协议在出现网络问题时会大大降低可用性而且对主恢复时间也很敏感。我们重新设计了几次协议直到我们有了一个性能良好的协议。但是生成的协议太复杂并且依赖于其他应用程序很少使用的Chubby功能的行为。 我们发现不仅在Bigtable代码中而且在Chubby代码中我们花费大量时间调试晦涩难解的案例。 最终我们放弃了该协议转而使用仅依赖于广泛使用的Chubby功能的更新的更简单协议。
参考链接 https://zhuanlan.zhihu.com/p/338566270 https://zhuanlan.zhihu.com/p/164926186 https://zhuanlan.zhihu.com/p/158607288
