仓库地址🦄🐋✨🎉🎊🛠🔧⌛
本项目是一个个人学习性质的开源项目，旨在系统阅读，整理、实现优秀的数据结构与算法，并结合实际编程语言知识沉淀项目经验。基于对Go语言的热爱与探索，项目中的绝大多数实现均采用Go语言完成。在设计与实现过程中，注重代码的可扩展性，每个功能模块都尽量以独立函数库的形式呈现，便于后续复用与拓展。同时，在代码实现上追求简洁清晰，剔除冗余逻辑，专注于保留最核心、最本质的实现内容，帮助理解底层原理。
布隆过滤器（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）的切片输入。
-
基数排序 (BaseSort)
- 基于数字每一位进行排序，适合整型数据。
- 使用桶（bucket）按位分类，并通过多次分配与收集完成排序。
-
堆排序 (HeapSort)
- 利用最大堆结构将数组调整为有序结构。
- 通过构建堆并逐步提取最大值完成排序，时间复杂度为 O(n log n)。
-
归并排序 (MergeSort)
- 分治策略：将数组不断二分，递归排序后合并两个有序数组。
- 稳定排序算法，适用于链表或大数据集排序。
-
快速排序 (QuickSort)
- 使用三路划分策略优化重复元素处理，随机选择基准值提升性能。
- 在平均情况下具有 O(n log n) 时间复杂度，空间效率高。
该代码库实现了一个通用的读写控制组件，包含多种策略以协调并发场景下的读写优先级。适用于需要对共享资源进行高效、安全访问的场景。
-
接口定义 (ReadWriter)
- 定义统一的读写接口，支持任意类型的数据操作。
-
公平读写策略 (EquityReadWrite)
- 保证读写操作公平竞争，避免某一方长期“饥饿”。
- 使用互斥锁与计数器控制并发访问，确保读写互斥、写写互斥、读读可并行。
-
读优先策略 (ReadFirst)
- 多个读者可以同时访问资源，但一旦有写者进入，后续读者必须等待。
- 适合读多写少的场景，如配置中心、缓存系统等。
-
写优先策略 (WriteFirst)
- 写操作优先于读操作，防止写者长时间等待。
- 确保写入及时生效，适合数据一致性要求高的场景，如日志写入、状态更新等。
该代码库实现了一个通用的限流组件，包含多种限流策略以应对不同场景下的请求控制需求。所有实现均支持基于令牌（Token）、计数（Count）或时间窗口（Window）的限流算法，并结合本地与 Redis 实现分布式环境下的统一限流管理。
-
计数限流 (CountLimiter)
- 基于固定时间窗口内的请求数进行限制。
- 每个时间窗口开始时重置计数器，适用于对突发流量有一定容忍度的场景。
-
漏桶限流 (LeakyBucketLimiter)
- 使用“漏水”模型控制请求速率，平滑输出流量。
- 适合严格控制请求速率、防止突发流量冲击的场景。
-
令牌桶限流 (TokenLimiter)
- 通过定期填充令牌并消费令牌来控制访问频率。
- 支持突发流量，在不超过桶容量的前提下允许短时高并发。
-
滑动窗口限流 (WindowLimiter)
- 将时间划分为多个槽位，记录每个时间段的请求数，滑动更新。
- 更精确地控制平均请求速率，适用于需要细粒度统计的场景。
-
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 机制，确保了跨服务实例的互斥访问，并支持自动续期、阻塞等待和超时释放等高级特性。
-
加锁机制
- 使用
HINCRBY记录每个客户端的持有次数，实现可重入性。 - 若锁未被占用则直接获取并设置过期时间（
PEXPIRE）。 - 支持设置最大等待时间（
waitTime）与持有时间（leaseTime），后者为-1表示启用看门狗自动续期。
- 使用
-
自动续期（Watchdog）
- 在锁成功获取后启动后台协程定期刷新过期时间，防止因业务执行时间过长导致锁提前释放。
-
解锁机制
- 使用 Lua 脚本安全减少引用计数，若计数归零则删除锁并发布解锁消息到 Redis 频道。
- 确保只有加锁方才能解锁，具备身份校验能力。
-
等待通知机制
- 基于 Redis 的 Pub/Sub 模型实现锁释放事件监听。
- 当前线程订阅指定频道，在锁竞争失败时进入等待状态，直到收到解锁通知或超时。
-
可重入支持
- 同一客户端多次加锁会递增引用计数，解锁时需对应次数的递减操作才会真正释放锁。
-
高可用与异常处理
- 加锁失败时自动退避并尝试重新获取，保障在分布式环境下的健壮性。
- 解锁失败或连接中断时提供合理的错误反馈，避免死锁。
| 功能 | 描述 |
|---|---|
| 分布式支持 | 基于 Redis 实现跨节点一致性 |
| 可重入 | 同一客户端可多次获取锁 |
| 自动续期 | 支持 Watchdog 定时刷新锁超时时间 |
| 阻塞等待 | 提供 TryLock 支持带超时的阻塞加锁 |
| 异常恢复 | 断开连接或失败时能正确释放资源 |
| 公平唤醒 | 依赖 Redis Pub/Sub 实现唤醒机制 |
此实现适合作为构建强一致性分布式系统的基础设施之一，可用于替代或增强原生的 Redis 锁方案。
该代码库实现了一个高效的分布式序列号生成系统（Segment ID），适用于需要全局唯一、有序且高性能的 ID 分配场景。通过 Redis 缓存与底层数据库结合，支持高并发请求和故障恢复。
-
接口定义 (SeqDatabase)
- 定义统一的 Malloc 接口用于分配指定大小的序列号区间。
- 支持多种底层存储实现，如本地文件模拟数据库或持久化数据库。
-
缓存机制 (SeqCacheRedis)
- 基于 Redis 实现大序列号段的缓存管理，减少对底层数据库的频繁访问。
- 使用 Lua 脚本保证原子操作，协调多个客户端之间的并发请求。
- 支持锁机制与过期控制，确保数据一致性与自动释放。
- 高性能：利用 Redis 缓存批量预取序列号，显著降低数据库压力。
- 高可用：Redis 故障时可降级至底层数据库，保障服务连续性。
- 强一致性：通过 Redis 锁与 Lua 脚本确保多节点间的同步安全。
- 易扩展：接口设计清晰，便于接入其他底层存储（如 MySQL、ETCD）。
适用于金融交易流水号、订单编号、日志追踪 ID 等需全局唯一且有序递增的业务场景。
该代码库实现了一个高性能缓存组件集合，包含多种主流缓存淘汰策略与统计结构，适用于需要高效内存管理、访问控制和热点数据识别的场景。
-
LFU（Least Frequently Used）lfu.go
- 基于访问频率进行缓存淘汰，使用频率越低的元素优先被清除。
- 通过 freq2items 映射维护每个频率对应的元素链表，并跟踪最小频率以优化淘汰效率。
- 支持并发访问控制，适合长期运行且访问模式变化较大的系统。
-
LRU（Least Recently Used）lru.go
- 基于最近最少使用原则淘汰数据，使用双向链表实现高效的插入与移动操作。
- 引入访问频率阈值（freqThreshold），避免短暂热点导致缓存污染。
- 支持并发安全读写，适合访问局部性较强的场景。
-
CountMin Sketch（CMS）cm_sketch.go
- 概率型数据结构，用于估计高频项（Heavy Hitters）的访问频率。
- 使用多组哈希函数与位压缩技术降低内存占用，支持增量更新与最小值估算。
- 适用于资源有限环境下对访问频次进行快速统计与过滤。
-
TinyLFU 与 Window TinyLFU（扩展预留）
- TinyLFU 是 LFU 的改进版本，引入滑动窗口与计数器衰减机制，提升适应性和空间效率。
- Window TinyLFU 在此基础上进一步限制窗口大小，更适用于时间敏感的热点探测。
- 当前代码仅声明包结构，尚未实现具体逻辑。
-
Segmented LRU（扩展预留）
- 分段 LRU 策略，将缓存划分为多个层级或区域，分别应用 LRU 管理，平衡命中率与公平性。
- 当前文件为空，可作为后续扩展方向。
该代码库实现了一个 AC 自动机（Aho-Corasick Automaton），是一种高效的多模式匹配算法，适用于在一段文本中同时查找多个关键词的出现位置。整体结构清晰，支持插入、删除和匹配操作，适合敏感词过滤、日志关键字检索等场景。
-
AC 自动机结构 (ACAutomation)
- 使用 Trie 树构建基础前缀结构。
- 每个节点包含子节点映射、是否为词尾标识、失败指针（fail）、深度信息。
-
构建 Trie 树 (insert / InsertMany)
- 将输入的字符串逐字符插入 Trie 树。
- 标记每个字符串结尾节点为 isEnd。
-
构建失败指针 (buildFail)
- 类似 KMP 算法中的失败跳转机制，用于加速回溯匹配。
- 通过 BFS 构建，确保每个节点的 fail 指针指向最长可匹配后缀。
-
模式匹配 (Match)
- 输入文本后，在 Trie 中遍历并查找所有匹配的关键词。
- 返回匹配的起始与结束索引（基于 Unicode 字符）。
-
删除关键词 (Delete)
- 定位目标词的结尾节点，并将其标记为非词尾（
isEnd = false），保留结构供其他词使用。
- 定位目标词的结尾节点，并将其标记为非词尾（
-
匹配结果结构 (MatchResult)
- 包含匹配的起始与结束索引，便于定位原始文本中的关键词位置。
- 高效多模匹配：一次构建，多次高效匹配，时间复杂度接近 O(n + m*k)，其中 n 为文本长度，m 为模式数，k 为平均匹配次数。
- 支持动态更新：可随时插入新词或删除旧词，不影响已有结构。
- Unicode 支持良好：使用 rune 表示字符，适配中文等多字节字符。
- 内存友好：Trie 结构共享前缀，节省存储空间。
该代码库实现了三种常见的平衡二叉搜索树结构（AVL 树、Treap、支持分裂与合并的 Treap），适用于需要高效插入、删除、查找和遍历操作的场景。每种实现都提供了基本的树操作，并通过统一的测试用例验证其正确性。
-
AVL 树 (AVLTree)
-
Treap (Treap)
- 结合了二叉搜索树和堆特性的随机化数据结构。
- 每个节点具有一个优先级，插入时通过旋转保持堆性质。
- 插入、删除、查找等操作基于键值比较与优先级判断完成。
-
支持分裂与合并的 Treap (TreapWithSM)
该代码（sync.Pool）实现 Go 标准库中的 sync.Pool 结构，是一个用于临时对象的并发安全缓存池，旨在减少频繁创建和销毁对象带来的性能开销。适用于对象生命周期短、分配频繁、可复用性强的场景。
-
对象缓存与复用
- 提供 Put 和 Get 方法用于存储和获取对象。
- 支持自动释放未使用对象，避免内存泄漏。
-
线程局部（Per-P）缓存机制
- 每个处理器（P）维护一个本地缓存 local，减少锁竞争。
- 使用
pin()将 goroutine 绑定到当前 P，确保缓存访问高效且线程安全。
-
私有与共享队列
-
双阶段回收机制
- 在垃圾回收前保留“受害者缓存”（victim），防止频繁 GC 导致的对象抖动。
- 垃圾回收时将主缓存迁移至受害者缓存，逐步淘汰老数据。
-
自动清理与 GC 集成
- 注册 poolCleanup 函数，在每次 GC 开始前清理 victim 缓存。
- 保证全局缓存一致性，并释放无用对象以减轻 GC 压力。
-
并发安全
- 所有操作均支持多协程并发访问，通过原子操作与内存屏障保障同步语义。
- 使用 race detector 支持检测潜在的数据竞争问题。
| 功能 | 描述 |
|---|---|
| 对象复用 | 存储并复用临时对象，降低内存分配压力 |
| 并发安全 | 多协程同时调用 Put/Get 安全 |
| 自动释放 | 对象可能在任意时间被清除（如 GC 期间） |
| 无锁设计 | 利用 per-P 缓存减少锁争用，提升性能 |
| 可扩展初始化 | 支持设置 New 函数用于按需生成新对象 |
- 缓存临时缓冲区（如
fmt,io等包使用的临时 buffer） - 减少高频小对象的内存分配次数
- 构建高效的线程安全资源池（如数据库连接、对象构造器等）
此结构不适合用于长期存活对象或需要精确控制生命周期的场景，因其内容会在 GC 时被清空，也不适合做严格意义上的对象池（Object Pool）。
该代码（github.com/bytedance/gopkg/util/gopool）实现了一个高性能、可配置的协程池（gopool），适用于管理并限制并发执行任务的数量，避免资源耗尽问题。整体结构清晰，分为 worker 和 task 两部分，并结合对象复用机制提升性能。 核心组件
- 协程池接口 (Pool)
提供统一的任务提交与管理接口：
- Go / CtxGo：提交无上下文或带上下文的任务函数。
- SetCap：动态设置最大并发协程数。
- WorkerCount：获取当前活跃 worker 数量。
- SetPanicHandler：设置全局 panic 捕获处理器。
- 任务模型 (task)
- 使用链表结构维护待执行任务队列。
- 支持上下文传递，便于超时控制和链路追踪。
- 利用 sync.Pool 实现对象复用，降低频繁分配释放带来的 GC 压力。
- 执行单元 (worker)
- 每个 worker 独立运行一个 goroutine，循环从任务队列中取出任务执行。
- 出现 panic 时调用注册的处理函数，确保异常可控。
- worker 对象通过 sync.Pool 复用，减少创建销毁开销。
- 内部任务调度机制
- 任务入队：通过加锁将新任务添加到链表尾部。
- 动态扩容：当任务积压超过阈值且未达容量上限时自动启动新 worker。
- 空闲回收：worker 在无任务时退出并归还至缓存池，减轻系统负载。
该代码（github.com/bytedance/gopkg/lang/mcache）实现了一个高效的字节缓冲区（[]byte）缓存池 mcache，基于大小分级的 sync.Pool 实现，用于优化频繁创建和释放临时字节数组带来的性能损耗。
-
分级缓存
- 使用一个固定大小的 caches 数组，每个元素是一个
sync.Pool。 - 每个 Pool 缓存容量为 2^i 字节的内存块（i ∈ [0, 45]），即支持最大 2^45 字节（约 32TB）的缓存对象。
- 使用一个固定大小的 caches 数组，每个元素是一个
-
内存分配 (Malloc)
- 支持指定长度与最小容量的字节切片分配。
- 自动选择最合适的缓存池，保证
cap(ret) >= cap。 - 利用
bytesHeader结构体操作切片底层字段，提升性能。
-
内存释放 (Free)
- 将使用完的字节切片归还到对应的缓存池中。
- 仅对容量为 2 的幂次方的缓冲区进行回收，确保一致性。
-
索引计算
- 通过 calcIndex 确定应使用的缓存池下标。
- 使用位运算快速判断是否为 2 的幂，并定位最高有效位（BSR）决定索引位置。
-
初始化机制
- 在 init 函数中预初始化所有缓存池，设置默认生成函数以提供统一内存分配方式。
- 每个缓存块实际由
dirtmake.Bytes创建并封装为*byte存储。
| 功能 | 描述 |
|---|---|
| 高性能缓存 | 基于 sync.Pool，避免频繁内存分配与 GC 压力 |
| 多级粒度 | 分为多个 2 的幂次方等级，适应不同大小请求 |
| 安全复用 | 提供统一接口用于获取和释放缓冲区，防止内存泄漏 |
| 并发安全 | 所有操作均线程安全，适用于高并发场景 |
| 内存对齐 | 只缓存容量为 2 的幂的缓冲区，便于管理与复用 |
主从reactor模型（源码阅读）
netpoll（github.com/cloudwego/netpoll） 是一个基于 Go 实现的高性能网络通信库，其核心架构采用 主从 Reactor 模型（Main-Sub Reactor）和 协程池 + 零拷贝缓冲区机制，结合 epoll I/O 多路复用模型，实现了高效的并发网络处理能力。
netpoll 使用了经典的 主从 Reactor 架构：
-
主 Reactor（Main Reactor）：
- 负责监听服务端口并接受新连接。
- 新连接建立后，将其分配给某个 Sub Reactor（Poller），实现负载均衡。
- 通过 EventLoop.Serve() 启动主事件循环，注册 Listener 并开始 Accept 连接。
-
从 Reactor（Sub Reactor）：
- 每个 Sub Reactor 对应一个 Poll 实例（默认为 epoll）。
- 负责监听已连接套接字上的读写事件，并触发相应的回调函数（如 OnRead、OnWrite）。
- 每个连接绑定一个 FDOperator，与 Poll 关联，用于在事件触发时执行具体操作。
该设计使得连接管理与事件处理分离，提升了系统的可扩展性和性能。
netpoll 在处理连接的业务逻辑时使用了 轻量级的协程池机制：
- 当连接上有数据可读时，会启动一个 goroutine 执行 OnRequest 回调来处理请求。
- 每个连接最多只有一个 OnRequest 协程在运行，避免并发问题。
- 请求处理完成后自动释放协程资源，形成类似“轻量级线程池”的结构，提高资源利用率。
此外，对于异步操作（如定时器、超时控制等），也利用 Go 的原生并发特性进行管理。
为了减少内存分配与 GC 压力，netpoll 使用了 链式零拷贝缓冲区（LinkBuffer）配合 字节池 来优化内存使用：
- LinkBuffer 支持按需分配多个 buffer 块，并维护一个链表结构，实现高效的数据读写。
- 缓冲区对象本身可通过 sync.Pool 或自定义缓存机制复用，降低频繁内存申请开销。
- 提供 Malloc, Next, Release 等方法，支持零拷贝读写操作，提升性能。
netpoll 中每个连接都包含两个缓冲区：
- Input Buffer（输入缓冲区）：用于接收来自对端的数据。
- Output Buffer（输出缓冲区）：用于暂存待发送的数据。
两者均实现了零拷贝接口：
- Reader 接口：提供 Next, Peek, Skip, ReadString, ReadBinary 等方法，直接访问底层 buffer 数据，避免额外拷贝。
- Writer 接口：提供 Malloc, Flush, WriteString, WriteBinary 等方法，用户可申请 buffer 写入数据后批量发送。
这种设计显著减少了系统调用次数和内存拷贝，提高了吞吐性能。
netpoll 默认使用 Linux 下的 epoll I/O 多路复用模型：
- 使用
epoll_ctl注册文件描述符事件（EPOLLIN、EPOLLOUT 等）。 - 使用
epoll_wait监听事件并分发到对应的 FDOperator。 - 支持 ET（边缘触发）模式，适用于高并发场景下的事件通知。
关键点包括：
- 事件驱动：只有当有 I/O 事件发生时才会唤醒处理逻辑，节省 CPU 资源。
- 事件封装：每个事件携带对应 FDOperator 的上下文信息，便于快速定位处理逻辑。
- 非阻塞 I/O：所有 socket 设置为非阻塞模式，配合 epoll 使用，避免系统调用阻塞。
此外，还使用了 eventfd 实现 Poll 的主动唤醒机制，确保主线程可以安全退出或重新调度。
| 模块 | 特性 |
|---|---|
| Reactor 模型 | 主从结构，主 Reactor 接收连接，子 Reactor 处理事件 |
| 协程池 | 利用 Go 协程实现轻量级任务调度，每个连接最多一个并发处理 |
| 字节池 | 使用 LinkBuffer 实现高效内存管理，减少 GC 开销 |
| 读写缓冲区 | 零拷贝 Reader/Writer，提升 IO 性能 |
| epoll 模型 | 基于 epoll 实现事件驱动、非阻塞 I/O 和边缘触发机制 |
整体来看，netpoll 通过上述技术组合，构建了一个高性能、低延迟、高并发的网络通信框架，适合构建大规模分布式服务。