Very close on the new, new database engine.

jasonrohrer · 2018-08-03 02:54:37

Using a bit of extra RAM, I've worked up something with near-mythical performance.

To answer that a given key isn't in the database, it uses 0 disk touches.

To return the value of an item in the database, or to update an existing item, it uses a single, random-access disk touch.

To insert a new item into the database, it uses a single NON-random access disk touch at the end of the file.

Thus, inserting a bunch of items into the database (like when loading the tutorial map) can be done almost at the speed of max disk streaming.

Furthermore, all items are stored on disk in the order in which they are inserted, so there is some spatial locality (nearby items on the map tend to be in somewhat nearby areas in the file).

Iterating through all of the items in the database also happens at almost the speed of disk streaming, as does rebuilding a new database from an existing one (like when we cull based on stale look times).

It uses 64.5 bits of RAM per record, regardless of record size, and can store up to four billion records, has 0 bytes of overhead in the data file per record, and minimal static RAM overhead, beyond the 64.5 bits per record.

And furthermore, it can resize the hash table (as the data set grows) WITHOUT a single disk touch.

Unfortunately, figuring all of this out has taken another full week of 10 hour days.... exhausted!

Turnipseed · 2018-08-03 04:45:41

Yay thank you for your time!!!

YAHG · 2018-08-03 05:28:35

I guess all those child sacrifices are working.

This is good to hear.

Christoffer · 2018-08-03 08:59:12

Sounds very promising!

What is the number of records on server 1, btw?

jasonrohrer · 2018-08-03 20:07:48

Last time I looked at it, server1 has 15 million records in the main map.

You may have noticed that server1 is offline. It actually ran out of disk space and crashed earlier today, because lineardb stored records on the disk in hash-table order, and ran with a 50% max load, so it was using 2x the space of the actual data records. The new database engine wastes no disk space like this.

Christoffer · 2018-08-04 01:04:08

Sounds like plenty of data...

I was wondering, if the new implementation relies on work memory to find the right records on disk, do you see any risk for data loss if the server process crashes? Or is the data on the disk enough to rebuild the RAM part of the database?

jasonrohrer · 2018-08-04 04:00:56

Yeah, I figured out a way to do it without storing the hash table on the disk at all. Turns out that this isn't really needed, in practice, because rehashing things is faster than reading the hash table from the disk in the first place. You want to reduce disk accesses. If you have to update the hash table on the disk as well as the data records, that's more disk accesses.

SO.... when the database is read on startup, the entire in-RAM hash table is rebuilt from scratch.

The data are stored in the file simply in the order that they are created.

If you're doing a bunch of inserts all in a row, you're essentially streaming data to the end of the file (very fast).

And reading the data on startup is also fast (to rehash them), because their order doesn't matter. Just read them in the order that they occur in the file.

Finally, another interesting consequence of doing it this way is that the data file is pretty much independent of any hashing algorithms, etc. Like, change the hash function, change the load limit in the table, or do anything else that dramatically changes the way hashing is done (maybe even switch collision algorithms... from separate chaining to linear probing or whatever), and the data just works, because it's just the data.

And during a crash, the hash table is lost.... but it's lost every time the server shuts down gracefully too! Doesn't matter.

Uncle Gus · 2018-08-04 05:19:47

So is the data written to the disk at all? How often? What's the worst loss from a crash?

Blazier · 2018-08-05 01:37:20

All the data is written to the disk, so there's no loss from a crash. The reason you lose nothing is that everything stored in the in-memory hash table is redundant data. The keys in the hash table are also written to the disk records, so that the hash table can be easily rebuilt from the disk. And the values in the hash table are simply pointers to where the data is on disk. So the stuff in memory is just some redundancy to speed up the disk access. Technically you could do all your lookups by searching through the entire disk every time, but that would be insanely slow.

Sounds like 4-billion records will take a long time to reach, but if it ever does, its nice that you can just swap out the hashing implementation with a new one. I'm imagining all you'd need to do is make an extra hash table that just stores a flag of whether the data is stored with a 32-bit file pointer, or a 64-bit file pointer. Then you have your big 4-billion record hash table for the 32-bit file pointers, and then a smaller hash table for the more memory-intensive 64-bit file pointers. Takes 2 hash lookups to find something, but its still memory-only, and should take much less memory than just storing a single 64-bit file pointer hash table.

Last edited by Blazier (2018-08-05 01:53:54)

One Hour One Life Forums

#1 2018-08-03 02:54:37

Very close on the new, new database engine.

#2 2018-08-03 04:45:41

Re: Very close on the new, new database engine.

#3 2018-08-03 05:28:35

Re: Very close on the new, new database engine.

#4 2018-08-03 08:59:12

Re: Very close on the new, new database engine.

#5 2018-08-03 20:07:48

Re: Very close on the new, new database engine.

#6 2018-08-04 01:04:08

Re: Very close on the new, new database engine.

#7 2018-08-04 04:00:56

Re: Very close on the new, new database engine.

#8 2018-08-04 05:19:47

Re: Very close on the new, new database engine.

#9 2018-08-05 01:37:20

Re: Very close on the new, new database engine.

Board footer