FASTER as LRU cache questions

[avonwyss]

We're looking into FASTER for a LRU (Last Recently Used) cache. I've had a look at the samples but since they are not always very explicit about what they do I'm not sure that I have the full picture yet, so it would be helpful to get some answers to the following questions.

Writing and reading with FASTER works already very well (including disk log, using a single log with ByteSpan for both keys and values), so we're now looking into eviction. Here's the planned approach:

1. Eviction based on number or size of cached data, e.g. after 20M entries or so (configurable). Is it correct that all we need to do for LRU operation is to use the CopyReadsToTail.FromReadOnly and truncate using Log.ShiftBeginAddress? Is Log.TailAddress-Log.BeginAddress the metric to be used for determining the untilAddress parameter?

2. Eviction of stale entries based on key content. Our key is a fixed-size struct which includes a version field. All entries but a specific version should be removed. Should we just use a process where we use Session.Compact<CompactionFunctions> for cleaning up?

[badrishc]

Eviction based on number or size of cached data, e.g. after 20M entries or so (configurable). Is it correct that all we need to do for LRU operation is to use the CopyReadsToTail.FromReadOnly and truncate using Log.ShiftBeginAddress? Is Log.TailAddress-Log.BeginAddress the metric to be used for determining the untilAddress parameter?

CopyReadsToTail.FromStorage causes any reads from disk to be copied to the tail of log. CopyReadsToTail.FromReadOnly causes any reads from either disk or the read-only region of memory to be copied to the tail of log. Latter is helpful when you do not want particularly hot items to "escape" to disk only to be immediately brought back to the tail of main memory.

To control total log size, yes, you can look at Log.TailAddress - Log.BeginAddress and use that to control untilAddress for ShiftBeginAddress. Set snapToPageStart to true if your new begin address may not be at a record boundary. Note that file deletion from disk only happens at segment granularity (LogSettings.SegmentSizeBits).

Eviction of stale entries based on key content. Our key is a fixed-size struct which includes a version field. All entries but a specific version should be removed. Should we just use a process where we use Session.Compact for cleaning up?

You can provide a custom compaction function (ICompactionFunctions) to check for deletion status at the time of compacting live entries from the begin address of log to the tail. It will copy all live records to the tail and then shift the begin address. However, note that compaction needs to check for key liveness, i.e., whether there exists a future key insertion with same key. If there is one, then the record is safe to eliminate, else it needs to be copied into the tail. This process involves scanning the entire log.

If you do not need such a check for liveness, you can do the compaction more efficiently yourself as follows:

1. Scan the log from BeginAddress to NewBeginAddress using our store.Log.Scan API [doc link]
2. For each key, check if the key meets version check, if yes, Upsert to tail, and if no, continue.
3. Do ShiftBeginAddress to NewBeginAddress (set snapToPageStart = true as described earlier, if your new begin address may not be at a record boundary).

Other Info

You can take a look at MemOnlyCache -- it operates as an LRU cache, but limited to main memory. It uses heap objects so needs to track heap sizes explicitly, but you do not need that with SpanByte.

Another resource is the documentation on tuning starting here: https://microsoft.github.io/FASTER/docs/fasterkv-tuning/#computing-total-faster-memory

[avonwyss]

@badrishc It's been a while but I want to thank you for the very helpful reply. I've implemented the cache mostly following your suggestions and it indeed works great. Keep up the good work, and thanks again!