4
\$\begingroup\$

I need to store and update collections of serialized data (of varying sizes) into a single file that is compact and allows for efficient random access to the stored data.

Some real world examples:

  1. Storing a series of JSON objects (of varying sizes) that can be pulled out individually for parsing given an index or hash key.
  2. Other serialized structures that may contain persisted state or configuration settings given an index or hash key.

How can I implement such a file format?

I think at the very least there would need to be an index that points to blocks of the serialized data. Minecraft uses the Region file format which allocates space in the file by a fixed block size and then store data in the header of the file to determine the location and size of the data.

If the data I was storing was static, something like this format would probably be a fit, however, the data could change in length. Because the length may change, I think some mechanism would need to be in place to defragment the file.

\$\endgroup\$
  • \$\begingroup\$ I've been working through the same problem myself. If pointers to objects will always be known, you can create an index file that points to locations in other files as needed. Objects can be appended to any of the file or inserted into a new file and the index updated. The obvious downsize is that removing an object from anywhere other than the end of the file requires some additional work to reindex, so to speak. \$\endgroup\$ – Jesse Williams Jul 14 '16 at 15:27
  • \$\begingroup\$ Asking for libraries, links to existing resources, et cetera isn't really on-topic here (and likely the reason for your close votes), but the basic question of how one might accomplish this is, so I removed the off-topic bits. That said, SQLite may be just fine and you should try it and benchmark it, probably. \$\endgroup\$ – Josh Jul 14 '16 at 15:40
  • 2
    \$\begingroup\$ This need is pretty atypical for games but very common for databases and filesystems. You'll have far better luck asking for this kind of advice from those sorts of developers rather than game devs, I think. \$\endgroup\$ – Sean Middleditch Jul 14 '16 at 16:07
  • \$\begingroup\$ Sean's probably right, although we did use a structure like this for GW2 (which is what most of my answer is based on). I can, however, migrate to SO if you'd like, Shroder. You'll probably get better answers there. \$\endgroup\$ – Josh Jul 14 '16 at 16:49
  • \$\begingroup\$ This answers my question in more ways then one, so keeping the post here is fine. It looks like I was trying to solve a problem that doesn't commonly exist in the game space. Thanks! \$\endgroup\$ – Shroder Jul 14 '16 at 18:56
6
\$\begingroup\$

To do this efficiently the first chunk of data in your file will need to be some kind of index or table-of-contents. Each row of this index refers to a distinct chunk of serialized data within the archive, a "sub-file." At a minimum, each row need only contain the offset to the actual sub-file data within the archive.

For example, if you use filename hashes to refer to your files and your sub-file dataset is small enough and entirely known beforehand, you may be able to create a perfect hash from key to index element.

In practice, though, you'll probably actually want the key to the sub-file in each index row as well, and to organize the rows so you can quickly find the correct row for a given key (for example, by sorting them, you allow for a binary search to locate the index row for a key sub-file key).

You'll also probably want to put the size of each file in the index row as well. You can simply expect that the first N bytes at the file's offset are it's size, of course, but I prefer having the size in the index because it's occasionally useful to have (and it keeps the chunks of serialized data more contiguous).

That's enough for a basic implementation, so you weren't too far off in your initial supposition. There's a few other pitfalls though.

If you're going to generally process the archive by reading it into memory, and then later writing back a new version of it, things are basically done. Fragmentation isn't an issue, nor is adding/removing/altering the size of files. You know the full set before you write to disk and can handle everything fairly trivially.

If you're not able to read the whole thing into memory and rewrite it every time, things get more complicated. Writing into the middle of a file isn't generally possible, unless memory-map the file. In those cases you can, but often cannot extend the size of the file as a tradeoff. This causes issues with both the index chunk (updating sizes, adding/removing rows) and the actual content of the sub-files (which may need to grow).

There are several ways to handle this, some more appropriate for particular scenarios than others, and some which need to be mixed-and-matched to create a full solution:

  • For the index, choose a fixed number of rows (say, 1024). That's how many sub-files you can have per archive. This solves issues with the index needing to be updated, but only defers the problem of adding new entries until you hit the threshold. It doesn't address the issue of the actual size of the sub-file data growing as items are added, though. You'd need to memory-map the file to update the index, most likely.

  • For the index, store it externally in a sidecar file. It's much quicker to update because it's generally way smaller and thus most of the concerns about having the storage to load the whole thing into memory go away. It does mean you have two files instead of one, and if you lose or corrupt one or the other, you're basically screwed.

  • For the sub-files, write all new or modified sub-files to the end of the file, leaving old versions of the files, or deleted files, in the archive consuming space until a defrag happens. You can write the file in append mode this way but you can't update the index chunk this way.

  • For the sub-files, maintain record deletion status in the index chunk so you know if a file was deleted. Add a free-list chunk after the index that defers to free regions of space in the sub-file chunk formerly taken up by removed sub-files or sub-file that shrank (maybe, though there are tradeoffs here if that sub-file ever needs to grow again). Try to write new stuff or modified-such-that-size-changed stuff into some of these free chunks. You can do this via memory-mapping, until you hit the case where can't fit anywhere and must write via append.

  • For something really complicated and probably overengineered, write an offset to the end of the file in your index chunk. Every time you need to add a new asset or update one, write a entirely new index chunk at the end of the file (purely appending), followed itself by an offset to the new end of the file, followed by the new data. This can be done entirely with an append write, but is probably the most complicated solution. It's also the most wasteful space-wise (nothing is ever re-used until a defrag), and least-optimal for random access as if you don't find the desired file in the initial index chunk you need to start hopping to the next chunk and trying there; as you get more and more index chunks, newer files take longer to search for.

For all cases where a defrag is required, simply loading everything and serializing it out fresh will suffice. It's expensive, memory-wise, but it's the simplest. Memory-mapping may let you do the defrag in-place but it's a lot more work.

\$\endgroup\$
  • 1
    \$\begingroup\$ ...or you could just use zip archives through one of the many available libraries. \$\endgroup\$ – Philipp Jul 14 '16 at 18:41
0
\$\begingroup\$

Use zip format, and take advantage of vast infrastructure of existing tools.

\$\endgroup\$
-1
\$\begingroup\$

Since your data is changing constantly it's not enough to store an index and keep 'subfiles' of data. This is easy to deal with in ram as separate loosely affiliated data structures but will require writing out the ENTIRE file every time you update some values.

The situation you describe is basically what a database is for. A database will store your data on disk in data structures that already have extra room allocated for additional entries, and indexes that allow you to access data items quickly and efficiently.

Doing all this on your own is actually much more work than it sounds like. SQLLite is an easy to use, free database that could be used for your needs.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.