第四篇论文 定义
Definitions：核心定义与证明 (C 部分) Definition 1：p-QDG p-QDG 是这篇论文的基础模型。 给定： 1r1 > r2 > ... > rp > 0 表示 p 种通信模式的通信半径。 两个节点之间距离越近，可用通信模式越多，边也越多。 例如 $p=3$ 时： 1234567891011dist(x,y) > r1：无边r2 < dist(x,y) ≤ r1：1 条边r3 < dist(x,y) ≤ r2：2 条边0 < dist(x,y) ≤ r3：3 条边 所以 p-QDG 是多重图。 Definition 2：Independent nodes 如果两个节点距离大于最大通信半径： 1dist(u,v) > r1 则它们相互独立。 也就是： 1两个节点之间没有任何通信模式对应的边 Lemma 1：独立邻居数量上界 Lemma 1 说明： 对任意节点 $u$，与 $u$ 相邻且彼此独立的节点数量不超过 5。 这是一个几何上界，后面会用于近似比证明。 你可以把它理解为： 在一个半径为...
第四篇论文 - 相关定义
一、测试说明 这篇文章用于测试 Hexo 博客中第四篇论文阅读笔记的显示效果，主要包括标题层级、文字内容、代码块以及公式显示等内容。 后续关于第四篇论文的阅读记录、算法理解、定义整理和实验复现内容，都可以放在当前目录下进行管理。 二、论文阅读内容测试 在无线传感网中，虚拟骨干网通常可以通过连通支配集（Connected Dominating Set，CDS）进行建模。网络中的普通节点可以通过骨干节点完成消息转发，从而减少全网广播带来的通信开销。 如果进一步考虑网络的容错能力，则需要构造具有更高连通性的虚拟骨干结构。例如，当骨干网络中任意一个节点失效后，剩余骨干节点之间仍然保持连通，则该骨干可以具有一定的容错能力。 三、公式显示测试 设原始网络图为： $$ G = (V, E) $$ 其中，$V$ 表示节点集合，$E$ 表示通信边集合。 若节点集合 $C \subseteq V$ 是一个连通支配集，则需要满足两个条件： 支配性：任意节点 $v \in V - C$，至少存在一个邻居节点属于 $C$； 连通性：由 $C$ 诱导出的子图 $G[C]$ 是连通图。 四、代码块显示测试...
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++) { ...
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.局部修改阶段：bptr...
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 - 执行安全的状态切换 * *...
16. KVStore 版本四 9️⃣ Snapshot / Compaction
9️⃣ Snapshot / Compaction 1. 函数集合 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 kvs...
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 ...