What are the benefits of storing data contiguously?

Question

I am designing an application file format which will store chunks of user data, ranging from a few bytes to a few gigabytes - median size probably in the 10MB - 30MB range.

I have the option of storing this data in a sequence of fixed-size blocks, each block having some lightweight structure to it. This structure would provide some minor benefits (such as storing a checksum).

The alternative is to store the data in a contiguous sequence of raw bytes. I am imagining some benefits to this approach, such as being able to read large extents of data without having to parse the block structure. But I can't quite put my finger on whether this is a real benefit or not.

Are there other implications of the two approaches that I should be considering?

Answer 1

The alternative is to store the data in a contiguous sequence of raw bytes. I am imagining some benefits to this approach, such as being able to read large extents of data without having to parse the block structure. But I can't quite put my finger on whether this is a real benefit or not.

In my experience and domain (Visual FX for films and games and so forth), it has been extremely beneficial, both in terms of performance and simplicity of the file savers and loaders, and without sacrificing extensibility, to favor large, contiguous, homogeneous blocks in file formats when possible as opposed to teeny little interleaved chunks. That said, our needs are much less sophisticated than like an RDMS. We just want to store all relevant data and read it all back efficiently in a rather sequential fashion, not model complex data structures like B+ trees on disk with lots of disk seeks to do binary searches and so forth. We do have strong extensibility requirements, however, since the computer graphics industry moves so quickly and constantly introduces game-changing concepts.

In particular we had this ancient file format which was binary and not particularly inefficient in terms of disk use or access (could be read sequentially, did not require seeking back and forth) but involved a lot of tiny chunks of variable-sized data interleaved with each other. And that sometimes made massive scenes artists created spanning gigabytes of data take 5 minutes to load, for example, not only in our native loaders but similar times when third party loaders would parse and load them.

Interleaving Tiny Variable-Sized Chunks

Specifically what was taking the most time as well as involving the most complex code was loading in geometry data (3D models), which would consist of vertex positions, UV texture coordinates, variable-length polygons (triangles, quads, n-gons with varying number of vertices), material data, etc.

