RDB parse

1 RDB 文件的结构和编码方式

1.1 RDB 文件的整体结构

RDB 文件划分为文件头、元属性区、数据区、结尾四个部分:

• 文件头包含 Magic Number 和版本号两部分

  • RDB文件以 ASCII 编码的 'REDIS' 开头作为魔数（File Magic Number）表示自身的文件类型

  • 接下来的 4 个字节表示 RDB 文件的版本号，RDB 文件的版本历史可以参考：RDB_Version_History

• 元属性区保存诸如文件创建时间、创建它的 Redis 实例的版本号、文件中键的个数等信息

• 数据区按照数据库来组织，开头为当前数据库的编号和数据库中的键个数，随后是数据库中各键值对。

查看 RDB 文件内容

• (1) xxd 命令，如：xxd dump.rdb

• (2) vim 打开然后在命令模式中输入：:%!xxd 开启二进制编辑

xxd 使用十六进制展示，两个十六进制数为一个字节，两个字节显示为一列

1.2 文件头

$ xxd bin/data/dump.rdb  | head -n 1
00000000: 5245 4449 5330 3030 36fe 0002 3772 6564  REDIS0006...7red

1.2.1 代码

package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"path/filepath"
)

func main() {
	path := "./bin/data/dump.rdb"
	absolutePath, _ := filepath.Abs(path)

	fp, _ := os.OpenFile(absolutePath, os.O_RDONLY, 0666)
	rd := bufio.NewReader(fp)

	buf := make([]byte, 9)
	_, _ = io.ReadFull(rd, buf)

	// [82 69 68 73 83 48 48 48 54]
	fmt.Println(buf)
	// [82 69 68 73 83]
	fmt.Println([]byte("REDIS"))
}

1.2.2 RDB 版本

>>> chr(48)
'0'
>>> chr(54)
'6'
>>>

故 48 48 48 54，就是版本 6

1.3 元属性区

1.3.1 RDB content

RDB_OPCODE_AUX(0xfa) <key.len> [key.data] <val.len> [val.data]

1.3.2 code

key := structure.ReadString(rd)
value := structure.ReadString(rd)

internal/rdb/structure/string.go:ReadString

func ReadString(rd io.Reader) string {
        // 获取长度
	length, special, err := readEncodedLength(rd)
	if err != nil {
		log.PanicError(err)
	}
	
	if special {
		switch length {
		case RDBEncInt8:
			b := ReadInt8(rd)
			return strconv.Itoa(int(b))
		case RDBEncInt16:
			b := ReadInt16(rd)
			return strconv.Itoa(int(b))
		case RDBEncInt32:
			b := ReadInt32(rd)
			return strconv.Itoa(int(b))
		case RDBEncLZF:
			inLen := ReadLength(rd)
			outLen := ReadLength(rd)
			in := ReadBytes(rd, int(inLen))

			return lzfDecompress(in, int(outLen))
		default:
			log.Panicf("Unknown string encode type %d", length)
		}
	}
	return string(ReadBytes(rd, int(length)))
}

1.4 数据区

数据区开头为数据库编号、数据库中键个数、有 TTL 的键个数，接下来为若干键值对

2 RDB 中的编码

2.1 LengthEncoding

Length Encoding 是一种可变长度的无符号整型编码，因为通常被用来存储字符串长度、列表长度等长度数据所以被称为 Length Encoding.

如果前两位是 00 那么下面剩下的 6 位就表示具体长度

如果前两位是 01 那么会再读取一个字节的数据，加上前面剩下的6位，共14位用于表示具体长度

如果前两位是 10

* 如果剩下的 6 位都是 0 那么后面 32 位表示具体长度(4 个字节)

* 如果剩下的 6 位为 000001, 那么后面的 64 位表示具体长度(8 个字节)

如果前两位是 11 表示为使用字符串存储整数的特殊编码

11 开头的Length Encoding 称为「特殊长度编码」，其它 3 种称为 「普通长度编码」

internal/rdb/structure/length.go:readEncodedLength

package structure

import (
	"encoding/binary"
	"fmt"
	"github.com/alibaba/RedisShake/internal/log"
	"io"
)

const (
	RDB6ByteLen  = 0 // RDB_6BITLEN
	RDB14ByteLen = 1 // RDB_14BITLEN
	len32or64Bit = 2
	lenSpecial   = 3 // RDB_ENCVAL
	RDB32ByteLen = 0x80
	RDB64ByteLen = 0x81
)

