关于golang:动手实现一个localcache-设计篇

前言

哈喽，大家好，我是asong。最近想入手写一个 localcache 练练手，工作这么久了，也看过很多共事实现的本地缓存，都各有千秋，本人平时也在思考如何实现一个高性能的本地缓存，接下来我将基于本人的了解实现一版本地缓存，欢送各位大佬们提出宝贵意见，我会依据意见不断完善的。

本篇次要介绍设计一个本地缓存都要思考什么点，后续为实现文章，欢送关注这个系列。

为什么要有本地缓存

随着互联网的遍及，用户数和访问量越来越大，这就须要咱们的利用撑持更多的并发量，比方某宝的首页流量，大量的用户同时进入首页，对咱们的应用服务器和数据库服务器造成的计算也是微小的，自身数据库拜访就占用数据库连贯，导致网络开销微小，在面对如此高的并发量下，数据库就会面临瓶颈，这时就要思考加缓存，缓存就分为分布式缓存和本地缓存，大多数场景咱们应用分布式缓存就能够满足要求，分布式缓存访问速度也很快，然而数据须要跨网络传输，在面对首页这种高并发量级下，对性能要求是很高的，不能放过一点点的性能优化空间，这时咱们就能够抉择应用本地缓存来进步性能，本地缓存不须要跨网络传输，利用和 cache 都在同一个过程外部，疾速申请，实用于首页这种数据更新频率较低的业务场景。

综上所述，咱们往往应用本地缓存后的零碎架构是这样的：

<img src=”https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/95d91bee0d0a40998e971bacb7e44bbc~tplv-k3u1fbpfcp-zoom-1.image” style=”zoom:67%;” />

本地缓存尽管带来性能优化，不过也是有一些弊病的，缓存与应用程序耦合，多个应用程序无奈间接的共享缓存，各利用或集群的各节点都须要保护本人的独自缓存，对内存是一种节约，应用缓存的是咱们程序员本人，咱们要依据依据数据类型、业务场景来精确判断应用何种类型的缓存，如何应用这种缓存，以最小的老本最快的效率达到最优的目标。

思考：如何实现一个高性能本地缓存

数据结构

第一步咱们就要思考数据该怎么存储；数据的查找效率要高，首先咱们就想到了哈希表，哈希表的查找效率高，工夫复杂度为 O(1)，能够满足咱们的需要；确定是应用什么构造来存储，接下来咱们要思考以什么类型进行存储，因为不同的业务场景应用的数据类型不同，为了通用，在java 中咱们能够应用泛型，Go语言中临时没有泛型，咱们能够应用 interface 类型来代替，把解析数据交给程序员本人来进行断言，加强了可扩展性，同时也减少一些危险。

总结：

• 数据结构：哈希表；
• key：string类型；
• value：interface类型；

并发平安

本地缓存的利用必定会面对并发读写的场景，这是就要思考并发平安的问题。因为咱们抉择的是哈希构造，Go语言中次要提供了两种哈希，一种是非线程平安的 map，一种是线程平安的sync.map，为了不便咱们能够间接抉择sync.map，也能够思考应用map+sync.RWMutex 组合形式本人实现保障线程平安，网上有人对这两种形式进行比拟，在读操作远多于写操作的时候，应用 sync.map 的性能是远高于 map+sync.RWMutex 的组合的。在本地缓存中读操作是远高于写操作的，然而咱们本地缓存不仅反对进行数据存储的时候要应用锁，进行过期革除等操作时也须要加锁，所以应用 map+sync.RWMutex 的形式更灵便，所以这里咱们抉择这种形式保障并发平安。

高性能并发拜访

加锁能够保证数据的读写安全性，然而会减少锁竞争，本地缓存原本就是为了晋升性能而设计进去，不能让其成为性能瓶颈，所以咱们要对锁竞争进行优化。针对本地缓存的利用场景，咱们能够依据 key 进行分桶解决，缩小锁竞争。

咱们的 key 都是 string 类型，所以咱们能够应用 djb2 哈希算法把 key 打散进行分桶，而后在对每一个桶进行加锁，也就是锁细化，缩小竞争。

对象下限

因为本地缓存是在内存中存储的，内存都是有限度的，咱们不可能有限存储，所以咱们能够指定缓存对象的数量，依据咱们具体的利用场景去预估这个上限值，默认咱们抉择缓存的数量为 1024。

淘汰策略

因为咱们会设置缓存对象的数量，当触发上限值时，能够应用淘汰策略淘汰掉，常见的缓存淘汰算法有：

LFU

LFU（Least Frequently Used）即最近不罕用算法，依据数据的历史拜访频率来淘汰数据，这种算法核心思想认为最近应用频率低的数据, 很大概率不会再应用，把应用频率最小的数据置换进来。

存在的问题：

