前言
前段时间, 校招投了 golang 岗位, 但是没什么好的项目往简历上写, 于是参考了许多网上资料, 做了一个简单的分布式缓存项目.
现在闲下来了, 打算整理下.
GitHub 项目地址: https://github.com/Jun10ng/Gache
里面还有我整理的一些面试问题, 给颗星吧.
typora-root-url: ./
Golang 校招面试项目 - 类 Redis 分布式缓存
实现一个分布式缓存, 功能有: LRU 淘汰策略, http 调用, 并发缓存, 一致性哈希, 分布式节点, 防止缓存击穿
实现 LRU 淘汰策略
LRU 的数据结构大致如下, 上层是一个 map,key 是数据对象的 key 值, 而 value 值则是指向 下层双向链表的节点, 在双向链表中, 每个节点存储的元素是完整的数据对象, 包含 key 值和 value.
get: 存在 -> 将元素所在节点提到最前面, 不存在 -> 返回失败
add: 存在 -> 更新, 不存在 -> 增加; 将元素所在节点提到最前面, 判断是否大于 maxSize
removeOldest: 删除链表最后方的节点
代码实现
具体代码实现看: https://github.com/Jun10ng/Gache/tree/master/lru
定义了三个数据结构
Value 是 golang 中的接口类型, 可以理解为 java 中的 Object 类, 是一个能 "兜底" 所有数据结构的数据类型.
entry 是一个双向链表存储的数据结构
Cache 则是 lru 核心数据结构, 包含一个哈希表和一个双向链表
- type Value interface {
- // 返回占用的内存大小
- Len() int
- }
- type entry struct {
- key string
- value Value
- }
- type Cache struct {
- // 允许使用的最大内存
- maxBytes int64
- // 当前已使用的内存
- nbytes int64
- ll *list.List
- cache map[string] *list.Element
- // 某条记录被移除时的回调函数, 可以是 nil
- OnEvicted func(key string, value Value)
- }
这里说一下 OnEvicted 成员, 这是一个函数对象, 他的作用是, 在缓存中没有需要的数据对象时, 我们需要去原始数据源获取,(Redis 中没有, 就需要去数据库中获取), 但是数据源不唯一, 有时候是数据库, 有时候是磁盘, 有时候是表格, 他们的获取方式都不相同, 所以 OnEvicted 成员传入的函数, 就是自定义的获取方法.
实现单机并发
具体代码实现:
上文实现的 LRU 数据结构并不支持并发, 需要加锁来实现并发, 所以使用 sync.Mutex, 在 LRU 数据结构上封装, 使之实现并发功能.
- type cache struct {
- mu sync.Mutex
- lru *lru.Cache
- cacheBytes int64
- }
cache 并没有 new 方法, 因为采用的是延迟初始化 在 add 方法中, 判断 c.lru 是否为 nil, 如果等于 nil 再创建 这种方法称为延迟初始化, 一个对象的延迟初始化意味着该对象的 创建将会延迟至第一次使用该对象时. 这个方法在 Redis 中很常见, 因为能一定程度上提高性能
- func (c *cache) add(key string, value ByteView){
- c.mu.Lock()
- defer c.mu.Unlock()
- if c.lru == nil{
- c.lru = lru.New(c.cacheBytes,nil)
- }
- c.lru.Add(key,value)
- }
主体结构
具体代码实现:
本质上是再进行一次封装
难道一台机器就只有一个缓存表吗? 你打开 Redis 的可视化工具, 能看到 Redis 还有 16 个池呢, 所以我们要实现多个缓存表. 怎么做? 再加一层. 试想一下:
- //groups 实例集合表
- groups = make(map[string]*Group)
我们要实现的数据结构大致是这样的, 是一个存储并发 cache 的表, 这是本项目的核心结构
- // 这里的 group 是实例
- type Group struct {
- name string
- getter Getter
- mainCache cache
- }
http 服务调用
具体代码实现:
当请求 URL 具有前缀 /_Gache / 时, 则认为该请求为缓存调用.
约定的请求 URL 为: http://XXX.com/_Gache/<groupname>/<key>
groupname 字段为主体结构中 groups 中的某个元素的 name 值, 由此调用. key 字段为元素中的元素的 key 值, 所以最后逻辑为
- groups[groupname][key]
- TODo
一致性哈希
分布式节点
主要参考资料: https://geektutu.com/post/geecache.html
来源: https://www.cnblogs.com/Jun10ng/p/12628081.html