xtools

仓库地址🦄🐋✨🎉🎊🛠🔧⌛

项目初衷

本项目是一个个人学习性质的开源项目，旨在系统阅读，整理、实现优秀的数据结构与算法，并结合实际编程语言知识沉淀项目经验。基于对Go语言的热爱与探索，项目中的绝大多数实现均采用Go语言完成。在设计与实现过程中，注重代码的可扩展性，每个功能模块都尽量以独立函数库的形式呈现，便于后续复用与拓展。同时，在代码实现上追求简洁清晰，剔除冗余逻辑，专注于保留最核心、最本质的实现内容，帮助理解底层原理。

项目介绍

• 布隆过滤器

• 跳表

• 多级缓存

• 无锁化队列

• 并查集

• 排序算法

• 读写者问题

• 限流器

• 分布式锁

• 分布式id

• 本地缓存

• AC自动机

• 搜索树

• 池

• 主从reactor模型

项目细节

布隆过滤器

布隆过滤器（Bloom Filter），用于高效判断一个元素是否可能存在于集合中。通过使用多个64位哈希函数和紧凑的位图（bitmap）结构，布隆过滤器以极低的空间开销支持大量数据的存储与查询。每次添加或查询元素时，均通过多个哈希函数计算出对应的位索引，并在位图上进行设置或检查操作。由于其概率性特性，布隆过滤器可能会存在一定的误判率，但不会漏判。这种结构特别适合用于缓存穿透防护、大规模数据检索等场景。

跳表

跳表（Skip Table），是一种基于链表结构的高效有序字典，支持快速插入、删除和查找操作。跳表通过多级索引结构将时间复杂度降低至 O(log n) 的期望水平，特别适合处理大规模有序数据。其核心思想是在原始链表之上构建多层“跳跃”指针，从而跳过大量节点以加速访问。本实现使用随机化策略决定节点的高度（层数），确保结构平衡性的同时简化了实现逻辑。

多级缓存

该代码实现了一个本地缓存组件（LocalCache）及其发布者（LocalCachePublisher），用于在分布式系统中高效缓存和同步数据。整体设计结合了 Redis 和本地缓存的优势，兼顾性能与一致性。

核心功能：

• 本地缓存：使用 sync.Map 或 LRU 缓存从 Redis 中加载的数据，减少对后端存储的直接访问，提升读取性能。
• 初始化机制：启动时通过扫描 Redis 中的指定键前缀填充本地缓存，并支持重试机制确保可靠性。
• 订阅更新：通过 Redis Pub/Sub 机制订阅数据变更事件，在其他节点修改缓存项时能够及时更新或清除本地缓存，保持数据一致性。
• 发布变更：发布者组件可在执行插入、更新或删除操作时向 Redis 频道广播消息，通知其他节点进行本地缓存同步。

该方案适用于需要快速读取、降低 Redis 压力并保证多实例间缓存一致性的场景，如用户状态缓存、配置中心等。

无锁化队列

该代码实现了一个无锁队列（LockFreeQueue），适用于高并发环境下的线程安全队列操作。通过使用原子操作（atomic包）而非互斥锁，避免了锁带来的性能瓶颈和死锁风险。

核心机制：

• 环形缓冲区：基于固定大小的数组实现，通过 head 和 tail 指针控制队列的入队与出队操作。
• CAS 原子操作：使用 CompareAndSwap 确保多协程并发访问时的状态一致性，实现无锁的 Push 与 Pop 操作。
• 超时支持：提供带超时机制的入队和出队方法，防止长时间阻塞，提升系统响应性。
• 动态容量管理：队列大小在初始化时设定，并采用环状结构提升空间利用率。

该设计适合用于对性能敏感、并发度高的场景，如网络数据包处理、任务调度器等。

并查集

该代码实现了一个并查集（Union-Find Set，也称不相交集合）数据结构，用于高效管理元素的分组问题，支持快速合并与查询操作。其核心特点是通过路径压缩和按秩合并优化，显著提升查找和合并的时间复杂度，接近常数级别。

主要功能：

