21. KVStore 版本五 B+树并发总结&梳理（二）
B+树并发总结&梳理（二）1.test_16 测试函数 分析1.1 测试函数代码：1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465// ========== test 16. 并发读写一致性测试 =======/** * - 场景：多线程混合执行 PUT 和 SEARCH 操作 * - 目的：验证 Root Latch 是否能有效防止 B+ 树在并发修改时发生段错误 */void* worker_thread(void* arg) { worker_arg* w = (worker_arg*)arg; long val_out; unsigned int seed = time(NULL) ^ (w->id * 7919); for (int i = 0; i < THREAD_OPS; i++) { // ...
Hello World
Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub. Quick StartCreate a new post1$ hexo new "My New Post" More info: Writing Run server1$ hexo server More info: Server Generate static files1$ hexo generate More info: Generating Deploy to remote sites1$ hexo deploy More info: Deployment
20. KVStore 版本五 B+树并发总结&梳理（一）
B+树并发总结&梳理（一）1 为什么要给 B+ 树加锁在单线程环境下，B+ 树的插入、删除、查找操作可以顺序执行，不会出现任何问题。但是在实际系统中，例如数据库或者存储引擎，多个线程可能同时访问同一棵 B+树。如果没有任何并发控制机制，就会产生严重的问题。 简单来说： 加锁的目的，就是保证 B+ 树在多线程环境下的结构一致性和内存安全。 如果没有锁，会发生什么？ 并发插入导致结构损坏 - 数组越界等 并发分裂导致树结构错误 - 指针问题导致段错误 读写冲突 - 访问已释放的阶段（段错误） 最简单的方案：全局锁给整棵树加一把锁：pthread_mutex_t tree_lock 每次操作： 123pthread_mutex_lock(&tree_lock);bptree_insert(tree, key);pthread_mutex_unlock(&tree_lock); 这样可以保证：同一时间只有一个线程操作 B+ 树 优点： 实现简单，不易出错 缺点： 并发性能极差，只有一个线程在工作所有线程都...
19. KVStore 版本五 B+ 树并发删除：函数调度全流程
B+ 树并发删除：函数调度全流程1. 入口与锁初始化：bptree_delete这是整个操作的“指挥官”，它负责初始化环境。 **动作：**创建空栈bptree_write_path path。 **状态决策：**调用bptree_find_leaf_delete_safe。 2.渗透加锁阶段：bptree_find_leaf_delete_safe这是整个并发处理最核心的过滤环节。 流程： 锁住root_lock → 锁住root->latch(WRLock) → 释放root_lock。 **循环向下：**锁住子节点next->latch。 安全判断： **若子节点“丰满”：**调用bptree_unlock_all_in_path(path)。这会释放当前节点以上的所有锁，并清空栈。大大提升了并发度，因为后续操作只锁定了这棵子树。 **若子节点“危险”：**不解锁，继续持有父锁，向下走（悲观策略）。 **结束状态：**返回叶子节点指针，此时path栈中记录了从“最后一个安全节点”到“叶子”的所有 WRLock。 3.局部修改阶段：bptree_d...
18. KVStore 版本五 B+ 树并发删除全景图
B+ 树并发删除梳理第一阶段：悲观查找与“安全释放”函数：bptree_find_leaf_delete_safe这是并发删除的起点。为了防止死锁，必须自上而下加锁 **全局入口锁：**首先通过 tree->root_lock 找到当前的根节点 123456struct _bptree { bptree_node* root; // == 入口指针锁 == pthread_mutex_t root_lock;}; 蟹行加锁 (Crabbing): 锁住parent,再锁住child。 **核心决策（早释放）：**如果child节点是丰满的，（即key_count > MIN_KEYS）,意味着即便在该子树发生删除，也不会导致parent节点发生合并或缩减。 **执行弹栈：**一旦发现child安全，立即调用bptree_unlock_all_in_path。这会释放从根节点到该child上方所有的锁。 最终状态：当函数返回时，path栈中仅保留了可能受删除影响的最少节点集合（通常只有叶子及其父节点）。 第二阶段...
17. KVStore 版本四 🔟 状态机
🔟 状态机1. 函数集合12345678static int kvstore_transit_state();static int kvstore_enter_recovering();static int kvstore_enter_ready();static int kvstore_enter_failed();static int kvstore_enter_compaction();static void kvstore_exit_compaction();static void kvstore_apply_state();static int kvstore_fatal(); 2. 函数复盘 + 规范注释2.1 static int kvstore_transit_state()123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354/** * kvstore_transit_state - 执行安全的状态切换 * * @d...
16. KVStore 版本四 9️⃣ Snapshot / Compaction
9️⃣ Snapshot / Compaction1. 函数集合123456static void kvstore_maybe_compact();int kvstore_compact();static int kvstore_compact_internal();static int compact_write_cb();static int snapshot_write_cb(); 2. 函数复盘 + 规范注释2.1 static void kvstore_maybe_compact()12345678910111213141516171819202122232425262728293031323334/** * kvstore_maybe_compact - 监控系统负载并自动触发日志压缩 * * 采取基于容量（Size）和频率（Ops）的双重触发机制策略。 * * 设计说明： * - compaction 属于维护行为，不影响 PUT / DEL 正确性 * - 即使 compaction 失败，WAL 仍然可保证数据安全 */static void k...
15. KVStore 版本四 8️⃣ 内存变更 Apply 层
8️⃣ 内存变更 Apply 层1. 函数集合1234static int kvstore_apply_put();static int kvstore_apply_del();static int kvstore_apply_put_internal();static int kvstore_apply_del_internal(); 2. 函数复盘 + 规范注释2.1 static int kvstore_apply_put()12345678910111213141516171819/** * kvstore_apply_put - 将数据变更最终应用到内存索引（B+ 树） * * - 该函数是纯净的。它假设所有的准入控制（状态，日志，权限）已经在上层完成 * - 它同时用于普通写路径和 WAL 重放 */static int kvstore_apply_put(kvstore* store, int key, long value) { // 1. 安全基石 if (!store) return KVSTORE_ERR_NULL; // ...
14. KVStore 版本四 7️⃣ 原子执行路径
7️⃣ 原子执行路径1. 函数集合1234static int kvstore_exec_write();static int kvstore_replay_put();static int kvstore_replay_del();static int kvstore_state_allow(); 2. 函数复盘 + 规范注释2.1 static int kvstore_exec_write()123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869/** * kvstore_exec_write * - 原子写入路径：统筹协调日志持久化与内存索引更新 * * 通过状态机 kvstore_state_allow 进行准入控制 *设计意图： kvstore_put ─┐ ├─ wal ├─ apply ...
13. KVStore 版本四 6️⃣ WAL 写入
6️⃣ WAL 写入1. 函数集合12static int kvstore_log_put();static int kvstore_log_del(); 2. 函数复盘 + 规范注释2.1 static int kvstore_log_put()12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849/** * kvstore_log_put - 将写入操作持久到 WAL 日志文件 * * 设计定位： * - WAL 层函数 * - 只负责“把一次 PUT 操作顺序写入磁盘日志” * - 不修改内存结构，不调用 B+ 树 * * 日志格式 * PUT <key>|<crc32>\n * * 执行流程： * 1. 校验日志文件是否已打开 * 2. 构造日志内容字符串 * 3. 计算 CRC32 校验值 * 4. 写入日志文件并强制刷盘 * 5. 更新日志统计信息（大小 / 操作次数） * * snprintf...