大数据那些事(11):复活的LSM-Tree--BigTable的\b系统实现(修)

修正一些小错误。

BigTable是一个非常复杂的系统,发表的论文面面俱到,但是每个方面都写得并不是很清楚。所幸Google开源了LevelDB这个Key-Value Store。这个项目的作者是Jeff Dean和Sanjay Ghemawat,被认为很大程度上重复使用了BigTable在单个节点上的实现。LevelDB为我们对BigTable的实现提供了重要的学习资料。

在BigTable的实现上,一个BigTable的cluster由一个client library,一个Master server和很多个的Tablet Server组成。按照论文的说法,一个大的BigTable会被分成若干个大小大致在100MB到200MB的tablets,而这些tablets 会被分配到一些Tablet Server上去给client 提供服务来。Tablet Server对超过200MB的tablet灰进行切分,对小于100MB的则会进行合并。

系统运行过程中的Tablet server的数量不是固定的,可以根据实际上的工作负载来增加或者减少,这方面的工作是Master server来控制的。Tablet server并不存储实际的文件,而是作为一种service和proxy来访问存在Google File System里的实际的tablet们。

和Tablet server不一样的是,Master Server始终都存在。Master server存在主要是把tablet分配给Tablet server,增加或者减少Tablet Server,并且负责去平衡不同的Tablet server的load。如果用户要创建一个新的Table,或者对已经有的Table做改动的话,譬如增加新的column family等,都是通过Master server来完成的。Master server通过Tablet server来实现对tablet的间接操作,本身并不负责对任何Tablet 的管理。

和大家直观上想象的不同,当一个client要访问BigTable的时候,client并不需要和Master server进行交流。这就保证了Master server的load并不是很重。那么,client是怎么样实现对BigTable的访问的呢? 这是BigTable比较精密的difference。这需要用到Chubby。

Chubby是一个highly distributed lock service。可以认为开源Zookeeper是一个Chubby的copycat。但是虽然说是CopyCat,实际上Chubby实现的是一个Paxos协议,而Zookeeper实现的是它的变种Zab。这方面我们不展开细讲。 具体的情况请阅读 The Chubby lock service for loosely-coupled distributed systems。

Chubby实现的是一个类似文件系统那样的目录结构。使用者可以访问这些文件来获得对被访问对象的锁。按照BigTable论文的说法,Chubby的用处有很多处,包括对Tablet的定位,对Tablet server的监控等等。

对我们来说最重要的是了解client怎么样对数据进行操作。这个操作首先要对Metadata进行访问。这个操作大致上是要通过访问一个三层的结构,其中第一层是一个Chubby file。通过Chubby file可以找到一个叫做Root Tablet的位置,Root Tablet下一层则是所有的metadata tablets。有一点非常的特别,Root Tablet从来不会被partition。所以一般来说client需要通过访问一个Chubby文件,一个Root Tablet和一个Metadata Tablet的三层结构去定位到对应的data。Client 会cache住它找到的metadata,但是cache并非必须。只要Chubby service是活着的,通过这个三层访问总是可以定位到对应的data的tablet的。通过Chubby,Master不需要承担任何datat活着metadata的发现。故而Master server的负担很轻。

论文没有谈及metadata的格式到底是什么,最详细描述基于下面的论文原话: The Meadata Table store是跳河locationof啊tablet under a row key that is en encoding of the tablet's table identifier and its end row. 但是其实不重要,聪明的engineer总是可以设计出自己的metadata的,比如说HBase就实现了自己的一套metadata。我想这个实现和BigTable应该很不一样。

在BigTable里, SSTable(Sorted Strings Table)是一个基本的单元。每个Tablet有若干个SSTable。论文里面并没有提到SSTable是怎么样实现的。但是根据对开源的LevelDB的学习,我们可以大致上可以描述一下SSTable是怎么实现的。这个实现复活了1993年由UMass Boston退休教授 Patrick O'Neil实现的LSM-Tree。我们把相关的论文放在下面供大家参考:

Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth (Betty) O'Neil, "The Log-Structured Merge-Tree," patent granted to Digital Equipment Corporation, December 1993; appeared in ActaInformatica 33, pp. 351-385, June 1996.

看起来这个tree是申请了专利的,专利授权给了已经挂掉的DEC公司。不知道Google用这个Tree是不是侵权,也不知道目前用了LevelDB的,以及Facebook克隆LevelDB做出来的RocketDB的各大公司们有没有获得专利公司的授权。还是说因为年代太久远而DEC公司已经挂掉了无数年了,大家可以肆无忌惮的用了呢?

整个SSTable的实现分为memTable和磁盘上的SSTable。在内存里使用的是skip-list。所以写的操作只是写内存,非常的快。而内存写满之后就会把这个memTable变成一个immutable的memTable。同时开一个新的可以写的memTable另外一个线程则会把这个immutable的内存表变成一个磁盘上的SSTable。当这个转变完成以后immutable的内存表被释放。如此往复磁盘上会产生很多的SSTable。这就需要compact。SSTable是有level1, level2,。。。的。其中进到level1的compact叫做minor compact。后面还有major compact。从level2开始以后任意两棵树的key之间不会有overlap,但是在level1这并不guarantee。

