从零开始写数据库（四）

实现LevelDB的日志系统

参考设计文档Log Format

前面创建了一个数据库，但是数据是存储在一个csv文件中，在实际的项目中，数据是以二进制的形式存储

我们最终的目的是写一个类似levelDB的数据库，我们先要了解下LevelDB的运作机制

在LevelDB中写入数据大概是这样几步

  1. 接收到请求Write(k, v)
  2. 把请求写入日志Op log
  3. 把数据写入MemTable
  4. 第三步完成就可以通知客户端写入成功了
  5. 当memtable的数据达到临界值的时候，转变成immutable memtable
  6. 压缩immutable memtable
  7. 写入sstable

这个信息量有点大，我们先来解释下几个名词

Op log

这个Op是对数据做改变的操作，所以Put和Delete都会写入Op log

op log文件是以块的形式存储的，每个块的大小固定为32KB,每个文件会有1个和多个块，这里我们简单点一个Block对应一个文件

具体来说，最终会在磁盘上像0.log、1.log、2.log的形式存储

Op Log的格式

1
2
3
4
5
6
7
8
9
10
11
+---------+-----------+-----------+--- ... ---+
|CRC (4B) | Size (2B) | Type (1B) | Payload   |
+---------+-----------+-----------+--- ... ---+

CRC = 32bit hash computed over the payload using CRC
Size = Length of the payload data
Type = Type of record
       (kZeroType, kFullType, kFirstType, kLastType, kMiddleType )
       The type is used to group a bunch of records together to represent
       blocks that are larger than kBlockSize
Payload = Byte stream as long as specified by the payload size

我们先生成定义日志的格式

record.go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
type Record struct {
	CRC uint32
	Size uint16
	Type uint8
	Payload []byte
}
// 新建记录，根据类型和数据
func NewRecord(typ uint8, payload []byte) Record {
	// 新建数据缓冲区，长度是type的长度加上数据的长度，type一个字节长度
	buf := bytes.NewBuffer(make([]byte, 1 + len(payload)));

	buf.WriteByte(typ)
	buf.Write(payload)

	// 计算crc32
	crc := crc32.ChecksumIEEE(buf.Bytes())

	return Record{
		crc,
		uint16(len(payload)),
		typ,
		payload,
	}
}