> It is a durable, consistent, high-performance key-value data store built out of a background-garbage-collected log-structured B+Tree.
Some questions for Colin, if he reads this thread:
I assume log-structured implies 'append-only'. Is that correct?
This seems to be fairly similar in spirit to the design of BDB-JE, but without offering many of JE's features (like ACID). This similarity is a good thing - JE does a really great job in many situations. Have you done any comparisons of kivaloo with BDB and BDB-JE, especially looking at IO constrained performance?
Although its pretty clear why BDB-JE wouldn't be ideal for Tarsnap (starting the the Java thing), why did you chose not to go with BDB? Just a licensing issue, or more technical?
How do you trigger garbage collection? What kind of effect does garbage collection have on the throughput of the database?
What kind of performance drop do you see with very sparse trees/logs, for example with workloads that are very insert and delete heavy?
I haven't had time to look at the source yet, so I apologize if these questions have obvious answers.
I assume log-structured implies 'append-only'. Is that correct?
Yes. (Technically, append-at-head and delete-from-tail only.)
Although its pretty clear why BDB-JE wouldn't be ideal for Tarsnap (starting the the Java thing), why did you chose not to go with BDB?
Last time I checked, BDB was a library. I wanted a server (because a server can cache data structures).
How do you trigger garbage collection?
The code keeps track of how much garbage is present and keeps a running tally of how much garbage collection it "owes" based on maintaining a long-term optimal GC rate. When that value is large enough, it looks for some old pages to clean.
What kind of effect does garbage collection have on the throughput of the database?
"It depends". The optimal cleaning rate depends on the amount of I/O you're already doing, so it turns out that cost-optimization automatically results in you doing more cleaning when the active I/O load is lower. In the common case where the load on the data store varies (either because it's bursty or because of daily/weekly load cycles) there won't be any cleaning happening during the high-load periods.
What kind of performance drop do you see with very sparse trees/logs, for example with workloads that are very insert and delete heavy?
The B+Tree is rebalanced every time pages are written to disk, so "sparse trees" aren't possible.
> Yes. (Technically, append-at-head and delete-from-tail only.)
Do you handle this by breaking the DB up into multiple small files, like BDB-JE?
> The code keeps track of how much garbage is present and keeps a running tally of how much garbage collection it "owes" based on maintaining a long-term optimal GC rate. When that value is large enough, it looks for some old pages to clean.
How long-term is that? I assume you have considered the degenerate case, where load is increasing linearly (instead of more common daily/weekly/etc. cycles) and garbage collection falls behind. In context of your next answer, it seems like this case would cause the GC to get starved out, leading to higher IO requirements for queries, leading to less time to GC, and so on to failure.
Granted, you would have to be running very hot for this to happen, but its possible.
One more question: Have you considered implementing in-memory locking/synchronisation (like a shared mutex)? Offering test-and-set type operations is a nice alternative to full-fledge transactions for many use cases. If these are just used as synchronisation primitives then fsyncing them every time seems wasteful, on the assumption that many use cases don't care about lock durability across server failure.
The block store component in kivaloo uses multiple files, yes.
Needing to do GC won't make you need more I/Os to service requests; the exact same sequence of B+Tree nodes will need to be loaded from disk. The only effect of GC is wasted disk space.
Kivaloo does support a data-loss mode, so you could store locks in a daemon running with that option. Personally I prefer to err on the side of caution when I'm dealing with locking and transactions.
Traditional C based BerkeleyDB is not log structured. BerkeleyDB JE is log structured, but is in Java. I don't see cperciva coding Java and the drawback of Java's IO subsystem is that interaction with page cache can be unpredictable if you're doing something beyond key/value lookups.
BerkeleyDB JE is also designed for low latency operation: the recommended way to run is to keep a checkpoint interval, which is then periodically flushed to disk. The flip side of that is that the larger the checkpoint interval, the longer it takes to recover from a crash (longer segment of the log to validate). It is possible to run it in an "fsync after every txn" mode, however. There are also modes available that allow different levels of transaction isolation and serializability. Looks like Colin wants to support one.
While I'm generally happy with BerkeleyDB JE, I can see Colin's decision especially in the greater context of what he's doing.
Comments
> It is a durable, consistent, high-performance key-value data store built out of a background-garbage-collected log-structured B+Tree.
Some questions for Colin, if he reads this thread:
I assume log-structured implies 'append-only'. Is that correct?
This seems to be fairly similar in spirit to the design of BDB-JE, but without offering many of JE's features (like ACID). This similarity is a good thing - JE does a really great job in many situations. Have you done any comparisons of kivaloo with BDB and BDB-JE, especially looking at IO constrained performance?
Although its pretty clear why BDB-JE wouldn't be ideal for Tarsnap (starting the the Java thing), why did you chose not to go with BDB? Just a licensing issue, or more technical?
How do you trigger garbage collection? What kind of effect does garbage collection have on the throughput of the database?
What kind of performance drop do you see with very sparse trees/logs, for example with workloads that are very insert and delete heavy?
I haven't had time to look at the source yet, so I apologize if these questions have obvious answers.
I assume log-structured implies 'append-only'. Is that correct?
Yes. (Technically, append-at-head and delete-from-tail only.)
Although its pretty clear why BDB-JE wouldn't be ideal for Tarsnap (starting the the Java thing), why did you chose not to go with BDB?
Last time I checked, BDB was a library. I wanted a server (because a server can cache data structures).
How do you trigger garbage collection?
The code keeps track of how much garbage is present and keeps a running tally of how much garbage collection it "owes" based on maintaining a long-term optimal GC rate. When that value is large enough, it looks for some old pages to clean.
What kind of effect does garbage collection have on the throughput of the database?
"It depends". The optimal cleaning rate depends on the amount of I/O you're already doing, so it turns out that cost-optimization automatically results in you doing more cleaning when the active I/O load is lower. In the common case where the load on the data store varies (either because it's bursty or because of daily/weekly load cycles) there won't be any cleaning happening during the high-load periods.
What kind of performance drop do you see with very sparse trees/logs, for example with workloads that are very insert and delete heavy?
The B+Tree is rebalanced every time pages are written to disk, so "sparse trees" aren't possible.
Thanks for the answers, this is very interesting.
> Yes. (Technically, append-at-head and delete-from-tail only.)
Do you handle this by breaking the DB up into multiple small files, like BDB-JE?
> The code keeps track of how much garbage is present and keeps a running tally of how much garbage collection it "owes" based on maintaining a long-term optimal GC rate. When that value is large enough, it looks for some old pages to clean.
How long-term is that? I assume you have considered the degenerate case, where load is increasing linearly (instead of more common daily/weekly/etc. cycles) and garbage collection falls behind. In context of your next answer, it seems like this case would cause the GC to get starved out, leading to higher IO requirements for queries, leading to less time to GC, and so on to failure.
Granted, you would have to be running very hot for this to happen, but its possible.
One more question: Have you considered implementing in-memory locking/synchronisation (like a shared mutex)? Offering test-and-set type operations is a nice alternative to full-fledge transactions for many use cases. If these are just used as synchronisation primitives then fsyncing them every time seems wasteful, on the assumption that many use cases don't care about lock durability across server failure.
The block store component in kivaloo uses multiple files, yes.
Needing to do GC won't make you need more I/Os to service requests; the exact same sequence of B+Tree nodes will need to be loaded from disk. The only effect of GC is wasted disk space.
Kivaloo does support a data-loss mode, so you could store locks in a daemon running with that option. Personally I prefer to err on the side of caution when I'm dealing with locking and transactions.
>Last time I checked, BDB was a library. I wanted a server (because a server can cache data structures).
Which begs the question, why not wrap a server around bdb instead of inventing your own B+Tree store?
Traditional C based BerkeleyDB is not log structured. BerkeleyDB JE is log structured, but is in Java. I don't see cperciva coding Java and the drawback of Java's IO subsystem is that interaction with page cache can be unpredictable if you're doing something beyond key/value lookups.
BerkeleyDB JE is also designed for low latency operation: the recommended way to run is to keep a checkpoint interval, which is then periodically flushed to disk. The flip side of that is that the larger the checkpoint interval, the longer it takes to recover from a crash (longer segment of the log to validate). It is possible to run it in an "fsync after every txn" mode, however. There are also modes available that allow different levels of transaction isolation and serializability. Looks like Colin wants to support one.
While I'm generally happy with BerkeleyDB JE, I can see Colin's decision especially in the greater context of what he's doing.