若谷学院
互联网公司技术架构分享

海量存储系列之九

http://rdc.taobao.com/team/jm/archives/1390 上一篇

终于来到了COLA树系,这套东西目前来看呢,确实不如LSM火,不过作为可选方案,也是个值得了解的尝试,不过这块因为只有一组MIT的人搞了个东西出来,所以其实真正的方案也语焉不详的。从性能来说,tokuDB的写入性能很高,但更新似乎不是很给力,查询较好,占用较少的内存。

http://www.mysqlperformanceblog.com/2009/04/28/detailed-review-of-tokutek-storage-engine/

这里有一些性能上的指标和分析性文字。确实看起来很心动,不过这东西只适合磁盘结构,到了SSD似乎就挂了。原因不详,因为没有实际的看过他们的代码,所以一切都是推测,如果有问题,请告知我。

先说原理,上ppt http://tokutek.com/presentations/bender-Scalperf-9-09.pdf,简单来说,就是一帮MIT的小子们,分析了一下为什么磁盘写性能这么慢,读的性能也这么慢,然后一拍脑袋,说:“哎呀,我知道了,对于两级的存储(比如磁盘对应内存,或内存对于缓存,有两个属性是会对整个查询和写入造成影响的,一个是容量空间小但速度更快的存储的size,另外一个则是一次传输的block的size.而我们要做的事情,就是尽可能让每次的操作传输尽可能少的数据块。

传输的越少,那么查询的性能就越好。

进而,有人提出了更多种的解决方案。

•B-tree [Bayer, McCreight 72]

• cache-oblivious B-tree [Bender, Demaine, Farach-Colton 00]

• buffer tree [Arge 95]

• buffered-repositorytree[Buchsbaum,Goldwasser,Venkatasubramanian,Westbrook 00]

• Bε

tree[Brodal, Fagerberg 03]

• log-structured merge tree [O’Neil, Cheng, Gawlick, O’Neil 96]

• string B-tree [Ferragina, Grossi 99]

这些结构都是用于解决这样一个问题,在磁盘上能够创建动态的有序查询结构。

在今天,主要想介绍的就是COLA,所谓cache-oblivious 就是说,他不需要知道具体的内存大小和一个块的大小,或者说,无论内存多大,块有多大,都可以使用同一套逻辑进行处理,这无疑是具有优势的,因为内存大小虽然可以知道,但内存是随时可能被临时的占用去做其他事情的,这时候,CO就非常有用了。

其他我就不多说了,看一下细节吧~再说这个我自己都快绕进去了。

众所周知的,磁盘需要的是顺序写入,下一个问题就是,怎么能够保证数据的顺序写。

我们假定有这样一个空的数据集合

可以认为树的高度是log2N。

每行要么就是空的,要么就是满的,每行数据都是排序后的数据。

如果再写一个值的时候,会写在第一行,比如写了3。

再写一个值11的时候,因为第一行已经写满了,所以将3取出来,和11做排序,尝试写第二行。又因为第二行也满了,所以将第二行的5和10也取出,对3,11,5,10 进行排序。写入第四行

这就是COLA的写入过程。

可以很清楚的看出,COLA的核心其实和LSM类似,每次“将数据从上一层取出,与外部数据进行归并排序后写入新的array”的这个操作,对sas磁盘非常友好。因此,写入性能就会有非常大的提升。

并且因为数据结构简单,没有维持太多额外的指针,所以相对的比较节省空间。

但这样查询会需要针对每个array都进行一次二分查找。

性能似乎还不是很高,所以,他们想到了下面这种方式,把它的命名为fractal tree,分形树。

用更简单的方法来说的话呢,就是在merge的时候,上层持有下层数据的一个额外的指针。

来协助进行二分查找。

这样,利用空间换时间,他的查询速度就又回到了log2N这个级别了。

到此,又一个有序结构被我囫囵吞枣了。

嘿嘿

在下一篇,我们将进入大家期待的分布式k-V场景,也就是noSQL的范畴了,让我们拨开nosql的神秘面纱,看看这东西到底意味着什么。

http://rdc.taobao.com/team/jm/archives/1411 下一篇

原文出自:

好烂呀没啥价值凑合看看还不错很精彩 (还没有人评分)
Loading...
本站文章来自互联网一线技术博客,若有侵权,请联系我们:若谷技术学院 » 海量存储系列之九
关注若谷技术,获得个性化即时架构文章推送

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

全球互联网技术架构,前沿架构参考

联系我们博客/网站内容提交