[LAC-Tech]

This is a classic appeal to authority. Let's play the argument, not the man.

(My understanding is that the GP wrote LMDB, works on openLDAP, and was a maintainer for BerkelyDB for a number of years. But even if he'd only written 'hello, world!' I'm much more interested in the specific arguments).

[hyc_symas]

Correct, and thank you. I wrote LMDB, wrote a lot of OpenLDAP, and worked on BerkeleyDB for many years. And actually Andy Pavlo invited me to CMU to give a lecture on LMDB a few years back. https://www.youtube.com/watch?v=tEa5sAh-kVk

Andy and I have had this debate going for a long time already.

[gavinray]

Well, I eat my shorts.

Isn't LMBD closer to an embedded key-value store than an RDBMS, though? Also there's a section in the paper that mentions it's single-writer.

[hyc_symas]

Yes, LMDB is an embedded key/value store but it can be used as the backing store of any other DB model you care for. E.g. as a backend to MySQL, or SQLite, or OpenLDAP, or whatever.

[jandrewrogers]

I think the real argument is more nuanced. Where you see mmap() fail badly on Linux, even for read-only workloads, is under a few specific conditions: very large storage volumes, highly concurrent access, non-trivial access patterns (e.g. high-dimensionality access methods). Most people do not operate data models under these conditions, but if you do then you can achieve large integer factor gains in throughput by not using mmap().

Interestingly, most of the reason for these problems has to do with theoretical limitations of cache replacement algorithms as drivers of I/O scheduling. There are alternative approaches to scheduling I/O that work much better in these cases but mmap() can’t express them, so in those cases bypassing mmap() offers large gains.

[pclmulqdq]

GP wrote a key-value store called LMDB that is constrained to a single writer, and often used for small databases that fit entirely in memory but need to persist to disk. There's a whole different world for more scalable databases.

[hyc_symas]

"fit entirely in memory" is not a requirement. LMDB is not a main-memory database, it is an on-disk database that uses memory mapping.

[LAC-Tech]

