Algorithm
题目：Leetcode 146. LRU 缓存
LRU（Least Recently Used）缓存算法是一种常用的算法，应用广泛。因此，笔者列举了一些经典实现
方法 0：哈希表 +双向链表
// 时间：40ms，内存：104.91MBclass LRUCache {
private final Map<Integer,DLinkedNode> cache = new HashMap<>(); // 虚拟的头、尾节点 private DLinkedNode head, tail;
private int size; private final int capacity;
public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; }
public void put(int key, int value) { DLinkedNode node = cache.get(key); if(node == null) { DLinkedNode newNode = new DLinkedNode(key, value); // 添加到链表头部 addToHead(newNode); // 加入缓存 cache.put(key,newNode); ++size; if (size > capacity) { // 如果超出容量，删除双向链表的尾节点 DLinkedNode tail = removeTail(); // 从缓存中清除 cache.remove(tail.key); --size; } } else { node.value = value; // 如果 key 存在，先通过哈希表定位，再移到头部 moveToHead(node); }
}
private DLinkedNode removeTail() { DLinkedNode res = tail.prev; removeNode(res); return res; }
private void addToHead(DLinkedNode node) { node.prev = head; head.next.prev = node; node.next = head.next; head.next = node; }
private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; }
private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); }
public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; } // 如果 key 存在，先通过哈希表定位，再移到头部 moveToHead(node); return node.value; }
}
/** * 双向链表 */class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next;
public DLinkedNode() { }
public DLinkedNode(int key, int value) { this.key = key; this.value = value; }}
复制代码
方法 1：jayway 的 json 实现
// com.jayway.jsonpath.spi.cache.LRUCache// 时间：1096ms，内存：112.74MBpublic class LRUCache implements Cache {
private final ReentrantLock lock = new ReentrantLock();
private final Map<String, JsonPath> map = new ConcurrentHashMap<String, JsonPath>(); private final Deque<String> queue = new LinkedList<String>(); private final int limit;
public LRUCache(int limit) { this.limit = limit; }
public void put(String key, JsonPath value) { JsonPath oldValue = map.put(key, value); if (oldValue != null) { removeThenAddKey(key); } else { addKey(key); } if (map.size() > limit) { map.remove(removeLast()); } }
public JsonPath get(String key) { JsonPath jsonPath = map.get(key); if(jsonPath != null){ removeThenAddKey(key); } return jsonPath; }
private void addKey(String key) { lock.lock(); try { queue.addFirst(key); } finally { lock.unlock(); } }
private String removeLast() { lock.lock(); try { final String removedKey = queue.removeLast(); return removedKey; } finally { lock.unlock(); } }
private void removeThenAddKey(String key) { lock.lock(); try { queue.removeFirstOccurrence(key); queue.addFirst(key); } finally { lock.unlock(); }
}
private void removeFirstOccurrence(String key) { lock.lock(); try { queue.removeFirstOccurrence(key); } finally { lock.unlock(); } }
public JsonPath getSilent(String key) { return map.get(key); }
public void remove(String key) { removeFirstOccurrence(key); map.remove(key); }
public int size() { return map.size(); }
public String toString() { return map.toString(); }}
复制代码
方法 2：MySQL 的实现
// com.mysql.cj.util.LRUCachepublic class LRUCache<K, V> extends LinkedHashMap<K, V> { private static final long serialVersionUID = 1L; protected int maxElements;
public LRUCache(int maxSize) { super(maxSize, 0.75F, true); this.maxElements = maxSize; }
@Override protected boolean removeEldestEntry(Entry<K, V> eldest) { return (size() > this.maxElements); }}
复制代码
方法 3：Mybatis 的实现
/** * Lru (least recently used) cache decorator. * org.apache.ibatis.cache.decorators.LruCache * * @author Clinton Begin */public class LruCache implements Cache {
private final Cache delegate; private Map<Object, Object> keyMap; private Object eldestKey;
public LruCache(Cache delegate) { this.delegate = delegate; setSize(1024); }
@Override public String getId() { return delegate.getId(); }
@Override public int getSize() { return delegate.getSize(); }
public void setSize(final int size) { keyMap = new LinkedHashMap<Object, Object>(size, .75F, true) { private static final long serialVersionUID = 4267176411845948333L;
@Override protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) { boolean tooBig = size() > size; if (tooBig) { eldestKey = eldest.getKey(); } return tooBig; } }; }
@Override public void putObject(Object key, Object value) { delegate.putObject(key, value); cycleKeyList(key); }
@Override public Object getObject(Object key) { keyMap.get(key); //touch return delegate.getObject(key); }
@Override public Object removeObject(Object key) { return delegate.removeObject(key); }
@Override public void clear() { delegate.clear(); keyMap.clear(); }
private void cycleKeyList(Object key) { keyMap.put(key, key); if (eldestKey != null) { delegate.removeObject(eldestKey); eldestKey = null; } }
}
复制代码
Review
原文链接：https://xie.infoq.cn/article/0b47c0cd97b58280bc7497165
本期 Review 的是 HashMap 类的源码，HashMap 是程序员日常工作中高频使用的类库，API 的调用很简单，这里不展开。通过深入的研究其实现原理、源码实现、code review 好处多多，长期坚持研究源码一定会让你受益匪浅。
带着问题去 debug 源码是最高效的学习方式之一，问题可以来自于你的疑惑、好奇、面试题...,比如：
new HashMap(size)，size=？时不会触发扩容？
什么是 hash 冲突？HashMap 是如何处理的？hash 冲突太严重的时候，查询效率效率低下，HashMap 采取了链表转红黑树来优化，底层是如何实现的？
扩容是如何具体实现的？
HashMap 是线程不安全，如何写一个 test case 来触发验证？
如果让你来设计一个类似的容器类，你会怎么设计？HashMap 的实现能给你什么启发？
Tip
因公司开拓了数据分析的业务，引入了 ETL 工具 RestCloud，已经使用它处理了 2 个数据同步的业务问题，后续还要继续研究下这个组件。不过也不要迷信这个工具，目前团队就发现了它一个和线程池异步相关的低级严重 bug。
Share
2023.08.26 深圳字节跳动举办了一场线下的技术分享。《云原生系列-从资源上云到深度用云》
直播回放：https://juejin.cn/live/7757766
分享 PPT：https://aozev637mr.feishu.cn/file/N98qbslhVoHJiJx633EcQHignHe?from=from_copylink
分享会讲了 4 个主题的实践，我对第 2 个主题尤其感兴趣，后面具体来分享，总体来说有以下几点收获：
体量大、集群规模大。
大公司的研究粒度、深度超乎想象。基于 eBPF 的可观测性实践，这是一种基于内核层的方案，粒度细化的可见一斑。
FinOps，云原生成本治理是直接和钱息息相关的主题，这在小公司很难看到有在应用，可能受限于精力和能力做不了此方面的研究吧。
字节跳动基于 eBPF 的可观测性实践
经典的 Kubernetes+Prometheus+Grafana 解决方案
OpenTelemetry 解决方案
可是仅仅这些还不够，字节还面临以下的挑战
于是引入了 eBPF 来细化可观测的粒度，下面是 eBPF 技术的基本概念和基本原理
后续就是具体的技术细节分析了，感兴趣的同学可以去看 ppt。
#ARTS 打卡计划#
评论