Mydb自定义数据库八股

日志

1.在 Mydb 数据库中，日志模块是如何实现崩溃恢复的？请详细说明日志格式、校验机制、写入流程和恢复逻辑，并分析可能存在的性能瓶颈及优化方案。

日志设计

redo log:记录事务提交后的数据修改，用于崩溃后重做已提交事务（如数据页修改记录）；

undo log:记录事务提交前的原始状态，用于回滚未提交事务（如行版本号、旧值）。

1
2
[全局校验码(4B)][日志条目1][日志条目2]...  
日志条目格式：[条目长度(4B)][校验码(4B)][数据内容(N字节)]

日志文件头部 4 字节为全局校验码，每条日志以[4字节长度+4字节校验码+数据]组成。启动时会从头部开始校验每条日志的 checksum，若全局校验码不一致则截断文件尾部。”

崩溃恢复

校验

  • 从文件头部开始读取每条日志，校验单条日志的 checksum；
  • 累计计算全局校验码，与文件头部校验码比对，不一致则截断文件尾部。

redo

  • 扫描日志，提取所有状态为COMMITTED的事务记录；
  • 按日志顺序重新执行数据修改操作（如更新数据页）。

undo

  • 扫描日志，找到状态为ACTIVE或ABORTED的事务；
  • 根据 Undo 日志恢复数据原始状态（如行版本号回退）。

日志写入和刷盘

1
2
3
4
5
6
7
// 日志写入伪代码  
void appendLog(byte[] data) {  
    byte[] entry = wrapLog(data); // 封装[长度+校验码+数据]  
    fileChannel.position(fileChannel.size());  
    fileChannel.write(ByteBuffer.wrap(entry));  
    updateGlobalChecksum(entry); // 更新全局校验码  
}

刷盘策略：

  • 同步刷盘（SYNC）：每条日志写入后立即调用force()刷盘，可靠性高但性能低；
  • 异步刷盘（ASYNC）：使用双阈值策略（时间阈值 + 大小阈值）：

使用一个异步的线程池来实现，满足任一条件即可刷盘，提升灵活性与性能保障

多次 flush() 只设置标志，合并后统一刷盘

使用原子变量 + synchronized 保证数据一致性

可通过 shutdown() 停止任务，或动态调整周期

可通过参数设定周期，如每 100ms 刷一次

最长可能延迟 flushIntervalMillis，适合非关键日志

异步刷盘使用ScheduledThreadPoolExecutor定时检查，当日志缓冲区大小超过 1MB 或距上次刷盘超过 2 秒时，加锁批量刷盘，避免多线程同时操作文件导致的一致性问题。”

  • 不刷盘（NO_FLUSH）：仅用于测试，数据可能丢失。

性能问题

同步刷盘导致的 IO 阻塞

高并发下刷盘成为瓶颈，TPS 下降（如单线程同步刷盘时 TPS≤1000）。

  • 采用组提交（Group Commit）：将多个日志条目批量刷盘（如每 100 条刷一次）；
  • 引入内存映射文件（MappedByteBuffer），减少用户态到内核态的拷贝。

异步刷盘的数据一致性风险

  • 实现WAL（Write-Ahead Logging） 机制：事务提交前强制刷盘 Redo 日志；
  • 增加刷盘回调机制：刷盘完成后通知事务提交。

日志校验的 CPU 开销

  • 用CRC32C 算法替代自定义校验（JDK1.8 java.util.zip.CRC32C，性能提升 3 倍）；
  • 对热数据日志启用校验缓存，避免重复计算。

日志缓存可将HashMap+ReentrantLock改为ConcurrentHashMap，利用分段锁减少并发竞争。例如，缓存热点日志的校验结果时，读操作无需加锁，写操作仅锁定对应分段。”

日志分段与归档

  • 按时间或大小分割日志文件（如每 1GB 一个文件），避免单文件过大；
  • 归档旧日志文件，定期清理无效日志（如已完成事务的 Undo 日志）。