• 查找（Find）：确定某个元素所属的集合（根节点），并通过路径压缩优化后续查询。
• 合并（Union）：将两个集合合并为一个，采用秩策略保持树的高度平衡。
• 判断连通性（IsConnected）：检查两个元素是否属于同一个集合。

该结构广泛应用于图的连通性判断、社交网络中的好友分组、图像处理中的连通区域识别等场景。

排序算法

该代码库实现了一个通用排序算法集合，支持多种高效的排序方式。所有算法均使用 Go 泛型语法，适用于任何可比较类型（cmp.Ordered）的切片输入。

1. 基数排序 (BaseSort)

   • 基于数字每一位进行排序，适合整型数据。
   • 使用桶（bucket）按位分类，并通过多次分配与收集完成排序。

2. 堆排序 (HeapSort)

   • 利用最大堆结构将数组调整为有序结构。
   • 通过构建堆并逐步提取最大值完成排序，时间复杂度为 O(n log n)。

3. 归并排序 (MergeSort)

   • 分治策略：将数组不断二分，递归排序后合并两个有序数组。
   • 稳定排序算法，适用于链表或大数据集排序。

4. 快速排序 (QuickSort)

   • 使用三路划分策略优化重复元素处理，随机选择基准值提升性能。
   • 在平均情况下具有 O(n log n) 时间复杂度，空间效率高。

读写者问题

该代码库实现了一个通用的读写控制组件，包含多种策略以协调并发场景下的读写优先级。适用于需要对共享资源进行高效、安全访问的场景。

1. 接口定义 (ReadWriter)

   • 定义统一的读写接口，支持任意类型的数据操作。

2. 公平读写策略 (EquityReadWrite)

   • 保证读写操作公平竞争，避免某一方长期“饥饿”。
   • 使用互斥锁与计数器控制并发访问，确保读写互斥、写写互斥、读读可并行。

3. 读优先策略 (ReadFirst)

   • 多个读者可以同时访问资源，但一旦有写者进入，后续读者必须等待。
   • 适合读多写少的场景，如配置中心、缓存系统等。

4. 写优先策略 (WriteFirst)

   • 写操作优先于读操作，防止写者长时间等待。
   • 确保写入及时生效，适合数据一致性要求高的场景，如日志写入、状态更新等。

限流器

该代码库实现了一个通用的限流组件，包含多种限流策略以应对不同场景下的请求控制需求。所有实现均支持基于令牌（Token）、计数（Count）或时间窗口（Window）的限流算法，并结合本地与 Redis 实现分布式环境下的统一限流管理。

1. 计数限流 (CountLimiter)

   • 基于固定时间窗口内的请求数进行限制。
   • 每个时间窗口开始时重置计数器，适用于对突发流量有一定容忍度的场景。

2. 漏桶限流 (LeakyBucketLimiter)

   • 使用“漏水”模型控制请求速率，平滑输出流量。
   • 适合严格控制请求速率、防止突发流量冲击的场景。

3. 令牌桶限流 (TokenLimiter)

   • 通过定期填充令牌并消费令牌来控制访问频率。
   • 支持突发流量，在不超过桶容量的前提下允许短时高并发。

4. 滑动窗口限流 (WindowLimiter)

   • 将时间划分为多个槽位，记录每个时间段的请求数，滑动更新。
   • 更精确地控制平均请求速率，适用于需要细粒度统计的场景。

5. Redis 分布式限流

   • RedisCounterLimiter：基于 Redis String的计数限流，使用 INCR 实现共享计数。
   • RedisLeakyBucketLimiter：Redis Hash存储水位状态，实现跨节点漏桶限流。
   • RedisSlidingWindowLimiter：使用ZSet维护请求时间戳，实现滑动窗口限流。
   • RedisTokenBucketLimiter：Redis Hash存储令牌状态，实现分布式的令牌桶限流。

该组件适用于 API 网关、微服务、支付系统等需对访问频率进行精细化控制的场景。

分布式锁