某些数据在短时间内被高频拜访，在之后的很长一段时间不再被拜访，因为之前的拜访频率急剧减少，那么在之后不会在短时间内被淘汰，占据着队列前头的地位，会导致更频繁应用的块更容易被革除掉，刚进入的缓存新数据也可能会很快的被删除。

LRU

LRU（Least Recently User）即最近起码应用算法，依据数据的历史拜访记录来淘汰数据，这种算法核心思想认为最近应用的数据很大概率会再次应用，最近一段时间没有应用的数据，很大概率不会再次应用，把最长工夫未被拜访的数据置换进来

存在问题：

当某个客户端拜访了大量的历史数据时，可能会使缓存中的数据被历史数据替换，升高缓存命中率。

FIFO

FIFO（First in First out）即先进先出算法，这种算法的核心思想是最近刚拜访的，未来拜访的可能性比拟大，先进入缓存的数据最先被淘汰掉。

存在的问题：

这种算法采纳相对偏心的形式进行数据置换，很容易产生缺页中断问题。

Two Queues

Two Queues是 FIFO + LRU 的联合，其核心思想是当数据第一次拜访时，将数据缓存在 FIFO 队列中，当数据第二次被拜访时将数据从 FIFO 队列移到 LRU 队列外面，这两个队列依照本人的办法淘汰数据。

存在问题：

这种算法和 LRU-2 统一，适应性差，存在 LRU 中的数据须要大量的拜访才会将历史记录革除掉。

ARU

ARU（Adaptive Replacement Cache）即自适应缓存替换算法，是 LFU 和LRU算法的联合应用，其核心思想是依据被淘汰数据的拜访状况，而减少对应 LRU 还是 LFU 链表的大小，ARU次要蕴含了四个链表，LRU 和 LRU Ghost， LFU 和 LFU Ghost，Ghost 链表为对应淘汰的数据记录链表，不记录数据，只记录 ID 等信息。

当数据被拜访时退出 LRU 队列，如果该数据再次被拜访，则同时被放到 LFU 链表中；如果该数据在 LRU 队列中淘汰了，那么该数据进入 LRU Ghost 队列，如果之后该数据在之后被再次拜访了，就减少 LRU 队列的大小，同时缩减 LFU 队列的大小。

存在问题：

因为要保护四个队列，会占用更多的内存空间。

抉择

每一种算法都有本人特色，联合咱们本地缓存应用的场景，抉择 ARU 算法来做缓存缓存淘汰策略是一个不错的抉择，能够动静调整 LRU 和 LFU 的大小，以适应以后最佳的缓存命中。

过期革除

除了应用缓存淘汰策略革除数据外，还能够增加一个过期工夫做双重保障，防止不常常拜访的数据始终占用内存。能够有两种做法：

• 数据过期了间接删除
• 数据过期了不删除，异步更新数据

两种做法各有利弊，异步更新数据须要具体业务场景抉择，为了投合大多数业务，咱们采纳数据过期了间接删除这种办法更敌对，这里咱们采纳懒加载的形式，在获取数据的时候判断数据是否过期，同时设置一个定时工作，每天定时删除过期的数据。

缓存监控

很多人对于缓存的监控也比拟疏忽，根本写完后不报错就默认他曾经失效了，这就无奈感知这个缓存是否起作用了，所以对于缓存各种指标的监控，也比拟重要，通过其不同的指标数据，咱们能够对缓存的参数进行优化，从而让缓存达到最优化。如果是企业应用，咱们能够应用 Prometheus 进行监控上报，咱们自测能够简略写一个小组件，定时打印缓存数、缓存命中率等指标。

GC 调优

对于大量应用本地缓存的利用，因为波及到缓存淘汰，那么 GC 问题必然是常事。如果呈现 GC 较多，STW 工夫较长，那么必定会影响服务可用性；对于这个事项个别是具体 case 具体分析，本地缓存上线后记得常常查看 GC 监控。

缓存穿透

应用缓存就要思考缓存穿透的问题，不过这个个别不在本地缓存中实现，根本交给使用者来实现，当在缓存中找不到元素时, 它设置对缓存键的锁定; 这样其余线程将期待此元素被填充, 而不是命中数据库（内部应用 singleflight 封装一下）。

参考文章

• https://zhuanlan.zhihu.com/p/…
• https://cloud.tencent.com/dev…
• https://tech.meituan.com/2017…
• https://www.cnblogs.com/vanca…

总结

真正想设计一个高性能的本地缓存还是挺不容易的，因为我也满腹经纶，本文的设计思维也是集体实际想法，欢送大家提出宝贵意见，咱们一起做进去一个真正的高性能本地缓存。

下篇文章我将分享本人的写的一个本地缓存，尽请期待！！！

欢送关注公众号：Golang 梦工厂