Get
Get
github.com/uber/jaeger/pkg/cache/lru.go
Jaeger的lru算法主要由2部分组成
- byKey：map[string]*list.Element 保存数据用于 key/value 查询
- byAccess：container/list 双向链表 用于实现懒惰删除
Get
1func (c *LRU) Get(key string) interface{} {
2 c.mux.Lock()
3 defer c.mux.Unlock()
4
5 elt := c.byKey[key]
6 if elt == nil {
7 return nil
8 }
9
10 cacheEntry := elt.Value.(*cacheEntry)
11 if !cacheEntry.expiration.IsZero() && c.TimeNow().After(cacheEntry.expiration) {
12 // Entry has expired
13 if c.onEvict != nil {
14 c.onEvict(cacheEntry.key, cacheEntry.value)
15 }
16 c.byAccess.Remove(elt)
17 delete(c.byKey, cacheEntry.key)
18 return nil
19 }
20
21 c.byAccess.MoveToFront(elt)
22 return cacheEntry.value
23}
通过key从map查询value
- 如果value过期把byKey和byAccess的数据都删除。
- 如果value没有过期就把value移到链表的最前面
Put
1func (c *LRU) putWithMutexHold(key string, value interface{}, elt *list.Element) interface{} {
2 ......
3
4 entry := &cacheEntry{
5 key: key,
6 value: value,
7 }
8
9 if c.ttl != 0 {
10 entry.expiration = c.TimeNow().Add(c.ttl)
11 }
12 c.byKey[key] = c.byAccess.PushFront(entry)
13 for len(c.byKey) > c.maxSize {
14 oldest := c.byAccess.Remove(c.byAccess.Back()).(*cacheEntry)
15 if c.onEvict != nil {
16 c.onEvict(oldest.key, oldest.value)
17 }
18 delete(c.byKey, oldest.key)
19 }
20
21 return nil
22}
把key，value，expiration组成一个元素，并把元素放入链表的最前面
- 如果链表长度超出限制，则删除链表最后的元素