异步刷盘策略下，系统崩溃导致 10 秒内的日志丢失（约 5000 条）。

  • 调整双阈值为大小阈值=1MB+时间阈值=2秒，平衡性能与可靠性；
  • 关键业务场景强制使用同步刷盘（如资金交易）。

2.你在开发 MYDB 数据库项目中实现日志恢复机制时，具体是怎么做的？有哪些技术难点？你是如何解决的？

  1. 实现目标：
  • 实现 事务的持久性与原子性
  • 在系统崩溃后能根据日志 进行正确恢复（Redo or Undo）
  1. 日志设计（你可说你仿照 MySQL）：
  • 实现了 Redo Log：记录事务修改了哪些数据页（PageLSN）。
  • 实现了 Undo Log：在事务失败时回滚未提交的更改。
  • 日志写入策略采用 Write-Ahead Logging（WAL）。

  1. 日志写入流程：

  2. 用户执行 SQL 变更操作。

  3. 系统先生成 Undo/Redo 日志并写入日志缓冲区。
  4. 修改数据页（缓存在 Buffer Pool 中），标记为 dirty。
  5. 后台使用异步线程（守护线程）周期性刷盘数据页和日志。

  6. 提交事务时，强制将日志落盘，保证事务持久性。

  7. 崩溃恢复逻辑：

  • 启动恢复时：
    • 从日志中 重做已提交但未刷盘的事务（Redo）
    • 撤销未提交事务的更改（Undo）
  • 按 LSN 顺序恢复数据页一致性。
  1. 技术挑战与优化：
  • 如何确保 日志和数据页写入顺序正确（WAL）
  • Redo/Undo 的实现细节（如日志格式、LSN机制）
  • 实现异步刷盘而不丢数据（可以说实现了日志缓冲与后台刷盘线程）
  • 用状态模式或者策略模式管理不同日志类型（你说的 case 分支控制可提一下）

3.你在 MYDB 项目中实现日志系统时，如何保证日志写入的一致性与性能？有没有考虑写放大、刷盘策略、异常恢复的问题？

为什么要先写日志？为了避免崩溃后数据丢失，我们会先写一份日志（WAL），保证只要日志落盘，数据一定可以恢复。

怎么写日志？（刷盘策略）？

  • 我们采用异步刷盘（后台线程批量顺序写日志），提高吞吐。

  • 使用批量提交 + 顺序IO（避免随机写盘）提升磁盘性能。

    如何做恢复？崩溃重启后，系统会从日志中进行 Redo（重做）。我们还配合 Checkpoint（检查点），减少恢复时扫描的日志量。

项目中的应用？在我的项目中（可提 MYDB），曾遇到“数据突然消失”问题，最终通过调整日志刷盘策略（从同步改异步）+ redo 恢复流程解决。

索引

1.在 Mydb 数据库中，B + 树索引是如何实现高效查询和插入的？请详细说明节点结构、查询算法、插入分裂策略，并分析高并发场景下的性能瓶颈及优化方案。

B + 树核心结构设计

1
2
3
[叶子标志(1B)][键数量(2B)][兄弟节点UID(8B)][子节点UID/键值对]  
叶子节点：[键1][值1][键2][值2]...[键n][值n]  
非叶子节点：[子节点UID1][键1][子节点UID2][键2]...[子节点UIDn][键n]
  • 叶子节点：存储实际键值对，通过双向链表连接（便于范围查询）；
  • 非叶子节点：仅存储键和子节点引用，加速检索。
  • 扇出（Fan-Out）：单个节点可容纳的子节点数，由键长和页大小决定（如 8KB 页 + 8B 键 + 8B 引用，扇出≈512）；
  • 阶数（Order）：节点的最小子节点数（通常为扇出的 1/2），保证树的平衡。

B + 树节点包含叶子标志位（1 字节）、键数量（2 字节）、兄弟节点 UID（8 字节），叶子节点存储键值对，非叶子节点存储子节点 UID 和分隔键，通过页结构（如 4KB）组织数据。”

