10 ms·
Design Review: Key-Value Storage
- deleted 8y ago[deleted]
- amelius 8y agoSeems like an instance of reinventing the wheel ...
- wvenable 8y agoFrom the article: "We propose ‘buying’, not building, the core of such a solution, and wrapping it in idiomatic libraries that we can use on all platforms. We propose that LMDB is a suitable core (see Appendix A for options considered): it is compact (32KB of object code), well-tested, professionally maintained, reliable, portable, scales well, and is exceptionally fast for our kinds of load. We have engineers at Mozilla with prior experience with LMDB, and their feedback is entirely positive."
- cpeterso 8y agoHow so? The project is building upon an existing key-value store (LMDB) to replace some custom data stores in Firefox using flat text files, JSON files, Kinto, and SQLite.
- ska 8y agoCurious comment. My reading of it is exactly the opposite of reinventing any wheels.
- smacktoward 8y agoBring back Mork! ducks
- jcranmer 8y agoMork actually sucked even as a key-value store. It's only decent if your requirements are a) only lookup on a fixed, autoincrement integer ID, b) the only operation you're likely to do is load an entire record or store an entire record at once, and c) parallelism is not in your vocabulary. Disclaimer: I'm one of the last people to make functional changes to mork.
- majewsky 8y agoThat's not a "Disclaimer". It's actually the polar opposite... a "Claimer"? ... I think "Source" is the best word to use there.
- pvg 8y agoWelcome to the war, majewsky. https://news.ycombinator.com/item?id=17607457#17618288 https://news.ycombinator.com/item?id=17607457#17618288
- majewsky 8y agoHah! :) I've been meaning to call out other misuses of "Disclaimer" vs. "Disclosure" before, but I usually don't because it's just tedious.
- espeed 8y agoNB: NB works for me.
- lclarkmichalek 8y agoI'm really surprised LSM trees didn't get more commentary. 'All are targeted at server workloads' - sure, but they're also incredibly popular and appear to be as close to the 'one-size-fits-all solution for storage' as we've found.
- coleifer 8y agoAlso typically more complicated and require a separate compaction process. They're good for writing lots of data, but not so great for random reads.
- mrjn 8y agoAuthor of Badger here. Our design of separating keys and values has gotten us incredibly fast writes, while still keeping the read latencies neck-to-neck against B+ trees. Worth checking out: https://github.com/dgraph-io/badger https://github.com/dgraph-io/badger
- nekitamo 8y agoThis looks very interesting. Do you have any builtin compression or tips on compressing data?
- dana321 8y agoBadger is really good, i'm using it.
- thstart 8y ago“Please note that Badger obtains a lock on the directories so multiple processes cannot open the same database at the same time.” With RocksDB there is not such limitation. Do you plan to lift it?
- digikata 8y agoBadger looks nicely done! Did you end up needing to change much in implementing Badger from what was described in the WiscKey paper?
- mamcx 8y agoI see their have some questions (like how good is the windows and android support) that are not answered? or only internally? I think will be good to see what them found.
- hyc_symas 8y agoWindows and Android are fully supported, have been for years. As are iOS and MacOSX and all the BSDs.
- mamcx 8y agoThats great to know, and I suspect that. But what I'm saying is that them ask some valid questions but where are the results of their findings? Because if I read this, I could conclude LMDB could have troubles in that areas...
- stevewilhelm 8y agoHow does this compare to Redis?
- detaro 8y agoRedis isn't embeddable, but a standalone server application, and thus it's not really the same space.
- nosequel 8y agoIt actually stores data.
- bgilroy26 8y agoThank you for asking this question. I don't know a lot about databases, but I would have thought redis, as a major key-value store, would have been part of this evaluation. So your answers were helpful.
- shekispeaks 8y agoThis doc says LevelDB has no transacion, thats not true, they have batch writes and LEVEL-DB is not implemented in Go. Its implemented in CPP
- derefr 8y ago> LEVEL-DB is not implemented in Go. Its implemented in CPP There is more than one implementation of LevelDB. This one (https://github.com/syndtr/goleveldb https://github.com/syndtr/goleveldb), in Go, is used in major projects such as https://github.com/ethereum/go-ethereum https://github.com/ethereum/go-ethereum.
- floatingatoll 8y agoTransactions let you perform any series of SQL commands with various expectations around data safety and locking guarantees depending on isolation level. Batch writes provide a tiny subset of the full possibilities of transactions. While sufficient in many cases, that cannot be generalized to "LevelDB supports transactions".
- romed 8y agoThat's just your pet definition of transaction. That is not universally accepted.
- Twirrim 8y agoI would love to see an example of someone actually knowledgeable about databases who has a different definition for transaction.
- erpellan 8y agoAtomicity, consistency, isolation, durability. https://en.wikipedia.org/wiki/ACID_(computer_science) https://en.wikipedia.org/wiki/ACID_(computer_science) But that's just like, the industry's opinion, man.
- acqq 8y agoI thought that the issues like this would be blocking: https://stackoverflow.com/questions/44407659/how-to-force-64-bit-lmdb-to-generate-a-32-bit-database https://stackoverflow.com/questions/44407659/how-to-force-64... Who knows how it should work on 32-bit systems? And isn't endianess also a problem? And doesn't SQLite solve both problems by default? And isn't also possible to configure SQLite to be very fast, if one know what he's doing? Btw I'd expected that the "notes here" https://docs.google.com/document/d/1bwbpqPb58a0GcEyB4W424pyftPFiZBSvxxp_0uuN-z0/edit https://docs.google.com/document/d/1bwbpqPb58a0GcEyB4W424pyf... are conclusions, but the document seems to be not publicly accessible.
- mykmelez 8y agoAccording to @hyc in https://monero.stackexchange.com/questions/2606/are-the-lmdb-files-cross-platform-compatible/2607#2607 https://monero.stackexchange.com/questions/2606/are-the-lmdb..., "As of v0.10.0, yes the LMDB files are cross-compatible between 32 and 64bit architectures. They have always been cross-compatible between OSs. They are still byte-order dependent but almost everyone uses little-endian CPUs these days so it's not much of an issue."
- acqq 8y agoSo the endianness answer is, from your link: "They are still byte-order dependent but almost everyone uses little-endian CPUs these days so it's not much of an issue." Which just means "we solve the problem by ignoring it completely." And what about the limitations on the 32-bit system? Isn't there also needed to use memory space of RAM for the complete size of the database, that's how that database works if I understood? Which makes LMDB effectively unsuitable for 32-bit systems: https://stackoverflow.com/questions/52862176/lmdb-open-large-databases-in-a-limited-memory-system https://stackoverflow.com/questions/52862176/lmdb-open-large... "your user will need to either enable PAE on their system, or upgrade to 64-bit CPU. If neither of these is an option in your application, then you cannot use a memory mapped file larger than your available address space" In short it still looks that LMDB is designed effectively only for one-endianness and only for 64-bit systems, which is still limiting for many use cases. Again, it seems that for LMDB is again "solving" the problem by ignoring it. Which is OK if it fits your use case... But shouldn't Firefox work properly on 32-bit systems? Or did they completely decide that they don't want to target any 32-bit platform anymore? Moreover, there are use-case scenarios where the memory mapped file approach can suffer from problems of unnecessarily reading the page that will anyway be completely overwritten. My conclusion is... if LMDB "works for you" fine, but do properly your research first. I still believe SQLite covers much more use cases and is safer starting point for many of them, including Firefox use cases, until I read that they really decided to reduce these.
- drzaiusx11 8y agoHopeful this goes better than WebSQL. WebSQL ran into standardization problems because they started with an existing implementation (SQLite) instead of a spec as their base implementation--meaning anyone making a greenfield implementation would need to implement all the quirks of SQLite to be compatible with other implementations. Sadly it died as a standard and we were stuck with either local storage or indexdb.
- Mossop 8y agoThere is no intent to standardize this or expose it to the web. This is purely for use internal to Firefox. Of course that may end up meaning that it is used as the internal storage for some web feature.
- drzaiusx11 8y agoThe first sentence on that page says "We propose the standardization of a simple key-value storage...usable from JS, Java, Rust, Swift, and C++" I assumed this meant an API callable from webasm/js. Did I miss something?
- drzaiusx11 8y agoAh, found my error: "Not-yet or never goals for this proposal are: Standardization via a standards body as a web API." So this is "internal" stuff I guess.
- Mossop 8y agoPoor wording perhaps. There are a bunch of places in Firefox that use key-value stores, this proposes standardising on one type of store.
- jimis 8y agoThe page writes that LMDB "is exceptionally fast for our kinds of load", and then links to an in-memory microbenchmark: http://www.lmdb.tech/bench/inmem/ http://www.lmdb.tech/bench/inmem/ Aren't they interested in persistence of the key-value data? In my experience, once data is persisted to disk or SSD, LMDB is way slower from alternatives because it needs to operate in synchronous mode to avoid corruption (effectively flushing to disk after after every transaction committed). If operated in the non-default MDB_NOSYNC mode (which is the mode chosen in the above benchmarks), then there is a high probability to be left with an unreadable database file after a crash, thus losing all your data. It is not fair to compare with other databases in sync mode, since they might operate safe but faster in async mode. For example sqlite with PRAGMA journal_mode=WAL and PRAGMA synchronous=NORMAL can operate in semi-asynchronous mode (fsync()ing sporadically) without fear of corruption in case of crash, because it keeps a WAL journal and is able to properly roll-back after a crash. This should be much faster than LMDB's default-and-safe synchronous mode, that msync()s on every value written.
- hyc_symas 8y agoWe have only ever compared LMDB in synchronous mode to other DBs in synchronous mode, and LMDB in asynch mode to other DBs in asynch mode. Come on, that's too obvious. And LMDB beats the crap out of SQLite, in any mode. http://www.lmdb.tech/bench/microbench/ http://www.lmdb.tech/bench/microbench/ Replacing SQLite's Btree engine with LMDB makes the SQLite footprint smaller, faster, and more reliable too. https://github.com/LMDB/sqlightning https://github.com/LMDB/sqlightning
- jimis 8y agoIt's not that simple. What you mean by saying "(a)synchronous mode" is very different from database to database. See my above comment. Is SQLite synchronous or asynchronous if you configure it as journal_mode=WAL and PRAGMA synchronous=NORMAL? For my purposes as an application developer, I care about comparing databases operating in safe mode i.e. a system crash should never cause total data loss. According to my experience SQLite's safe mode is many times faster than LMDB's safe mode, with a write workload. While LMDB is thrashing the disk and achieves only a handful of write transactions per second.
- erichocean 8y agoLMDB is awesome, can't tell how many times I've wished to have access to it from the browser...
- alexnewman 8y agoWhy do they make this proposal? What does that mean?
- Mossop 8y agoIt's a proposal for making use of a new storage engine to store Firefox internal data.
- jinqueeny 8y agoCurious about how this compares to TiKV...
- adobeeee 8y agoI have a layman question if somebody could please answer. I have never in my entire life seen databases fail. But db failures and issues seem to be brought up all the time. Now I understand that part if this maybe the cost function associated with them. But I'm sure there's also something that I have no clue about. So my questions are: 1) what kind of problems do databases actually face. 2) what kind of scenarios create those problems. 3) how does a programmer go about testing them?
- mbreese 8y agoThe easiest scenario to imagine is a hardware failure or power outage. The database was in the middle of doing something, and then was prevented by a hard drive dying or the lights going out. One way to test such a thing is to literally unplug the computer to see how it handles the failure. So, let's say you have a client/server application... the client is telling the server (database) to write some records to the database. In the middle of the write, you pull the plug. Some questions you'd want to know: what does the database look like when it restarts? Can we read it? What is the current state? Did any of the new data get written? What does the client think was written? If there was an uncommitted database transaction, was the database left unaltered? It's just as important to test the client in these scenarios. While the server may have crashed, what does the client think happened? Was it waiting for an ACK or "OK" message? Did it get the message? If the update failed, what does the client do in that situation? Things can get even more complicated if you're thinking of replication across different servers. If one of the servers fails, how does the replication work? Do sessions fail over to other servers? How many servers are required? If there was a corrupted record, did it propagate or was it scrubbed?
- AboutTheWhisles 8y agoIt really sounds like they should take a look at this: https://github.com/LiveAsynchronousVisualizedArchitecture/simdb https://github.com/LiveAsynchronousVisualizedArchitecture/si... "One appealing aspect of LMDB is its relative ease of use from multiple processes, above and beyond its basic capabilities as yet-another-fast-key-value-store." simdb is only lock free and thread safe. While LMDB is benchmarked at around 10k writes, this should be able to do millions of mixed reads and writes with 4 modern cores. LMDB seems to use a separate lock file to sync multiple threads/processes. The only catch here is that the keys aren't sorted, which doesn't seem to be a requirement of theirs.
- nilsocket 8y agoDidn't they review badger from dgraph. https://github.com/dgraph-io/badger https://github.com/dgraph-io/badger Here is the comparison back in 2017: https://blog.dgraph.io/post/badger-lmdb-boltdb/ https://blog.dgraph.io/post/badger-lmdb-boltdb/ It supports concurrent ACID transactions with serializable snapshot isolation (SSI) guarantees.
- sidcool 8y agoThis is a great example of how to conduct a technical design review.
- catwell 8y agoIn case someone involved in this reads this thread: the document does not specify which LMDB version you tested. I suggest you run your tests with the `mdb.master` branch, i.e. the work towards a future 1.0, and not the stable 0.9 branch. The answers to several of your interrogations will depend on that: with `mdb.master` you can use the VL32 mode which greatly improves usage on 32 bit platforms, and Windows support is much better. Regarding NFS: I have recently started testing LMDB on NFS v4 and had no issues so far, but with a single process using the database. AFAIK the warning at http://www.lmdb.tech/doc/ http://www.lmdb.tech/doc/ is only for multiple processes using the DB concurrently. I am still not entirely sure there won't be any mmap-related issues, but so far so good. Regarding "being careful": this is a very important point. The LMDB API does not hold your hand, it lets you do dangerous things which will result in corruption of your database, which you will discover too late. I suggest writing a wrapper around the API to ensure you are using it correctly. (I wish there was a compile flag like LUA_USE_APICHECK [1] for LMDB, which could help detect problems like this, but there isn't.) [1] https://www.lua.org/manual/5.3/manual.html#4 https://www.lua.org/manual/5.3/manual.html#4
- hyc_symas 8y agoThe main reason for that warning about NFS is that people will try it, see that it seems to work, and then get careless and try to use the same DB from two different hosts at once. It's inevitable when you're working on files living on networked filesystems, and it cannot work. NFS doesn't offer any cache coherency guarantees, and the mutexes used for synchronizing writers only work on the host that created them. Not sure what you're talking about re: the API letting you corrupt your database.
- justin66 8y agoIf we're using lmdb for something that's largely or entirely read only, how viable is using it on NFS with (shudder) lock files or something like that?
- hyc_symas 8y agoIf it's 100% read-only, you could probably use it safely. Make sure its filesystem on the NFS server is mounted read-only, and obviously all the clients' NFS mounts must also be read-only. As for "largely read only" - if there are any writers at all, all bets are off. LMDB automatically detects read-only filesystems, and turns off its locking in that case, so it should perform as well as anyone could expect NFS to perform.