Overview
本文章基于k8s release-1.17分支代码。
之前一篇文章学习 Kubernetes学习笔记之ServiceAccount TokensController源码解析 ，次要学习
ServiceAccount无关常识，发现其中应用了LRU Cache，代码在 L106 。
k8s本人封装了一个LRU cache的对象 MutationCache ，
正好趁此机会温习下 LRU 算法常识。
LRU算法个别也是面试必考算法题，算法内容也很简略很直观，次要是通过在固定容量空间内，不常被拜访被认为旧数据能够先删除，最近被拜访的数据能够认为前面被拜访概率很大，作为最新的数据。比方，
漫画：什么是LRU算法？ 这幅漫画形容的那样，在容量无限状况下，能够删除那些最老的用户数据，留下最新的用户数据。
这样就感觉数据依照顺叙排列似的，最后面的是最新的，最开端的是最旧的数据。
数据存储能够通过双向链表存储，而不是单向链表，因为当晓得链表的一个元素element时，能够通过element.prev和element.next指针就能晓得以后元素的前驱元素和
后驱元素，删除和增加操作算法复杂度都是O(1)，而单向链表无奈做到这一点。
另外一个问题是如何晓得O(1)的查问到一个元素element的值，这能够通过哈希表即 map[key]*element 构造晓得，只有晓得key，就立即O(1)晓得element，
再联合双向链表的O(1)删除和O(1)增加操作。
通过组合双向链表和哈希表组成的一个lru数据结构，就能够实现删除旧数据、读取新数据和插入新数据算法复杂度都是O(1)，这就很厉害很高效的算法了。
设计编写LRU算法代码
首先是设计出一个双向链表list，能够间接应用golang自带的双向链表，代码在 /usr/local/go/src/container/list/list.go ，本文这里参考源码写一个并学习之。
首先设计双向链表的构造，Element对象是链表中的节点元素。这里最要害设计是list的占位元素root，是个值为空的元素，其root.next是链表的第一个元素head，
其root.prev是链表的最初一个元素tail，这个设计是间接O(1)晓得链表的首位元素，这样链表list就形成了一个链表环ring：
// 算法设计：应用哈希表+双向链表实现type Element struct { prev, next *Element Value interface{}}// root这个设计很奇妙，连着双向链表的head和tail，能够看Front()和Back()函数// 获取双向链表的第一个和最初一个元素。root相似一个占位元素type list struct { root Element len int}// root是一个empty Element，作为补位元素使得list为一个ring// list.root.next 是双向链表的第一个元素；list.root.prev 是双向链表的最初一个元素func (l *list) Init() *list { l.root.prev = &l.root l.root.next = &l.root l.len = 0 return l}func (l *list) Len() int { return l.len}而后就是双向链表的新退出一个元素并置于最后面、挪动某个元素置于最后面、从链表中删除某个元素这三个重要办法。
新退出一个元素并置于最后面办法，比较简单：
// element置于newest地位，置于最前func (l *list) PushFront(v interface{}) *Element { e := &Element{ Value: v, } return l.insert(e, &l.root)}// e插入at的地位，at/e/at.next指针须要从新赋值func (l *list) insert(e, at *Element) *Element { // 插入以后地位 e.prev = at e.next = at.next e.prev.next = e e.next.prev = e l.len++ return e}挪动某个元素置于最后面办法：
// 把e置双向链表最后面func (l *list) MoveToFront(e *Element) { if e == l.root.next { return } l.move(e, &l.root)}func (l *list) move(e, at *Element) { if e == at { return } // 从原来地位删除 e.prev.next = e.next e.next.prev = e.prev // 插入以后地位 e.prev = at e.next = at.next e.prev.next = e e.next.prev = e}从链表中删除某个元素办法：
func (l *list) Remove(e *Element) { e.prev.next = e.next e.next.prev = e.prev e.prev = nil e.next = nil l.len--}以上逻辑都比较简单，最初加上返回链表的head和tail元素等等办法：
// 返回list的最初一个元素func (l *list) Back() *Element { if l.len == 0 { return nil } // 这里list是一个ring return l.root.prev}// 返回list的最前一个元素func (l *list) Front() *Element { if l.len == 0 { return nil } // 这里list是一个ring return l.root.next}func (l *list) Prev(e *Element) *Element { p := e.prev if p != &l.root { return p } return nil}可见设计出这样的一个双向链表还是比较简单的，接下来就是LRU对象了。LRU对象蕴含双向链表，同时蕴含哈希表 map[interface{}]*Element 来O(1)查问某个
key的Element数据，残缺LRU代码如下：
type LRU struct { // 指定LRU固定长度，超过的旧数据则移除 capacity int // 双向链表，链表存储每一个*list.Element cache *list // 哈希表，每一个key是Entry的key items map[interface{}]*Element}type Entry struct { key interface{} value interface{}}func NewLRU(capacity int) (*LRU, error) { if capacity <= 0 { return nil, fmt.Errorf("capacity must be positive") } cache := &LRU{ capacity: capacity, cache: new(list).Init(), items: make(map[interface{}]*Element), } return cache, nil}func (c *LRU) Purge() { c.cache.Init() c.items = make(map[interface{}]*Element) c.capacity = 0}// 增加一个Entry，O(1)func (c *LRU) Add(key, value interface{}) (evicted bool) { // (key,value)曾经存在LRU中 if element, ok := c.items[key]; ok { c.cache.MoveToFront(element) // 从双向链表中置前，从原有地位删除，而后置最前 element.Value.(*Entry).value = value // 更新值 return false } entry := &Entry{key: key, value: value} ent := c.cache.PushFront(entry) // 新元素置最前 c.items[key] = ent evict := c.cache.Len() > c.capacity if evict { // 如果超过指定长度，移除旧数据 c.removeOldest() } return evict}func (c *LRU) Get(key interface{}) (value interface{}, ok bool) { if element, ok := c.items[key]; ok { // 置前，复杂度O(1) c.cache.MoveToFront(element) return element.Value.(*Entry).value, true } return nil, false}// 删除最旧的数据O(1)func (c *LRU) removeOldest() { element := c.cache.Back() if element != nil { c.removeElement(element) }}// 算法复杂度O(1)func (c *LRU) removeElement(element *Element) { // 间接应用双向链表的Remove()，复杂度O(1) c.cache.Remove(element) key := element.Value.(*Entry).key // 别忘了从哈希表中删除Entry.key delete(c.items, key)}// 双向链表的长度func (c *LRU) Len() int { return c.cache.Len()}// Keys returns a slice of the keys in the cache, from oldest to newest.func (c *LRU) Keys() []interface{} { keys := make([]interface{}, len(c.items)) i := 0 // 这里从最末端，即最旧的数据开始查问 for ent := c.cache.Back(); ent != nil; ent = c.cache.Prev(ent) { keys[i] = ent.Value.(*Entry).key i++ } return keys}func (c *LRU) Remove(key interface{}) bool { e, ok := c.items[key] if !ok { return false } // 从双向链表中删除element，复杂度O(1)，同时从哈希表items中删除 c.cache.Remove(e) delete(c.items, key) return true}设计好了LRU对象，而后代码测试验证下后果正确性：
// 执行后果没问题func TestSimpleLRU(test *testing.T) { l, _ := NewLRU(128) for i := 0; i < 256; i++ { l.Add(i, i) } if l.Len() != 128 { panic(fmt.Sprintf("bad len: %v", l.Len())) } // 这里v==i+128才正确，0-127曾经被删除了 for i, k := range l.Keys() { if v, ok := l.Get(k); !ok || v != k || v != i+128 { test.Fatalf("bad key: %v", k) } } for i := 0; i < 128; i++ { _, ok := l.Get(i) if ok { test.Fatalf("should be evicted") } } for i := 128; i < 256; i++ { _, ok := l.Get(i) if !ok { test.Fatalf("should not be evicted") } } for i := 128; i < 192; i++ { ok := l.Remove(i) if !ok { test.Fatalf("should be contained") } ok = l.Remove(i) if ok { test.Fatalf("should not be contained") } _, ok = l.Get(i) if ok { test.Fatalf("should be deleted") } } l.Get(192) // expect 192 to be last key in l.Keys() for i, k := range l.Keys() { if (i < 63 && k != i+193) || (i == 63 && k != 192) { test.Fatalf("out of order key: %v", k) } } l.Purge() if l.Len() != 0 { test.Fatalf("bad len: %v", l.Len()) } if _, ok := l.Get(200); ok { test.Fatalf("should contain nothing") }}漫画：什么是LRU算法？ 这篇文章中小灰遇到了一个难题，用户零碎要爆炸了，不晓得怎么去删除那些
缓存的用户数据来缩小内存应用，必定不是随机删除。然而通过双向链表加上哈希表简略组合，形成了一个弱小靠谱的LRU构造，删除最旧的数据，保留最新的数据
(这里假如最近被拜访的数据是新数据，未被拜访的数据则排队置后)，就完满解决了难题，可见LRU算法的奇妙弱小。k8s源码中同样应用了LRU构造，
不会LRU算法看k8s源码都吃力。可见算法和数据结构的重要性，刷leetcode是个须要始终坚持下去的活。
参考文献
漫画：什么是LRU算法？
mutation_cache.go应用LRU Cache
golang自带双向链表：/usr/local/go/src/container/list/list.go
golang-lru
leetcode #146
leetcode #460
leetcode #1625