type
status
date
slug
summary
tags
category
icon
password
Sub-item
Last edited time
Mar 24, 2024 01:53 AM
Parent item
领域
LRU 是 Least Recently Used 的缩写，即最近最少使用，按照时间排序。是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。
最近被频繁访问的数据，将来被访问的几率也更高，会具备更高的留存，从而淘汰那些不常被访问的数据。
主要流程如下：
- 新数据插入到链表头部；
- 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
- 当链表满的时候，将链表尾部的数据丢弃。
LRU插入和更新流程
插入F：挤掉A
访问C：C移到链表头
插入G：挤掉B
插入H：挤掉D
访问E：E移到链表头
插入I：挤掉F
LRU的性能指标和数据结构
LRU 要求查询尽量高效，O(1) 内查询。
只有map结构存储数据才能满足需求， 但是map不能排序。
修改，删除也要尽量 O(1) 完成。
因为要排序，并快速移动数据，map不满足要求，只能使用双向链表。
综上，LRU需要同时使用map和list存储数据。
举例：
在List中，元素类型是list.Element
在Element的Value中存储pair结构数据。
在map结构Keys中， 存储K-V的pair值， 因为查询和插入map后，需要对list更新操作，如果map中只存储value， 那么更新时只能遍历list， 无法做到O(1)，印尼该吃要存储key值， 加快更新查询速度。
LRU的查询操作
LRU插入
总结，LRU 是由一个 map 和一个双向链表组成的数据结构。map 中 key 对应的 value 是双向链表的结点。双向链表中存储 key-value 的 pair。双向链表表首更新缓存，表尾淘汰缓存。如下图：
优化
- 把官方list换成自己实现， 因为官方的有interface类型推断， 影响性能。
- 第一点内存分配与回收 GC 一定要快，最好是 Zero GC 开销
- 第二点执行操作耗时最少
- 由于要做到高并发，瞬间的 TPS 可能会很大，所以要最快的分配内存，开辟新的内存空间。
- 垃圾回收也不能慢，否则内存会暴涨。
- 针对 LRU / LFU 这个问题，执行的操作是 get 和 set，耗时需要最少。耗时高了，系统吞吐率会受到严重影响，TPS 上不去了。
- 再者，在高并发的场景中，一定会保证线程安全。这里就需要用到锁。最简单的选用读写锁。
终极实现：支持高并发
要想做到高并发，需要考虑 2 点，
详细的：
以下举例以 LRUCache 为例。LFUCache 原理类似。
一般要做到并发， 据需要加锁保护，例如：
但这样的锁保护的范围太大，需要减少锁的颗粒度。
下面把数据分区，分成256个分区， 每个分区有自己的锁， 这样不同分区的操作就不会相互影响。
下面使用channel实现：