The polygons in particular would be interleaved so loading them might involve parsing a quadrangle chunk and then checking to see how many vertices it has (4), then add 4 vertices to the mesh (or some auxiliary structure with the mesh operations deferred) and form a polygon from them, and the reader might then encounter a triangle (for which it'd have to do the same thing again) followed by a quadrangle followed by a triangle again followed by an n-gon and so forth.

Specifically interleaving all this tiny variable-sized data (a 3-vertex triangle interleaved with a 4-vertex quad, e.g.) made it so the loaders would have to stop and check the size of every little polygon chunk even to know how much data to read to move to the next chunk. And profiling the code didn't actually reveal hotspots in disk I/O. We were using efficient file I/O APIs that would buffer things and the disk access was straightforward and sequential. The hotspots were rather distributed across the board and coming more from all the extra branching and little virtual function calls and little memory allocations that sort of representation tended to promote.

Contiguous, Homogeneous, Fixed-Sized Chunks

So later on I was tasked to design a new file format, and actually not with efficiency as the primary reason for doing that (we wanted a simpler, fresher format that wasn't 2 decades old with all sorts of backwards compatibility support for legacy concepts that hadn't been in the software in over a decade). And one of the first things I did was avoid interleaving variable-sized data like polygons. Instead of:

 triangle   quad         triangle   n-gon
[3: v1v2v3][4: v1v2v3v4][3: v1v2v3][5: v1v2v3v4v5][....]

I did it like this:

[triangles  ][count][v1v2v3][v1v2v3][v1v2v3][v1v2v3][v1v2v3][...]
[quadrangles][count][v1v2v3v4][v1v2v3v4][v1v2v3v4][v1v2v3v4][...]

And only for n-gons (polygons with 5 or more vertices, not frequently used by artists) would I interleave variable-length polygon chunks. And the main benefit I thought of doing that was that it really simplified our code because we could read all the triangles for a mesh not only in a single read call but also not have to get clever with how we allocated little chunks of memory efficiently since we knew exactly how much to allocate in advance to store all triangles (one huge memory allocation as opposed to a boatload of teeny ones). I didn't expect it to perform that much better on a first try since that legacy format had been optimized and tuned to death for decades by the team.

But, almost by accident, on my first try I ended up being able to load the same scene that took over 5 minutes to load in our legacy format in under 200 milliseconds. And I wasn't doing anything more as far as efficiency was concerned in the new format except just that (favoring bulkier, contiguous chunks of memory following a tag which is parsed over little teeny variable-sized chunks). So that really helped a lot on top of simplifying the entire format in our case.

Extensibility With Zip Files

Another thing that I don't think tied to efficiency but did simplify a lot is that our previous file format was sort of like how XML might look like if it was turned into binary (with nested "start/end tags" to indicate the beginning and end of blocks). I ended up just using the zip format here (uncompressed) and, in place of nested tags, I used folders and files stored in the zip file (ex: file.zip/scene/mesh.dat instead of the binary equivalent of like <scene><mesh>...</mesh></scene>). That also made it easier to inspect the file for how it was arranged using standard zip software as a secondary measure for analysis.

And that gave the desired extensibility since if we introduced some new concept (let's call it "Foo"), we can just add like a scene/Foo.dat (or even a sub-directory/folder) to the zip file which newer versions of the loaders could pick up and read. We did give those files a proprietary extension to avoid confusion with general zip files, but it was basically just a zip file with stuff inside of it.

There might be one efficiency argument to favoring zip since our previous format favored sequential access for the most part (couldn't effectively skip data so well). It did identify how many bytes were in a given block/chunk in advance, so you could theoretically skip that stuff, but it was a bit unwieldy to do so and our native loaders as well as ones written by third parties tended to just favor reading everything for simplicity. With the ZIP format it's pretty easy to just ignore files and folders inside the ZIP that aren't of interest to whomever is loading the format (ex: a third party application), so skipping over data that isn't of interest becomes particularly easy there.

Answer 2

Depends on so many factors, but here are a couple points to consider:

1. Recognize that if you use a very large file format that is "contiguous," its contiguousness is logical, not physical. The operating system could put parts of the file all over the disk depending how fragmented the filesystem is. So don't use a contiguous file under the illusion that it will give you nice clean reads.

2. Filesystems offer locking and sharing mechanisms that work per file. If you have only one big file, only one process can have an exclusive lock on it. If you have several smaller files then you could have different processes with different locks.

3. Very large files are a pain in the neck for system administrators. They are hard to copy from place to place, sometimes ftp times out halfway in between, and sometimes it is a huge problem just to open them up in a text/hex editor just to peek at them. Smaller files are much more manageable in general.

4. Date/time stamps and "archive" flags (if your O/S has one) operate on a per-file basis. If you have one big file, you'd have to back up the entire thing every time, while with smaller files you can just back up the files that have been modified since date X.

Answer 3

This appears to be case of premature optimisation - it is an attempt to performance-tune a design that has not exposed a performance problem and in doing so, tightly couples the file format to assumptions about the physical environment that do not hold in modern environments.

If you need to make design decisions, try looking at examples of prior art and decoupling your processing of data content from the storage.

The first thing you could look at (even if your data is not media) is the MPEG4 file format. This is not merely contiguous bytes but is a variable length chunk format comprised of fields/chunks of data that are written contiguously - in essence you have this repeating format...

• chunk type
• size
• payload

Since your level of abstraction is a file/stream you are not in control of how your data is physically represented/stored. As a result optimisations you try to make may not hold true in the real world and where they present a gain in one environment may be a penalty in others. There is no reason to use fixed-size blocks. Equally what may be a straightforward 'replace this bit of file' operation for you to write may not be so easy for the file system.

If you find your file access is too heavy then you can always create an index which in it's simplest form is just a list of all the chunks and maybe some metadata about the content to aid searching.

Answer 4

strictly append-only - no updates to already-written data are allowed.

This sounds suspiciously like a log. Did you consider a log-oriented data storage? Like a blockchain or logstash or git?

The benefit of storing data contiguously is better locality. Read and writes from/to contiguous area is rarely slower than random access, especially from spinning disk but there is some benefit even in a solid state storage due to some readahead by the operating system. You also benefit from defragmentation tools built into the filesystem.

There are two ways to store contiguous data, one is to use fixed size chunk (and store oversized data separately) and two is to use variable sized chunk.

Fixed chunk storage wastes space, but fixed size chunk allows you to seek directly to n'th entry in O(1) time. With variable sized storage, you'll have to do a binary search to find n'th entry. The wasted space in fixed chunk also means that you'll have to read more data from storage to process the same number of entries, so if your fixed chunks have lots of wasted space and you often need to do sequential read of the database (e.g. log replays), then you might want to consider variable sized chunk.

A third option is a hybrid. You store a fixed size headers in one contiguous file, which contains the address of the variable sized data in a contiguous file storage or store oversized data using its checksum as filename. When you want to do sequential replay, you read two files in parallel. When you want to get the n'th item, you seek on the header files, get the address of the variable data and seek to that address in the variable data file or get the file from the stored checksum.

Storing chunks contiguously is only beneficial if you're storing large number of small chunks. If your chunks size are fairly big, then storing each chunk as their own entry in the filesystem is very sensible.

Answer 5

I think you should try an embedded database instead.

Why don't you give Berkeley DB a chance? It's a powerful non-relational database from before the time NoSql was a buzzword. I think it will handle all your needs nicely if you're going to implement a file-based data store.

Answer 6

for what you described a file where the chunk is prefixed to be the size and type will allow you skip faster to the record you want and still be compact.

The problem is when you delete a chunk. Either you rewrite the whole file or make a more complicated logic to mark the space for later use. Updates will also have its quirks.

Also, avoid files bigger than 1Gb. Some NFS solutions and filesystems (Microsoft ones) will corrupt the file if get bigger than 2Gb. in Java you can work around that by making a input/output stream that abstract this from your system. That makes several files seem to be a big one for the programming language.