Go 存储系统实现详解（B+树/MVCC/连接池/Redis客户端）

2022-02-11T10:00:00+08:00 | 7分钟阅读 | 更新于 2022-02-11T10:00:00+08:00

@
存储系统实现数据库核心缓存与序列化高级存储结构B+树节点MVCC连接池Redis ClientJSON MarshalJSON UnmarshalLSM Tree分库分表插入/删除RESP解析MemTable版本链PipelineSSTableGap LockVarint编码深分页优化保活机制

学习目标

读完本文，你应该能够：

  • 理解 B+ 树的节点结构和插入删除逻辑，并手写简化版
  • 实现 MVCC 的多版本并发控制简化版
  • 手写数据库连接池，包含健康检查和最大空闲回收
  • 解析 RESP 协议实现简易 Redis Client
  • 理解 LSM Tree 的核心逻辑（MemTable + SSTable）
  • 实现 Protobuf Varint 编码/解码

一、B+ 树实现

概念讲解

B+ 树是数据库索引的标准实现，理解其分裂合并机制有助于排查查询性能问题。

应用场景

在实际项目中，这个知识点经常应用于：

  1. 典型场景一：说明具体应用场景
  2. 典型场景二：说明另一个应用场景
  3. 面试要点：提醒面试中可能被问到的点

二、MVCC 简化实现

2.1 核心概念

// 版本号
type Version int64

// 记录版本
type VersionedRecord struct {
    Version Version
    Value   []byte
    Next    *VersionedRecord
}

// 数据行
type Row struct {
    VersionChain *VersionedRecord
    DeleteMask   Version  // 软删除版本
}

2.2 读写快照

type MVCCStore struct {
    data      map[string]*Row
    readView  Version
    writeVer  Version
    mu        sync.RWMutex
}

func NewMVCCStore() *MVCCStore {
    return &MVCCStore{
        data: make(map[string]*Row),
    }
}

// Get 读取指定版本的数据
func (store *MVCCStore) Get(key string, version Version) ([]byte, error) {
    store.mu.RLock()
    defer store.mu.RUnlock()
    
    row, ok := store.data[key]
    if !ok {
        return nil, fmt.Errorf("key not found")
    }
    
    // 遍历版本链，找到≤version的最大版本
    curr := row.VersionChain
    var result []byte
    for curr != nil {
        if curr.Version <= version {
            result = curr.Value
            break
        }
        curr = curr.Next
    }
    
    if result == nil {
        return nil, fmt.Errorf("no version found")
    }
    return result, nil
}

// Put 写入带新版本号的数据
func (store *MVCCStore) Put(key string, value []byte) error {
    store.mu.Lock()
    defer store.mu.Unlock()
    
    store.writeVer++
    
    row, ok := store.data[key]
    if !ok {
        row = &Row{}
        store.data[key] = row
    }
    
    // 插入新的版本
    newRecord := &VersionedRecord{
        Version: store.writeVer,
        Value:   value,
        Next:    row.VersionChain,
    }
    row.VersionChain = newRecord
    return nil
}

三、数据库连接池

概念讲解

连接池管理着宝贵的数据库连接资源，设计良好的连接池能显著提升系统稳定性。

应用场景

在实际项目中，这个知识点经常应用于：

  1. 典型场景一：说明具体应用场景
  2. 典型场景二：说明另一个应用场景
  3. 面试要点：提醒面试中可能被问到的点

四、简易 Redis Client（RESP 协议解析）

type RESPParser struct {
    buf bytes.Buffer
}

// 读取一行
func (p *RESPParser) readLine(conn net.Conn) (string, error) {
    var line []byte
    for {
        var b [1]byte
        if _, err := conn.Read(b[:]); err != nil {
            return "", err
        }
        line = append(line, b[0])
        if b[0] == '\n' {
            break
        }
    }
    return string(bytes.TrimRight(line, "\r\n")), nil
}

// 解析简单字符串
func (p *RESPParser) parseSimpleString(conn net.Conn) (string, error) {
    line, err := p.readLine(conn)
    if err != nil {
        return "", err
    }
    if line[0] != '+' {
        return "", fmt.Errorf("expected simple string, got: %s", line)
    }
    return line[1:], nil
}

// 解析整数
func (p *RESPParser) parseInt(conn net.Conn) (int64, error) {
    line, err := p.readLine(conn)
    if err != nil {
        return 0, err
    }
    if line[0] != ':' {
        return 0, fmt.Errorf("expected integer, got: %s", line)
    }
    return strconv.ParseInt(line[1:], 10, 64)
}

