Networked hashing database

If you find such a thing, please tell, this is something I've been looking for a while :-)

The only remotely similar thing I know about is, you guessed it, MySQL cluster, but it sucks for some quite obvious reasons. Mostly, because it's not persistent at all. Really, it could have been The One Thing, if for example the recently added "on disk data" hadn't been done so half-assed (which makes it pointless).

I fact, I've been wondering how much pain it is to roll your own ACID (kind of, application-level ACID). Because if ACID isn't a requirement, there are lots of systems out there...

(in fact, most of them are CID, it's just the A that's missing)

To get "A" (atomic) across multiple objects that live on multiple nodes, "all" you need is a transaction monitor and two-phase commit. You can let an arbitrary database node act as transaction monitor for an arbitrary transaction if you want to.

Doing "A" and "C" while supporting live migration/partitioning of the key space starts to get interesting.

Similarly, Darkstar has a little bit of this approach, but they put object serialization on top and a back-end that doesn't currently scale performance across nodes. Versant also has a little bit of this (any OODB has to have it), but again, it adds too much intrusive object stuff on top. I also don't know how it scales across nodes (anyone have recent experience with Versant?)

On the other end, there's BigTable, SimpleDB, Google FS, Hadoop, Mogile and friends. They seem to focus more on storing really large blobs (like files) rather than memcached-style smaller chunks of data. I guess BigTable and SimpleDB come the closest among that ilk. Neither of which is easily accessible as open source for installation in my own data center, btw :-)

Quote:

Original post by hplus0603 On the other end, there's BigTable, SimpleDB, Google FS, Hadoop, Mogile and friends.

I've been thinking about mongoDB for a while, which seems, at first glance, pretty cool and almost exactly what one would dream of to store a blob of game data, except, well... except it doesn't have the "A". It does claim atomicity for single records, but well, not across several.

So yes, you'd have to implement a transaction monitor either inside your application or on an intermediate server, and what's worse, you'd have to fetch all involved data over the network before every single update (else, you can't roll back once you see something went wrong).
On the other hand, the only scary problem would be duplicating or losing the "Sword of Exalted Awesomness" if a transaction goes wrong mid-way. So... actually you only need to implement a transaction monitor for very few scenarios such as trades. If single-record updates are ACID, then storing for example a character's skills in this DB would be perfectly ok without anything extra. Or, one could use this for frequently updated single-record data and leave the rest on a standard SQL database.

In addition to real blobs, you get BSON (binary JSON) blobs with mongoDB too, which seems a nice bonus. In particular, they say you can update a BSON field inside a record without having to fetch the whole record (that is, in place).

On the other hand, the documentation proudly claims how efficient these updates are due to "lazy writes", which again makes me wonder how much "D" those updates have after all then. Maybe I'm a bit pedantic, but if the database doesn't write data to disk before reporting success, I don't think it can be called very durable. Well, hopefully those go into a journal or something.

Quote:

if the database doesn't write data to disk before reporting success

QFT!

Actually, the feature set of mongoDB looks almost exactly like what I was thinking of. Too bad their largest user seems to be "the front end of SourceForge.net" with not much else to show scalability so far. Compared to the Googles and Yahoos and Facebooks of the world.

I recently ran across Redis. It appears to support append-only persistence with compaction.

The numbers claimed are in the 100k range, but with no automatic sharding (needs to be done client-side).

Quote:

Too bad their largest user seems to be "the front end of SourceForge.net" with not much else to show scalability so far

Well, Redis is apparently used by github... Seems that code repositories attract this type of databases.

We actually have a few of these internally where I work. At least one I know of is a roll-your-own solution utilizing BDB and aggressive in-memory caching. Unfortunately, I we haven't released any of this, so I can't offer any help there.

I've also looked at CouchDB and HBase in one form or another, although I doubt they're what you'll need. The latter doesn't seem to have the kind of performance you need.

Redis has a bit of the right thought: Put some common operations on the server to allow atomicity. Also, the "append only" file is usually known as the "log" on most other database systems :-)

Too bad about the client-based fan-out. The problem with that is when you want to introduce a new node: All clients need to be told about the new configuration, and if the servers can't enforce the key space range, then a client may race with a key space partition operation such that you get orphan keys on various servers. (Key migration to new nodes is another interesting problem)

With memcached, this is not a bad problem, because memcached isn't considered the source of truth, so a race won't impact correctness.

If I understand the workings of redis correctly, it is quite simple and yet seems ingenious at first sight. It saves data periodically by calling fork() and write(), swapping files, and exiting the parent.

Sounds perfect, at least for small datasets. However, it means you use at most half of your RAM, since the other half will have to be available to OS buffers.
I see a possible race condition there too, if the child process gets a request to modify data while the parent is still blocking on the memcpy inside write, which might, thinking of gigabyte datasets, take anywhere from some milliseconds to half a second. Unless there is an explicit lock for that (which there isn't?), this has potential to fail.

Also, seeing that 8 or 16 GB of main memory isn't a terrible lot for a server these days, I wonder about the time to complete the write. Even with fast disk arrays, writing out 5-10 gigabytes can take anywhere from half a minute to five minutes. Assume your RAID can write out 150 MB/s, then 10 GB will take 68 seconds. Let's really hope no other process ever needs to access the hard disk!
Now, if you have a save interval of a minute or so and the next save starts while the disks are still busy on the first one, you may be in serious trouble. In the worst possible case, the OS would have to start swapping because it has to hold the dataset, and two copies in write buffers, all of which compete for physical memory.
Thus, for large datasets, you would need to use increasingly longer save intervals to prevent that possibility, which means you will lose a lot more transactions in case of a crash.

I would much more like to see a database which keeps only one dataset in RAM and does some kind of MVCC, and writes the dirty records out asynchronously. That would mean a little extra overhead for the multiple versions of changed records, but this isn't nearly as bad as copying the whole dataset to buffers.
In theory, this could be implemented perfectly with file mapping and msync. Unluckily, however, it won't work under Linux, because file mapping is intentionally broken (and the documentation lies about it!) in that respect.
One could probably still try to do synchronous writes using a scheme similar to the fork/write idea that redis is using. That might be as good as you can get.

Quote:

it means you use at most half of your RAM, since the other half will have to be available to OS buffers

First, the fork() implementation will do copy-on-write, so only pages that get dirtied after the fork will need to be duplicated.

Second, most modern UNIX-es allow unbuffered writes, which means that disk will pull the data straight from the pages in the process, so no file buffers needed.

Third, if the system is single-threaded, then the fork() will by definition happen while you're not mutating data. If it's multi-threaded, then it's easy enough to put in a barrier that temporarily suspends servicing write() requests while the fork() pends. A multiple-readers, single-writer style lock would be perfect for this (treat the fork() as writer, and all other requests as readers()). Once the fork gets the lock and forks, the lock is released again, so the runtime cost is minimal.

Fourth, yes, dumping a large data set to disk will take time. Non-striped SSDs get you up to 200 MB/s of actual throughput, so about 5 seconds per GB, or about a minute for a typical modern server. If you do that every five minutes, and trickle out update records in the meanwhile, you could have a fully consistent database (across a single node, at least).

Fifth, trickling out changes is what almost all databases do; it's generally known as "log files" or "binlogs." The draw-back is that re-playing these on start-up after crash can be quite slow. Thus, you want to checkpoint to disk at regular intervals, so that the time for start-up in recovery can be bounded.