func ReadLength(rd io.Reader) uint64 {
	length, special, err := readEncodedLength(rd)
	if special {
		log.Panicf("illegal length special=true, encoding: %d", length)
	}
	if err != nil {
		log.PanicError(err)
	}
	return length
}

func readEncodedLength(rd io.Reader) (length uint64, special bool, err error) {
	var lengthBuffer = make([]byte, 8)

	firstByte := ReadByte(rd)
	first2bits := (firstByte & 0xc0) >> 6 // first 2 bits of encoding
	switch first2bits {
	case RDB6ByteLen:
		length = uint64(firstByte) & 0x3f
	case RDB14ByteLen:
		nextByte := ReadByte(rd)
		length = (uint64(firstByte)&0x3f)<<8 | uint64(nextByte)
	case len32or64Bit:
		if firstByte == RDB32ByteLen {
			_, err = io.ReadFull(rd, lengthBuffer[0:4])
			if err != nil {
				return 0, false, fmt.Errorf("read len32Bit failed: %s", err.Error())
			}
			length = uint64(binary.BigEndian.Uint32(lengthBuffer))
		} else if firstByte == RDB64ByteLen {
			_, err = io.ReadFull(rd, lengthBuffer)
			if err != nil {
				return 0, false, fmt.Errorf("read len64Bit failed: %s", err.Error())
			}
			length = binary.BigEndian.Uint64(lengthBuffer)
		} else {
			return 0, false, fmt.Errorf("illegal length encoding: %x", firstByte)
		}
	case lenSpecial:
		special = true
		length = uint64(firstByte) & 0x3f
	}
	return length, special, nil
}

2.2 StringEncoding

RDB 的 StringEncoding 可以分为三种类型：

• 简单字符串编码

• 整数字符串

• LZF 压缩字符串

internal/rdb/structure/string.go:ReadString

package structure

import (
	"github.com/alibaba/RedisShake/internal/log"
	"io"
	"strconv"
)

const (
	RDBEncInt8  = 0 // RDB_ENC_INT8
	RDBEncInt16 = 1 // RDB_ENC_INT16
	RDBEncInt32 = 2 // RDB_ENC_INT32
	RDBEncLZF   = 3 // RDB_ENC_LZF
)

func ReadString(rd io.Reader) string {
	length, special, err := readEncodedLength(rd)
	if err != nil {
		log.PanicError(err)
	}
	if special {
		switch length {
		case RDBEncInt8:
			b := ReadInt8(rd)
			return strconv.Itoa(int(b))
		case RDBEncInt16:
			b := ReadInt16(rd)
			return strconv.Itoa(int(b))
		case RDBEncInt32:
			b := ReadInt32(rd)
			return strconv.Itoa(int(b))
		case RDBEncLZF:
			inLen := ReadLength(rd)
			outLen := ReadLength(rd)
			in := ReadBytes(rd, int(inLen))

			return lzfDecompress(in, int(outLen))
		default:
			log.Panicf("Unknown string encode type %d", length)
		}
	}
	return string(ReadBytes(rd, int(length)))
}

func lzfDecompress(in []byte, outLen int) string {
	out := make([]byte, outLen)

	i, o := 0, 0
	for i < len(in) {
		ctrl := int(in[i])
		i++
		if ctrl < 32 {
			for x := 0; x <= ctrl; x++ {
				out[o] = in[i]
				i++
				o++
			}
		} else {
			length := ctrl >> 5
			if length == 7 {
				length = length + int(in[i])
				i++
			}
			ref := o - ((ctrl & 0x1f) << 8) - int(in[i]) - 1
			i++
			for x := 0; x <= length+1; x++ {
				out[o] = out[ref]
				ref++
				o++
			}
		}
	}
	if o != outLen {
		log.Panicf("lzf decompress failed: outLen: %d, o: %d", outLen, o)
	}
	return string(out)
}

StringEncode 总是以 LengthEncoding 开头, 普通字符串编码由普通长度编码 + 字符串的 ASCII 序列组成, 整数字符串和 LZF 压缩字符串则以特殊长度编码开头。

2.3 ListEncoding & SetEncoding & HashEncoding

ListEncoding 开头为一个普通长度编码块表示 List 的长度，随后是对应个数的 StringEncoding 块。

SetEncoding 与 ListEncoding 完全相同。

HashEncoding 开头为一个普通长度编码块表示哈希表中的键值对个数，随后为对应个数的：Key StringEncoding + Value StringEncoding 组成的键值对。

\

传送门

GitHub - HDT3213/rdb: Golang implemented Redis RDB parser for secondary development and memory analysisGitHub

Redis RDB Dump File FormatGitHub