该代码（github.com/cheerego/go-redisson）实现了一个基于 Redis 的分布式读锁（RLock），适用于多节点环境下对共享资源的并发控制。通过 Lua 脚本、Redis Hash 与 Pub/Sub 机制，确保了跨服务实例的互斥访问，并支持自动续期、阻塞等待和超时释放等高级特性。

核心功能

1. 加锁机制

   • 使用 HINCRBY 记录每个客户端的持有次数，实现可重入性。
   • 若锁未被占用则直接获取并设置过期时间（PEXPIRE）。
   • 支持设置最大等待时间（waitTime）与持有时间（leaseTime），后者为 -1 表示启用看门狗自动续期。

2. 自动续期（Watchdog）

   • 在锁成功获取后启动后台协程定期刷新过期时间，防止因业务执行时间过长导致锁提前释放。

3. 解锁机制

   • 使用 Lua 脚本安全减少引用计数，若计数归零则删除锁并发布解锁消息到 Redis 频道。
   • 确保只有加锁方才能解锁，具备身份校验能力。

4. 等待通知机制

   • 基于 Redis 的 Pub/Sub 模型实现锁释放事件监听。
   • 当前线程订阅指定频道，在锁竞争失败时进入等待状态，直到收到解锁通知或超时。

5. 可重入支持

   • 同一客户端多次加锁会递增引用计数，解锁时需对应次数的递减操作才会真正释放锁。

6. 高可用与异常处理

   • 加锁失败时自动退避并尝试重新获取，保障在分布式环境下的健壮性。
   • 解锁失败或连接中断时提供合理的错误反馈，避免死锁。

特性总结

此实现适合作为构建强一致性分布式系统的基础设施之一，可用于替代或增强原生的 Redis 锁方案。

分布式id

该代码库实现了一个高效的分布式序列号生成系统（Segment ID），适用于需要全局唯一、有序且高性能的 ID 分配场景。通过 Redis 缓存与底层数据库结合，支持高并发请求和故障恢复。

1. 接口定义 (SeqDatabase)

   • 定义统一的 Malloc 接口用于分配指定大小的序列号区间。
   • 支持多种底层存储实现，如本地文件模拟数据库或持久化数据库。

2. 缓存机制 (SeqCacheRedis)

   • 基于 Redis 实现大序列号段的缓存管理，减少对底层数据库的频繁访问。
   • 使用 Lua 脚本保证原子操作，协调多个客户端之间的并发请求。
   • 支持锁机制与过期控制，确保数据一致性与自动释放。

特性与优势

• 高性能：利用 Redis 缓存批量预取序列号，显著降低数据库压力。
• 高可用：Redis 故障时可降级至底层数据库，保障服务连续性。
• 强一致性：通过 Redis 锁与 Lua 脚本确保多节点间的同步安全。
• 易扩展：接口设计清晰，便于接入其他底层存储（如 MySQL、ETCD）。

应用场景

适用于金融交易流水号、订单编号、日志追踪 ID 等需全局唯一且有序递增的业务场景。

本地缓存

该代码库实现了一个高性能缓存组件集合，包含多种主流缓存淘汰策略与统计结构，适用于需要高效内存管理、访问控制和热点数据识别的场景。

核心缓存策略

1. LFU（Least Frequently Used）lfu.go

   • 基于访问频率进行缓存淘汰，使用频率越低的元素优先被清除。
   • 通过 freq2items 映射维护每个频率对应的元素链表，并跟踪最小频率以优化淘汰效率。
   • 支持并发访问控制，适合长期运行且访问模式变化较大的系统。

2. LRU（Least Recently Used）lru.go

   • 基于最近最少使用原则淘汰数据，使用双向链表实现高效的插入与移动操作。
   • 引入访问频率阈值（freqThreshold），避免短暂热点导致缓存污染。
   • 支持并发安全读写，适合访问局部性较强的场景。

3. CountMin Sketch（CMS）cm_sketch.go

   • 概率型数据结构，用于估计高频项（Heavy Hitters）的访问频率。
   • 使用多组哈希函数与位压缩技术降低内存占用，支持增量更新与最小值估算。
   • 适用于资源有限环境下对访问频次进行快速统计与过滤。