// 解析 Bulk String
func (p *RESPParser) parseBulkString(conn net.Conn) (string, error) {
    line, err := p.readLine(conn)
    if err != nil {
        return "", err
    }
    if line[0] != '$' {
        return "", fmt.Errorf("expected bulk string, got: %s", line)
    }
    length, _ := strconv.Atoi(line[1:])
    if length == -1 {
        return "", nil // nil
    }
    
    body := make([]byte, length+2)
    if _, err := io.ReadFull(conn, body); err != nil {
        return "", err
    }
    return string(body[:length]), nil
}

// 解析 Array
func (p *RESPParser) parseArray(conn net.Conn) ([]interface{}, error) {
    line, err := p.readLine(conn)
    if err != nil {
        return nil, err
    }
    if line[0] != '*' {
        return nil, fmt.Errorf("expected array, got: %s", line)
    }
    count, _ := strconv.Atoi(line[1:])
    if count == -1 {
        return nil, nil
    }
    
    result := make([]interface{}, count)
    for i := 0; i < count; i++ {
        result[i], err = p.parseNext(conn)
        if err != nil {
            return nil, err
        }
    }
    return result, nil
}

func (p *RESPParser) parseNext(conn net.Conn) (interface{}, error) {
    line, err := p.readLine(conn)
    if err != nil {
        return nil, err
    }
    switch line[0] {
    case '+':
        return line[1:], nil
    case '-':
        return line[1:], nil
    case ':':
        return strconv.ParseInt(line[1:], 10, 64)
    case '$':
        length, _ := strconv.Atoi(line[1:])
        if length == -1 {
            return nil, nil
        }
        body := make([]byte, length+2)
        if _, err := io.ReadFull(conn, body); err != nil {
            return nil, err
        }
        return string(body[:length]), nil
    case '*':
        count, _ := strconv.Atoi(line[1:])
        if count == -1 {
            return nil, nil
        }
        arr := make([]interface{}, count)
        for i := 0; i < count; i++ {
            arr[i], err = p.parseNext(conn)
            if err != nil {
                return nil, err
            }
        }
        return arr, nil
    default:
        return nil, fmt.Errorf("unknown RESP type: %c", line[0])
    }
}

// Redis Client
type RedisClient struct {
    conn    net.Conn
    parser  *RESPParser
}

func Dial(addr string) (*RedisClient, error) {
    conn, err := net.Dial("tcp", addr)
    if err != nil {
        return nil, err
    }
    return &RedisClient{
        conn:   conn,
        parser: &RESPParser{},
    }, nil
}

func (rc *RedisClient) Get(key string) (string, error) {
    msg := fmt.Sprintf("*2\r\n$3\r\nGET\r\n$%d\r\n%s\r\n", len(key), key)
    if _, err := rc.conn.Write([]byte(msg)); err != nil {
        return "", err
    }
    return rc.parser.parseBulkString(rc.conn)
}

func (rc *RedisClient) Set(key, value string) error {
    msg := fmt.Sprintf("*3\r\n$3\r\nSET\r\n$%d\r\n%s\r\n$%d\r\n%s\r\n",
        len(key), key, len(value), value)
    _, err := rc.conn.Write([]byte(msg))
    return err
}

func (rc *RedisClient) Close() error {
    return rc.conn.Close()
}

五、LSM Tree 核心逻辑

type MemTable struct {
    data map[string]string
    mu   sync.RWMutex
}

func NewMemTable() *MemTable {
    return &MemTable{data: make(map[string]string)}
}

func (mt *MemTable) Put(key, value string) {
    mt.mu.Lock()
    defer mt.mu.Unlock()
    mt.data[key] = value
}

func (mt *MemTable) Get(key string) (string, bool) {
    mt.mu.RLock()
    defer mt.mu.RUnlock()
    v, ok := mt.data[key]
    return v, ok
}

type SSTable struct {
    entries []KVEntry
    filename string
}

type KVEntry struct {
    Key   string
    Value string
}

type LSMTree struct {
    memTable   *MemTable
    level0     []*SSTable
    levels     [][]*SSTable
    options    LSMOptions
}

type LSMOptions struct {
    memTableSize   int64      // MemTable 大小上限
    level0FileSize int64      // L0 文件单文件大小
    numLevels      int        // 层级数量
}

func (lsm *LSMTree) Put(key, value string) {
    lsm.memTable.Put(key, value)
    
    // 检查是否达到 flush 条件
    if lsm.memTableSize >= lsm.options.memTableSize {
        lsm.flush()
    }
}

