Google开源了一个kv存储的库leveldb,从提交的代码和contributor名单来看,毫无疑问,就是bigtable论文描述的tablet的实现。也就是我们常说的LSMTree的一个实现。 http://code.google.com/p/leveldb/
那LSMTree是什么呢?
http://www.douban.com/group/topic/19607128/
The Log-Structured Merge-Tree (LSM-Tree)
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.44.2782&;rep=rep1&type=pdf
这篇文章读起来感觉有难度,细节太多。它介绍了 LSM-Tree 这种算法思想。这种算法思想主要用于解决日志记录索引的问题。这种应用的特点是数据量大、写速率高(2000条/s),又要建立有效的索引来查找日志中的特定条目。 采用 B+ 树索引,因为数据量大,每次又是随机的写到一个 page 中,导致无法进行有效的 page 缓存,每次写基本上对应两次 I/O,因此不可行。
解决思路就是把写操作延迟和批处理化。具体的做法就是写一个条目的时候先写到内存中的数据结构中,然后批量的 merge 到磁盘中的数据结构中。但是内存中的数据结构和磁盘中的数据结构具体是怎么样的,论文中只做了简要的描述。
Cassandra 中采用类似的思想,只是采用的数据结构是 SSTable,和论文中说的不一样。 http://my.donews.com/eraera/2006/09/26/swogzstwtqdnwlfrzgsljctkjsbrtuiumxzj/
翻译:Google大表(BigTable)
大表(Bigtable):结构化数据的分布存储系统
http://labs.google.com/papers/bigtable-osdi06.pdf
{中是译者评论,程序除外}
{本文的翻译可能有不准确的地方,详细资料请参考原文.}
摘要
bigtable是设计来分布存储大规模结构化数据的,从设计上它可以扩展到上2^50字节,分布存储在几千个普通服务器上.Google的很多项目使用BT来存储数据,包括网页查询,google earth和google金融.这些应用程序对BT的要求各不相同:数据大小(从URL到网页到卫星图象)不同,反应速度不同(从后端的大批处理到实时数据服务).对于不同的要求,BT都成功的提供了灵活高效的服务.在本文中,我们将描述BT的数据模型.这个数据模型让用户动态的控制数据的分布和结构.我们还将描述BT的设计和实现.
1.介绍
在过去两年半里,我们设计,实现并部署了BT.BT是用来分布存储和管理结构化数据的.BT的设计使它能够管理2^50 bytes(petabytes)数据,并可以部署到上千台机器上.BT完成了以下目标:应用广泛,可扩展,高性能和高可用性(high availability). 包括google analytics, google finance, orkut, personalized search, writely和google earth在内的60多个项目都使用BT.这些应用对BT的要求各不相同,有的需要高吞吐量的批处理,有的需要快速反应给用户数据.它们使用的BT集群也各不相同,有的只有几台机器,有的有上千台,能够存储2^40字节(terabytes)数据.
BT在很多地方和数据库很类似:它使用了很多数据库的实现策略.并行数据库〔14〕和内存数据库〔13〕有可扩展性和高性能,但是BT的界面不同.BT不支持完全的关系数据模型;而是为客户提供了简单的数据模型,让客户来动态控制数据的分布和格式{就是只存储字串,格式由客户来解释},并允许客户推断底层存储数据的局部性{以提高访问速度}.数据下标是行和列的名字,数据本身可以是任何字串.BT的数据是字串,没有解释{类型等}.客户会在把各种结构或者半结构化的数据串行化{比如说日期串}到数据中.通过仔细选择数据表示,客户可以控制数据的局部化.最后,可以使用BT模式来控制数据是放在内存里还是在硬盘上.{就是说用模式,你可以把数据放在离应用最近的地方.毕竟程序在一个时间只用到一块数据.在体系结构里,就是:locality, locality, locality}
第二节描述数据模型细节.第三节关于客户API概述.第四节简介BT依赖的google框架.第五节描述BT的实现关键部分.第6节叙述提高BT性能的一些调整.第7节提供BT性能的数据.在第8节,我们提供BT的几个使用例子,第9节是经验教训.在第10节,我们列出相关研究.最后是我们的结论.
2.数据模型
BT是一个稀疏的,长期存储的{存在硬盘上},多维度的,排序的映射表.这张表的索引是行关键字,列关键字和时间戳.每个值是一个不解释的字符数组.{数据都是字符串,没类型,客户要解释就自力更生吧}.
(row:string, column:string,time:int64)->string {能编程序的都能读懂,不翻译了}
//彼岸翻译的第二节
我们仔细查看过好些类似bigtable的系统之后定下了这个数据模型。举一个具体例子(它促使我们做出某些设计决定), 比如我们想要存储大量网页及相关信息,以用于很多不同的项目;我们姑且叫它Webtable。在Webtable里,我们将用URL作为行关键字,用网页的某些属性作为列名,把网页内容存在contents:列中并用获取该网页的时间戳作为标识,如图一所示。

Photobucket – Video and Image Hosting
图一:一个存储Web网页的范例列表片断。行名是一个反向URL{即com.cnn.www}。contents列族{原文用 family,译为族,详见列族}存放网页内容,anchor列族存放引用该网页的锚链接文本。CNN的主页被Sports Illustrater{即所谓SI,CNN的王牌体育节目}和MY-look的主页引用,因此该行包含了名叫“anchor:cnnsi.com”和 “anchhor:my.look.ca”的列。每个锚链接只有一个版本{由时间戳标识,如t9,t8};而contents列则有三个版本,分别由时间 戳t3,t5,和t6标识。