4. TinyLFU 与 Window TinyLFU（扩展预留）

   • TinyLFU 是 LFU 的改进版本，引入滑动窗口与计数器衰减机制，提升适应性和空间效率。
   • Window TinyLFU 在此基础上进一步限制窗口大小，更适用于时间敏感的热点探测。
   • 当前代码仅声明包结构，尚未实现具体逻辑。

5. Segmented LRU（扩展预留）

   • 分段 LRU 策略，将缓存划分为多个层级或区域，分别应用 LRU 管理，平衡命中率与公平性。
   • 当前文件为空，可作为后续扩展方向。

AC自动机

该代码库实现了一个 AC 自动机（Aho-Corasick Automaton），是一种高效的多模式匹配算法，适用于在一段文本中同时查找多个关键词的出现位置。整体结构清晰，支持插入、删除和匹配操作，适合敏感词过滤、日志关键字检索等场景。

核心功能

1. AC 自动机结构 (ACAutomation)

   • 使用 Trie 树构建基础前缀结构。
   • 每个节点包含子节点映射、是否为词尾标识、失败指针（fail）、深度信息。

2. 构建 Trie 树 (insert / InsertMany)

   • 将输入的字符串逐字符插入 Trie 树。
   • 标记每个字符串结尾节点为 isEnd。

3. 构建失败指针 (buildFail)

   • 类似 KMP 算法中的失败跳转机制，用于加速回溯匹配。
   • 通过 BFS 构建，确保每个节点的 fail 指针指向最长可匹配后缀。

4. 模式匹配 (Match)

   • 输入文本后，在 Trie 中遍历并查找所有匹配的关键词。
   • 返回匹配的起始与结束索引（基于 Unicode 字符）。

5. 删除关键词 (Delete)

   • 定位目标词的结尾节点，并将其标记为非词尾（isEnd = false），保留结构供其他词使用。

6. 匹配结果结构 (MatchResult)

   • 包含匹配的起始与结束索引，便于定位原始文本中的关键词位置。

特性与优势

• 高效多模匹配：一次构建，多次高效匹配，时间复杂度接近 O(n + m*k)，其中 n 为文本长度，m 为模式数，k 为平均匹配次数。
• 支持动态更新：可随时插入新词或删除旧词，不影响已有结构。
• Unicode 支持良好：使用 rune 表示字符，适配中文等多字节字符。
• 内存友好：Trie 结构共享前缀，节省存储空间。

搜索树

该代码库实现了三种常见的平衡二叉搜索树结构（AVL 树、Treap、支持分裂与合并的 Treap），适用于需要高效插入、删除、查找和遍历操作的场景。每种实现都提供了基本的树操作，并通过统一的测试用例验证其正确性。

核心数据结构

1. AVL 树 (AVLTree)

   • 一种自平衡二叉搜索树，通过旋转操作维持高度平衡。
   • 每个节点维护 高度 和 平衡因子，在插入和删除时自动调整结构。
   • 支持插入、删除、查找和中序遍历操作。

2. Treap (Treap)

   • 结合了二叉搜索树和堆特性的随机化数据结构。
   • 每个节点具有一个优先级，插入时通过旋转保持堆性质。
   • 插入、删除、查找等操作基于键值比较与优先级判断完成。

3. 支持分裂与合并的 Treap (TreapWithSM)

   • 扩展版 Treap，支持高效的 split 和 merge 操作。
   • 可用于构建区间树、支持范围查询或动态集合运算的场景。

池

go官方池（源码阅读）

该代码（sync.Pool）实现 Go 标准库中的 sync.Pool 结构，是一个用于临时对象的并发安全缓存池，旨在减少频繁创建和销毁对象带来的性能开销。适用于对象生命周期短、分配频繁、可复用性强的场景。

核心功能

1. 对象缓存与复用

   • 提供 Put 和 Get 方法用于存储和获取对象。
   • 支持自动释放未使用对象，避免内存泄漏。

2. 线程局部（Per-P）缓存机制

   • 每个处理器（P）维护一个本地缓存 local，减少锁竞争。
   • 使用 pin() 将 goroutine 绑定到当前 P，确保缓存访问高效且线程安全。

