Google BigTable: 数据库实现的典范

 Google BigTable论文刚出来的时候匆匆读过，没什么感想，只记得是一个分布式多维映射表。今天重读一遍论文，再对照数据库里的相关技术，感觉有点意思了。一般来说，数据库的技术专家大多数时间都在研究一些具体的算法等问题，对一个数据库系统（或一个数据存储系统）从总体上如何实现的问题却不太做考虑，这方面的学术资料也就比较少。

当要开发一个新的数据库系统或数据存储系统时，最难决定的就是各种技术应该如何选择的问题。比如，应该使用面向属性还是面向记录的存储模型、应该使用基于锁还是多版本的并发控制、应该对数据进行本地更新还是将修改记录在别处、如何进行数据分区、如何做索引、需要提供什么样的并发控制和事务功能等等。每个地方都有很多选择，即使你知道这些选择是如何实现的，各种选择有什么优缺点，你还是很难选择。但今天看了BigTable的论文后发现BigTable实在算得上是数据库实现的典范，BigTable中采用的所有技术都来自于数据库领域的已有研究成果，但BigTable最成功的是很多技术的选择、取舍都恰到好处。

BigTable中最重要的选择是将数据存储分为两部分，主体部分是不可变的，以SSTable的格式存储在GFS中，最近的更新则存储在内存（称为memtable）中。读操作需要根据SSTable和memtable还综合决定要读取的数据的值。这一技术在数据库系统中不太常用，但其实也有很多研究。最早的应该是LSM Tree，这一索引结构会在内存中缓存对传统B+树索引的更新，隔一段时间后再将内存中的更新合并后主索引中去，在合并的时候就可以对键值进行排序，这样就将对索引的随机更新转换为顺序更新，提高了性能。Stonebraker设计的C-Store系统也采用这一架构。这一技术的使用案例还有很多，比如MySQL的InnoDB存储引擎中insert buffer，MySQL新的事务型存储引擎Falcon（只缓存记录更新，不缓存索引更新）。新的SSD硬盘的顺序写性能很高，但随机写性能很差，因此SSD更新时也不会更新原数据，而是将新数据顺序写在一块集中的位置，这就是来自于数据库System R中的影子页技术。使用不可变的存储的好处是多方面的，可以使用非常激进的压缩算法，可以不需要考虑并发控制的问题。假如BigTable不采用这一选择，整个系统的设计都会完全不同，而且实现将会严重复杂化。

第二个重要的决定是不支持事务，只保证对单条记录的原子性。事务是好东西，但事务也是导致数据库实现复杂化、性能下降最主要的根源。BigTable的开发者通过调研后发现其实大家对事务都没什么需求，只要保证对单条记录的更新是原子的就可以了。这样，为了支持事务所要考虑的串行化、事务的回滚等、死锁检测（一般认为，分布式环境中的死锁检测是不可能的，一般都用超时解决）等等复杂问题都不见了。系统实现进一步简化。

除了这两大选择，BigTable里用到的数据库技术还有非常多，这些技术都不是BigTable的开发者发明的，但都被它们非常好的进行了整合，最终产生一个架构简洁、模型明晰、易于实现、易于使用、可伸缩性和稳定性优秀的系统。这些技术如：
1. Locality groups: 指定将一组属性存储在单独的SSTable中，这是数据库中垂直分区技术的直接应用；
2. Tablet的分割与定位: 用数据库的术语来说就是水平分区，使用Global index；
3. 布隆过滤器(Bloom filter): 一种不精确的索引，可以判定一个键值是否不存在，布隆过滤器可能会说一个本来不存在的键值存在，但决不会说一个本来存在的值不存在。BigTable主要的瓶颈是从GFS中读取的数据量，用这个过滤器处理处理就够了，不需要建精确的索引，这样索引占用的空间也会非常小。

总之，BigTable的论文值得仔细阅读。

最后再说一点，BigTable的设计决定了它处理随机读取小型记录的性能是比较差的，这是因为要读的数据再少，也要从GFS中传输一个至少8K的块。需要可以在客户端做一些缓存，但除非数据访问热点非常明显，这些缓存估计没太大用处，因为一般来说客户端的缓存容量比起总的数据量来说实在是太小了。