一个Golang自研小组件，分享一下研发过程。从2020年团队转型Golang开始，团队内小伙伴在学习Golang的过程中，逐步积累了一些开源组件的使用经验，比如布隆过滤器、位图、localcache等技术组件，结合业务场景，我们将这些开源组件集成起来，形成一套整体解决方案TCache。
视频会员场景下，部分产品功能来自APP的请求量非常大，如果直接透传到存储层，一方面对存储的性能要求会比较高，另一方面一旦请求异常升高，存储可能会成为性能瓶颈，引发故障。因此这里希望能够做适当缓存，减少底层存储的压力，提升系统可用性。我们考察了业界开源的布隆过滤器、位图、localcache等技术组件，发现相关组件非常多，同时各具特点，不同组件可能适合不同场景，这促使我们将众多开源组件集成起来，形成一套整体解决方案，业务根据自身特点配置化选用不同底层组件，这是TCache的设计初衷。
✓ 最上层是一些用到cache的业务场景 ✓ 中间件层：这层是TCache的核心部分，综合底层各个组件，试图构建一个TCache中间件，基本思路是抽象一个统一接口，各算法都可以实现该接口逻辑适配:通过适配逻辑，屏蔽各算法差异，实现抽象接口自适应算法:根据业务特点，自适应选择不同算法配置化设计:业务可以通过配置指定使用特定算法 ✓ 组件层：TCache中间件的实现是基于开源组件的，对这些组件我们进行实验研究:通过实验对比，指出各个组件的优缺点源码分析:通过源码分析，搞懂其实现原理 ✓ 算法层：通过论文解读的形式，搞清楚各个算法的技术原理:缓存替换算法；Bitmap位图；布隆过滤器。
整个TCache计划以下几类组件：KV型结构Cache：已经集成freecache，fastcache和bigcache，localcache存在性判断BitMap：计划集成2个开源组件，经典bitmap和roaring概率性判断BloomFilter：暂未启动大型计数器Hyperloglog：暂未启动
附：cache接口定义
附：构造函数定义，用户可以通过engine指定底层cache
附：缺省实现，tcache提供了一个缺省实现，默认使用freecache
附：localcache的接口定义
BitMap虽不如Cache使用普遍，但也有一定使用场景，目前的开源组件有两条技术路线： 1） 经典BitMap：这类算法一般都是在原始位图的基础上进行内存压缩，以减小内存空间 2） Roaring位图：本质上是一种自适应算法，会动态的根据元素的大小和特征，选择[ArrayContainer,BitmapContainer,RunContainer]中的一种来表示。为了便于使用，这个API仅限于对单个位图的操作，不涉及两个位图之间的集合操作。
附：开源组件的实际接口
做tcache的过程，其实是一个慢慢酝酿的过程，往前可以追溯到19-20年团队从c++切换到golang语言，当时做了一个cache库的技术选型，然后我们知道业界已经有非常多的开源cache库，记得当时我们做了一些功能分析，还做了一些简单的性能对比。在这之后，作为深入学习golang的方法之一，我开始带领团队分析这些开源组件的源码，一边读源码一边用uml做建模，陆陆续续几个同学把所有常见的组件分析了一遍。之所以分析源码，是因为我一直觉得阅读优秀源码是提高编码能力最快最有效的方法之一。看完源码之后，发现只搞懂了这些开源组件的技术实现，里面的算法，别人为什么要那么设计，完全搞不懂。也就是说做完了源码分析，只做到了知其然不知其所以然，然后我们开始找这些算法背后的论文，然后开始研读，慢慢积累了一些读书笔记并发了几篇km文章。看技术论文的过程中，发现几乎所有论文都会对不同算法进行对比分析，用以说明自己算法的优点。受这种思路的启发，我们也建立了一个研究框架，将我们研究过的所有开源组件，从功能和性能两方面多个维度做对比研究，从整体上呈现出各个组件的技术特点。然后是组件化。22年下半年部门发起了技术立项，然后我们发起了TCache项目，将业界常用的缓存组件集成起来，业务可以根据其特点选择不同算法。
本地缓存可认为是一个基于本地内存的KV数据库，相比一般的存储系统，本地缓存对数据一致性的要求相对宽松，常用于缓存一段时间内不太变化的数据。一个优秀的本地缓存组件一般需要具有如下特点： ✓ 线程安全：支持并发访问，在多线程场景下，能处理并发读写等数据竞争问题。 ✓ 高命中率：支持数据过期淘汰，能够适应一些非随机的数据访问规律，缓存热点数据。 ✓ 高吞吐量：避免系统长时间GC，导致实际性能下降。 ✓ 支持内存限制：限制内存使用量，避免OOM影响本身业务。目前常见的golang本地缓存组件有：
● 本地缓存组件核心技术点：设置缓存容量，限制内存大小，避免OOM ✓ key哈希后数据分片，缩小锁粒度 ✓ 优化key哈希算法，减少碰撞 ✓ 实现singleflight机制，避免缓存穿透 ✓ 优化索引和数据的存储结构，规避Go GC，提高吞吐量 ✓ 跟踪和统计缓存访问记录，实现多种缓存替换策略，提高缓存命中率 ✓ 自定义缓存回调函数，可以在key加载、过期、删除时做一些处理 ✓ 持久化和热加载，处理缓存冷启动问题详细信息参考：https://km.woa.com/articles/show/562682
作为学习golang的一部分，开始研究一些经典cache开源组件，一边读源码一边用uml做建模。下面是几个例子。 ✧ 例子：BigCache根据对BigCache实现原理的深入分析，BigCache最适合缓存图片、软件制品、文本以及任何二进制数据，这些数据一经生成则很少修改。BigCache支持数据过期但不支持LRU，本质上是一种先进先出。基本原理：
核心数据结构：
以上只是BigCache的例子，全部组件参见：Cache组件源码分析
✧ 例子：BloomFilter核心数据结构：
字段含义： ● m：底层bitmap长度 ● k：哈希函数个数 ● b：底层存储的bitmap内存使用：
更多内容参见：BloomFilter-Golang源码分析，pishi ✧ 例子：RoaringBitmap核心数据结构：
字段含义： ● highlowcontainer：包装了底层存储bitmap的数据结构roaringArray：字段含义： ● keys：与containers和needCopyOnWrite配合使用，作为一个map。key值对应的是一个int的高16位，以升序排列 ● containers：与keys配合使用，作为一个容器map。value值对应的是对应的container类型，可以是arraycontainer、bitcontainer和runcontainer中的一种 ● needCopyOnWrite：与keys配合使用，作为一个标记map。value值标记在container写入时，是否需要拷贝 ● copyOnWrite：全局标记，container写入时是否拷贝container：
内存使用：
更多内容参见：RoaringBitmap-Golang源码分析，pishi
研究完源码后，发现知其然不知其所以然，然后开始找论文，研究背后的算法。 ✧ 常见的缓存替换算法从策略上大致有以下几种： ➢ Belady最优策略缓存替换的最优算法（MIN/OPT，Optimal）在1966年由Laszlo A.Belady提出，此算法在已知未来所有访问记录的前提下，每次都替换未来不再被访问/最远被访问的现存数据。该算法是理论上的最优算法，因为需要已知未来所有访问记录，并不具备可实现性，通常用于衡量其它缓存替换算法的优劣。 ➢ 随机替换策略随机替换算法（RAND，Random）从现存数据中随机选择一个元素进行替换，该算法不需要维护历史访问记录的任何信息，实现上简单高效，但命中率通常一般。 ➢ 简单排队策略先进先出算法（FIFO，First In First Out）每次替换最先进入缓存的数据，该算法认为最先进入的数据在将来被访问到的可能性最小。FIFO算法存在Belady现象：在某些情况下，缓存容量增大命中率反而降低。 ➢ 最近不使用策略最近最少使用算法（LRU，Least Recently Used）每次替换最久未被访问的数据，该算法认为最近一段时间没有被访问到的数据在将来被访问的可能性最小，这种策略在实际中应用较广。 ➢ 最不经常使用策略最近最不常用算法（LFU，Least Frequently Used）每次替换访问次数最小的数据，该算法的思想是最近一段时间被访问次数最小的数据在将来被访问的可能性最小。 ➢ 重引用间隔预测策略重引用间隔预测算法（RRIP，Re-Reference Interval Prediction）使用M bits来存储每个数据的RRPV值，RRPV值随着每个数据被访问的频率动态变化，每次替换RRPV值等于的数据。 ➢ 近似Belady最优策略Hawkeye算法通过使用过去的访问记录来模拟OPT算法的行为产生输入来训练Hawkeye Predictor，再基于Predictor做决策。 ➢ 机器学习策略PARROT算法将缓存替换任务建模为强化学习任务，目标是找到能使长期累积奖赏最大化的缓存替换策略。 上面对缓存替换算法进行了简要介绍，技术上它们可分为基于经验规则的古典算法和基于机器学习的现代算法。古典算法是人类基于直观经验，对一些数据访问模式人工总结经验而设计得到的一类算法，如RAND、FIFO、LRU、LFU、2Q、MQ、ARC、LRFU、RRIP等。古典算法主要是基于数据的最近访问时间（Recency）或访问频率（Frequency）平衡策略，算法模型和实现相对简单，实际应用较广。现代算法是将缓存替换建模成机器学习任务，基于历史访问记录，利用机器学习技术训练模型，使用习得的模型决策淘汰哪个缓存元素的一类算法，如Hawkeye、PARROT等。现代算法的模型和实现相对复杂，目前还处在实验研究阶段。
详细信息参考：https://km.woa.com/articles/show/562681 ✧ 位图算法，以下是一个相关位图算法的综述2015年清华大学团队以互联网流量归集系统(Internet Traffic-Achival System,ITAS)为研究场景，以ITAS中的重要组成部分索引存储和压缩为重点，综述了位图索引压缩技术。论文中虽然对不同的位图索引压缩技术做了总结，但并未进一步深入其算法原理。因此，本文将从细节的算法方面，对位图索引压缩技术做进一步综述。
详细信息参考：https://km.woa.com/articles/show/569551 ✧ 布隆过滤器，演进关系与技术特征
详细信息参考：https://km.woa.com/articles/show/569014
参考学术论文的方法，我们也建立了一个研究框架，从功能和性能两方面多个维度做对比研究，主要的研究结论如下： 1) 对于整体业务数据量不是很大的高并发场景，推荐使用freecache（PS：freecache内存是根据初始参数预先分配好的，可能会浪费内存） 2) 对于数据量大、高并发，所有数据可共用一个全局的过期时间（比如都是写入60s后过期）的场景，推荐使用bigcache（PS：bigcache仅预先分配少量内存，后续动态扩容）。 3) 对于数据不需要定时过期，且后续需要持久化到磁盘，单个缓存数据都小于64KB，高并发的场景，推荐使用fastcache。 4) 对于可以接受数据写入可能延迟（Set之后立刻去取可能取不到，Delete之后可能还会读到），读多写少的场景，推荐使用localcache。（PS：localcache是内部自研组件） 5) 对于可以接受Set操作不保证成功，对缓存key的价值有清晰认识，数据访问模式符合LFU策略的场景，推荐尝试一下ristretto。（PS：在本文的各基准数据集上ristretto命中率并不高，可能是config设置和cost传值不合适，需要更多探索） 6) 对于数据量小，业务并发量不高的场景，也可以使用gcache（支持过期时间）和golang-lru（不支持过期时间），这两个组件支持多种淘汰算法，其中ARC是一种自适应的缓存淘汰算法，是基于Recency/Frequency的平衡策略。（PS：这里有一篇缓存替换算法的文章） 7) ttlcache、go-cache和burrowcache不太推荐。go-cache无法限制缓存容量，没有淘汰策略，历史数据会一直累积，有OOM的风险。
详细信息参考：https://km.woa.com/articles/show/562682
22年下半年，部门内开始做一些技术立项，于是有了开头的TCache组件：
在构思TCache的时候，MySQL的插件存储引擎体系，给了我们很大启发：
开发TCache组件，本身是一个无心插柳的过程，最后能够结出一个小果实，也是意外之举。从结果来看，我们似乎找到一个既有理论深度又有技术深度的垂直切口深挖，在业务开发的空余间隙里，花时间慢慢沉淀，最终总算是开花结果，弄出一个小组件。如何找到创新方向，既有技术上的长期积累，也需要积极思考业务场景中的公共技术需求，技术和场景找到交叉点就是创新。有时候可遇不可求。
TCache只是一个微创新，但也是一个小的原创，写这篇文章只是介绍一下整个过程。结合当下如火如荼的AICG、ChatGPT，如果也能利用业界的开源工具链，整合出一套原创组件并找到应用场景，比如AI辅助编程、借助AI将UML图转化为代码等等，那么很有可能颠覆我们这个开发行业。