func (lsm *LSMTree) flush() {
    sstable := &SSTable{
        filename: fmt.Sprintf("l0_%d.sst", time.Now().UnixNano()),
    }
    // 将 MemTable 内容写入 SSTable
    lsm.memTable.mu.RLock()
    for k, v := range lsm.memTable.data {
        sstable.entries = append(sstable.entries, KVEntry{Key: k, Value: v})
    }
    lsm.memTable.mu.RUnlock()
    
    // 追加到 L0
    lsm.level0 = append(lsm.level0, sstable)
    
    // 触发 Compaction
    lsm.compactIfNeeded()
}

func (lsm *LSMTree) compactIfNeeded() {
    // 简化的 compaction 逻辑
    if len(lsm.level0) > 4 {
        // 合并 L0 多个文件
        merged := lsm.mergeSSTables(lsm.level0[:])
        lsm.level0 = lsm.level0[len(merged):]
        lsm.levels[0] = append(lsm.levels[0], merged...)
    }
}

func (lsm *LSMTree) mergeSSTables(ssts []*SSTable) []*SSTable {
    // 使用多路归并
    // 省略详细实现
    return nil
}

**LSM Tree 核心结构：内存 MemTable/WAL 与磁盘分层 SSTable + compaction 回边**

<svg viewBox="0 0 1000 600" xmlns="http://www.w3.org/2000/svg" font-family="-apple-system, BlinkMacSystemFont, 'PingFang SC', 'Microsoft YaHei', sans-serif">
  <defs>
    <marker id="l7" markerWidth="10" markerHeight="8" refX="9" refY="4" orient="auto">
      <path d="M0,0 L10,4 L0,8 z" fill="#B03030"/>
    </marker>
  </defs>
  <g stroke="#B03030" stroke-width="2.5" fill="#fff">
    <rect x="40" y="40" width="430" height="250" rx="12" stroke-width="3"/>
    <text x="255" y="66" text-anchor="middle" fill="#B03030" font-size="15" font-weight="700" stroke="none">内存（易失）</text>

    <rect x="55" y="80" width="400" height="72" rx="8"/>
    <text x="255" y="106" text-anchor="middle" fill="#1a1a1a" font-size="13" font-weight="700" stroke="none">MemTable（有序结构 · 可读写）</text>
    <text x="255" y="128" text-anchor="middle" fill="#666" font-size="11" stroke="none">写满达到 memTableSize → flush</text>

    <rect x="55" y="172" width="400" height="56" rx="8" stroke-dasharray="7 4"/>
    <text x="255" y="196" text-anchor="middle" fill="#1a1a1a" font-size="13" font-weight="700" stroke="none">WAL（预写日志 · 顺序写磁盘）</text>
    <text x="255" y="216" text-anchor="middle" fill="#666" font-size="11" stroke="none">崩溃恢复用，flush 后对应段可截断</text>

    <rect x="55" y="252" width="400" height="28" rx="6"/>
    <text x="255" y="271" text-anchor="middle" fill="#1a1a1a" font-size="11" stroke="none">读路径：先查 MemTable，未命中再下沉到各层 SSTable</text>
  </g>

  <g stroke="#B03030" stroke-width="2.5" fill="#fff">
    <rect x="540" y="40" width="420" height="540" rx="12" stroke-width="3"/>
    <text x="750" y="66" text-anchor="middle" fill="#B03030" font-size="15" font-weight="700" stroke="none">磁盘（持久 · 不可变 SSTable）</text>

    <rect x="555" y="82" width="390" height="64" rx="8"/>
    <text x="750" y="106" text-anchor="middle" fill="#1a1a1a" font-size="13" font-weight="700" stroke="none">L0（多文件 · key 区间允许重叠）</text>
    <text x="750" y="126" text-anchor="middle" fill="#666" font-size="11" stroke="none">flush 直接落盘，文件数超阈值触发 compaction</text>

    <rect x="555" y="170" width="390" height="56" rx="8"/>
    <text x="750" y="194" text-anchor="middle" fill="#1a1a1a" font-size="13" font-weight="700" stroke="none">L1（合并为单文件 · key 不重叠）</text>
    <text x="750" y="214" text-anchor="middle" fill="#666" font-size="11" stroke="none">多路归并去重，仅保留最新版本</text>

    <rect x="555" y="250" width="390" height="50" rx="8"/>
    <text x="750" y="274" text-anchor="middle" fill="#1a1a1a" font-size="12.5" stroke="none">L2 / L3 …（更冷数据 · 以空间放大换读放大降低）</text>

    <rect x="555" y="330" width="390" height="60" rx="8" stroke-dasharray="7 4"/>
    <text x="750" y="354" text-anchor="middle" fill="#1a1a1a" font-size="12.5" stroke="none">Compaction（合并 + 丢弃旧版本 / 墓碑）</text>
    <text x="750" y="374" text-anchor="middle" fill="#666" font-size="11" stroke="none">compactIfNeeded 触发，降低读放大与空间放大</text>

    <rect x="555" y="430" width="390" height="50" rx="8"/>
    <text x="750" y="454" text-anchor="middle" fill="#1a1a1a" font-size="12.5" stroke="none">Bloom Filter + 稀疏索引（加速 SSTable 定位）</text>

    <rect x="555" y="510" width="390" height="50" rx="8"/>
    <text x="750" y="534" text-anchor="middle" fill="#1a1a1a" font-size="12.5" stroke="none">Get 查找：L0 → L1 → L2（逐层，命中即返回）</text>
  </g>

  <g stroke="#B03030" stroke-width="2.5" fill="none" marker-end="url(#l7)">
    <path d="M470 116 L545 116"/>
    <path d="M750 146 L750 168"/>
    <path d="M750 226 L750 248"/>
  </g>
  <path d="M555 360 Q 450 360 450 250 L450 200 Q 450 150 545 150" fill="none" stroke="#B03030" stroke-width="2.5" stroke-dasharray="8 5" marker-end="url(#l7)"/>
  <g text-anchor="middle" fill="#B03030" font-size="11" font-family="-apple-system, BlinkMacSystemFont, 'PingFang SC', 'Microsoft YaHei', sans-serif">
    <text x="508" y="106">flush</text>
    <text x="772" y="162">compaction</text>
    <text x="772" y="240">compaction</text>
    <text x="360" y="250">回边：下层合并</text>
    <text x="360" y="266">后写回更高层</text>
  </g>
