Home       About Me       Contact       Downloads       Part 52    Part 54   

Part 53: Storing World Data

April 3, 2012

Minecraft stores its world data in a collection of files. Over the multiple versions of the program, the structure seems to have turned into a bit of a mess. The region directory contains two versions of everything -- the old mcr files and the new mca files. I think the DB is using both ZLib compression (for regions), and GZip file format (for the level.dat file.) The compressed formats don't just compress the raw data, but compress the "NBT" file format which originally stored the data in individual files.

Needless to say, I don't want anything like this to happen to my database format! I also have the problem that in Crafty at least, game developers are going to want to add their own state information. So I need a format that will support growth and extensions by other programmers.

Back in the early parts of this project, I had a version of Crafty with a file format of its own. I was storing all the 32 by 32 by 32 chunks of landscape in individual XML files. The sample world had several thousand of these chunks. I was relying on the Octree format to provide for some compression, but not doing much otherwise.

When Notch switched to the region format, it was claimed that storing multiple individual chunks in a single large region file improved performance. I have no reason to doubt this, but it is irritating. Storing data on disk is the job of the operating system. Redoing this in your own layer seems like reinventing the wheel. On the other hand, I could clearly see that copying these thousands of files, between my machines or to make backups, was extremely slow. The file system just isn't optimized around this kind of use.

So I need a format that can store large amounts of data, be used for individual files (for things like avatars) or huge collections (for regions), which can grow to hold new information, that isn't locked down to the particulars of the world (like chunk sizes), and that can be upgraded without breaking anything in old code.

It was tempting to do something XML-ish, with nested tags and so on, since that's the direction of file formats out on the net. On the other hand, I didn't want a complex format or interface, since there would inevitably be problems with it.

I also need something with decent performance, which means binary data and indexes which point directly to objects in the file, not text which you parse. I finally decided to go the other direction, and make it all brutally simple.

The Interface

There is a format signature at the very beginning of the file, which can be read without knowing anything else about the file format. This means that if a better implementation comes along, I can create a new format, signaled by a new signature, and completely change the structure of the files without changing this interface.

The interface supports a table of objects, each of which is an unformatted byte array. Each object is identified by a key, which is a variable-length string, with some reasonably large maximum length (say 512 bytes.) In addition, each object has a 64-bit version id.

This version represents changes to the object, not to the format of an object. So for example, the first version of a landscape before you modify it is version 0. Then when you add a block, that's version 1. Add another block, that's version 2, etc.

This will be used in the multiplayer game world. Your local database will be a cache for objects you've seen. When you enter the world, the client will display the versions it has on disk. At the same time, it is requesting the most recent versions from the server, with queries of the form "get chunk at 32, 64, 32. I have version 1234". If the server has a more recent version, it can send it. Otherwise, the client uses what it has.

Here is the complete interface of the ObjectStore class. I implemented this in C++, but I'll 'pseudocode' it for non-C programmers.

getFormat(string fileName) returns string formatSig
       Return the format signature on a file. The signature is the first line of a file, terminated by a newline. No other data is required for this method.
create(string fileName, string formatSig)
       Create a new object DB, with the filename and signature. It's an error if the file already exists.
open(string fileName, string formatSig)
       Open an existing object DB. It's an error if the format signature does not match.
       Close the DB.
writeObject(string key, int64 version, int32 length, byte array data)
       Writes the new version of an object identified by key. If an old version exists, it is deleted.
readObject(string key) returns int64 version, int32 length, byte array data
       Read the object identifed by key, returning the data and version. If the object does not exist, a null is returned.
deleteObject(string key)
       Delete the object identified by key.
indexStartPosition() returns an int32 position
       Start reading the index. A position of -1 indicates read complete.
indexNextKey(int32 position) returns string key, int64 version, int32 position
       Read the next entry in the index. The key and version of an object are returned. A position of -1 indicates read complete.

As I said, it's simple. The structure is all in the keys. For example, the Minecraft-style chunks have a major code, minor code for each brick (2 bytes total), and two lighting codes (4 bits each). You could implement this with keys like:

  • "block/32,64,32/bricks" for the brick codes, writing 32 by 32 by 32 by 2 bytes of brick type data.

  • "block/32,64,32/lights" for the light codes, writing 32 by 32 by 32 by 8 bits of light intensity data.

