-
-
- [freecache](#freecache)
-
- [结构](#结构)
-
- [segment](#segment)
-
- [set()](#set)
-
- [淘汰算法](#淘汰算法)
-
- [get()](#get)
-
- [RingBuf](#ringbuf)
-
- [Write()](#write)
-
- [ReadAt()](#readat)
-
- [Evacuate()](#evacuate)
-
-
<!-- /TOC -->
-
-
# freecache
-
-
-
## 结构
-
-
一个 Cache 有 256 个 segment, 每个 segment 有一把锁。
-
-
一个 segment 有 `256 * n` 个 slot, 每个 slot 存放的是 entry 的指针信息。槽的数量是动态调整的, 如果同一 slotID 对应的槽的数量超过或等于 n 了, 那么槽的数量就会增多一倍。
-
-
segment 的结构如下:
-
-
```go
-
type segment struct {
-
rb RingBuf // 存放具体的数据
-
segId int
-
entryCount int64 // entry 的数量
-
totalCount int64 // entry 的数量, 包括删除的entry
-
totalTime int64 // 时间总和, 用于计算平均时间
-
vacuumLen int64 // 空闲空间, 空闲空间不够的话需要覆盖旧数据
-
slotLens [256]int32 // 每个槽的实际长度
-
slotCap int32 // 每个指针在槽中占用多大空间, 初始时是1
-
slotsData []entryPtr // 指针数组
-
}
-
```
-
-
指针记录了 entry 在 RingBuf 中的信息, 指针结构如下:
-
-
```go
-
type entryPtr struct {
-
offset int64 // 在 RingBuf 中的偏移位置
-
hash16 uint16 // 用于排序的, RingBuf 中的 entry 根据这个字段排序, 查找时使用二分查找。
-
keyLen uint16 // key 长度, 用于比较指针指向的 entry 是不是想要的(主要是可以在不查找 entry 的情况下排除掉一些不匹配的)
-
reserved uint32
-
}
-
```
-
-
具体的数据放在了 RingBuf 中, RingBuf 是一个环形缓存, 底层是一个字节数组, 数组按序写入, 写满后重新从0位置开始写。
-
-
-
## segment
-
-
-
### set()
-
-
slotID 和 hash16 的计算(hashVal 是 `hash(key)` 的值):
-
-
```go
-
slotID := uint8(hashVal >> 8)
-
hash16 := uint16(hashVal >> 16)
-
```
-
-
在一个初始状态的 segment 中写入数据的过程是这样的:
-
-
```go
-
// 查找具有相同 slotID 的 slot, 因为相同 id 的都放在一起了, 像这样: `| idx | idx | id-ok | id-ok | idx | idx | ...`, 所以可以直接根据 slotID 来计算出偏移量
-
slotOff := slotID * slotCap
-
slot := findSlotsSameID(slotsData, slotID, slotOff)
-
// 查找新的 entry 应该在哪个索引位置, 这里使用了二分查找来加速, 根据 hash16 加速
-
idx := lookupSlotIndex(slot, key, hash16)
-
// 把新的 entryPtr 插入到 idx 位置, 保证在 slot 中是按照 hash16 排序的。
-
insertEntryPtr(idx)
-
// 写入到 RingBuf 中的数据按先后顺序分别是: hdr, key, value, [一些空格], 这里的空格可能发生的情况是 value 为空时。
-
insertDataToRingBuf()
-
```
-
-
- 怎么按照 hash16 排序?
-
- 先根据 key 和 hash16 通过二分查找来找到应该放在哪个位置 idx, 然后插入数据的时候插入到 idx 中, 这样就保证了相同 slotID 的那一块数据是按照 hash16 来排序的。
-
- 插入 entryPtr 时的扩容问题?
-
- 插入数据时会检测 slotID 对应的槽中有多少 ptr 了, 如果 `slotLen[id] == slotCap` 了, 再插入 ptr 时就会覆盖旧的 ptr, 所以这里会有一个扩容的操作。
-
- 扩容很粗暴, 直接将 `slotCap * 2`, 然后原来的 ptr 放到正确的位置上。 比如现在是 `|id1|id1|id2|id2|`, 扩容后 slotCap 变为 4, 变成 `|id1|id1| | |id2|id2| | |`。
-
-
-
hdr 的结构如下:
-
-
```go
-
type entryHdr struct {
-
accessTime uint32
-
expireAt uint32
-
keyLen uint16
-
hash16 uint16
-
valLen uint32
-
valCap uint32
-
deleted bool
-
slotId uint8
-
reserved uint16
-
}
-
```
-
-
-
如果前后两个 entry 的 key 相同, 那么前一个 entry 会被删除。 这里的删除分两种情况:
-
1. 新的 value 长度小于等于旧的 value 长度。 这意味着旧 entry 在 RingBuf 中的空间可以被复用, 只需要修改 entryHdr 的信息以及用新 value 覆盖旧 value 即可。
-
2. 新的 value 长度大于旧的 value 长度。此时会将旧 entry 软删除(entryHdr的deleted字段置为true, entryPtr从slotsData中删除)。然后再将新 entry 插入到 RingBuf 中, 将 entryHdr 插入到 slotsData 中。
-
-
-
#### 淘汰算法
-
-
淘汰发生在 `set()` 被调用时, 会检查空闲空间是否能容得下新数据。
-
-
```go
-
func (seg *segment) evacuate(entryLen int64, slotId uint8, now uint32) (slotModified bool) {
-
consecutiveEvacuate := 0 // 连续将有效 entry 重写的次数
-
for seg.vacuumLen < entryLen {
-
// 软删除的 和 过期的, vacuumLen 会增加被删除的 entryLen, 所以下次 oldOff 可以指向下一个 entry.
-
// 重写 entry 的话会修改 end, 但 vacuumLen 不变, 所以下次 oldOff 也可以指向下一个 entry.
-
oldOff := seg.rb.End() + seg.vacuumLen - seg.rb.Size()
-
oldEntry := readEntryByOff(oldOff)
-
// 被软删除了, 回收空间
-
if oldEntry.deleted {
-
consecutiveEvacuate = 0
-
seg.vacuumLen += oldEntryLen
-
continue
-
}
-
// 过期的, 或者最后一次访问时间小于等于平均访问时间的, 或者连续重写 entry 的次数超过 5 次
-
expired := oldHdr.expireAt != 0 && oldHdr.expireAt < now
-
leastRecentUsed := int64(oldHdr.accessTime)*seg.totalCount <= seg.totalTime // accessTime <= totalTime / totalCount
-
if expired || leastRecentUsed || consecutiveEvacuate > 5 {
-
// 删除 ptr 并且标记 entry 被删除了
-
seg.delEntryPtr(oldHdr.slotId, oldHdr.hash16, oldOff)
-
if oldHdr.slotId == slotId {
-
slotModified = true
-
}
-
consecutiveEvacuate = 0
-
seg.vacuumLen += oldEntryLen
-
} else {
-
// evacuate an old entry that has been accessed recently for better cache hit rate.
-
// 将 oldOff 对应的 entry 追加到 ringBuf 后, 相当于重新写了一遍。
-
newOff := seg.rb.Evacuate(oldOff, int(oldEntryLen))
-
// 更新指针的偏移
-
seg.updateEntryPtr(oldHdr.slotId, oldHdr.hash16, oldOff, newOff)
-
consecutiveEvacuate++
-
}
-
}
-
return
-
}
-
```
-
-
在检查空余空间时会将没有被删除的且没有过期的 entry 从前面重写到 RingBuf 后面, 防止被新的数据覆盖。
-
-
-
-
-
### get()
-
-
```go
-
hdr := lookupHdr(slotsData, key, hash16) // 二分查找
-
if expired(hdr) {
-
// 软删除, 标记 hdr.deleted, 删除 entryPtr
-
delEntryPtr()
-
return
-
}
-
// 设置 hdr.accessTime 为当前时间
-
setHdrAccessTime(now)
-
return readValue()
-
```
-
-
-
-
## RingBuf
-
-
### Write()
-
-
代码:
-
-
```go
-
func (rb *RingBuf) Write(p []byte) (n int, err error) {
-
if len(p) > len(rb.data) {
-
err = ErrOutOfRange
-
return
-
}
-
for n < len(p) {
-
written := copy(rb.data[rb.index:], p[n:])
-
rb.end += int64(written)
-
n += written
-
rb.index += written
-
if rb.index >= len(rb.data) {
-
rb.index -= len(rb.data) // 只重置了 index, 没有重置 end
-
}
-
}
-
// begin 和 end 最多相距 len(data)
-
if int(rb.end-rb.begin) > len(rb.data) {
-
rb.begin = rb.end - int64(len(rb.data))
-
}
-
return
-
}
-
```
-
-
假设 RingBuf 大小是 16, 初始状态:
-
-
```
-
0 16
-
+--------------------------------------------------+
-
| |
-
+--------------------------------------------------+
-
^
-
+
-
begin, end, index
-
```
-
-
写了 10 个字节后:
-
-
```
-
0 10 16
-
+--------------------------------+-----------------+
-
| | |
-
+--------------------------------+-----------------+
-
^ ^
-
+ +
-
begin end, index
-
```
-
-
再写 10 个字节后:
-
-
```
-
0 4 16 20
-
+------+-------------------------------------------+ +
-
| | | |
-
+------+-------------------------------------------+ +
-
^ ^
-
+ +
-
begin, index end
-
```
-
-
-
### ReadAt()
-
-
代码:
-
-
```go
-
func (rb *RingBuf) ReadAt(p []byte, off int64) (n int, err error) {
-
if off > rb.end || off < rb.begin {
-
err = ErrOutOfRange
-
return
-
}
-
// off 是相对于 begin 而言的, off - begin 就是从有效数据的某个偏移位置开始读
-
var readOff int
-
if rb.end-rb.begin < int64(len(rb.data)) { // 说明 end 还没有超出 data 的范围
-
readOff = int(off - rb.begin) // 有效数据从 0 开始的
-
} else {
-
readOff = rb.index + int(off-rb.begin) // 有效数据从 index 开始, index 是有效数据的第一个位置, 也是下一个要覆盖写的位置
-
}
-
if readOff >= len(rb.data) {
-
readOff -= len(rb.data)
-
}
-
readEnd := readOff + int(rb.end-off) // 可被读取的数据最长为 end-off.
-
if readEnd <= len(rb.data) { // 没有超出实际边界
-
n = copy(p, rb.data[readOff:readEnd])
-
} else { // 超出实际边界了要分两次读取
-
n = copy(p, rb.data[readOff:])
-
if n < len(p) {
-
// readEnd - len(data) 是从 0 开始的有效数据的长度
-
n += copy(p[n:], rb.data[:readEnd-len(rb.data)])
-
}
-
}
-
if n < len(p) {
-
err = io.EOF
-
}
-
return
-
}
-
```
-
-
假设现在写了 10 个字节, 要全部读取出来, 可能会调用 `ReadAt(p, 0)`, 其中 `len(p) == 10`:
-
-
```
-
0 10 16
-
+--------------------------------+-----------------+
-
| | |
-
+--------------------------------+-----------------+
-
^ ^
-
+ +
-
begin end, index
-
```
-
-
此时读取的位置是 `data[0:10]`
-
-
再次放入 10 个字节后, 状态变为:
-
-
```
-
0 4 16 20
-
+------+-------------------------------------------+ +
-
| | | |
-
+------+-------------------------------------------+ +
-
^ ^
-
+ +
-
begin, index end
-
```
-
-
将刚才写入的 10 个字节读出来, 调用 `ReadAt(p, 10)`, 其中 `len(p) == 10`, 此时读取的位置是 `data[10: 20]`, 分两次读取, 先读取 `data[10:16]`, 再读取 `data[0:4]`。
-
-
-
-
### Evacuate()
-
-
Evacuate 读取特定位置的数据重新写到 RingBuffer 的后面。
-
-
```go
-
func (rb *RingBuf) Evacuate(off int64, length int) (newOff int64) {
-
if off+int64(length) > rb.end || off < rb.begin {
-
return -1
-
}
-
// 转换 off
-
var readOff int
-
if rb.end-rb.begin < int64(len(rb.data)) {
-
readOff = int(off - rb.begin)
-
} else {
-
readOff = rb.index + int(off-rb.begin)
-
}
-
if readOff >= len(rb.data) {
-
readOff -= len(rb.data)
-
}
-
-
if readOff == rb.index {
-
// 读取的位置正好是有效数据开始的位置, 不需要复制了, 直接移动指针就可以了
-
rb.index += length
-
if rb.index >= len(rb.data) {
-
rb.index -= len(rb.data)
-
}
-
} else if readOff < rb.index {
-
// 要读取的数据在 index 前面
-
// 如果 readOff + length 超过了有效数据的范围了呢? 不会的, 上面会检测 off+length 是否在有效数据范围内的
-
var n = copy(rb.data[rb.index:], rb.data[readOff:readOff+length])
-
rb.index += n
-
if rb.index == len(rb.data) {
-
// data 已经写到底了, 读取的数据还不够 length, 读取剩余的数据到 data 开始的位置
-
rb.index = copy(rb.data, rb.data[readOff+n:readOff+length])
-
}
-
} else {
-
// 读取的位置在 index 后面
-
var readEnd = readOff + length
-
var n int
-
if readEnd <= len(rb.data) {
-
// 不用转弯, 要读取的数据在 index - len(data) 之间
-
n = copy(rb.data[rb.index:], rb.data[readOff:readEnd])
-
rb.index += n
-
if rb.index == len(rb.data) {
-
// 既然 readOff > index, readEnd <= len(data), 那这里 index 不可能达到 len(data) 的位置啊
-
rb.index = copy(rb.data, rb.data[readOff+n:readEnd])
-
}
-
} else {
-
// 需要转弯
-
n = copy(rb.data[rb.index:], rb.data[readOff:])
-
rb.index += n
-
var tail = length - n // 还有多少没读的
-
n = copy(rb.data[rb.index:], rb.data[:tail])
-
rb.index += n
-
if rb.index == len(rb.data) { // 写到底了还没有写完
-
rb.index = copy(rb.data, rb.data[n:tail])
-
}
-
}
-
}
-
// 更新 end 和 begin, 确保 begin 和 end 最多相差 len(data) 的长度
-
newOff = rb.end
-
rb.end += int64(length)
-
if rb.begin < rb.end-int64(len(rb.data)) {
-
rb.begin = rb.end - int64(len(rb.data))
-
}
-
return
-
}
-
```
-
- 基本思路是确定从 data 的哪个位置开始读取数据, 然后写到 index 后面。