尧图网站开发 
不要被Redis 作者的新项目带偏antirez 的 ds4 到底在做什么值得我们学什么Redis 作者 Salvatore Sanfilippo网名 antirez最近在 GitHub 上活跃起来这次他不是在维护 Redis而是开了一个名为ds4的新仓库。在很多技术群里这个话题引发了一个非常典型的误读antirez 要写一个替代 Redis 的新数据库了。这个判断基本不成立。ds4并不是要再造一个 Redis也不是要挑战什么基础设施它更像是一个资深系统程序员回归 C 语言、用最朴素的方式重新整理数据结构的练习与分享。真正值得关注的是为什么一个写出了 Redis 这种顶级中间件的人会回头去写跳表、链表、布隆过滤器这些基础到不能再基础的东西本文会先讲清楚ds4是什么、不是什么然后分析它背后的设计哲学再给出可落地的 C 语言示例让你能自己把项目拉下来编译运行最后聊聊这个项目对普通开发者的价值在哪里、哪些地方需要理性看待。1. 这篇文章真正要解决的问题国内技术社区对 antirez 的关注度一直很高毕竟 Redis 几乎是后端开发的标配。当他发布新项目时很容易出现两种极端反应一种是把项目捧成Redis 继任者架构新范式另一种则是看到项目标题里的 Data Structures觉得不就是大学课设吗有什么好写的。这两种反应都偏离了项目本身。ds4的价值恰恰集中在三个层面第一编码风格。antirez 在 Redis 社区以代码写得清清爽爽著称。他的 C 语言风格强调可读性、命名直观、结构克制。看ds4的代码就像在翻一位工程师的笔记本而不是读一本教科书。第二设计取舍。每个数据结构在 Redis 内部都有特定的应用场景抽出来重新实现时需要做大量简化、取舍和接口设计。这个思考过程比代码本身更有学习价值。第三编程心态。antirez 明确表示做这个项目是为了乐趣和学习而不是为了生产。这种心态在如今每个项目都恨不得做成平台的氛围里非常少见。读完这篇文章你会掌握ds4到底是什么、它的边界在哪里。为什么 antirez 要做这个项目它的设计理念是什么。如何拉取源码并在本机编译运行。仿照ds4的思路如何自己写一个跳表和布隆过滤器的最小 C 语言实现。实际项目中哪些东西可以借鉴哪些东西要保留谨慎。2. antirez 是谁为什么他写的 C 代码值得关注在很多入行较晚的开发者眼里antirez 可能只是Redis 的作者。但这个名字背后的分量得稍微展开一下。antirez 是意大利人早年以写嵌入式软件和 Web 应用为生后来因为兴趣开发了 LVM一种虚拟机监控脚本工具再后来为了做实时 Web 项目写了一个远程字典服务这就是 Redis 的起点。Redis 后来有多成功大家都知道它成了内存数据库的事实标准几乎每个互联网公司都在用。更夸张的是Redis 的核心代码长期保持得非常短小精悍一个几千行 C 文件就是一套完整的高性能存储引擎。antirez 的编程风格有几个鲜明特点不堆抽象。Redis 里的数据结构就是直来直去的实现很少搞多层封装。命名追求直观。变量名和函数名一看就知道意图。重视局部性。代码逻辑尽量集中在一个文件里而不是散落到几十个小文件中。性能服务于场景。做优化之前先问这个操作在这个场景下真的会是热点吗。这些特点不一定都符合大厂工程化的口味但非常适合学习。你在学习 C 语言或数据结构时如果一开始就读非常复杂的工业级源码很容易迷失而读 antirez 的代码会觉得原来 C 语言可以写得这么干净。ds4就是这个风格的最新载体。它不是 Redis 的一部分也不是 Redis 的延续而是独立的小项目——可以把它理解成 antirez 的数据结构笔记本。3. ds4 到底是什么以及它不是什么先给出结论ds4是 antirez 用 C 语言实现的一组数据结构的集合项目用于教学、演示和自娱自乐。名字里的 ds 是 Data Structures 的缩写4 可以理解为第四版或新一版含义并不神圣。从项目仓库的公开信息和 antirez 的发布说明来看ds4目前主要包含一些常用数据结构例如跳跃表skiplist、布隆过滤器bloom filter、链表、字典等。这些数据结构并不稀罕任何一本算法书上都有antirez 的贡献不在于发明新结构而在于用他的方式重新实现了一遍并让代码保持足够简单方便他人阅读和修改。它不是 Redis 的替代品。Redis 是一个完整的网络服务有协议解析、事件循环、持久化、复制、集群、内存分配器管理等等。ds4里的数据结构只是 Redis 内部各类数据结构的一个子集拿出来重新实现并不包含任何网络层、持久化层的东西。它不是一个新的业务框架。它没有任何配置系统、插件系统、API 网关之类的概念。它就是一个 C 语言库你可以在自己的程序里链接它也可以把它当作源码阅读对象。它不是学术研究的产物。里面不会有大段论文引用不会有复杂的渐进复杂度证明也不会有验证了某种理论的结论。它更接近一位老程序员在周末写了几百行 C然后把源码分享出来的状态。那它为什么值得关注因为当一个经验极其丰富的人用最简单的工具来做一件简单的事情时他的取舍就特别有参考价值。这里有一个非常重要的观点简单事情做到极致比复杂事情做得庞大更能体现一个工程师的水平。4. 与 Redis 内部数据结构的对照一个更熟悉的坐标系要理解ds4最好的坐标系就是 Redis 源码里已经存在的数据结构。因为 antirez 对这些结构的理解最初就是在 Redis 的开发过程中建立起来的。4.1 跳表skiplistRedis 的有序集合ZSet在元素数量较大、元素是字符串时底层使用跳表 字典的组合。跳表的核心思想是多层链表通过空间换时间让查找、插入、删除的时间复杂度都接近 O(log n)。在ds4中跳表重新以一个轻量库的形式出现。和 Redis 内部版本相比它砍掉了和命令解析、内存编码、持久化有关的逻辑只保留最核心的跳表操作。4.2 布隆过滤器布隆过滤器是一种概率型数据结构用来判断某个元素一定不存在或者某个元素可能存在。它最典型的应用是防止缓存穿透在查询数据库之前先用布隆过滤器快速过滤掉肯定不存在的 key。Redis 本身通过模块RedisBloom支持布隆过滤器内核里没有直接内置。antirez 在ds4中单独实现了它代码量通常非常小可能只要一两百行。4.3 链表和字典Redis 里的链表和字典都经过精心打磨。链表用于列表键的早期版本后来被快速链表替代字典用于哈希键和数据库键空间。ds4中重新实现了这些基础结构但遵循同样的宁可简单不要复杂原则。这个对照关系告诉我们一件事你在ds4中看到的每个结构几乎都能在 Redis 内部找到原型。读ds4等于拿到了 Redis 源码的简化导读版。5. 设计哲学为什么 antirez 强调代码是给人读的antirez 在多个场合表达过类似观点代码首先是给人读的其次才是给机器执行的。这个观点听起来像老生常谈但真正做起来非常难。在ds4中这种哲学体现在几个具体的地方第一函数命名非常直白。你不会看到像x_calc_impl_v2这种名称更多的可能是skiplist_insert、bloom_add这种一眼能看懂的命名。命名上的克制不是偷懒而是对读者负责。第二文件组织不追求工程规范到病态的程度。一个很小的项目也用五层目录、十几个抽象接口反而会增加阅读成本。ds4的做法是让代码按结构聚合你需要看哪个结构就打开哪个文件。第三注释讲为什么而不是是什么。我在 Redis 代码里就注意到antirez 写注释经常解释为什么要这么设计而不是重复一遍代码逻辑。这种注释对后来者的帮助远超想象。第四尽量避免花哨的宏和语法技巧。C 语言里可以写出非常炫技的代码比如复杂的宏替换、内嵌汇编、原子操作。但在ds4这种分享型项目里坚持用最朴素的表达方式反而降低了理解门槛。这里需要做一个辨析代码可读不等于代码没有性能。好的可读性和好的性能在大多数场景下并不冲突。ds4的代码简单但并不是笨代码它只是没有为了微小的性能提升而牺牲可读性。6. 拉取源码并编译一套完整的上手流程如果你已经决定要看源码第一步是把项目拉到你本地。这里提供一个通用的流程不依赖 IDEA 或任何重型 IDE一个终端就够了。6.1 安装 C 编译环境在 Linux如 Ubuntu / Debian上执行sudo apt update sudo apt install build-essential git在 macOS 上确保安装 Xcode Command Line Toolsxcode-select --install在 Windows 上推荐使用 WSL2 的 Ubuntu 发行版然后在 WSL 里执行上面的 Linux 命令。6.2 克隆项目git clone https://github.com/antirez/ds4.git cd ds4如果没有找到仓库路径说明项目可能还在调整中可以直接去 GitHub 搜索antirez的用户主页查看最新仓库列表。6.3 查看目录结构和构建方式进入仓库后先看 README 和 Makefilels -la cat README.md不同的仓库版本构建方式可能有差异。从常见的 C 项目实践来看如果存在 Makefile通常直接执行make如果项目没有提供 Makefile而是分散的.c文件可以手动编译某个测试文件例如gcc -Wall -O2 -g -o test_skiplist test_skiplist.c skiplist.c ./test_skiplist6.4 跑一个测试或示例ds4大概率会带有简单的测试程序。运行后你能看到每个数据结构的基本操作输出例如插入、删除、查找的结果。这一步主要是确认本机环境能编译运行 C 代码并且源码本身可以工作。如果编译失败优先检查三件事是否缺少build-essential或 Xcode Command Line Tools。当前目录是否真的在仓库根目录。编译器版本是否过老比如 gcc 版本过低导致 C 标准语法不支持可以在gcc命令后加-stdc11。7. 用自己的代码重现核心思想跳表和布隆过滤器的最小实现读完源码后最有价值的练习是合上源码自己写一遍。这里给出两个仿照ds4设计思路的极简 C 语言实现目的是让你理解核心机制同时感受 antirez 式的简单直接。请注意下面两个示例是教学演示代码不是ds4仓库的原始实现API 与仓库源码无关。你可以对照学习但不要直接当作项目源码用。7.1 一个极简跳表按层数 4 的简化版跳表的核心是每个节点持有一个指针数组指针数组的长度由随机层数决定。查找时从最高层开始如果下一个节点的值小于目标值就向右移动否则下降到下一层。// 文件路径demo_skiplist.c // 编译gcc -Wall -O2 -o demo_skiplist demo_skiplist.c #include stdio.h #include stdlib.h #include string.h #include time.h #define MAX_LEVEL 4 typedef struct SkipNode { int key; int value; struct SkipNode *next[MAX_LEVEL]; } SkipNode; typedef struct SkipList { SkipNode *header; int level; } SkipList; static int random_level(void) { int level 1; while ((rand() % 2) level MAX_LEVEL) { level; } return level; } SkipList *skiplist_create(void) { SkipList *list (SkipList *)malloc(sizeof(SkipList)); if (!list) return NULL; list-header (SkipNode *)calloc(1, sizeof(SkipNode)); list-level 1; return list; } void skiplist_insert(SkipList *list, int key, int value) { SkipNode *update[MAX_LEVEL]; SkipNode *cur list-header; for (int i list-level - 1; i 0; i--) { while (cur-next[i] cur-next[i]-key key) { cur cur-next[i]; } update[i] cur; } // 如果 key 已存在直接更新 value SkipNode *next_node cur-next[0]; if (next_node next_node-key key) { next_node-value value; return; } int new_level random_level(); if (new_level list-level) { for (int i list-level; i new_level; i) { update[i] list-header; } list-level new_level; } SkipNode *node (SkipNode *)calloc(1, sizeof(SkipNode)); node-key key; node-value value; for (int i 0; i new_level; i) { node-next[i] update[i]-next[i]; update[i]-next[i] node; } } int skiplist_search(SkipList *list, int key) { SkipNode *cur list-header; for (int i list-level - 1; i 0; i--) { while (cur-next[i] cur-next[i]-key key) { cur cur-next[i]; } } cur cur-next[0]; if (cur cur-key key) { return cur-value; } return -1; } void skiplist_free(SkipList *list) { SkipNode *cur list-header; while (cur) { SkipNode *tmp cur-next[0]; if (cur ! list-header) free(cur); cur tmp; } free(list-header); free(list); } int main(void) { srand((unsigned)time(NULL)); SkipList *list skiplist_create(); const char *names[] {apple, banana, cherry, date, elderberry}; for (int i 0; i 5; i) { skiplist_insert(list, i 1, names[i][0]); } for (int i 1; i 5; i) { printf(key %d - value code %d\n, i, skiplist_search(list, i)); } printf(search key 99 - %d\n, skiplist_search(list, 99)); skiplist_free(list); return 0; }这段代码使用固定最大层数 4随机层数通过抛硬币方式决定。你可能会觉得它比ds4或 Redis 里的实现少了很多东西比如没有自定义内存分配器、没有压缩、没有容错处理。这正是教学代码和工程代码的差别先理解核心再逐步补细节。运行结果示例key 1 - value code 97 key 2 - value code 98 key 3 - value code 99 key 4 - value code 100 key 5 - value code 101 search key 99 - -17.2 一个极简布隆过滤器布隆过滤器的核心是一个位数组和多个哈希函数。插入时把多个哈希位置置 1查询时只要发现任一位为 0就说明元素一定不存在。// 文件路径demo_bloom.c // 编译gcc -Wall -O2 -o demo_bloom demo_bloom.c #include stdio.h #include stdlib.h #include string.h #define BIT_SIZE 1024 #define HASH_NUM 3 typedef struct BloomFilter { unsigned char bits[BIT_SIZE / 8]; } BloomFilter; static unsigned int hash1(const char *s) { unsigned int h 5381; while (*s) h (h 5) h (unsigned char)(*s); return h % BIT_SIZE; } static unsigned int hash2(const char *s) { unsigned int h 0; while (*s) h h * 31 (unsigned char)(*s); return h % BIT_SIZE; } static unsigned int hash3(const char *s) { unsigned int h 7; while (*s) h (h * 37) ^ (unsigned char)(*s); return h % BIT_SIZE; } void bloom_init(BloomFilter *bf) { memset(bf-bits, 0, sizeof(bf-bits)); } void bloom_add(BloomFilter *bf, const char *s) { bf-bits[hash1(s) / 8] | (1 (hash1(s) % 8)); bf-bits[hash2(s) / 8] | (1 (hash2(s) % 8)); bf-bits[hash3(s) / 8] | (1 (hash3(s) % 8)); } int bloom_check(BloomFilter *bf, const char *s) { if (!(bf-bits[hash1(s) / 8] (1 (hash1(s) % 8)))) return 0; if (!(bf-bits[hash2(s) / 8] (1 (hash2(s) % 8)))) return 0; if (!(bf-bits[hash3(s) / 8] (1 (hash3(s) % 8)))) return 0; return 1; } int main(void) { BloomFilter bf; bloom_init(bf); bloom_add(bf, user:1001); bloom_add(bf, user:1002); printf(user:1001 exists? %d\n, bloom_check(bf, user:1001)); printf(user:9999 exists? %d\n, bloom_check(bf, user:9999)); return 0; }运行结果示例user:1001 exists? 1 user:9999 exists? 0注意布隆过滤器存在误判可能如果检查某个 key 返回 1只能说可能存在因为不同 key 的哈希位可能重叠返回 0 则能确定不存在。实际工程里通常用它做缓存穿透防护的第一道闸门。8. 运行验证与调试思路不管你是运行ds4自带的测试还是运行上面两个演示程序验证方法都差不多。第一步编译时开启警告。gcc -Wall -Wextra -O2 -g -o demo_skiplist demo_skiplist.c编译时如果出现警告不要直接忽略先理解警告内容。比如implicit declaration of function通常意味着你没有包含对应的头文件。第二步运行并观察输出。跳表的输出应该按 key 顺序打印出 value布隆过滤器应该对已插入的 key 返回 1。第三步用 Valgrind 检查内存。在 Linux 上安装 Valgrind 后运行sudo apt install valgrind valgrind --leak-checkfull ./demo_skiplist如果输出中没有definitely lost或indirectly lost说明内存管理基本正常。这一步非常值得做C 语言内存问题用肉眼很难完全发现。第四步如果输出不对先打印关键中间变量。比如跳表插入失败先打印每层指针的地址、key 值、层数。这类问题十有八九是层数更新或者指针交接写错了。9. 常见问题与排查方向问题现象可能原因排查方式解决方案make提示找不到命令未安装构建工具检查 gcc 是否存在安装 build-essential 或 Xcode CLT编译报错unknown type name缺少头文件或结构体定义顺序错误查看报错行附近的 include 和 struct调整 include 顺序或前置声明运行跳表程序崩溃指针未初始化或越界用 gdb 查看调用栈检查next数组是否用calloc初始化布隆过滤器误判过高位数组太小或哈希函数不够分散统计实际误判率增大位数组增加哈希函数数量valgrind报告内存泄漏链表/跳表释放逻辑不完整对照插入逻辑检查释放逻辑先释放节点最后释放头节点和表结构修改源码后运行结果不变编译产物未更新确认是否重新执行了 gcc先make clean再重新编译还有两个非常容易犯的 C 语言错误值得单独提醒错误一插入跳表时忘记了从 header 的最高层开始查找。如果你每次都是从第 0 层开始跳表的优势就完全丢失退化成普通链表。错误二释放链表时把 header 节点一起 free 了但后面又访问它。释放顺序问题会导致 undefined behavior。10. 我们能从 ds4 学到什么以及不必学什么任何项目都有值得借鉴和需要保持距离的部分ds4也一样。10.1 值得学判断边界的能力antirez 花大量精力写的不是更复杂的数据结构而是够用的数据结构 极简的接口。这给我们的启示是在业务开发中很多时候我们并不需要一上来就引入红黑树、跳表、布隆过滤器的完整工业实现先用一个简单的版本跑通流程等真有性能瓶颈时再做针对性优化。10.2 值得学写自测代码的习惯ds4这种项目通常会带简单的测试主函数。哪怕不是完整单元测试框架一个能直接编译运行并输出结果的main函数就能保证功能不腐化。很多业务项目恰恰缺少这种最小可运行自测导致代码越改越复杂最后没人敢动。10.3 值得学从 C 语言视角理解数据结构很多后端开发者对数据结构的理解停留在 LeetCode 刷题层面只能写出 Python / Java 版本。而 C 语言会强制你考虑内存布局、指针、释放时机。读ds4或者仿写它能极大提升你对数据结构的实感。10.4 不必学过度简化的接口设计ds4是教学和演示性的项目它的接口不会像 Redis 那样考虑持久化、并发、多线程、扩展性。如果你把它的代码直接用在生产环境大概率会遇到问题。生产环境仍然建议选用经过大量测试的成熟库比如 Redis 本身、Jemalloc 相关的数据结构库、或者 C 的标准容器。10.5 不必学不兼容现代工程化的风格现代大型工程需要 CI/CD、代码覆盖率、动态分析、fuzz 测试、二进制兼容性管理。ds4并没有把这些做到极致。它像是一个手工作坊作品值得我们把它当作教材而不是模板。11. 对开发者的实际建议如何用这个项目提升自己如果你看完这篇文章想真正把这个项目利用起来我建议你按下面的路径走第一步通读 README。不要先读代码先了解项目作者想表达什么、包含哪些结构。第二步挑一个你工作中最常用的结构比如跳表或布隆过滤器。打开源码逐行读画出它的插入流程图。注意不要背代码而是理解每一行在干什么、为什么会这么写。第三步合上源码自己从零实现一遍。用自己的命名风格、文件组织方式。实现完后和原版对比找出差异点。第四步给项目加一个功能或者写一段测试。比如给布隆过滤器写一个统计误判率的测试。这个动作会逼迫你真正理解位数组大小、哈希函数数量和误判率之间的关系。第五步思考Redis 为什么会采用这个结构。回到 Redis 源码里看看t_zset.c、dict.c等文件对比ds4的实现和 Redis 的实现差在哪里。这比读完整个 Redis 源码更高效。12. 总结把它当作一本 C 语言数据结构随笔集ds4不会改变 Redis 的生态也不会催生新的基础设施。它真正的价值在于一个经验丰富的程序员把复杂工程中最核心的抽象拆解出来用极具个人风格的方式重新表达了一遍。对它最准确的定位不是新框架也不是Redis 替代品而是一本可以随时翻阅的源码风格随笔。你在里面看到的不仅是跳表怎么删除、布隆过滤器怎么计算更是很久以前驱动 antirez 写出 Redis 的那种编程直觉先理解问题再写代码先让人读懂再让机器跑快。如果你正好在学习 C 语言或者想提升自己对数据结构的理解ds4是一个非常合适的阅读材料。拉下来编译它读一遍再自己写一遍然后把它放回书架上。不需要在这上面做太多宏大的规划保持轻松反而能收获更多。 
不要被Redis 作者的新项目带偏antirez 的 ds4 到底在做什么值得我们学什么Redis 作者 Salvatore Sanfilippo网名 antirez最近在 GitHub 上活跃起来这次他不是在维护 Redis而是开了一个名为ds4的新仓库。在很多技术群里这个话题引发了一个非常典型的误读antirez 要写一个替代 Redis 的新数据库了。这个判断基本不成立。ds4并不是要再造一个 Redis也不是要挑战什么基础设施它更像是一个资深系统程序员回归 C 语言、用最朴素的方式重新整理数据结构的练习与分享。真正值得关注的是为什么一个写出了 Redis 这种顶级中间件的人会回头去写跳表、链表、布隆过滤器这些基础到不能再基础的东西本文会先讲清楚ds4是什么、不是什么然后分析它背后的设计哲学再给出可落地的 C 语言示例让你能自己把项目拉下来编译运行最后聊聊这个项目对普通开发者的价值在哪里、哪些地方需要理性看待。1. 这篇文章真正要解决的问题国内技术社区对 antirez 的关注度一直很高毕竟 Redis 几乎是后端开发的标配。当他发布新项目时很容易出现两种极端反应一种是把项目捧成Redis 继任者架构新范式另一种则是看到项目标题里的 Data Structures觉得不就是大学课设吗有什么好写的。这两种反应都偏离了项目本身。ds4的价值恰恰集中在三个层面第一编码风格。antirez 在 Redis 社区以代码写得清清爽爽著称。他的 C 语言风格强调可读性、命名直观、结构克制。看ds4的代码就像在翻一位工程师的笔记本而不是读一本教科书。第二设计取舍。每个数据结构在 Redis 内部都有特定的应用场景抽出来重新实现时需要做大量简化、取舍和接口设计。这个思考过程比代码本身更有学习价值。第三编程心态。antirez 明确表示做这个项目是为了乐趣和学习而不是为了生产。这种心态在如今每个项目都恨不得做成平台的氛围里非常少见。读完这篇文章你会掌握ds4到底是什么、它的边界在哪里。为什么 antirez 要做这个项目它的设计理念是什么。如何拉取源码并在本机编译运行。仿照ds4的思路如何自己写一个跳表和布隆过滤器的最小 C 语言实现。实际项目中哪些东西可以借鉴哪些东西要保留谨慎。2. antirez 是谁为什么他写的 C 代码值得关注在很多入行较晚的开发者眼里antirez 可能只是Redis 的作者。但这个名字背后的分量得稍微展开一下。antirez 是意大利人早年以写嵌入式软件和 Web 应用为生后来因为兴趣开发了 LVM一种虚拟机监控脚本工具再后来为了做实时 Web 项目写了一个远程字典服务这就是 Redis 的起点。Redis 后来有多成功大家都知道它成了内存数据库的事实标准几乎每个互联网公司都在用。更夸张的是Redis 的核心代码长期保持得非常短小精悍一个几千行 C 文件就是一套完整的高性能存储引擎。antirez 的编程风格有几个鲜明特点不堆抽象。Redis 里的数据结构就是直来直去的实现很少搞多层封装。命名追求直观。变量名和函数名一看就知道意图。重视局部性。代码逻辑尽量集中在一个文件里而不是散落到几十个小文件中。性能服务于场景。做优化之前先问这个操作在这个场景下真的会是热点吗。这些特点不一定都符合大厂工程化的口味但非常适合学习。你在学习 C 语言或数据结构时如果一开始就读非常复杂的工业级源码很容易迷失而读 antirez 的代码会觉得原来 C 语言可以写得这么干净。ds4就是这个风格的最新载体。它不是 Redis 的一部分也不是 Redis 的延续而是独立的小项目——可以把它理解成 antirez 的数据结构笔记本。3. ds4 到底是什么以及它不是什么先给出结论ds4是 antirez 用 C 语言实现的一组数据结构的集合项目用于教学、演示和自娱自乐。名字里的 ds 是 Data Structures 的缩写4 可以理解为第四版或新一版含义并不神圣。从项目仓库的公开信息和 antirez 的发布说明来看ds4目前主要包含一些常用数据结构例如跳跃表skiplist、布隆过滤器bloom filter、链表、字典等。这些数据结构并不稀罕任何一本算法书上都有antirez 的贡献不在于发明新结构而在于用他的方式重新实现了一遍并让代码保持足够简单方便他人阅读和修改。它不是 Redis 的替代品。Redis 是一个完整的网络服务有协议解析、事件循环、持久化、复制、集群、内存分配器管理等等。ds4里的数据结构只是 Redis 内部各类数据结构的一个子集拿出来重新实现并不包含任何网络层、持久化层的东西。它不是一个新的业务框架。它没有任何配置系统、插件系统、API 网关之类的概念。它就是一个 C 语言库你可以在自己的程序里链接它也可以把它当作源码阅读对象。它不是学术研究的产物。里面不会有大段论文引用不会有复杂的渐进复杂度证明也不会有验证了某种理论的结论。它更接近一位老程序员在周末写了几百行 C然后把源码分享出来的状态。那它为什么值得关注因为当一个经验极其丰富的人用最简单的工具来做一件简单的事情时他的取舍就特别有参考价值。这里有一个非常重要的观点简单事情做到极致比复杂事情做得庞大更能体现一个工程师的水平。4. 与 Redis 内部数据结构的对照一个更熟悉的坐标系要理解ds4最好的坐标系就是 Redis 源码里已经存在的数据结构。因为 antirez 对这些结构的理解最初就是在 Redis 的开发过程中建立起来的。4.1 跳表skiplistRedis 的有序集合ZSet在元素数量较大、元素是字符串时底层使用跳表 字典的组合。跳表的核心思想是多层链表通过空间换时间让查找、插入、删除的时间复杂度都接近 O(log n)。在ds4中跳表重新以一个轻量库的形式出现。和 Redis 内部版本相比它砍掉了和命令解析、内存编码、持久化有关的逻辑只保留最核心的跳表操作。4.2 布隆过滤器布隆过滤器是一种概率型数据结构用来判断某个元素一定不存在或者某个元素可能存在。它最典型的应用是防止缓存穿透在查询数据库之前先用布隆过滤器快速过滤掉肯定不存在的 key。Redis 本身通过模块RedisBloom支持布隆过滤器内核里没有直接内置。antirez 在ds4中单独实现了它代码量通常非常小可能只要一两百行。4.3 链表和字典Redis 里的链表和字典都经过精心打磨。链表用于列表键的早期版本后来被快速链表替代字典用于哈希键和数据库键空间。ds4中重新实现了这些基础结构但遵循同样的宁可简单不要复杂原则。这个对照关系告诉我们一件事你在ds4中看到的每个结构几乎都能在 Redis 内部找到原型。读ds4等于拿到了 Redis 源码的简化导读版。5. 设计哲学为什么 antirez 强调代码是给人读的antirez 在多个场合表达过类似观点代码首先是给人读的其次才是给机器执行的。这个观点听起来像老生常谈但真正做起来非常难。在ds4中这种哲学体现在几个具体的地方第一函数命名非常直白。你不会看到像x_calc_impl_v2这种名称更多的可能是skiplist_insert、bloom_add这种一眼能看懂的命名。命名上的克制不是偷懒而是对读者负责。第二文件组织不追求工程规范到病态的程度。一个很小的项目也用五层目录、十几个抽象接口反而会增加阅读成本。ds4的做法是让代码按结构聚合你需要看哪个结构就打开哪个文件。第三注释讲为什么而不是是什么。我在 Redis 代码里就注意到antirez 写注释经常解释为什么要这么设计而不是重复一遍代码逻辑。这种注释对后来者的帮助远超想象。第四尽量避免花哨的宏和语法技巧。C 语言里可以写出非常炫技的代码比如复杂的宏替换、内嵌汇编、原子操作。但在ds4这种分享型项目里坚持用最朴素的表达方式反而降低了理解门槛。这里需要做一个辨析代码可读不等于代码没有性能。好的可读性和好的性能在大多数场景下并不冲突。ds4的代码简单但并不是笨代码它只是没有为了微小的性能提升而牺牲可读性。6. 拉取源码并编译一套完整的上手流程如果你已经决定要看源码第一步是把项目拉到你本地。这里提供一个通用的流程不依赖 IDEA 或任何重型 IDE一个终端就够了。6.1 安装 C 编译环境在 Linux如 Ubuntu / Debian上执行sudo apt update sudo apt install build-essential git在 macOS 上确保安装 Xcode Command Line Toolsxcode-select --install在 Windows 上推荐使用 WSL2 的 Ubuntu 发行版然后在 WSL 里执行上面的 Linux 命令。6.2 克隆项目git clone https://github.com/antirez/ds4.git cd ds4如果没有找到仓库路径说明项目可能还在调整中可以直接去 GitHub 搜索antirez的用户主页查看最新仓库列表。6.3 查看目录结构和构建方式进入仓库后先看 README 和 Makefilels -la cat README.md不同的仓库版本构建方式可能有差异。从常见的 C 项目实践来看如果存在 Makefile通常直接执行make如果项目没有提供 Makefile而是分散的.c文件可以手动编译某个测试文件例如gcc -Wall -O2 -g -o test_skiplist test_skiplist.c skiplist.c ./test_skiplist6.4 跑一个测试或示例ds4大概率会带有简单的测试程序。运行后你能看到每个数据结构的基本操作输出例如插入、删除、查找的结果。这一步主要是确认本机环境能编译运行 C 代码并且源码本身可以工作。如果编译失败优先检查三件事是否缺少build-essential或 Xcode Command Line Tools。当前目录是否真的在仓库根目录。编译器版本是否过老比如 gcc 版本过低导致 C 标准语法不支持可以在gcc命令后加-stdc11。7. 用自己的代码重现核心思想跳表和布隆过滤器的最小实现读完源码后最有价值的练习是合上源码自己写一遍。这里给出两个仿照ds4设计思路的极简 C 语言实现目的是让你理解核心机制同时感受 antirez 式的简单直接。请注意下面两个示例是教学演示代码不是ds4仓库的原始实现API 与仓库源码无关。你可以对照学习但不要直接当作项目源码用。7.1 一个极简跳表按层数 4 的简化版跳表的核心是每个节点持有一个指针数组指针数组的长度由随机层数决定。查找时从最高层开始如果下一个节点的值小于目标值就向右移动否则下降到下一层。// 文件路径demo_skiplist.c // 编译gcc -Wall -O2 -o demo_skiplist demo_skiplist.c #include stdio.h #include stdlib.h #include string.h #include time.h #define MAX_LEVEL 4 typedef struct SkipNode { int key; int value; struct SkipNode *next[MAX_LEVEL]; } SkipNode; typedef struct SkipList { SkipNode *header; int level; } SkipList; static int random_level(void) { int level 1; while ((rand() % 2) level MAX_LEVEL) { level; } return level; } SkipList *skiplist_create(void) { SkipList *list (SkipList *)malloc(sizeof(SkipList)); if (!list) return NULL; list-header (SkipNode *)calloc(1, sizeof(SkipNode)); list-level 1; return list; } void skiplist_insert(SkipList *list, int key, int value) { SkipNode *update[MAX_LEVEL]; SkipNode *cur list-header; for (int i list-level - 1; i 0; i--) { while (cur-next[i] cur-next[i]-key key) { cur cur-next[i]; } update[i] cur; } // 如果 key 已存在直接更新 value SkipNode *next_node cur-next[0]; if (next_node next_node-key key) { next_node-value value; return; } int new_level random_level(); if (new_level list-level) { for (int i list-level; i new_level; i) { update[i] list-header; } list-level new_level; } SkipNode *node (SkipNode *)calloc(1, sizeof(SkipNode)); node-key key; node-value value; for (int i 0; i new_level; i) { node-next[i] update[i]-next[i]; update[i]-next[i] node; } } int skiplist_search(SkipList *list, int key) { SkipNode *cur list-header; for (int i list-level - 1; i 0; i--) { while (cur-next[i] cur-next[i]-key key) { cur cur-next[i]; } } cur cur-next[0]; if (cur cur-key key) { return cur-value; } return -1; } void skiplist_free(SkipList *list) { SkipNode *cur list-header; while (cur) { SkipNode *tmp cur-next[0]; if (cur ! list-header) free(cur); cur tmp; } free(list-header); free(list); } int main(void) { srand((unsigned)time(NULL)); SkipList *list skiplist_create(); const char *names[] {apple, banana, cherry, date, elderberry}; for (int i 0; i 5; i) { skiplist_insert(list, i 1, names[i][0]); } for (int i 1; i 5; i) { printf(key %d - value code %d\n, i, skiplist_search(list, i)); } printf(search key 99 - %d\n, skiplist_search(list, 99)); skiplist_free(list); return 0; }这段代码使用固定最大层数 4随机层数通过抛硬币方式决定。你可能会觉得它比ds4或 Redis 里的实现少了很多东西比如没有自定义内存分配器、没有压缩、没有容错处理。这正是教学代码和工程代码的差别先理解核心再逐步补细节。运行结果示例key 1 - value code 97 key 2 - value code 98 key 3 - value code 99 key 4 - value code 100 key 5 - value code 101 search key 99 - -17.2 一个极简布隆过滤器布隆过滤器的核心是一个位数组和多个哈希函数。插入时把多个哈希位置置 1查询时只要发现任一位为 0就说明元素一定不存在。// 文件路径demo_bloom.c // 编译gcc -Wall -O2 -o demo_bloom demo_bloom.c #include stdio.h #include stdlib.h #include string.h #define BIT_SIZE 1024 #define HASH_NUM 3 typedef struct BloomFilter { unsigned char bits[BIT_SIZE / 8]; } BloomFilter; static unsigned int hash1(const char *s) { unsigned int h 5381; while (*s) h (h 5) h (unsigned char)(*s); return h % BIT_SIZE; } static unsigned int hash2(const char *s) { unsigned int h 0; while (*s) h h * 31 (unsigned char)(*s); return h % BIT_SIZE; } static unsigned int hash3(const char *s) { unsigned int h 7; while (*s) h (h * 37) ^ (unsigned char)(*s); return h % BIT_SIZE; } void bloom_init(BloomFilter *bf) { memset(bf-bits, 0, sizeof(bf-bits)); } void bloom_add(BloomFilter *bf, const char *s) { bf-bits[hash1(s) / 8] | (1 (hash1(s) % 8)); bf-bits[hash2(s) / 8] | (1 (hash2(s) % 8)); bf-bits[hash3(s) / 8] | (1 (hash3(s) % 8)); } int bloom_check(BloomFilter *bf, const char *s) { if (!(bf-bits[hash1(s) / 8] (1 (hash1(s) % 8)))) return 0; if (!(bf-bits[hash2(s) / 8] (1 (hash2(s) % 8)))) return 0; if (!(bf-bits[hash3(s) / 8] (1 (hash3(s) % 8)))) return 0; return 1; } int main(void) { BloomFilter bf; bloom_init(bf); bloom_add(bf, user:1001); bloom_add(bf, user:1002); printf(user:1001 exists? %d\n, bloom_check(bf, user:1001)); printf(user:9999 exists? %d\n, bloom_check(bf, user:9999)); return 0; }运行结果示例user:1001 exists? 1 user:9999 exists? 0注意布隆过滤器存在误判可能如果检查某个 key 返回 1只能说可能存在因为不同 key 的哈希位可能重叠返回 0 则能确定不存在。实际工程里通常用它做缓存穿透防护的第一道闸门。8. 运行验证与调试思路不管你是运行ds4自带的测试还是运行上面两个演示程序验证方法都差不多。第一步编译时开启警告。gcc -Wall -Wextra -O2 -g -o demo_skiplist demo_skiplist.c编译时如果出现警告不要直接忽略先理解警告内容。比如implicit declaration of function通常意味着你没有包含对应的头文件。第二步运行并观察输出。跳表的输出应该按 key 顺序打印出 value布隆过滤器应该对已插入的 key 返回 1。第三步用 Valgrind 检查内存。在 Linux 上安装 Valgrind 后运行sudo apt install valgrind valgrind --leak-checkfull ./demo_skiplist如果输出中没有definitely lost或indirectly lost说明内存管理基本正常。这一步非常值得做C 语言内存问题用肉眼很难完全发现。第四步如果输出不对先打印关键中间变量。比如跳表插入失败先打印每层指针的地址、key 值、层数。这类问题十有八九是层数更新或者指针交接写错了。9. 常见问题与排查方向问题现象可能原因排查方式解决方案make提示找不到命令未安装构建工具检查 gcc 是否存在安装 build-essential 或 Xcode CLT编译报错unknown type name缺少头文件或结构体定义顺序错误查看报错行附近的 include 和 struct调整 include 顺序或前置声明运行跳表程序崩溃指针未初始化或越界用 gdb 查看调用栈检查next数组是否用calloc初始化布隆过滤器误判过高位数组太小或哈希函数不够分散统计实际误判率增大位数组增加哈希函数数量valgrind报告内存泄漏链表/跳表释放逻辑不完整对照插入逻辑检查释放逻辑先释放节点最后释放头节点和表结构修改源码后运行结果不变编译产物未更新确认是否重新执行了 gcc先make clean再重新编译还有两个非常容易犯的 C 语言错误值得单独提醒错误一插入跳表时忘记了从 header 的最高层开始查找。如果你每次都是从第 0 层开始跳表的优势就完全丢失退化成普通链表。错误二释放链表时把 header 节点一起 free 了但后面又访问它。释放顺序问题会导致 undefined behavior。10. 我们能从 ds4 学到什么以及不必学什么任何项目都有值得借鉴和需要保持距离的部分ds4也一样。10.1 值得学判断边界的能力antirez 花大量精力写的不是更复杂的数据结构而是够用的数据结构 极简的接口。这给我们的启示是在业务开发中很多时候我们并不需要一上来就引入红黑树、跳表、布隆过滤器的完整工业实现先用一个简单的版本跑通流程等真有性能瓶颈时再做针对性优化。10.2 值得学写自测代码的习惯ds4这种项目通常会带简单的测试主函数。哪怕不是完整单元测试框架一个能直接编译运行并输出结果的main函数就能保证功能不腐化。很多业务项目恰恰缺少这种最小可运行自测导致代码越改越复杂最后没人敢动。10.3 值得学从 C 语言视角理解数据结构很多后端开发者对数据结构的理解停留在 LeetCode 刷题层面只能写出 Python / Java 版本。而 C 语言会强制你考虑内存布局、指针、释放时机。读ds4或者仿写它能极大提升你对数据结构的实感。10.4 不必学过度简化的接口设计ds4是教学和演示性的项目它的接口不会像 Redis 那样考虑持久化、并发、多线程、扩展性。如果你把它的代码直接用在生产环境大概率会遇到问题。生产环境仍然建议选用经过大量测试的成熟库比如 Redis 本身、Jemalloc 相关的数据结构库、或者 C 的标准容器。10.5 不必学不兼容现代工程化的风格现代大型工程需要 CI/CD、代码覆盖率、动态分析、fuzz 测试、二进制兼容性管理。ds4并没有把这些做到极致。它像是一个手工作坊作品值得我们把它当作教材而不是模板。11. 对开发者的实际建议如何用这个项目提升自己如果你看完这篇文章想真正把这个项目利用起来我建议你按下面的路径走第一步通读 README。不要先读代码先了解项目作者想表达什么、包含哪些结构。第二步挑一个你工作中最常用的结构比如跳表或布隆过滤器。打开源码逐行读画出它的插入流程图。注意不要背代码而是理解每一行在干什么、为什么会这么写。第三步合上源码自己从零实现一遍。用自己的命名风格、文件组织方式。实现完后和原版对比找出差异点。第四步给项目加一个功能或者写一段测试。比如给布隆过滤器写一个统计误判率的测试。这个动作会逼迫你真正理解位数组大小、哈希函数数量和误判率之间的关系。第五步思考Redis 为什么会采用这个结构。回到 Redis 源码里看看t_zset.c、dict.c等文件对比ds4的实现和 Redis 的实现差在哪里。这比读完整个 Redis 源码更高效。12. 总结把它当作一本 C 语言数据结构随笔集ds4不会改变 Redis 的生态也不会催生新的基础设施。它真正的价值在于一个经验丰富的程序员把复杂工程中最核心的抽象拆解出来用极具个人风格的方式重新表达了一遍。对它最准确的定位不是新框架也不是Redis 替代品而是一本可以随时翻阅的源码风格随笔。你在里面看到的不仅是跳表怎么删除、布隆过滤器怎么计算更是很久以前驱动 antirez 写出 Redis 的那种编程直觉先理解问题再写代码先让人读懂再让机器跑快。如果你正好在学习 C 语言或者想提升自己对数据结构的理解ds4是一个非常合适的阅读材料。拉下来编译它读一遍再自己写一遍然后把它放回书架上。不需要在这上面做太多宏大的规划保持轻松反而能收获更多。