3 ms·

Happy to fill in the gaps here. Building a data structure that is lock free, performant at concurrent reads and writes, and fast at scanning data is very challe

by ankrgyl 12y ago

Happy to fill in the gaps here. Building a data structure that is lock free, performant at concurrent reads and writes, and fast at scanning data is very challenging. Skip lists enable us to implement this in a straightforward way, but are aggressive with respect to random access. You can indeed leverage swap to extend a lock free skip list onto the disk, but the fact that a skip list links together nodes with pointers does not play very well with swap. Swap performance for random access is an extremely well known problem in Linux. Disk-based databases reduce their dependence on random access by using data structures like B-Trees, which do a much better job (i.e. maintain good scan and seek performance) as they spill on and off the disk. These data structures, however, are not feasible to implement lock free.

colanderman 12y ago
So it's not a disk vs. memory thing, it's a B-tree vs. skiplist thing. That makes a lot more sense.
- latch 12y ago
  I'm pretty sure the two are related, no? A B-trees is a disk-friendly structure (shallow and wide), skiplist aren't (but they are a concurrency friendly structure)
  - colanderman 12y ago
    Right. My point is that "you can't use atomic instructions with disk-backed databases" is oversimplified to the point of being incorrect: it's wholly feasible for, say, Postgres to implement a skiplist-based index (or some other lock-free data structure) while still backing its store with the disk, with the only downside being a performance hit if working memory is not large enough.
jeffdavis 12y ago
Do you think this is a fundamental trade-off, or does it just happen that the structures we know about that are good at lock-free happen to have a lot of random access? Kind of a loaded question, because obviously new research might reveal new algorithms. I'm just trying to get an idea whether you think there is a fundamental connection between lock-free and random-access structures.

by ankrgyl 12y ago

colanderman 12y ago

So it's not a disk vs. memory thing, it's a B-tree vs. skiplist thing. That makes a lot more sense.

latch 12y ago
I'm pretty sure the two are related, no? A B-trees is a disk-friendly structure (shallow and wide), skiplist aren't (but they are a concurrency friendly structure)
- colanderman 12y ago
  Right. My point is that "you can't use atomic instructions with disk-backed databases" is oversimplified to the point of being incorrect: it's wholly feasible for, say, Postgres to implement a skiplist-based index (or some other lock-free data structure) while still backing its store with the disk, with the only downside being a performance hit if working memory is not large enough.

jeffdavis 12y ago

Do you think this is a fundamental trade-off, or does it just happen that the structures we know about that are good at lock-free happen to have a lot of random access? Kind of a loaded question, because obviously new research might reveal new algorithms. I'm just trying to get an idea whether you think there is a fundamental connection between lock-free and random-access structures.