海量数据存储之存储设计(二)

本节重点讲述数据的Durability(可靠性)，纵然CAP理论中的三个关键点(Consistent, Available, Partition-Tolerant )无法达成一致，A和P目前来看变化不太多，可能变化比较多的是在C上，将一致性模型的文章毫无疑问首推Amazon CTO：Werner Vogels的两篇文章：

• Eventually Consistent
• Eventually Consistent - Revisited

这是工业界的经验之谈：在一定程度上做一些取舍，从而使得系统整体趋近于平衡。

回到本文主题，上面所说的一致性可能更多的是分布式层面上的一致性，而在我们的系统内部，也有很多策略去保证数据的可靠性，目前存储领域比较流行的当属WAL(Write Ahead Log)预写日志，使用WAL的产品有HBase,Berkeley DB,Innodb等等。之所以使用WAL，很大的一方面原因是能够避免数据每次更改都要写硬盘(很多都是随机写)的尴尬，并且可以与数据所在的盘分开，而利用WAL日志的顺序IO达到性能上可接受的程度，下面就WAL特性做一些介绍.

更多理论知识可以见：Transaction Processing: Concepts and Techniques

 

 Write Ahead Log Format

首先介绍的是预写日志的格式，在前面的文章：HBase存储文件格式概述 一文中就曾经讲述过HBase的WAL文件格式：HLog。这里讲述一下更为小巧的Derby的WAL日志格式。流程和设计规范主要如下：

1. 在某个page可以被更新之前必须被排它锁锁住。
2. 当这个锁被持有时，更新需要被记录到日志，这个页需要通过LSN（Log Sequence Number ）将其标记为dirty。
3. 当这个页即将被持久到存储中时，所有指向这个页(LSN)的日志必须立刻forced到磁盘。
4. 一旦日志成功写入到磁盘，内存中的脏页即写入文件替换掉之前版本的页。

在当前的流程下，即使出现系统crash的情况，我们也能根据WAL进行restore。

在derby中，WAL分为两种格式：

The log file

log文件包括了记录有所有对数据库作出的改变。

它的格式就要复杂多了：

 

类型	描述
int	指向FILE_STREAM_LOG_FILE的格式ID
int	版本（obsolete log file version）--未使用
long	日志文件的编号
long	上一条日志的编号
[log record wrapper]	经过包装的一条或者多条日志
int	结束标记
[int fuzzy end]	0表示该文件还有未完成的日志

 

这里的log record wrapper实际是包装了我们的单条日志记录的一个集合：

  

类型	描述
int	长度(供正向扫描)
long	计数器
byte[]	日志记录
int	长度(供逆向扫描)

 

那么真正的日志是什么格式呢？

 

类型	描述
int	指向LOG_RECORD的格式ID
CompressedInt	Loggable Groups
TransactionId	该事物所属的ID
Loggable	操作日志

 

The log control file

log控制文件包括了一些控制信息，比如，哪个具体的日志文件记录了当前的改变，上次的checkpoint发生的日志记录的位置。

由于该文件记录的都是一些控制信息，所以格式比较简单：

 

类型	描述
int	指向FILE_STREAM_LOG_FILE的格式ID
int	版本（obsolete log file version）
long	指向上一次checkpoint的LSN
int	版本（JBMS (older name for Cloudscape/Derby) version）
int	checkpoint的间隔
long	备用
long	备用
long	备用

 

 

Transaction Commited

 一般说来事物提交时主要有三种级别的保障：

• 调用fsync强制讲数据写到磁盘，这种方式可靠性最高，但是代价也最大
• 讲数据交给操作系统缓冲区，由操作系统决定何时真正的讲数据写到物理磁盘。这种方式可靠性略次，但是对Jvm crash的情况下，仍然可以保证数据可靠。
• 直接写到内存，由后台的checkpoint或者由于自带buffer满了触发的物理持久保证。这种性能最好，但是就只能祈祷程序运行正常了。

 Recovery

 由于有了checkpoint来保证数据在某一个时间点是正常的，这样我们在异常情况发生后做恢复时，无需从头再来，只需要从上一次checkpoint之后开始就行了。对于大部分NoSQL产品来说，数据结构是基于B-tree的，那么做recovery时，实际上是要去修复这棵树。在修复的过程中是不应该对外提供服务的。

Any Other?

按照通用的日志写入方式来看，我们可以将事物系统分为两种：

• 日志与数据独立：这是大多数系统的解决方式，实现比较复杂，但是却能带来比较高的查询和更新性能。
• 日志与数据在一起：Log-structured的解决方式，这种实现简单，但是查询性能会比较受影响(文件大小)。目前Berkeley DB Je和PostgreSQL使用的这种方法，它比较适合于读较多的系统。

这里不去评价两种方案的优劣，因为毕竟适用的场景就不一样。这里重点解释一下在Log-structured的文件结构上，我们如何做WAL、Checkpoint及Recovery。

 

简单来说，我们在WAL上做了一点小小的变化，前面已经讲过，每条日志(在log-structured中，每条数据也是一条日志)都有一个唯一标识符LSN，那么我们约定，当且仅当一条数据写到文件里面以后我们才生成一个LSN，因此，在新添加一条数据的情况下，我们需要先把这条数据写到磁盘，然后通过获得到的LSN交给其父节点引用，这样，其父节点在日志当中必然要出现在该数据所在的叶节点之后，由于我们的数据本身就是一条日志，因此在事物提交时，由于transaction log需要引用被修改的数据的LSN(记录本次事物的所有操作)，因此，当事物日志写到磁盘之前，我们的数据就已经在磁盘上了。

 

那么对于recovery来说，我们需要从上一次checkpoint之后进行所有恢复操作，根据我们之前的约定，叶子节点会更靠前一点，而非叶子节点会更靠后，那么我们需要由后向前扫描，从树的上层逐级做恢复。

 

关于checkpoint，由于前面的key-value简介已经讲过了，这里简单提一点关于log-structured中的一个很重要的小技巧：由于我们的文件是只追加的，那么对于非叶子节点来说就是一个噩梦，因为它被修改的概率是叶子节点的128倍(假设非叶子节点有128个子节点)，如果对于每一次修改都写一条记录的话，数据膨胀就非常厉害了，一般来说，有几种方案可以一定程度上改变这种情况：

1.  lazy log。就是说尽量保证非叶子节点的修改都发生在内存中，这样能极大提高某一时刻对某一数据的频繁修改(如热门商品库存数据)导致的非叶子节点频繁写磁盘。
2. delta log。简单来说，就是记录增量信息，然后和前面的数据做聚合，这样能够避免对某一个节点的修改导致需要写其父节点完整的数据。

差不多了，下次打算写一点关于并发控制(不仅仅是mvcc)的原理：

毫无疑问，锁并不是解决问题的根本办法，在高并发情况下，任何一点锁都可能导致性能的急剧下降。。。

 

相关文章推荐：

海量数据存储之Key-Value存储简介

海量数据存储之存储设计(一)

海量数据存储之新存储设备性能优化

Berkeley DB Java Edition存储文件格式概述

HBase存储文件格式概述

 

评论

2 楼 红五月 2011-03-25  

1 楼 lance_123 2011-03-14  

期待MVCC的原理，锁对于分布式系统来说，其实一定程序上会影响扩展性，虽说有分布式锁，但是目前还是存在一些不足，而在高访问高吞吐量的互联网，MVCC其实是一种满足业务且利于分布式扩展的办法。