sstable: include a blob value index #4552
Comments
|
We should give thought to how this works when a sstable is virtualized. |
Virtualized sstables conceptually slice off a prefix or suffix of the sstable, right? Doesn't that correspond to slicing off a prefix or suffix of this live-value bitmap? Can that slicing be done when the bitmap is read (which occurs rarely) by seeking into the sstable and finding the first/last value ID? Is the above what you're thinking needs to be given thought, or are there additional complexities with virtual sstables? |
|
To be honest, I gave it about 10 seconds of thought when Sumeer brought this up as an aside during the storage weekly. I posted that comment so we'd remember there was something to consider when we got to this. Thinking about it now, I think there's a little bit of a wrinkle in that we need the first and last value ID for a particular referenced blob file among many referenced blob files. Those references can be anywhere within the bounds of the virtual table. We could seek and scan, but in the worst case we would end up iterating over the entirety of the virtual table. I think that'd probably still be fine given its rarity. |
Uh oh!
There was an error while loading. Please reload this page.
As a part of addressing value separation space amplification, we'd like the ability to compact a blob file without compacting referencing sstables. To do this, we need to be able to determine which values within a blob file are still live and which are dead. Once we switch to using an integer ID to identifying values within a blob file (#4483), we can think of this as a problem of encoding a bitmap (logically, not necessarily physically) per referenced blob file where each bit represents a value in a blob file.
Using a physical bitmap might be fine, because compressing the block should remove overhead of sparseness. We don't care much about the uncompressed size of this block, because it's never read or held in-memory until we're performing a blob file compaction. Then it's read once, and we can avoid ever inserting it into the block cache. Even if we use a physical bitmap, we can elide any beginning or ending of the index space that is all zeroes. Because referencing sstables tend to be narrower in the keyspace than the referenced blob files (due to narrowing of sstable boundaries as they descend the LSM), this should meaningful reduce the size of the bitmap.
If the size of the bitmap somehow proves to be a problem, we can easily switch to a run-length encoding.
A blob file rewrite would read the index for the blob file in each extant referencing sstable and OR together the bitmaps to derive the set of live values.
The above ideas are the product of conversations with @sumeerbhola and @petermattis
Informs #112.
Jira issue: PEBBLE-399
The text was updated successfully, but these errors were encountered: