### 前言 想要学习分布式缓存的开发，所以决定自己写一个分布式缓存框架。 进行学习的文章和框架有： [七天实现分布式缓存框架](https://geektutu.com/post/geecache-day1.html) [groupcache](https://github.com/golang/groupcache) 这个文章用于记录自己开发时的困惑。 [自己开发的分布式内存框架](https://github.com/StarYuhen/GolCache) --- #### day1  代码如下： [collapse status="false" title="点击展开代码"] ```Golang package Lru import ( "container/list" "fmt" ) // 2022-8-12 lru缓存策略 第一版 https://geektutu.com/post/geecache-day1.html // LRU(Least Recently Used) // 最近最少使用，相对于仅考虑时间因素的 FIFO 和仅考虑访问频率的 LFU， // LRU 算法可以认为是相对平衡的一种淘汰算法。LRU 认为，如果数据最近被访问过， // 那么将来访问的概率也会更高。LRU 算法的实现非常简单，维护一个队列，如果某条记录被访问了， // 则移动到队尾，那么队首则是最近最少访问的数据，淘汰该条记录即可。 // list.PushFront 会将其添加到链表最后的意思时添加到了第一个添加到了最后的就是最后的内容，如添加了test1 // 如：依次添加了 "test1", "test2", "test3",写的DeleteElimination方法就会最先删除test1,因为他在最后， // 后续的list.PushFront 都排在了第一个使用这个添加的元素后面 // Cache 定义缓存结构体 type Cache struct { maxByte int64 // 允许的最大内存 usedByte int64 // 已经使用的内容 linkedList *list.List // 定义的双向链表 cache map[string]*list.Element // 定义的链表缓存字典 OnRemove func(key string, value Value) // 定义的移除回调 } // 构建控制基础结构体,方便淘汰机制使用 type control struct { key string value Value } // Value 关于值的方法 type Value interface { Len() int // 返回当前值的长度 } // Len 返回链表长度--仅供test时使用 func (c *Cache) Len() int { return c.linkedList.Len() } // New 实现New创建基础缓存 func New(max int64, OnRemove func(key string, value Value)) *Cache { return &Cache{ maxByte: max, linkedList: list.New(), // 初始化双向链表 cache: make(map[string]*list.Element), // 使用make 返回初始化内存 OnRemove: OnRemove, } } // Get 查找缓存,同时将查找的双向链表节点移植最前面 func (c *Cache) Get(key string) (Value, bool) { // 这里利用字典的查找方法来使用，ok是因为其实Golang字典中采用查找会自动返回值和是否存在的bool if element, ok := c.cache[key]; ok { // 利用双向链表函数移植最前面 c.linkedList.MoveToFront(element) kv := element.Value.(*control) return kv.value, true } return nil, false } // DeleteElimination 利用缓存淘汰来删除，即移除最近最少访问的节点（队尾）,同时更新占用缓存 func (c *Cache) DeleteElimination() { // back用于返回最后一个元素，也就是队尾,不存在会返回nil if element := c.linkedList.Back(); element != nil { // 删除该节点 c.linkedList.Remove(element) // 删除map的映射 kv := element.Value.(*control) delete(c.cache, kv.key) // 同时更新占用缓存 c.usedByte -= int64(len(kv.key)) + int64(kv.value.Len()) // 进行删除回调 if c.OnRemove != nil { c.OnRemove(kv.key, kv.value) } } } // Add 新增或修改缓存 func (c *Cache) Add(key string, value Value) { if element, ok := c.cache[key]; ok { // 利用双向链表函数移植最前面 c.linkedList.MoveToFront(element) kv := element.Value.(*control) // 更新占用缓存 c.usedByte += int64(value.Len()) - int64(kv.value.Len()) kv.value = value } else { // 不存在则新增,添加到双向链表最后面 element := c.linkedList.PushFront(&control{key, value}) c.cache[key] = element c.usedByte += int64(len(key)) + int64(value.Len()) } fmt.Println(c.linkedList.Back().Value) // 当发现占用大小大于限制的最高大小则开始删除元素 for c.maxByte != 0 && c.maxByte < c.usedByte { c.DeleteElimination() } } ``` [/collapse] 这里发现了一个问题，与借鉴的文章不同的内容。  在他的文章中这个函数是将文章放在队尾的意思，实际上源码注释是写在队列最上面的。 ```Golang // MoveToFront moves element e to the front of list l. // If e is not an element of l, the list is not modified. // The element must not be nil. func (l *List) MoveToFront(e *Element) { if e.list != l || l.root.next == e { return } // see comment in List.Remove about initialization of l l.move(e, &l.root) } ``` 因为这里我不确定，因为想要根据那一篇文章来，但是经过test动手实践后才发现确实是写在队首。  因为文章所有有点错误理解。 按照我的理解是，每一个的添加或修复都会将元素防止队首。 而每一次访问也会将元素改为队首。 每一个自动删除的时候删除的是队尾。 这里采用的平衡缓存淘汰机制是lur。 ##### 1.3 LRU(Least Recently Used) 最近最少使用，相对于仅考虑时间因素的 FIFO 和仅考虑访问频率的 LFU，LRU 算法可以认为是相对平衡的一种淘汰算法。LRU 认为，如果数据最近被访问过，那么将来被访问的概率也会更高。LRU 算法的实现非常简单，维护一个队列，如果某条记录被访问了，则移动到队尾，那么队首则是最近最少访问的数据，淘汰该条记录即可。 --- Loading... ### 前言 想要学习分布式缓存的开发，所以决定自己写一个分布式缓存框架。 进行学习的文章和框架有： [七天实现分布式缓存框架](https://geektutu.com/post/geecache-day1.html) [groupcache](https://github.com/golang/groupcache) 这个文章用于记录自己开发时的困惑。 [自己开发的分布式内存框架](https://github.com/StarYuhen/GolCache) --- #### day1  代码如下： <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-162f2247158d254ff6dd7a6e7112496f34" aria-expanded="true"><div class="accordion-toggle"><span style="">点击展开代码</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-162f2247158d254ff6dd7a6e7112496f34" class="collapse collapse-content"><p></p> ```Golang package Lru import ( "container/list" "fmt" ) // 2022-8-12 lru缓存策略 第一版 https://geektutu.com/post/geecache-day1.html // LRU(Least Recently Used) // 最近最少使用，相对于仅考虑时间因素的 FIFO 和仅考虑访问频率的 LFU， // LRU 算法可以认为是相对平衡的一种淘汰算法。LRU 认为，如果数据最近被访问过， // 那么将来访问的概率也会更高。LRU 算法的实现非常简单，维护一个队列，如果某条记录被访问了， // 则移动到队尾，那么队首则是最近最少访问的数据，淘汰该条记录即可。 // list.PushFront 会将其添加到链表最后的意思时添加到了第一个添加到了最后的就是最后的内容，如添加了test1 // 如：依次添加了 "test1", "test2", "test3",写的DeleteElimination方法就会最先删除test1,因为他在最后， // 后续的list.PushFront 都排在了第一个使用这个添加的元素后面 // Cache 定义缓存结构体 type Cache struct { maxByte int64 // 允许的最大内存 usedByte int64 // 已经使用的内容 linkedList *list.List // 定义的双向链表 cache map[string]*list.Element // 定义的链表缓存字典 OnRemove func(key string, value Value) // 定义的移除回调 } // 构建控制基础结构体,方便淘汰机制使用 type control struct { key string value Value } // Value 关于值的方法 type Value interface { Len() int // 返回当前值的长度 } // Len 返回链表长度--仅供test时使用 func (c *Cache) Len() int { return c.linkedList.Len() } // New 实现New创建基础缓存 func New(max int64, OnRemove func(key string, value Value)) *Cache { return &Cache{ maxByte: max, linkedList: list.New(), // 初始化双向链表 cache: make(map[string]*list.Element), // 使用make 返回初始化内存 OnRemove: OnRemove, } } // Get 查找缓存,同时将查找的双向链表节点移植最前面 func (c *Cache) Get(key string) (Value, bool) { // 这里利用字典的查找方法来使用，ok是因为其实Golang字典中采用查找会自动返回值和是否存在的bool if element, ok := c.cache[key]; ok { // 利用双向链表函数移植最前面 c.linkedList.MoveToFront(element) kv := element.Value.(*control) return kv.value, true } return nil, false } // DeleteElimination 利用缓存淘汰来删除，即移除最近最少访问的节点（队尾）,同时更新占用缓存 func (c *Cache) DeleteElimination() { // back用于返回最后一个元素，也就是队尾,不存在会返回nil if element := c.linkedList.Back(); element != nil { // 删除该节点 c.linkedList.Remove(element) // 删除map的映射 kv := element.Value.(*control) delete(c.cache, kv.key) // 同时更新占用缓存 c.usedByte -= int64(len(kv.key)) + int64(kv.value.Len()) // 进行删除回调 if c.OnRemove != nil { c.OnRemove(kv.key, kv.value) } } } // Add 新增或修改缓存 func (c *Cache) Add(key string, value Value) { if element, ok := c.cache[key]; ok { // 利用双向链表函数移植最前面 c.linkedList.MoveToFront(element) kv := element.Value.(*control) // 更新占用缓存 c.usedByte += int64(value.Len()) - int64(kv.value.Len()) kv.value = value } else { // 不存在则新增,添加到双向链表最后面 element := c.linkedList.PushFront(&control{key, value}) c.cache[key] = element c.usedByte += int64(len(key)) + int64(value.Len()) } fmt.Println(c.linkedList.Back().Value) // 当发现占用大小大于限制的最高大小则开始删除元素 for c.maxByte != 0 && c.maxByte < c.usedByte { c.DeleteElimination() } } ``` <p></p></div></div></div> 这里发现了一个问题，与借鉴的文章不同的内容。  在他的文章中这个函数是将文章放在队尾的意思，实际上源码注释是写在队列最上面的。 ```Golang // MoveToFront moves element e to the front of list l. // If e is not an element of l, the list is not modified. // The element must not be nil. func (l *List) MoveToFront(e *Element) { if e.list != l || l.root.next == e { return } // see comment in List.Remove about initialization of l l.move(e, &l.root) } ``` 因为这里我不确定，因为想要根据那一篇文章来，但是经过test动手实践后才发现确实是写在队首。  因为文章所有有点错误理解。 按照我的理解是，每一个的添加或修复都会将元素防止队首。 而每一次访问也会将元素改为队首。 每一个自动删除的时候删除的是队尾。 这里采用的平衡缓存淘汰机制是lur。 ##### 1.3 LRU(Least Recently Used) 最近最少使用，相对于仅考虑时间因素的 FIFO 和仅考虑访问频率的 LFU，LRU 算法可以认为是相对平衡的一种淘汰算法。LRU 认为，如果数据最近被访问过，那么将来被访问的概率也会更高。LRU 算法的实现非常简单，维护一个队列，如果某条记录被访问了，则移动到队尾，那么队首则是最近最少访问的数据，淘汰该条记录即可。 --- 最后修改：2022 年 08 月 12 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 4 如果觉得我的文章对你有用，请随意赞赏