3. 私有与共享队列

   • 每个 P 缓存包含一个私有字段（private）和一个共享队列（shared）。
   • 优先访问私有对象，其次尝试共享队列，最后从其他 P 共享队列中“偷取”对象。

4. 双阶段回收机制

   • 在垃圾回收前保留“受害者缓存”（victim），防止频繁 GC 导致的对象抖动。
   • 垃圾回收时将主缓存迁移至受害者缓存，逐步淘汰老数据。

5. 自动清理与 GC 集成

   • 注册 poolCleanup 函数，在每次 GC 开始前清理 victim 缓存。
   • 保证全局缓存一致性，并释放无用对象以减轻 GC 压力。

6. 并发安全

   • 所有操作均支持多协程并发访问，通过原子操作与内存屏障保障同步语义。
   • 使用 race detector 支持检测潜在的数据竞争问题。

特性总结

应用场景

• 缓存临时缓冲区（如 fmt, io 等包使用的临时 buffer）
• 减少高频小对象的内存分配次数
• 构建高效的线程安全资源池（如数据库连接、对象构造器等）

此结构不适合用于长期存活对象或需要精确控制生命周期的场景，因其内容会在 GC 时被清空，也不适合做严格意义上的对象池（Object Pool）。

协程池（源码阅读）

该代码（github.com/bytedance/gopkg/util/gopool）实现了一个高性能、可配置的协程池（gopool），适用于管理并限制并发执行任务的数量，避免资源耗尽问题。整体结构清晰，分为 worker 和 task 两部分，并结合对象复用机制提升性能。 核心组件

1. 协程池接口 (Pool) 提供统一的任务提交与管理接口：

   • Go / CtxGo：提交无上下文或带上下文的任务函数。
   • SetCap：动态设置最大并发协程数。
   • WorkerCount：获取当前活跃 worker 数量。
   • SetPanicHandler：设置全局 panic 捕获处理器。

2. 任务模型 (task)

   • 使用链表结构维护待执行任务队列。
   • 支持上下文传递，便于超时控制和链路追踪。
   • 利用 sync.Pool 实现对象复用，降低频繁分配释放带来的 GC 压力。

3. 执行单元 (worker)

   • 每个 worker 独立运行一个 goroutine，循环从任务队列中取出任务执行。
   • 出现 panic 时调用注册的处理函数，确保异常可控。
   • worker 对象通过 sync.Pool 复用，减少创建销毁开销。

4. 内部任务调度机制

   • 任务入队：通过加锁将新任务添加到链表尾部。
   • 动态扩容：当任务积压超过阈值且未达容量上限时自动启动新 worker。
   • 空闲回收：worker 在无任务时退出并归还至缓存池，减轻系统负载。

字节池（源码阅读）

该代码（github.com/bytedance/gopkg/lang/mcache）实现了一个高效的字节缓冲区（[]byte）缓存池 mcache，基于大小分级的 sync.Pool 实现，用于优化频繁创建和释放临时字节数组带来的性能损耗。

核心功能

1. 分级缓存

   • 使用一个固定大小的 caches 数组，每个元素是一个 sync.Pool。
   • 每个 Pool 缓存容量为 2^i 字节的内存块（i ∈ [0, 45]），即支持最大 2^45 字节（约 32TB）的缓存对象。

2. 内存分配 (Malloc)

   • 支持指定长度与最小容量的字节切片分配。
   • 自动选择最合适的缓存池，保证 cap(ret) >= cap。
   • 利用 bytesHeader 结构体操作切片底层字段，提升性能。

3. 内存释放 (Free)

   • 将使用完的字节切片归还到对应的缓存池中。
   • 仅对容量为 2 的幂次方的缓冲区进行回收，确保一致性。

4. 索引计算

   • 通过 calcIndex 确定应使用的缓存池下标。
   • 使用位运算快速判断是否为 2 的幂，并定位最高有效位（BSR）决定索引位置。

5. 初始化机制

   • 在 init 函数中预初始化所有缓存池，设置默认生成函数以提供统一内存分配方式。
   • 每个缓存块实际由 dirtmake.Bytes 创建并封装为 *byte 存储。