Other likely objects would include position of the players, animals, etc. No structure is imposed on the key names, but the programmer can clearly create a complex structure with this interface.

As the game code evolves, and the programmer wants to keep compatibility, he creates new key names. A version of the brick data with more brick types might be named "block/32,64,32/bigbricks". To do the conversion, the program reads the index for all objects ending in "/bricks" and upgrades them to "/bigbricks" blocks, deleting the old versions.

New data is added to the world by generating new keys. If biomes are introduced, a new key "block/32,64,32/biome" can be used. In old databases where it is not present, a new version can be generated.

Two restrictions on the DB can be seen immediately:

  • There should be few enough objects per DB to conveniently scan through them all, at load time, or on demand. DB files do not contain millions of objects.

  • Each object is small enough to return as a single byte array. There is no method for reading subareas of an object. I am keeping the data compressed with ZLib, so partial reads would be a nuisance to implement. Minecraft blocks are on the order of 32K bytes.

In use, a single DB could be one object (such as an avatar definition), all the attributes of a single chunk, or a region of chunks. It's left to the programmer to decide what granularity to use.

The Implementation

My first thought was that I needed to read and write objects as continuous ranges of bytes in the file, to get the best performance. I would then have to track free space and do some kind of first-fit or best-fit algorithm to allocate ranges for objects. I don't want an index at the start which would grow and require objects to be moved, so the index could be put at the end. You will be rewriting the index whenever you write new data anyway.

Several things put me off doing this kind of implementation:

  • The data is going through ZLib for compression and decompression. That's liable to be the bottleneck, not disk I/O.

  • Most objects will compress to a block or two, making I/O even less of an issue.

  • Although performance of reads could be important, writes are done in the background, and are not performance critical.

  • Even if you use continuous ranges of a file, the OS is not going to allocate continuous blocks on disk.

  • The objects will slowly grow as the game is used, making fragmentation a problem. You are always going to need a slightly bigger slot than the object previously required.

  • When the program eventually crashes, the code can die in the middle of an object write, corrupting the DB. I need to be able to reconstruct the objects despite partial writes.

I decided to just do something straightforward, and use a linked list of blocks, even though that guarantees I'll never read more than one block at a time. If this turns out to be an issue, I can revisit the design. File systems seem to cache an awful lot of file data in memory nowadays, so I'm not sure I'll even notice.

My impulse was to put a block header at the start of each block, but I didn't do that here. I wanted the very first bytes of the file to be the format signature, not the block zero header, so I put the header at the end of each (4K) block. The header contains the complete key of the object, version number, a block sequence number, and the next block in the chain. The last block has a next-block value of -1.

When I write an object, the code writes the new version then deletes the old version. A new index is written when there's nothing else to do. In case of a crash, odds are that at least one complete version of the object will be present. Since all blocks are tagged with the key, version and block sequence numbers, I can sequentially read the DB and rebuild the index if it has been corrupted.

The index is just another object, with two exceptions. First, it always starts in block zero. Second, when it is rewritten, it reuses the existing chain of index blocks, instead of allocating new ones. Since I am reusing block zero, it doesn't make sense to allocate new blocks for the rest of the index on a rewrite.

The free block list is written after the index, and updated when the index is. In addition, blocks are zero'd when they are freed (when an object is deleted.) This is unnecessary, since the free list could be computed from all the blocks not used in objects, if the DB had to be reconstructed.

It's a bit of extra work, rewriting all the deleted blocks, so if it turns out to be performance critical, I might stop doing it. But as I noted above, writes are done in the background and are not going to be performance critical. For debugging, I wanted the deleted blocks to be empty.

Current Status

I've implemented a first pass on this, and done a trivial amount of testing. Next I'll probably add some code to McrView to export into this format. Crafty and SeaOfMemes will import these files and use them to store modified world data.

I'm still working on the new code for modifiable landscape. Hopefully, that will be done for the next part.


Home       About Me       Contact       Downloads       Part 52    Part 54   

blog comments powered by Disqus