查找

非叶子节点：用二分查找确定子节点方向；

叶子节点：顺序遍历键值对（因叶子节点有序，可快速定位）。

IO 次数：3 层 B + 树可存储约 1000 万条数据，查询仅需 3 次 IO（页大小 16KB，扇出 1000）；

内存效率：非叶子节点仅存储键和引用，内存占用比二叉搜索树低 80%。

查询时非叶子节点用二分查找确定子节点方向，叶子节点因有序可快速定位，范围查询时通过叶子节点的双向链表遍历，避免全树扫描。

插入与分裂

插入

  • 定位到目标叶子节点，若空间足够则直接插入；
  • 若空间不足，触发节点分裂。

分裂逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void splitLeafNode(LeafNode node) {  
    LeafNode newNode = new LeafNode();  
    int mid = node.keyCount / 2;  
    // 复制后半部分键值对到新节点  
    for (int i = mid; i < node.keyCount; i++) {  
        newNode.insert(node.keys[i], node.values[i]);  
    }  
    node.keyCount = mid;  
    // 连接兄弟节点  
    newNode.sibling = node.sibling;  
    node.sibling = newNode.uid;  
    // 向父节点插入新节点引用  
    insertIntoParent(node, newNode.smallestKey, newNode.uid);  
}
  • 分裂点：取节点中键的中间位置，前半部分保留，后半部分放入新节点；
  • 父节点更新：父节点插入新节点的最小键和 UID，若父节点也满则递归分裂。

分裂时将节点后半部分数据移至新节点，新节点的兄弟指针指向原节点的兄弟，原节点的兄弟指针指向新节点，并向父节点插入新节点的最小键和 UID，若父节点已满则递归分裂。

插入 / 分裂时仅锁定目标节点,ReentrantLock.

性能问题

节点锁竞争