特性总结

主从reactor模型（源码阅读）

netpoll（github.com/cloudwego/netpoll） 是一个基于 Go 实现的高性能网络通信库，其核心架构采用 主从 Reactor 模型（Main-Sub Reactor）和 协程池 + 零拷贝缓冲区机制，结合 epoll I/O 多路复用模型，实现了高效的并发网络处理能力。

1. 主从 Reactor 模型

netpoll 使用了经典的 主从 Reactor 架构：

• 主 Reactor（Main Reactor）：

  • 负责监听服务端口并接受新连接。
  • 新连接建立后，将其分配给某个 Sub Reactor（Poller），实现负载均衡。
  • 通过 EventLoop.Serve() 启动主事件循环，注册 Listener 并开始 Accept 连接。

• 从 Reactor（Sub Reactor）：

  • 每个 Sub Reactor 对应一个 Poll 实例（默认为 epoll）。
  • 负责监听已连接套接字上的读写事件，并触发相应的回调函数（如 OnRead、OnWrite）。
  • 每个连接绑定一个 FDOperator，与 Poll 关联，用于在事件触发时执行具体操作。

该设计使得连接管理与事件处理分离，提升了系统的可扩展性和性能。

2. 协程池（Goroutine Pool）

netpoll 在处理连接的业务逻辑时使用了 轻量级的协程池机制：

• 当连接上有数据可读时，会启动一个 goroutine 执行 OnRequest 回调来处理请求。
• 每个连接最多只有一个 OnRequest 协程在运行，避免并发问题。
• 请求处理完成后自动释放协程资源，形成类似“轻量级线程池”的结构，提高资源利用率。

此外，对于异步操作（如定时器、超时控制等），也利用 Go 的原生并发特性进行管理。

3. 字节池（Byte Pool）

为了减少内存分配与 GC 压力，netpoll 使用了 链式零拷贝缓冲区（LinkBuffer）配合 字节池 来优化内存使用：

• LinkBuffer 支持按需分配多个 buffer 块，并维护一个链表结构，实现高效的数据读写。
• 缓冲区对象本身可通过 sync.Pool 或自定义缓存机制复用，降低频繁内存申请开销。
• 提供 Malloc, Next, Release 等方法，支持零拷贝读写操作，提升性能。

4. 双向读写缓冲区（Zero-Copy Reader/Writer）

netpoll 中每个连接都包含两个缓冲区：

• Input Buffer（输入缓冲区）：用于接收来自对端的数据。
• Output Buffer（输出缓冲区）：用于暂存待发送的数据。

两者均实现了零拷贝接口：

• Reader 接口：提供 Next, Peek, Skip, ReadString, ReadBinary 等方法，直接访问底层 buffer 数据，避免额外拷贝。
• Writer 接口：提供 Malloc, Flush, WriteString, WriteBinary 等方法，用户可申请 buffer 写入数据后批量发送。

这种设计显著减少了系统调用次数和内存拷贝，提高了吞吐性能。

5. epoll 模型

netpoll 默认使用 Linux 下的 epoll I/O 多路复用模型：

• 使用 epoll_ctl 注册文件描述符事件（EPOLLIN、EPOLLOUT 等）。
• 使用 epoll_wait 监听事件并分发到对应的 FDOperator。
• 支持 ET（边缘触发）模式，适用于高并发场景下的事件通知。

关键点包括：

• 事件驱动：只有当有 I/O 事件发生时才会唤醒处理逻辑，节省 CPU 资源。
• 事件封装：每个事件携带对应 FDOperator 的上下文信息，便于快速定位处理逻辑。
• 非阻塞 I/O：所有 socket 设置为非阻塞模式，配合 epoll 使用，避免系统调用阻塞。

此外，还使用了 eventfd 实现 Poll 的主动唤醒机制，确保主线程可以安全退出或重新调度。

核心

整体来看，netpoll 通过上述技术组合，构建了一个高性能、低延迟、高并发的网络通信框架，适合构建大规模分布式服务。