所以我们的一个读操作要读memTable,immutable memTable,level1的tree,和level2以及以下的level的1棵树。这说明读的操作相对写的操作会更贵一些。大家需要注意的是,如果我们访问的是最新的版本,那么有可能会在内存里,所以这个设计对于读的操作主要是优化了新版本的读。对于cool data的读则要慢很多。顺便补充一句,Facebook的copycat RocksDB和LevelDB最主要的区别据说是引入了一个叫做universal compact的东西。当然我没有研究过这个codebase,不清楚universal compact到底有多牛。

当然,就像任何一个类似的系统一样,BigTable的recovery基于log,所有的写操作进内存之前写进log。LevelDB的log format并不是太难懂,是经典的append only的操作。基于log的读写恢复是任何一个系统的基础了。我就不再展开叙述。

说起来非常的有意思,这个LSM-Tree是一个挺了不起的发明,但是波澜不兴的在Industry很多年。发明者Patrick O'Neil在DB界固然是混一个教授到退休,但是也没有获得和他发明相匹配的知名度。也不知道Google的员工们是怎么样从一本并不怎么知名的杂志里把这个东西给挖出来,复活了。有时候我在想,倘若当年没有成名可以理解,现在已经成为了BigTable的基础了,那么作为database research community是不是应该recognize一下。实际上当然是没有。出乎我意料之外的是今年2016的VLDB我居然在印度遇到了Patrick的PhD,实在无法想象这么老了还在带学生。Database community有一些时候对某些人的recognition可能确实是差了一些。比如说Peter Chen,这位在MIT没有拿到tenure在路易斯安那州立大学安家的人,发明了E-R model,为database的发扬光大做出了巨大的贡献。但是我觉得整个community对他的recognition非常的有限。比如说Goetz Graefe,这个在query optimization和query execution做出过巨大贡献的人,发明了Volcano optimizer和经典的Volcano execution model,包括今天大行其道的Exchange operator,居然到今天也没有获得 Sigmod Edgar Codd Innovations Award,我实在是不能理解。

原文发布于微信公众号 - 飞总聊IT(feiitworld)

原文发表时间:2016-11-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏无原型不设计

优秀原型设计欣赏:美食类App原型制作-Kitchen Stories

题材有Mockplus(摹客)团队提供,仅供参考学习。

22370
来自专栏企鹅号快讯

宇宙神器:微信“活字转换”

一直想将笔耕时代发表的作品,输入电脑存word文档,以便修改和使用。由于作品较多且忙于写作加上惰性,使用电脑20年,始终未能如愿。平时看到心仪的好文字,短些的记...

37690
来自专栏知晓程序

海量高清二次元壁纸!快来把老婆抱回家吧

今天,知晓程序(微信号 zxcx0101)要给广大动漫迷们,推荐一款名叫「Soda 壁纸」小程序,导航用的是颜文字,图库里全是高清壁纸,十分带感。

10320
来自专栏牛客网

19届前端实习生面经

17500
来自专栏IT派

关于微信和Python的点点滴滴

微信自上线以来,一直没有自动回复的功能,想必是有他们的理念。但是有些人群,确实对此功能有一定需求,我举两个栗子:

11100
来自专栏知晓程序

举报!这里有人,在光天化日之下聚众撸猫

但并不是每个人都有机会成为「猫奴」。这时候,你需要 「吸猫君」 ,来帮你开启「云吸猫」的生活。

9320
来自专栏程序人生

10分钟:教你学会做出能击败80%人的公众号语音

微信前些日子开放了语音功能,想必很多人都在尝试这个功能。录音是件费时费力的事情,咱都不是专业主播,没法子一气呵成。一大段内容,想到哪说到哪,录遭了怎么办?如何编...

40280
来自专栏coding

AOC显示器提示OSD锁定怎么办?

macpro虽好,但屏幕实在太小了,而且原生的键盘敲起来很费劲,还是用机械键盘噼里啪啦敲打显得爽快。于是,给macpro外接了键鼠以及27寸的AOC显示器。

2.3K40
来自专栏嵌入式程序猿

博世小功率变频器拆解

变频器在工业生产中应用非常的广泛,橡胶行业的轮胎产线就有很多,而且轮胎产线环境恶劣,灰尘大,今天帮朋友修理一台力士乐的变频器,因为长期使用加上环境恶劣,变频器里...

50220
来自专栏信安之路

CTF初识与深入

这段时间一直在忙活CTF相关的东西,从参赛者到出题人,刷过一些题,也初步了解了出题人的逻辑;这篇文章就简单地讲一下CTF如何入门以及如何深入的学习、利用CTF这...

19700

扫码关注云+社区

领取腾讯云代金券