disagg: make cache persistent

[RaduBerinde]

As a follow-up to #2541, make the cache persistent, using the following ideas:

• we persist the mapping of which logical blocks (in objects) map to which physical blocks (in the cache); we don't persist any other cache eviction metadata
• use a "working set" of blocks (say 100 of them). Whenever a block gets evicted, we don't immediately overwrite/reuse the block but use one of the working set blocks instead. This allows us to delay flushing of the metadata, which is still valid as long as the original block isn't overwritten. After we flush the metadata, the blocks that were evicted become part of the new working set.
• metadata changes can be logged efficiently using the following scheme:
  • consider the metadata to be a table where the i-th entry describes the logical contents of the i-th cache block; the table is fixed in size (say N blocks).
  • we maintain a global "pointer" P to an entry in this table
  • whenever we make a change to the table, we append an entry with the change, and an entry that logs the current value of entry P; P is advanced circularly (i.e. P = (P+1)%N)
  • note that the entire contents of the table are always available from the last 2N entries; we can have a circular log of fixed size 2N with no need for background log rotations / compactions

Jira issue: PEBBLE-191

Epic CRDB-40358

[joshimhoff]

I'm not sure I'm understanding the persistence scheme. Apologies if I'm missing something basic!

whenever we make a change to the table, we append an entry with the change

Are you saying what is stored on disk is a log of updates to the logical block to cache block mapping? So whenever we update the mapping (modulo the batching stuff) we append to the circular log? I think that is what you are saying, but then I don't understand this part:

note that the entire contents of the table are always available from the last 2N entries; we can have a circular log of fixed size 2N with no need for background log rotations / compactions

Why? What if the same entry in the cache is continuously updated? Or what if some entry in the cache is very hot, meaning we have not updated logical block to cache block metadata for it for a long time? I don't understand why we'd see an entry in the circular log in the last 2N entries then.

With a log of fixed size 2N, I can imagine writing the entire table out, on every flush of metadata to disk. Is that what you mean? Since we have 2N entries, can append to not disturb the current flushed metadata, which avoids consistency issues due to partial write, etc. If this is what you are thinking, the last thing I don't understand is P = (P+1)%N. In my mental model, you could do P = (P+1)%3 instead.

Let's imagine we have a 1 TB cache with 1 million blocks. Let's also imagine 13 bytes for a entry in the log. So 13 MBs to flush full cache metadata across all shards. Is that a lot, or does it sound fine?

[RaduBerinde]

Let me write down an example.

Say N = 6. I will denote logical cache blocks with number 0 through 5 and the values as letters (would correspond to filenum/offset pairs).

Say that the table starts out with the values below and P is on 0 (think of P as holding your finger on one of the entries of the table; the finger moves along the table, circularly):

P
|
V
0 1 2 3 4 5
-------------
a b c d e f

Say we need to make the following updates to the cache: 3->h 1->k 3->l 3->m 1->n 4->o

For each real update, we will log two "updates". The second one is not really an update, it just logs the current value of P.
Log of updates:

3->h 0->a  [P moves to 1]
1->k 1->k  [P moves to 2]
3->l 2->c  [P moves to 3]
3->m 3->m  [P moves to 4]
1->n 4->e  [P moves to 5]
4->o 5->f  [P moves to 0]

Among the last 2N entries, if you look at every other update, they will contain each entry exactly once. So the last 2N entries always contain all table values.

This is conceptually not super different from flushing the entire table every N updates; we just de-amortize and flush it bit by bit instead of a single large flush.

The buffer doesn't need to be circular; we could for example have multiple log files of N entries each and keep at most two full files.

With a circular buffer, you need to be able to figure out where the "head" begins. This can be done by including a monotonic sequence number which each update (or batch of updates).

[joshimhoff]

Ah, I get it now! Super cool. I was thinking that P was the monotonic sequence number, which led me astray.

[joshimhoff]

Before I roll off storage in August, I plan to at least merge #2577. More to do after that PR tbc.

[github-actions]

We have marked this issue as stale because it has been inactive for
18 months. If this issue is still relevant, removing the stale label
or adding a comment will keep it active. Otherwise, we'll close it
in 10 days to keep the issue queue tidy. Thank you for your
contribution to Pebble!