3 ms·

Looks like I already do pretty much all those things in twoskip: https://blog.fastmail.com/2016/12/03/cyrus-databases-twoskip-and-beyond/ https://blog.fastmail

Looks like I already do pretty much all those things in twoskip: https://blog.fastmail.com/2016/12/03/cyrus-databases-twoskip-and-beyond/ https://blog.fastmail.com/2016/12/03/cyrus-databases-twoskip... (except for the level choice. Which is a bit meh to me, because a write will probably trigger 3 fsyncs, so the cost of level choice is very low) That said, my next DB won't have any skiplists in it I don't think, or at most an in-memory one, but not on disk.

ComputerGuru 10y ago
>That said, my next DB won't have any skiplists in it I don't think, or at most an in-memory one, but not on disk. What will you use instead (and why)?
- rawnlq 10y ago
  B-trees, LSM trees, or any data structure that's actually designed to be cache friendly. I think his claim that his optimizations can beat a b-tree is bullshit otherwise he would've shown benchmarks.
  - brongondwana 10y ago
    I haven't written it yet. I suspect I can't beat b-tree in entirely random read workloads.
- falcolas 10y ago
  Adding to rawnlq's comments: Disk access (reads and writes) still happen in chunks, even with SSDs. It's much more efficient to write entire chunks of data out than to write a few hundred bytes over a dozen different chunks. The requirements for writing out a B-Trees to disk is in line with writing out chunks of data, which makes them very popular (and performant) with database implementations. And this doesn't cover how performant CPUs are at performing operations over a contiguous list of data. The complexity may be O(n), but the implementation introduces a fractional constant which can outperform a O(log(n)) algorithm which involves cache misses.
  - vardump 10y ago
    > Disk access (reads and writes) still happen in chunks, even with SSDs. It's much more efficient to write entire chunks of data out than to write a few hundred bytes over a dozen different chunks. To add, also memory access happens in chunks. Currently chunk (cache line) size is 64 bytes on almost all x86 and ARM CPUs. It's the smallest quantity of data you can read from or write to RAM. CPUs can also efficiently prefetch when they detect sequential access patterns, so accessing large contiguous blocks of memory is preferable to achieve high performance.
- brongondwana 10y ago
  Sorry I didn't get back to this. It's a virtual linear log file which gets split occasionally by appending a sorted list of pointers to the end and "closing" that log file, along with occasional tasks repacking the log files together. Individual records (either key/value or key/tombstone) have a pointer showing how far back they cast a "shadow" so you know how long you need to keep tombstones for. Since only the active log file can ever have changes made, you can repack any two adjacent files together into a single compacted log file at any time, removing any duplicates or tombstones that don't cast a shadow outside the range being compacted.

ComputerGuru 10y ago

>That said, my next DB won't have any skiplists in it I don't think, or at most an in-memory one, but not on disk. What will you use instead (and why)?

rawnlq 10y ago
B-trees, LSM trees, or any data structure that's actually designed to be cache friendly. I think his claim that his optimizations can beat a b-tree is bullshit otherwise he would've shown benchmarks.
- brongondwana 10y ago
  I haven't written it yet. I suspect I can't beat b-tree in entirely random read workloads.
falcolas 10y ago
Adding to rawnlq's comments: Disk access (reads and writes) still happen in chunks, even with SSDs. It's much more efficient to write entire chunks of data out than to write a few hundred bytes over a dozen different chunks. The requirements for writing out a B-Trees to disk is in line with writing out chunks of data, which makes them very popular (and performant) with database implementations. And this doesn't cover how performant CPUs are at performing operations over a contiguous list of data. The complexity may be O(n), but the implementation introduces a fractional constant which can outperform a O(log(n)) algorithm which involves cache misses.
- vardump 10y ago
  > Disk access (reads and writes) still happen in chunks, even with SSDs. It's much more efficient to write entire chunks of data out than to write a few hundred bytes over a dozen different chunks. To add, also memory access happens in chunks. Currently chunk (cache line) size is 64 bytes on almost all x86 and ARM CPUs. It's the smallest quantity of data you can read from or write to RAM. CPUs can also efficiently prefetch when they detect sequential access patterns, so accessing large contiguous blocks of memory is preferable to achieve high performance.
brongondwana 10y ago
Sorry I didn't get back to this. It's a virtual linear log file which gets split occasionally by appending a sorted list of pointers to the end and "closing" that log file, along with occasional tasks repacking the log files together. Individual records (either key/value or key/tombstone) have a pointer showing how far back they cast a "shadow" so you know how long you need to keep tombstones for. Since only the active log file can ever have changes made, you can repack any two adjacent files together into a single compacted log file at any time, removing any duplicates or tombstones that don't cast a shadow outside the range being compacted.