</svg>

> **看图要点**：LSM 的核心矛盾是"写放大 vs 读放大 vs 空间放大"的三角权衡——MemTable 让写入只落在内存+顺序 WAL（快），compaction 在后台把零散 L0 归并成不重叠的高层（读更快但写/空间更费）。面试官高频追问：compaction 在什么时机触发、为什么 L0 允许 key 重叠而 L1 不重叠、WAL 与 SSTable 的关系（WAL 只用于崩溃恢复，flush 后即可丢弃）。

六、Protobuf Varint 编码

func EncodeVarint(n uint64) []byte {
    var buf []byte
    for n >= 0x80 {
        buf = append(buf, byte(n)|0x80)
        n >>= 7
    }
    buf = append(buf, byte(n))
    return buf
}

func DecodeVarint(buf []byte) (uint64, int) {
    var result uint64
    var shift uint
    for i, b := range buf {
        if b < 0x80 {
            result |= uint64(b) << shift
            return result, i + 1
        }
        result |= uint64(b&0x7F) << shift
        shift += 7
    }
    return 0, 0
}

七、自测题

面试官
B+ 树相比 B 树有什么优势？为什么数据库索引用 B+ 树？
候选人

B+ 树的优势：

  1. 所有数据都在叶子节点，查询性能稳定
  2. 叶子节点形成链表，范围查询高效
  3. 非叶子节点只存索引，单页能容纳更多键，树更矮胖

    MySQL InnoDB 使用 B+ 树作为聚簇索引，正是因为其范围查询优势和稳定的查询性能。
面试官
MVCC 是怎么解决读写冲突的？
候选人
MVCC 的核心思想：读不阻塞写，写不阻塞读。 每个事务有一个快照视图（Snapshot View），只能看到提交前版本的数据。 写操作创建新版本，旧版本保留供读事务继续使用。 这就是为什么 SELECT 不会锁表，INSERT/UPDATE/DELETE 也不会被 SELECT 阻塞。

八、本章小结

复习提示：
  • B+ 树是数据库索引的标准选择，理解其分裂合并机制有助于深入 MySQL/PostgreSQL
  • MVCC 通过版本链实现快照隔离，是高并发数据库的核心技术
  • 连接池要处理健康检查、最大空闲回收、等待超时等细节
  • RESP 协议是 Redis 通信的基础，理解其类型编码格式
  • 下一篇将讲解性能分析与调试：pprof、trace、race detector 等实战技巧

参考

  • 《MySQL 技术内幕：InnoDB 存储引擎》第 6 章：索引
  • LSM-Tree 论文：https://smoss.com/papers/lsm-toc.pdf
  • RESP 协议规范：https://redis.io/docs/protocol/spec/
上一页 Go 网络与协议实现详解（TCP/HTTP/DNS/TCP粘包）
下一页 Go 性能分析与调试详解（pprof/trace/race）
About Me

没什么想介绍的，一个很大众的码农…

喜欢代码，车，马，真的是 🐎

讨厌别人让我给自己的代码写注释 最厌烦别人的程序没有写注释

目标

学AI，加油！加油！