数据库文档数据库后端【免费下载链接】couchdbSeamless multi-primary syncing database with an intuitive HTTP/JSON API, designed for reliability项目地址https://gitcode.com/gh_mirrors/co/couchdb点击查看免费下载导读本文以 CouchDB 官方 RFCsrc/docs/rfcs/012-fdb-reduce.md为核心深入剖析在 FoundationDBFDB之上实现 reduce 索引的三种候选方案并重点讲解被选中的跳跃表Skip List算法——包括索引的创建、查询、更新流程、FDB 数据模型以及附录中可运行的 JavaScript 原型实现。读完本文你将理解 CouchDB 为何难以在 FDB 上复刻 B 树的 reduce 聚合能力、跳跃表如何解决group_level与startkey/endkey查询的聚合问题以及这一设计在真实代码中的落点如couch_mrview的参数校验与couch_views的未来规划。背景Reduce 索引为何难在 FoundationDB 上实现CouchDB 的 reduce 视图允许用户基于 map 函数产出的 key/value 执行聚合_count、_sum、_stats、_approx_count_distinct或自定义 reduce 函数。当前实现中每个 map/reduce 索引内部以 B 树存储非叶节点保存其子节点结果的聚合值因此可以高效检索任意层级的聚合结果。FoundationDB 是分布式键值存储其数据模型是全局有序的 key-value 空间与事务 API无法原样复刻 B 树的非叶节点聚合行为。RFC 因此提出了三种候选方案最终选择了跳跃表Skip List路线。三种候选方案对比Option 1查询时即时计算On the fly reduce最简单的方案查询 reduce 视图时直接读取 map 索引边从 FDB 抓取 key 边执行 reduce 聚合。优点实现成本最低几乎不需要额外存储结构。致命缺陷查询性能随数据库和索引规模增长持续恶化最终可能达到reduce 查询直接不可用的程度。这一方案本质上放弃了预聚合每次查询都要做全量扫描仅适合作为退路或极小型索引的兜底。Option 2预计算所有 group 层级Precompute of all group-levels为每个 reduce 函数预计算所有group_level的结果以 key/value 形式存入 FDB查询时直接读取。优点查询极快结果已预先算好。困难一更新对内建_sum、_count可以一次计算、套用到所有层级但对自定义 reduce 函数、以及_stats尤其是min/max和_approx_count_distinct更新每个 group 层级必须先读取该层级下所有 key、对全部 group 层级跑一遍 reduce、再写回 FDB成本极高。困难二范围查询带startkey/endkey的查询很昂贵——必须对 startkey 与 endkey 两个 key 区间分别做聚合尤其group_level 0配合 startkey/endkey 时需要对区间内全部 key 做完整聚合同样是高成本操作。Option 3跳跃表Skip List实现 —— 最终选择跳跃表可以理解为分层链表最底层Level 0包含索引中的全部元素每往上一层元素数量按比例缩减RFC 原文戏称 a reduced (pun intended) number of elements。相比 Option 2跳跃表让startkey/endkey查询更容易且对所有类型的 reduce 函数更新索引都更高效因此被选为最可行方案。Figure 1一个简单的跳跃表布局——Level 0 包含全部元素 1~5逐层向上元素按规则缩减1、3、5 → 1、3 → 1。跳跃表实现细节RFC 用一个具体的设计文档贯穿始终演示如何创建、查询、更新 reduce 索引{ _id: _design/reduce-example views: { example: { map: function (doc) { emit([doc.year, doc.month, doc.day], 1); }, reduce: _count } } }该视图 emit 出的 key/value 结果供 reduce 使用如下[2017, 03, 1] 1 [2017, 04, 1] 1 [2017, 04, 1] 1 [2017, 04, 15] 1 [2017, 05, 1] 1 [2018, 03, 1] 1 [2018, 04, 1] 1 [2018, 05, 1] 1 [2019, 03, 1] 1 [2018, 04, 1] 1 [2018, 05, 1] 1注RFC 原文数据中有两处疑似笔误如views缺少冒号、[2019, 04, 1]等键与上下文不一致引用时请以逻辑意图为准。创建Create构建跳跃表时所有 key 先加入 Level 0。当多个文档 emit 相同 key 时先对这些 value 做 re-reduce即reduce 的 reduce再写入 Level 0。之后每一层向上都会缩减 key 的数量每个高于 Level 0 的层级若某 key/value 未被加入该层则该 key 的 value 会与这一行中前一个节点聚合因此每个层级中每个节点的值等于它自身在 Level 0 的 key/value加上上一个层级中大于该节点、且小于该层下一个节点的所有 key/value的聚合。下图是上例 key 加入跳跃表后的形态Figure 2上例中 emit 的 reduce 键加入跳跃表后的层级分布——Level 0 为全部日期键Level 1~4 依次聚合为更粗粒度的月度年度乃至全局聚合如顶层0 9表示全部数据的_count总和。跳跃层级与分布算法Skip Levels and Level Distribution跳跃表的层级数设计为可配置最佳层级数将通过性能测试确定。key 在各层级的分布算法如下const MAX_LEVELS 6; const LEVEL_FAN_POW 4; // 2^X per level or (1 / 2^X) less than previous level const hashCalc (key, level) { const keyHash hashCode(JSON.stringify(key)); const out (keyHash ((1 (level * LEVEL_FAN_POW)) - 1)); if (out ! 0) { return false; } return true; }hashCode将 key 哈希为整数从而在各层级间获得一致、可预测的分布LEVEL_FAN_POW同样可配置它决定每上升一层保留多少比例的节点2^X分之一。查询Query结合 Figure 2group true直接使用 Level 0 返回全部精确 keygroup_level 0无 startkey/endkey 时直接使用最高层级全局聚合group_level 1需要遍历跳跃表并聚合结果后再返回。以group_level 2为例见 Figure 3从 Level 4 开始下降到 Level 3 比较节点0与节点[2018, 03, 1]——二者在group_level 2下不是同一 key于是继续下移层级重复比较当前节点与下一节点是否为同一分组 key直到找到匹配节点或到达 Level 0。到达[2017, 03, 1]后返回而在[2017, 04, 1]处可以回升到 Level 2比较[2017, 04, 1]与[2017, 04, 15]——两者同属[2017, 04]分组于是继续在 Level 1 收集所有[2017, 04, x]键收齐后统一跑一遍 re-reduce 再返回。这一比较当前节点与下一节点、相同时尝试向上一层、不同时用下一层节点横向移动的流程持续到查询结束。Figure 3group_level 2查询的遍历路径——顶层快速定位后向下钻取、同分组内横向收集红色箭头最后对收集到的键做 re-reduce。带startkey/endkey的查询流程类似从最高层开始横向遍历直到超过 startkey再向下移动找到 startkey 或距离它最近的节点随后按上述流程遍历直到到达大于等于 endkey 的节点为止。更新Update更新 reduce 索引时复用 map id 索引记录哪些 key 与哪个文档关联删除文档先从 Level 0 移除该文档关联的 key。若 reduce 函数是_sum或_count则对 Level 0 以上所有曾包含这些 key 值的节点执行原子更新对于无法原子更新的 reduce 函数每个高于 Level 0 的层级都要取该节点下方一层中参与计算该节点聚合值的所有 key/value → re-reduce 出新值 → 写回 FDB。更新文档先按删除流程移除不再 emit 的旧 key再把新 key 加入 Level 0Level 0 以上按同一分布算法决定 key/value 是否加入该层——若加入则聚合该节点之后、下一层的节点来计算自身聚合值同时重算前一个节点的值一直处理到最高层_sum/_count走原子更新其他 reduce 走 re-reduce若新 key/value 未被加入该层则其 value 与该层中小于该 key 的节点聚合。多文档 emit 相同 key这些 key 在写入 FDB 前先做 re-reduce。FoundationDB 数据模型跳跃表方案在 FDB 中的 key/value 数据模型如下{database, ?DB_VIEWS, Sig, ?VIEW_REDUCE_SK_RANGE, ViewId, SkipLevel, ReduceKey} {UnEncodedKey, Value} SkipLevel 0..?MAX_SKIP_LEVEL各字段含义database具体数据库命名空间?DB_VIEWS视图命名空间Sig设计文档的视图签名View Signature?VIEW_REDUCE_SK_RANGEreduce 命名空间ViewId设计文档中某个视图的 idSkipLevel该 key/value 所在的跳跃层级0..?MAX_SKIP_LEVELReduceKey编码后的 emit 键RowType指示该行存储的是 emit 的 key 还是 valueUnEncodedKey未编码的 emit 键Value这些 emit 键对应的 reduce 值。Value 中同时保存 reduce 值与非编码 key以便查询时直接返回。附录 A 提供了完整的 JavaScript 参考实现见下文。附录 A可运行的 JavaScript 原型实现RFC 附录给出了一段基于 Node.js foundationdb驱动包的跳跃表原型原始完整代码约 1096 行位于 RFC 文档附录也可从作者的fdb-skiplist-reduce仓库克隆运行。原型做了如下简化假设所有 key 均为[Year, Month, Day]数组仅实现startkey/endkey未实现删除是确保创建/更新/遍历逻辑正确的基础实现不覆盖边界情况与错误处理。本地运行方式npm install foundationdb node skiplist.js核心常量与数据结构const PREFIX skiplist; const MAX_LEVELS 6; const LEVEL_FAN_POW 1; // 原型中实测采用较小的扇出值 const END 0xFF; fdb.setAPIVersion(600); // 必须在打开数据库前调用 const db fdb.openSync() .at(PREFIX) // 所有操作的数据库前缀 .withKeyEncoding(fdb.encoders.tuple) .withValueEncoding(fdb.encoders.json); // 数据模型 // (level, key) reduce_value原型中几个关键函数的设计与 RFC 正文完全对应hashCalc(key, level, pow)判定 key 是否加入某一层insert(tn, key, value)Level 0 永远插入已存在则 re-reduce 后覆盖高层若hashCalc为真则插入该层并重算前驱节点值与自身聚合值用下一层区间getRange的 value 做 re-reduce否则把新值 re-reduce 进前一个节点getNextRangeAndLevel(...)traverse(...)决定在哪个层级、哪个区间扫描收集同分组键后collateRereduce聚合再以区间末尾作为下一轮 startkey 继续遍历直到到达 endkeyquery(opts)分别处理groupLevel 0 精确返回、group_level 0且无 startkey/endkey最高层直接出全局聚合、以及一般group_level走遍历print()校验每一层的 levelTotal 必须等于 Level 0 的 total——这正是跳跃表聚合不变量每层节点值的总和恒等于全量数据的总和是原型的正确性自检手段simpleQueries()/largeQueries()用assert.deepEqual验证查询结果并将跳跃表查询结果与纯 Level 0 全量扫描结果queryLevel0做交叉对比。作者在运行原型后记录了两条实测结论插入时间不随跳跃表增长而变差——即使跳跃表不断变大单条 key 的插入耗时保持稳定较小索引百万行以下更适合较低的LEVEL_FAN_POW——否则大多数 key 会停留在 Level 0 和 Level 1高层级形同虚设查询无法利用跳跃优势但代价是插入会略慢。方案的优势与劣势优势Advantages跳跃表既可支持内建 reduce也可支持自定义 reduce 函数相比 Option 2预计算所有层级更新索引对所有 reduce 类型都更高效相比 Option 1即时计算查询不需要全量扫描可通过高层级快速跳过。劣势Disadvantages由于层级是哈希随机生成的、各层节点值为聚合值与 B 树相比查询时在较低层级的遍历次数会增多本质上是用更多指针跳跃换取预聚合的权衡。关键变更Key Changes不再使用 B 树存储 reduce 聚合而是在 FoundationDB 之上用类跳跃表算法实现 CouchDB 的 reduce 功能。与当前仓库代码的对应关系RFC 是面向未来 FDB 重构的设计提案其提及的couch_views模块在该仓库中尚未实现相关 RFC 见 src/docs/rfcs/008-map-indexes.md 中couch_mrview 将被新的 couch_views OTP 应用取代的规划。当前仓库中与本文主题最直接相关的实现位于couch_mrview应用src/couch_mrview/src/couch_mrview_util.erl 中的validate_args/1与determine_group_level/1L563-L713实现了 RFC 查询语义在现有 B 树实现中的参数约束groupfalse与group_level0互斥L709-L710、reduce 视图多 key 查询必须grouptrueL576-L584、group_level必须 0L634-L640等。这些语义正是 RFC 中group、group_level、startkey/endkey讨论对应的 HTTP 查询参数src/couch_mrview/src/couch_mrview_util.erl 展示了现有 B 树路径的 reduce 聚合实现couch_btree:full_reduce/1、couch_btree:fold_reduce/4、final_reduce/2可作为对比参照RFC 正是要把这些非叶节点聚合能力迁移到 FDB 的跳跃表模型上src/couch_mrview/src/couch_mrview.erl 的validate_ddoc_fields/1校验设计文档中视图的map与reduce字段类型对应 RFC 示例设计文档的合法形态。结论012-fdb-reduceRFC 为 CouchDB 迁移到 FoundationDB 时如何保留 reduce 能力给出了完整的技术路线放弃查询时全量计算与预计算所有层级两种低效/笨重方案采用跳跃表作为 reduce 索引的核心数据结构并配套给出层级分布算法、创建/查询/更新流程、FDB key-value 数据模型与一份可运行的 JavaScript 原型。该设计同时覆盖了group、group_level、startkey/endkey等 CouchDB 视图查询的全部核心语义且不需要任何 HTTP API 变更RFC 明确不会有 HTTP API 新增或弃用安全影响方面也未识别出问题。对于关注 CouchDB FDB 化路线图的读者这份 RFC 与其姊妹篇如 008-map-indexes.md、016-fdb-replicator.md共同勾勒出下一代 CouchDB 存储引擎的蓝图。赞分享数据库文档数据库后端【免费下载链接】couchdbSeamless multi-primary syncing database with an intuitive HTTP/JSON API, designed for reliability项目地址https://gitcode.com/gh_mirrors/co/couchdb点击查看免费下载相关推荐500 AI Agent 项目案例库五分钟跑通源码框架选型一篇讲清500 AI Agent 项目案例库五分钟跑通源码框架选型一篇讲清 选型调研最耗人的地方往往不是读某一个 demo而是要把几十个案例一条条翻出来比。5数据库文档数据库后端跳表Skip List详解Swift 中的概率型有序数据结构实现跳表Skip List详解Swift 中的概率型有序数据结构实现 跳表Skip List是一种概率型数据结构用多层有序链表近似替代平衡树实现 O示例工程教程Apache CouchDB 的 FoundationDB 序列索引设计_changes 数据模型、索引维护与访问模式深度解析Apache CouchDB 的 FoundationDB 序列索引设计_changes 数据模型、索引维护与访问模式深度解析 本文基于 Apache Cou数据库文档数据库后端上一篇微信好友关系检测终极指南3步快速识别谁已删除或拉黑你下一篇三步搞定Steam游戏清单Onekey终极指南让你轻松解锁游戏库创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考