4 ms·
> But you are already near to the I/O limit, what happens once you start writing a new file to rewrite the btree? The additional I/O can affect badly the perfor
by ot 16y ago
> But you are already near to the I/O limit, what happens once you start writing a new file to rewrite the btree? The additional I/O can affect badly the performance of the btree.
I wonder if there are any benchmark that compare append-only + compaction vs. updates in-place (with a free list or something). To me it is not obvious why the second should be less I/O-intensive (for example, in-place does random writes while append-only is sequential).
Also, if persistence is done by checkpointing every n seconds (as far as I understand this will be the default behaviour) part of the compaction can be done in memory before committing the batch of the last n seconds worth of operations. In append-only, this can save a lot of I/O if the operations are on a small set of keys.
I think that Bitcask (http://downloads.basho.com/papers/bitcask-intro.pdf http://downloads.basho.com/papers/bitcask-intro.pdf) uses a similar approach, with append-only storage. I would be curious to see a performance comparison with Redis diskstore.
- moe 16y agoMany smart people have pondered long and hard over this exact problem for decades. Why not climb on their shoulders and adopt the WAL approach that's working so well for most RDBMS?
- jbellis 16y agobq. Why not climb on their shoulders and adopt the WAL approach The WAL approach solves a different problem: "how do we provide durable writes with minimal performance impact?" WAL is not queryable, so the question of "how do we efficiently provide random, indexed access to data" is a separate one. (And the traditional answer of B-trees is working increasingly poorly in the face of a growing capacity:seek time gap.)
- btilly 16y agoThe WAL approach solves a different problem: "how do we provide durable writes with minimal performance impact?" WAL does more than that. Part of providing durable writes is to be able to fix up the potentially corrupted associated binary data structure on disk on startup. So, for instance, if you wrote a link before the associated node is actually saved to disk, then when you replay the WAL you're guaranteed to write the link and the node, and are not going to be corrupted.
- moe 16y agoYou are right, I realize I misjudged/simplified the problem somewhat. My mind had spontaneously formed this idea of an in-memory overlay b-tree of committed (WAL) but not yet merged changes... But thinking it through further I have to admit that this would quickly lead to a complexity explosion (MVCC'ish). I also notice my tone in that comment was more snarky than I meant to be, sorry for that. However I still believe that this is a wheel that's been reinvented often enough (and that is complex enough) that it'd be a good idea to focus on researching how the others have eventually solved it - to minimize the risk of repeating history.
- ot 16y agoRDBMS have consistency guarantees that require the engine to fsync at each commit. This ensures that if the system crashes after a transaction no data is lost, but the transaction throughput is limited by the disk writes. Conversely Redis (with BGSAVE or diskstore) and other systems only ensure integrity, which means that if there is a crash you don't end up with a corrupted database, but you may lose the latest data that you wrote in the DB because they haven't yet been committed to disk. Relaxing these guarantees completely changes the rules of the game, so the tradeoffs that work well with RDBMS, such as WAL, may not be the best fit in this world.