Can you explain "high-dimensionality access methods" to me? (Or if it's too big for an HN comment, maybe recommend a paper).

[heisjustsosmart]

This guy talks a lot of crap. See his website for examples, and don't waste your time with him

<<<There is one significant drawback that should not be understated. Algorithm design using topology manipulation can be enormously challenging to reason about. You are often taking a conceptually simple algorithm, like a nested loop or hash join, and replacing it with a much more efficient algorithm involving the non-trivial manipulation of complex high-dimensionality constraint spaces that effect the same result. Routinely reasoning about complex object relationships in greater than three dimensions, and constructing correct parallel algorithms that exploit them, becomes easier but never easy.>>>

http://www.jandrewrogers.com/2015/10/08/spacecurve/

[ilyt]

I'd imagine same kind of worst case access would also be a problem doing IO the "classical" way

[gavinray]

The argument is that:

- Queries can trigger blocking page faults when accessing (transparently) evicted pages, causing unexpected I/O stalls

- mmap() complicates transactionality and error-handling

- Page table contention, single-threaded page eviction, and TLB shootdowns become bottlenecks

[hyc_symas]

1 - for reading any uncached data, the I/O stalls are unavoidable. Whatever client requested that data is going to have to wait regardless.

2 - complexity? this is simply false. LMDB's ACID txns using MVCC are much simpler than any "traditional" approach.

3 - contention is a red herring since this approach is already single-writer, as is common for most embedded k/v stores these days. You lose more perf by trying to make the write path multi-threaded, in lock contention and cache thrashing.

[RaisingSpear]

> for reading any uncached data, the I/O stalls are unavoidable.

Excuse me for a silly question, but whilst an I/O stall may be unavoidable, wouldn't a thread stall be avoidable if you're not using mmap?

Assuming that you're not swapping, you'll generally know if you've loaded something into memory or not, whilst mmap doesn't help you know if the relevant page is cached. If the data isn't in memory, you can send the I/O request to a thread to retrieve it, and the initiating thread can then move onto the next connection. I suspect this isn't doable under mmap based access?

[pclmulqdq]

It's kind of disingenuous to talk about how great your concurrency system is when you only allow a single writer. RCU (which I imagine your system is isomorphic to) is pretty simple compared to what many DB engines use to do ACID transactions that involve both reads and writes.

[hyc_symas]

You don't need more than single-writer concurrency if your write txns are fast enough.

Our experience with OpenLDAP was that multi-writer concurrency cost too much overhead. Even though you may be writing primary records to independent regions of the DB, if you're indexing any of that data (which all real DBs do, for query perf) you wind up getting a lot of contention in the indices. That leads to row locking conflicts, txn rollbacks, and retries. With a single writer txn model, you never get conflicts, never need rollbacks.

[jandrewrogers]

> You don't need more than single-writer concurrency if your write txns are fast enough.

This only works on systems with sufficiently slow storage. If your server has a bunch of NVMe, which is a pretty normal database config these days, you will be hard-pressed to get anywhere close to the theoretical throughput of the storage with a single writer. That requires 10+ GB/s sustained. It is a piece of cake with multiple writers and a good architecture.

Writes through indexing can be sustained at this rate (assuming appropriate data structures), most of the technical challenge is driving the network at the necessary rate in my experience.

[hyc_symas]

That's all just false. Just because you're single-writer at the application level doesn't mean the OS isn't queueing enough writes to saturate storage at the device level. We've benchmarked plenty of high speed NVMe devices, like Intel Optane SSDs, etc. showing this. http://www.lmdb.tech/bench/optanessd/

[pclmulqdq]

That's probably because your OpenLDAP benchmarks used a tiny database. If you have multi-terabyte databases, you will start to see huge gains from a multi-writer setup because you will be regularly be loading pages from disk, rather than keeping almost all of your btree/LSM tree in RAM.

[hyc_symas]

Yeah, no. Not with a DB 50x larger than RAM, anyway.

http://www.lmdb.tech/bench/hyperdex/

RAM is relatively cheap too, there's no real reason to be running multi-TB databases at greater than a 50x ratio.

[jeffffff]

take a look at http://nms.csail.mit.edu/~stavros/pubs/OLTP_sigmod08.pdf - the overhead of coordinating multiple writers often makes multi-writer databases slower than single-writer databases. remember, everything has to be serialized when it goes to the write ahead log, so as long as you can do the database updates as fast as you can write to the log then concurrent writers are of no benefit.

[pclmulqdq]

This is another cool example of a toy database that is again very small:

> The database size for one warehouse is approximately 100 MB (we experiment with five warehouses for a total size of 500MB).

It is not surprising that when your database basically fits in RAM, serializing on one writer is worth doing, because it just plainly reduces contention. You basically gain nothing in a DB engine from multi-writer transactions when this is the case. A large part of a write (the vast majority of write latency) in many systems with a large database comes from reading the index up to the point where you plan to write. If that tree is in RAM, there is no work here, and you instead incur overhead on consistency of that tree by having multiple writers.

I'm not suggesting that these results are useless. They are useful for people whose databases are small because they are meaningfully better than RocksDB/LevelDB which implicitly assume that your database is a *lot* bigger than RAM.

[hyc_symas]

> RocksDB/LevelDB which implicitly assume that your database is a lot bigger than RAM.

Where are you getting that assumption from? LevelDB was built to be used in Google Chrome, not for multi-TB DBs. RocksDB was optimized specifically for in-memory workloads.

[ayende]

I am using the same rough model, and I'm using that on a 1.5 TB db running on Raspberry PI very successfully.

Pretty much all storage libraries written in the past couple of decades are using single writer. Note that single writer doesn't mean single transaction. Merging transactions is easy and highly profitable, after all.

[AdamProut]

Yeah for workloads with any long running write transactions a single writer design is a pretty big limitation. Say some long running data load (or a big bulk deletion) running along with some faster high throughput key value writes - the big data load would block all the faster key-value writes when it runs.

No "mainstream" database I'm aware of has a global single writer design.

[jemfinch]

"Taking full control of your I/O and buffer management is great if (a) your developers are all smart and experienced enough to be kernel programmers" is already an appeal to authority in itself.

We shouldn't apply a higher bar to the counterargument than we applied to the argument in the first place.