Ok, so one thing I want to clarify about the l0 SSTs in SlateDB is that they behave slightly differently than l0 SSTs in traditional LSMs. I think it's relevant to the l0 compaction stuff you mention in universal compaction.

With SlateDB, memtables are flushed directly to l0 SSTs on a fixed time interval (flush_ms) or when a size limit is reached (flush_bytes to be implemented in #30). Because we have no WAL, writers that want durability will block on their put() calls until the MemTable with their data is written to object storage as an l0 SST. This allows writers that wantt durable writes to select whether they want to pay for the API cost of more frequent writes (e.g. flush_ms=1) to object storage or incur higher latency by having fewer flushes (e.g. flush_ms=100). This tradeoff is documented in detail in my Materialized View post)

This architecture has a number of side effects when applied to an LSM:

l0 SSTs will tend to have few kv-pairs in them
l0 SSTs will tend to be frequently written

l0 SSTs will have only a few kv-pairs in them when flush_ms causes a memtable to be flushed and write throughput is low. The default is currently 10ms. So any put() will result in an l0 SST within 10ms.

Frequent l0 SSTs will occur whenever we have frequent put's per-second (distributed evenly across the second; i.e. non-bursty). In this case, non-empty memtables will be written to object store every N-milliseconds (due to flush_ms) or whenever the memtable is full (due to flush_bytes under high throughput).

To get concrete, imagine we have a single writer with a sustained write throughput of 100 writes per-second that are evenly distributed across the second. That is, the writer does 1 write every 10ms. Now, imagine we have a 10ms flush_ms set. In such an example, the memtable (with a single write in it) will be flushed every 10ms. At the end of 1 second, we will have 100 l0 SSTs each with a single kv-pair in it.

Of course, as we increase write throughput, SSTs will start to have more kv-pairs. For example, if we have a sustained write throughput of 100,000 writes per-second and a 10ms flush_ms, each l0 SST will average 1,000 kv-pairs.

Long story short, we're going to have tons of l0 SSTs and they might be quite small (like.. just one or two kv-paris) until throughput increases enough. In some sense, l0 looks like a WAL, but written as a bunch of little SSTs.

I think there are two things to consider here:

Read performance when we have a lot of l0 SSTs
Recover time when we have a lot of l0 SSTs

For (1), with flush_ms=10, we'll end up 6,000 l0 SSTs per-minute. At flush_ms=1 (lowest possible latency) we'd have 60,000 l0 SSTs per-minute. Somewhere in this range I suspect reads performance will suffer since we'll have to search every l0 SST (as they're not range partitioned).

For (2), @vigneshc's current proposal uses l0 SSTs as part of the recovery process on startup. Essentially, the manifest that's persisted to object store (and contains a list of SSTs) is only written after compaction. So the recovery process when a new writer starts is to load the manifest from object storage, then list all SSTs in l0 and add those into the in-memory DB state (essentially, merge the list of l0 SSTs with the manifest SSTs). The more l0 SSTs are, the longer this recovery process will take.

For both of these reasons, I'd been thinking of running l0 compaction fairly frequently (like.. on the order of every second). The idea I had was to check every second if there were greater than N SSTs in l0, and if so, trigger an l0 compaction to move all the l0 SSTs into l1. This would allow us to keep the number of l0 SSTs fairly small when there's high write throughput.

A second thought I had was to decouple library's reads from l0 object store SSTs. The way reads currently work is a get() comes into the library, the library checks its memtable, then it checks l0 SSTs, then l1+ ssts (which don't yet exist). Right now the l0 SSTs just exist in object storage, so the library has to go to object storage to read from l0, thus it's could have to read through 1000s of l0 SSTs in high write-throughput cases (see my 1,000 SST per-second example above). If we decouple the l0 on object storage from the l0 in the library, we no longer need to worry about read throughput issues due to high SSTs in l0.

For example, we might decide to merge the mutable MemTables into a single in-memory skiplist after the MemTable is written to l0 SST on object storage. This single in-memory skiplist would represent all of the data that's in l0 on object storage. get() call would check the mutable MemTable, followed by the in-memory l0 skiplist (representing all data in the l0 SSTs), and then l1+ SSTs on object storage. Essentially, the library wouldn't read from the l0 object storage SSTs at all. This treats l0 on object storage only as a WAL. We'd just be using SSTs as the WAL format because we're batching writes to eliminate API cost (see comments at the start of this post).

I'm not sure if this decoupling is strictly required. Between block caching, frequent compaction, and caching SSTs locally on disk, it might not be needed. But been on my mind.

@vigneshc one thing I want your input on is how reasonable it is to trigger an l0->l1 compaction every second. How frequently do you think we can sustain manifest updates on object storage, especially as the manifest size grows?

Uh oh!

Compact SSTs on object storage #7

Description

Metadata

Metadata

Assignees

Labels

Type

Fields

Projects

Milestone

Relationships

Development

Issue actions