高并发插入时，多个线程争夺同一节点锁，导致吞吐量下降（如 1000TPS 时下降至 300TPS）

  • 分层锁（Locking Hierarchy）：
    • 非叶子节点用ReadWriteLock，读操作共享锁，写操作排他锁；
    • 叶子节点用ReentrantLock，支持可重入和公平锁模式。

  • 使用乐观锁：

  • ```java
    boolean casInsert(Node node, long expectedVersion) { 

    if (node.version != expectedVersion) return false;  
// 插入操作...  
node.version++;  
return true;

    } 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171

    **缓存失效与 IO 风暴**

    大量随机插入导致 B + 树重组，缓存命中率下降（如从 90% 降至 50%）。

    - **节点预读（Read-Ahead）**：查询时预判下一层节点，提前加载到缓存；
    - **冷热数据分离**：用`LRU缓存`存储热点节点，冷节点定期淘汰（如最近 10 分钟未访问的节点）。LRU可以使用hashmap+reentrantlock或者使用更加精细的concurrenthashmap+readwritrlock

    **范围查询性能衰减**

    大范围查询时遍历叶子链表，导致 CPU 占用过高（如查询 10 万条记录时 CPU 占比 100%）。

    - **批量读取（Batch Read）**：一次读取多个页（如 16 个页），减少 IO 次数；
    - **异步查询（Async Query）**：将大范围查询放入单独线程池，避免阻塞业务线程：

    优化

    **写入优化：批量插入与合并分裂**

    - **批量插入**：将多个插入操作合并为一批，减少分裂次数（如每 1000 条插入后统一分裂）；
    - **分裂合并**：当相邻节点利用率低于 50% 时，合并节点以减少树高。

    **索引覆盖与前缀索引**

    - **索引覆盖**：设计索引时包含查询所需全部字段，避免回表（如`SELECT id,name FROM table WHERE id>100`）；
    - **前缀索引**：对长字符串取前缀建立索引（如取 URL 前 100 字节），减少索引体积。

    **监控与调优指标**

    节点锁等待时间（理想≤1ms）；

    缓存命中率（理想≥95%）；

    平均 IO 次数（理想≤3 次 / 查询）。

    调优工具：

    - 用`JProfiler`监控索引操作热点方法；
    - 用`BTrace`追踪节点锁竞争场景。

    **电商大促时，商品索引插入性能骤降，导致订单创建延迟从 50ms 升至 500ms。**

    高并发插入导致 B + 树频繁分裂，节点锁竞争激烈。

    - 启用**写入限流**（如每秒最多 1 万次插入），超出则返回 “系统繁忙”；
    - 采用**分段 B + 树**：按商品 ID 哈希分为 16 段，每段独立索引，减少锁冲突；
    - 大促前预扩容索引，预留 30% 空间（如初始扇出 512，大促时调整为 358）。
    - 高并发插入时，可采用写入分组（如按 UID 哈希分 16 组，每组独立索引），配合令牌桶限流（如每组每秒 1000 次插入），减少节点锁竞争；同时用乐观锁（CAS）避免频繁加锁。

    ## 2.在 “MinaDB” 项目中，你提到实现了基于 B + 树的索引结构，说说 B + 树相比 B 树在索引场景下的优势？如果数据库中某个表的查询频繁出现 “索引失效”，你会从哪些方面排查原因？

    B 树的非叶子节点同时存储索引键和数据行指针，而 B + 树非叶子节点仅存储索引键，相同空间可存储更多索引项，查询时 IO 次数更少。此外，B 树查询到数据后直接返回，而 B + 树需遍历到叶子节点，看似多一层，但 B + 树叶子节点数据更紧凑，且磁盘预读特性下，连续的叶子节点访问效率反而更高。

    索引失效一般都是不满足联合索引未满足最左前缀原则，

    比如，使用or前面的有索引，后面的没索引。

    使用了like模糊匹配，在查询的使用了函数或者运算

    没有遵守联合查询的最左匹配

    进行了索引跳跃

    还有**数据类型不匹配**：如索引列是`varchar`，查询时未加引号导致隐式转换

    **统计信息过时**：表数据大量更新后未重建索引或 analyze 表，优化器误判索引效率



    # 事务&MVCC

    ## 1.在 Mydb 数据库中，如何实现事务的 ACID 特性？请详细说明事务日志（Redo/Undo）、锁机制、MVCC 的作用，并分析高并发场景下的脏读、不可重复读、幻读解决方案。

    ACID

    - **原子性（Atomicity）**：通过 Undo 日志记录事务前状态，回滚时恢复；
    - **一致性（Consistency）**：通过 Redo+Undo 共同保证（Redo 重做已提交事务，Undo 回滚未提交事务）；
    - **持久性（Durability）**：Redo 日志刷盘后，即使崩溃也能恢复数据；
    - **隔离性（Isolation）**：通过 MVCC + 锁机制实现不同隔离级别。

    事务提交时，先写 Undo 日志记录旧值，再写 Redo 日志记录新值，最后刷盘 Redo 日志（WAL 原则），确保崩溃后 Redo 已提交事务，Undo 回滚未提交事务。

    MVCC

    “MVCC 通过版本号（或时间戳）实现快照读：

    1. 事务启动时记录当前最大活跃事务 ID（max_trx_id）；
    2. 读取数据时，若数据版本号 < 当前事务 ID 且不在活跃事务列表中，可读；
    3. 若数据版本号 >= max_trx_id，不可见
    3. 数据版本号在活跃事务id里面，不可见
    4. MVCC 通过快照读避免锁竞争，适合读多写少场景（如报表查询）；锁机制适合写多场景（如订单扣款），需根据业务场景选择。”

    隔离级别：

    - **读已提交（RC）**：每次查询加行级锁，读完释放，避免脏读；
    - **可重复读（RR）**：查询加快照读（MVCC），更新加行级锁 + 间隙锁，避免不可重复读和幻读；
    - **串行化（Serializable）**：全表加锁，串行执行。

    ## 2.你如何实现 MVCC 和 2PL，两者如何配合确保事务隔离性？

    我们结合了**MVCC** 和 **两阶段锁协议（2PL）** 来实现并发控制和事务隔离。

    - **MVCC：\**为每条记录维护多个版本（写入时间戳 + 删除时间戳），读操作基于事务启动时的快照时间戳进行\**可见性判断**，避免读写冲突。
    - **2PL：**所有写操作必须获得写锁，锁管理器基于图结构维护加锁顺序，确保无冲突的串行调度。
    - **两者配合：**
      - **读操作走 MVCC，非阻塞（Snapshot Read）**
      - **写操作基于 2PL 上锁（Exclusive Lock）**
      - 事务提交前统一写日志 + 写入版本链
      - 可配置事务隔离级别（Read Committed, Repeatable Read）

    这种设计兼顾了**高并发读性能（通过 MVCC）\**与\**写入一致性保证（通过 2PL）**，可以支持 SQL 标准的事务隔离模型。

    3.

    # 网络编程

    ## 1.在 “MinaDB - 自研轻量级数据库系统” 项目里，你实现了基于 Java NIO 的数据页读写管理模块，提升了 3 倍访问效率，讲讲 Java NIO 是咋在这个模块里发挥作用的，和传统 I/O 相比，具体优化点在哪呀？

    BIO 与 NIO 的区别：

    **BIO（Blocking I/O）**：每个请求需要一个线程处理，线程阻塞在 I/O 操作上，连接数一多就容易造成线程资源耗尽，系统响应慢。

    **NIO（Non-blocking I/O）**：通过 **Selector + Channel + Buffer** 实现多路复用，单线程可监听多个 Channel，避免大量线程阻塞等待，提高了资源利用率。

    NIO 工作机制：

    - 客户端连接通过 `ServerSocketChannel` 接收；
    - 每个 `Channel` 注册到 `Selector` 上，监听感兴趣的事件（如 `READ`、`WRITE`）；
    - Selector 使用 `select()` **非阻塞轮询**就绪事件；
    - 当某个 Channel 有事件到达，就通过 `Buffer` 读写数据，由工作线程处理请求。

    这种模型的优势是：**少量线程可处理高并发请求**，适合 I/O 密集型场景。

    数据库应用：

    数据库系统天然是多并发场景，传统 BIO 每个连接对应一个线程，会造成线程浪费甚至上下文切换频繁；

    使用 NIO 模型后，我们**采用 Reactor 模式**，用**一个主线程监听所有连接事件**，用线程池异步处理真正的读写请求；

    每个客户端连接通过 Channel 注册到 Selector 上，提升了连接并发处理能力；

    底层页式读写通过 Buffer 显著减少了系统调用次数和数据拷贝成本，提高了磁盘 I/O 效率。



    在我们 MineDB 项目中，使用了 NIO 的非阻塞 SocketChannel 与 Selector 结合，实现高效的连接处理。具体流程是：主线程监听所有连接事件（如 Accept、Read），一旦某个 Channel 可读，即触发事件处理逻辑，从 SocketChannel 读取数据写入 ByteBuffer，再进行解析与调度。



    并发控制说明：

    因为是数据库系统，多用户可能同时对同一数据页进行访问；

    在读写路径上，我们结合了**读写锁**机制和自实现的**MVCC（多版本并发控制）**，确保事务隔离的一致性；

    NIO 负责连接层的高效事件处理，MVCC 负责数据访问层的并发安全。



    # SQL

    ## 1.在 “MinaDB” 项目中，你实现了 SQL 解析器模块，将 SQL 语句转换为执行计划。如果遇到复杂查询（如多表 JOIN、子查询），解析器是如何处理语法树构建和优化的？有没有遇到过解析错误的场景，是如何调试和解决的？

    普通分析：

    整个sql解析过程分为三个阶段：

    词法分析：：：：

    我们使用正则表达式 + 手写有限状态机（手写有限状态机就是用代码明确写出“当前状态 + 输入 → 转移 + 处理”的逻辑流程）实现了一个轻量级的词法分析器，将输入 SQL 拆分成 Token 序列（如关键字、标识符、常量、运算符等）。每个 Token 类型都有枚举定义，便于后续语法分析器使用。

    [SELECT] [IDENT(name)] [FROM] [IDENT(users)] [WHERE] [IDENT(age)] [>] [NUMBER(18)]

    1
    2
    3
    4
    5
    6
    7

    语法分析：：：：

    我们基于递归下降（Recursive Descent）实现了手写语法分析器，根据文法规则（Backus-Naur Form）构建**抽象语法树**（AST）。

    例如 `SELECT-FROM-WHERE` 子句会被解析为如下结构：

    SelectNode
    ├── Projection: [name]
    ├── From: TableNode(“users”)
    └── Filter: BinaryExpr(age > 18)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11

    逻辑执行计划生成：：：：

    AST 会被转化为内部统一表示的 **LogicalPlan**，包括 `Scan`, `Filter`, `Project`, `Join`, `Aggregate` 等操作节点。这个计划结构便于后续执行器调度和优化器优化。

    多表查询：

    **JOIN 查询**

    当语法分析器检测到 `JOIN` 或 `LEFT JOIN` 等关键字时，会构建一个 `JoinNode`，将左右子表作为子节点，同时捕获 `ON` 条件表达式作为连接条件。

    SELECT * FROM A JOIN B ON A.id = B.a_id

    1
    2
    3

    构建的AST为

    JoinNode
    ├── Left: TableScan(“A”)
    ├── Right: TableScan(“B”)
    └── Condition: A.id = B.a_id

1
2
3
4
5

此结构可以支持后续优化器决定使用嵌套循环连接（Nested Loop Join）还是哈希连接（Hash Join）。

**子循环嵌套**

SELECT name FROM users WHERE id IN (SELECT user_id FROM orders)
```

这种情况，解析器会递归调用自身处理内部子 SELECT，并将其嵌套成 SubqueryExpr，插入到父语句的 WHERE 条件表达式树中。

异常处理:

如关键字拼写错误、括号不匹配、非法表达式等，解析器通过异常机制抛出带位置信息的错误，并记录 Token 序列以便定位。

调试方式：

  • 打印词法 Token 序列
  • 可视化 AST 结构（使用简易 tree dump 工具）
  • 增加行列号定位信息

曾遇到过解析器处理 SQL 文件时出现乱码，调查后发现部分文件编码为 GBK，解析器默认以 UTF-8 解读导致失败。解决方法是在读取输入流时统一使用 UTF-8 编码，并在 SQL 入口统一处理 BOM 头和非法字符替换。

错误恢复机制

在早期版本中，解析器一旦遇错就直接中断，影响批量 SQL 执行。后来加入了简单的错误恢复机制，例如：

  • 跳过非法 Token，尝试恢复到下一个合法语句起点（如分号 ;）
  • 将错误信息记录而不立即终止，提高系统健壮性

死锁

1.你实现的是哪种死锁检测方式？如何中止事务？

死锁的四个条件：

条件 说明
互斥条件 资源一次只能被一个事务占用
请求与保持条件 一个事务持有资源的同时申请新的资源
不剥夺条件 已获得的资源不能被强制剥夺
循环等待条件 若干事务之间形成循环等待链

我们实现的是基于等待图（Wait-For Graph）的死锁检测机制：

  • 每次事务申请锁失败时，记录依赖关系 T1 → T2
  • 定期运行死锁检测器，对等待图进行有向环检测
  • 一旦发现环，选择最小代价事务（如等待时间短、操作数少）回滚中止
  • 通知锁管理器释放锁资源，唤醒相关等待事务

这种方式可以有效防止系统进入长时间互相等待状态，尤其在高并发写场景下非常关键。

设置锁等待时间上限（如 3 秒），超过即触发检测；