Design issues related to superblock switching

[MBronsom]

Hi @geky

We know that when the super block is written more than block_cycles times now, it will trigger the process of switching super blocks. However, from the current observation, after switching blocks, will the two previously used super blocks be discarded. From a user's perspective, this will result in losing space for two blocks. May I ask why this design was considered at that time?

[geky]

Hi @MBronsom, it's a good question.

Technically, the previous superblocks aren't discarded, they are just relegated to containing a single pointer to the active superblocks.

When this happens, the previous superblocks will be written to much less frequently, but will still be updated when the active superblock is moved as a part of wear leveling.

The problem is that we want to be able to move our root block so it can participate in wear leveling, but we also want something at a known location (blocks {0,1}) so we can find our filesystem quickly during mount. Most logging filesystems scan the entire disk to find the most recently written block, but this does not scale well when the disk gets large.

The solution here is to start with the root at blocks {0,1}, but if we noticed a significant amount of writes to blocks {0,1}, we convert the root into a linked-list with the head residing at blocks {0,1} and the tail being the active root in the filesystem. Exactly when we expand the superblocks is a bit arbitrary, so we use block_cycles for this.

In practice, the number of writes needed to update the superblock at {0,1} grows extremely quickly. $c^n$ where $c$ is block_cycles and $n$ is the number of superblocks. So it's unlikely most filesystems end up with more than one or two superblocks.

SPEC.md has a bit more documentation on this: here, though I realize it's not documented well in DESIGN.md...

[MBronsom]

@geky , Thank you for your reply!

Does that mean, as long as the subsequent application of superblocks is not on 0/1, when balancing the wear of superblocks again in the future (for example, using 2/3 currently and applying for 4/5 later), will lfs recycle the 2/3 block?

[geky]

Does that mean, as long as the subsequent application of superblocks is not on 0/1, when balancing the wear of superblocks again in the future (for example, using 2/3 currently and applying for 4/5 later), will lfs recycle the 2/3 block?

Ah yes, it's only the superblock {0,1} that needs to stay at a fixed position. The other superblocks can move around freely.

There's probably a visual way to demonstrate this, though it might be a bit illegible:

block_cycles = 2
assuming random block allocations

.----.----.----.----.----.----.----.----.----.----.
|sb01|                                            |
|r: 0|                                            |
'----'----'----'----'----'----'----'----'----'----'

.----.----.----.----.----.----.----.----.----.----.
|sb01|                                            |
|r: 1|                                            |
'----'----'----'----'----'----'----'----'----'----'

   .-------------.
.--|-.----.----.-v--.----.----.----.----.----.----.
|sb01|         |root|                             |
|r: 2|         |r: 0|                             |
'----'----'----'----'----'----'----'----'----'----'

   .-------------.
.--|-.----.----.-v--.----.----.----.----.----.----.
|sb01|         |root|                             |
|r: 2|         |r: 1|                             |
'----'----'----'----'----'----'----'----'----'----'

   .---------------------------------.
.--|-.----.----.----.----.----.----.-v--.----.----.
|sb01|                             |root|         |
|r: 3|                             |r: 0|         |
'----'----'----'----'----'----'----'----'----'----'

   .---------------------------------.
.--|-.----.----.----.----.----.----.-v--.----.----.
|sb01|                             |root|         |
|r: 3|                             |r: 1|         |
'----'----'----'----'----'----'----'----'----'----'

   .--------..--------.
.--|-.----.-v|-.----.-v--.----.----.----.----.----.
|sb01|    |sb..|    |root|                        |
|r: 4|    |r: 0|    |r: 0|                        |
'----'----'----'----'----'----'----'----'----'----'

   .--------..--------.
.--|-.----.-v|-.----.-v--.----.----.----.----.----.
|sb01|    |sb..|    |root|                        |
|r: 4|    |r: 0|    |r: 1|                        |
'----'----'----'----'----'----'----'----'----'----'

   .--------..----------------------------.
.--|-.----.-v|-.----.----.----.----.----.-v--.----.
|sb01|    |sb..|                        |root|    |
|r: 4|    |r: 1|                        |r: 0|    |
'----'----'----'----'----'----'----'----'----'----'

   .--------..----------------------------.
.--|-.----.-v|-.----.----.----.----.----.-v--.----.
|sb01|    |sb..|                        |root|    |
|r: 4|    |r: 1|                        |r: 1|    |
'----'----'----'----'----'----'----'----'----'----'
   .-----------------------.
   |             .---------|.
.--|-.----.----.-v--.----.-v|-.----.----.----.----.
|sb01|         |root|    |sb..|                   |
|r: 5|         |r: 0|    |r: 0|                   |
'----'----'----'----'----'----'----'----'----'----'
   .-----------------------.
   |             .---------|.
.--|-.----.----.-v--.----.-v|-.----.----.----.----.
|sb01|         |root|    |sb..|                   |
|r: 5|         |r: 1|    |r: 0|                   |
'----'----'----'----'----'----'----'----'----'----'

   .-----------------------..------------------.
.--|-.----.----.----.----.-v|-.----.----.----.-v--.
|sb01|                   |sb..|              |root|
|r: 5|                   |r: 1|              |r: 0|
'----'----'----'----'----'----'----'----'----'----'

   .-----------------------..------------------.
.--|-.----.----.----.----.-v|-.----.----.----.-v--.
|sb01|                   |sb..|              |root|
|r: 5|                   |r: 1|              |r: 1|
'----'----'----'----'----'----'----'----'----'----'

[MBronsom]

Understood, thank you for your response.😊