Proposal: Standardizing a lightweight, SQL-free index format for embedded and resource-constrained environments

[unxed]

Hello,

I am the developer of unxed/tar, a pure-Go advanced TAR library that features on-the-fly indexing and true $O(1)$ random-access seeking. Since ratarmount is the leading solution in this domain, I designed my library's SQLite database schema and binary GZIDX integration to be fully compatible with your implementation.

While the current SQLite index format works well for desktop and server environments, SQLite engine can be a heavy dependency in highly constrained, bare-metal, or embedded systems. Ironically, these low-resource environments are often where the performance benefits of indexed random-access are needed most, yet they cannot afford the overhead of a database engine.

To address this, I would like to propose discussing a more portable, lightweight index format as a common cache standard. Such a format would maintain the core indexing logic of ratarmount while allowing embedded-friendly clients to read and seek inside archives.

I would love to hear your thoughts on this proposal, and whether you have previously considered alternative, database-free index backends for lightweight use cases.

[mxmlnkn]

Thank you for reaching out. If this wall of text is too much, we can also move to a chat platform instead.

While the current SQLite index format works well for desktop and server environments, SQLite engine can be a heavy dependency in highly constrained, bare-metal, or embedded systems. Ironically, these low-resource environments are often where the performance benefits of indexed random-access are needed most, yet they cannot afford the overhead of a database engine.

I don't work with embedded. What concrete constraints are you optimizing for: flash size, RAM usage, allocator behavior, real-time properties, licenses, certifications, dependencies? I feel like SQLite is already aiming somewhat towards embedded system usage with its comparatively small shared library size of 1.5 MB, no dependencies, and even various memory optimizations, including a "Zero-malloc option".

Alternatively, have you considered supporting a necessary subset to read the SQLite file with custom code? I have never looked at the SQLite file format, but in principle, the data is only a matrix of values (hidden behind a page B-tree layer), so it shouldn't be too complicated, one would hope. The querying could then also be done with custom code instead of SQL. It might not play well together with my move towards (deduplicated) views, though. Maybe there are even embedded solutions for that already that are even smaller than libsqlite, or it might be possible to compile only a required subset of libsqlite.

I would love to hear your thoughts on this proposal, and whether you have previously considered alternative, database-free index backends for lightweight use cases.

I'll try to summarize my experience with the database.

Previously considered/implemented alternatives:

• The first version (50e8dbb) simply stored everything into a dictionary and used pickle to write (de)serialize it.
• Shortly thereafter (3131918), I considered lots of alternatives to pickle, such as JSON (with various optimized libraries), msgpack, etc. The benchmarks are still available here. The main problem with all of these is that the whole index has to be kept in memory, which leads to out-of-memory errors for large archives. Even worse, many libraries doubled peak memory usage because the (de)serialization process had to store an additional full copy, so it seems. This was vastly disappointing.
• Only a few months later (598fd43), the SQLite backend was introduced to fix the memory usage issues, which have been fixed for good, I'd say (non-embeddedly). There have been some hiccups, e.g., when it comes to the primary index choice to optimize for fast lookup and to optimize row insertion. The benchmark page documents lots of those kinds of problems.

I also tried to design an index format for gzip indexes, only to find that the gztool index file format gets me there 99% of the way. I guess the only reason to give that another try would be to have one unified index for gzip, bzip2, and possibly other compression formats. However, this attempt taught me some things, and there are various file format considerations in the code comments of that commit.

Before designing a new index format, I would look at the metadata indexes for squashfs, romfs, cramfs, ZIP, Cap'n Proto (zero-copy also implies the option to combine it intelligently with mmap to get O(1) memory usage), etc.

In principle, ZIP is already something like TAR (sequential interleaved stream of headers + file contents) with an index (the central directory) appended. However, it is not optimized for fast lookup, as would be nice for really large archives. You would have to linearly scan that index each time, I think. That's why I convert even ZIP indexes into an SQLite index.

Squashfs, I think, tries to alleviate this by requiring "ASCIIbetically" sorted file names so that a bisection algorithm could be executed directly on the (mmaped) file index. This is nice, but a hash table might be even better to achieve O(1) instead of O(log(n)), especially as that O(log(n)) would also be the number of I/O seeks+reads inside the index, which might have very bad latency, which gets sequentially chained, basically pointer chasing on disk. Having the option to create additional SQLite indexes on columns to speed up access in a backward or even ad-hoc/on-demand manner is really nice to have in SQLite.

I am planning some short/mid-term changes to the SQLite tables:

• I want to deduplicate folder names because a deeply nested folder with lots of files will repeat the folder name in each row unnecessarily. To make it backward-compatible, I would create a view that behaves like the previous table version. I already have code like this for the xattrs table to deduplicate key names, and I have also tried to benchmark it, but I probably need to reevaluate the conclusion. I have some large indexes, which could be halved in size by this optimization.
• Similarly, I also looked into deduplicating the metadata rows, which rarely change, i.e., deduplicate the tuple (mode, type, uid, gid, istar, issparse, igenerated, recursiondepth). In my tests, there are only 5 unique values for these tuples because the archive is single-user and only the mode changes between directory, file, and symbolic link, and maybe some different permissions, so the deduplication ratio achieved with this is basically O(n) -> O(1), but the space savings were only a modest 10% (after the folder path deduplication, else it would have been more like 5% space savings) because the tuple is not very large in size.
• I want to unify the ad-hoc scheme for the binary blobs for the compression backends, i.e., the hodgepodge of tables such as: gzipindex, gzipindexes, gztoolindex, bzip2blocks, zstdblocks is to be unified into some table such as compression_indexes with columns: file ID, recursion level, compression type, sequential blob ID, blob. The file ID would then point to the / row for the archive itself, the recursion level would enable working with .gz.bz2 files, for example, and the file ID pointing to arbitrary rows of the archive would also enable storing indexes for compressed files inside the archive recursively. Note that this whole Blob inside SQLite storage is definitely not ideal because it makes it hard, and therefore currently not implemented, to avoid reading the whole index into memory. It would be nice if the compression index, just as the SQLite index, could be read from disk only as required. Only loading the large seek point data when required and only keeping the seek point offset list in memory would be a first step to get us 95% of the way already, but would still grow linearly over the archive size in memory usage, although only very slowly.
• I want to make use of the added recursion level column. Currently, its only use is to filter the rows in case the index was created with a higher recursion depth analysis than requested for a subsequent mount from the index. However, it would be nice to use this to enable merging of nested indexes (Add metadata for recursive compressed TARs into database of outer TAR #79). This last point might take longer to implement, based on how long the issue has been open :(.

Requirements on the file format container:

• Backward-compatible extensibility (Key-Value abstraction layer?): It should be easily extensible in a backwards-compatible manner. Adding SQLite columns works for that case when taking care not to depend on the number of columns and when avoiding column renames or reorderings. Added tables are completely ignored and therefore are also trivially backward-compatible. Heck, with views, you can even emulate tables in a backward-compatible manner. As mentioned above, I tried to design a rapidgzip index file format in the usual hard-coded struct manner. This is definitely not the way. The file format should have some arbitrary key-value (+ skip offset) abstraction layer to have the option to skip unknown keys easily. Some kind of variable integer format would also be nice to reduce file size, but might be difficult to implement. With JSON, you get this for free, because the integer simply ends after the next non-digit symbol.
• Constant-time querying: Usual operations, such as lookup by file path and some unique ID, should be faster than O(n). At least O(log(n)) by sorting the file names, but even better would be O(1). When I am talking about scaling over n, I mean over the archive size and the number of files in the archive, both, and/or the index size.
• Fixed maximum memory overhead: It would be really nice if the format did not require me to load the whole file into memory to make it usable. I guess in theory, one could always try to write an abstraction layer on top of mmap, to enable this, but it ties into the previous point, because such solutions might have to be slow. Some formats are also better suited than others. JSON parsing with its escape rules and no possibility to easily skip forward to the end of a data structure would not be well-suited.
• The above two points were considered from the read-time, but it would also be nice to have these at write-time, although at write-time O(log(N)) insertion would also be fine, as it is rarer.
• The cherry on top would be some compression layer on top. Even after deduplication, my tests still show a compressibility of factor 3 with gzip -6, factor 4-5 with zstd -19. In regard to SQLite, some per-page compression would be nice to have. There are some solutions, such as phiresky/sqlite-zstd, sqlite_zstd_vfs, sqlite3-compression-encryption-vfs, but it they pose various challenges regarding compatibility and deployment.

I think that's already it from a binary format standpoint. The other issues should then all be solvable on the semantic layer if properly separated, i.e., the keys, matrices, and arrays whose existence is required. For that, the current SQL schema would be a good start to look at. But I "fear" that meeting all the above issues would result in something similar to libsqlite. Compression is the only thing missing in libsqlite. And, as far as I know, it is also hard to emulate because libsqlite wants a real file descriptor to work with, so one would have to spin up a whole FUSE layer only to emulate file-layer compression.

[unxed]

Hi, @mxmlnkn! Longreads are ok 🙂

As a potential middle ground between a completely custom binary format and SQLite, standardizing on FlatBuffers for the index format could be a practical path forward. For resource-constrained and embedded environments, FlatBuffers is suitable because the generated reader code adds minimal footprint to the compiled binary — a few kilobytes compared to several megabytes for SQLite — and reads directly from memory-mapped files with zero-copy overhead. This approach natively supports fast binary search on sorted vector keys to achieve low lookup latency, allows for backward-compatible schema changes to accommodate future metadata deduplication, and provides official, lightweight support in both Python that you use and Go that use I to ensure robust cross-language integration without the need to write and maintain custom parsing logic.

That do you think?

[mxmlnkn]

I like the FlatBuffers tables, which have some of the compatibility guarantees I like in SQLite.

[mxmlnkn]

There are also several pure-Go SQLite libraries. Do you know about those? https://github.com/cvilsmeier/go-sqlite-bench

[unxed]

I use modernc.org/sqlite, but together with its dependencies it increased my binary size by 10 MB! Just for read/write access to a database in pure Go. That’s insane.

glebarez/go-sqlite and zombiezen/go-sqlite use the same modernc.org dependencies, so they likely won’t produce a significantly smaller binary either, just like ncruces/go-sqlite3, which uses WASM. cvilsmeier/sqinn-go relies on a separate C binary, which in my case breaks the full portability requirement that made me choose Go in the first place.

I completely agree about compatibility. That’s exactly why I suggested FlatBuffers as a baseline standard solution — libraries for it exist for many languages.

There are also a couple of other issues worth considering.

First, shouldn’t files in the new format be placed under a different path to avoid breaking compatibility? In that case, if you wanted, you could choose some generic name that many projects could use (this Go implementation is not the only one I plan to make; for example, I’d also like to adapt libarchive accordingly: libarchive/libarchive#2638). Something like .tarindex, .arcidx, .archive-index, or something along those lines.

Second, we’ll probably need a converter from the old format to the new one that would transparently re-encode the user’s cache during upgrades.

Third, we probably need some way to handle the accumulation of indexes for deleted or moved files. I don’t really have any ideas for that yet.

Ideally, it would also be nice to somehow track copies and moves. In my file manager f4, for which I actually need indexed tgz support (I had been considering a similar solution for far2l for a long time, but after seeing yours I realized I’m unlikely to come up with anything more elegant, so it makes more sense to implement compatibility instead of reinventing the wheel), I simply track such archive operations and keep their index files synchronized.

UPD: Also, modernc.org/libc required by modernc.org/sqlite fails to build under DragonFly BSD:
unxed/f4#121

[unxed]

To move things forward, I would like to propose a concrete draft of a FlatBuffers schema. This would allow us to see exactly how we can implement the deduplication strategies you mentioned (folder names and metadata tuples) while maintaining the O(1) random-access properties.

Standardizing this would involve:

1. A .fbs schema defining the FileNode and Index structure.
2. A convention for storing these indexes (e.g., using the .arcidx or .tarindex extension).
3. Logic for handling recursive archives within the same binary blob.

Would you be open to reviewing a draft schema? If so, I can prepare the specific field mappings and deduplication logic.

[mxmlnkn]

Hi, thanks for moving it forward. I would be open to reviewing a draft. Some performance benchmarks would be even better.

I don't see myself completely replacing the SQLite index format soon, although a conversion tool would help quicken such a migration. I like the simplicity of SQLite and the possibility to inspect indexes with command line tools. However, I fear that I have also seen some latency issues caused by the SQL queries behind each FUSE call if I remember correctly, so I would definitely want to try out a first version for performance, e.g., the "find" performance, or I have another worst case (compiling inside a ratarmounted tarball with a write overlay, which has millions of stat calls to non-existing shared library files on each compiler invocation, which slow down the compilation heavily). If I add it to ratarmount, I would probably only add it as an alternative backend at first instead of suddenly replacing the existing format. Removing the old format would be something for a 2.0 version.

As for your earlier message. .tarindex does not really fit because it is intended for all kinds of archives.

First, shouldn’t files in the new format be placed under a different path to avoid breaking compatibility?

I don't fully understand. Normally, the files are created as sidecar files directly beside the archive. In that context "different path" would only break down to "different extension". Only in cases where the archive is in a read-only location, is the index created in $XDG_CACHE_DIR/ratarmount.

Third, we probably need some way to handle the accumulation of indexes for deleted or moved files. I don’t really have any ideas for that yet.

In ratarmount, the user is responsible for managing that. As the indexes are beside the archive, normally, you would delete the indexes when deleting the archives. Except if you have the archives in cold storage and want to keep the indexes for some search operations in that cold storage or the like. As for moving, normally it should move with the archive. If it is stored inside a centralized fallback location such as $XDG_CACHE_DIR/ratarmount, it is a bit harder to do that. It might be nice to key them by some "reliable" sparse hash, as reliable as those can get anyway. However, only keying them by hash feels too unusable to me because I would not be able to match the indexes to the archives without having those indexes. I guess one could add a metadata file. The Linux trash system with .trashinfo files and such might be a source of inspiration for that.

[unxed]

Hi @mxmlnkn,

Thanks for the detailed feedback! I completely agree with keeping SQLite as the default format until at least version 2.0. To ensure a smooth transition, I'll implement a transparent cache converter in unxed/tar that will seamlessly migrate users' existing caches between SQLite and the new format.

Regarding the cache location, standardizing on the .arcidx extension for sidecar files (e.g., archive.tar.arcidx) makes sense. For read-only locations, we can use ~/.cache/arcidx/.

Here is the draft FlatBuffers schema (.fbs). As requested, it uses integer references (path_id, metadata_id) to tightly deduplicate folder paths and heavily repeated metadata tuples (mode, uid, gid, mtime), reducing the footprint exactly as you envisioned:

namespace arcidx;

// Deduplicated metadata tuples
struct MetadataTuple {
  mode: uint32;
  uid: uint32;
  gid: uint32;
  mtime: int64;
}

table Xattr {
  key: string;
  value: [ubyte];
}

// Block offsets for ZSTD/BZIP2
struct BlockOffset {
  block_offset: int64;
  data_offset: int64;
}

table FileNode {
  path_id: uint32;       // Index into ArchiveIndex.paths
  name: string;
  offset_header: int64;
  offset_data: int64;    // Direct offset for O(1) random access
  size: int64;
  type_flag: ubyte;      // TAR typeflag
  link_name: string;
  is_tar: bool = false;
  is_sparse: bool = false;
  is_generated: bool = false;
  recursion_depth: int32 = 0;
  metadata_id: uint32;   // Index into ArchiveIndex.metadata_tuples
  xattrs: [Xattr];
  acl: [ubyte];
}

table ArchiveIndex {
  version: int32 = 1;
  backend_name: string;
  paths: [string];                       // Deduplicated directory paths
  metadata_tuples: [MetadataTuple];      // Deduplicated mode/uid/gid/mtime
  files: [FileNode];                     // Ordered by path_id -> name for binary search
  zstd_blocks: [BlockOffset];
  bzip2_blocks: [BlockOffset];
  gzip_index: [ubyte];                   // Binary GZIDX blob
}

root_type ArchiveIndex;

I have also prepared a pure-Go performance benchmark simulating this FlatBuffers layout vs SQLite memory mapping. It shows $O(1)$ zero-copy read latency and massive throughput improvements for find-like operations. You can view the schema and benchmarks in the unxed/tar repository here.

Results:

~/dev/tar/arcidx_bench$ go test -bench=. -benchmem ./...
goos: linux
goarch: amd64
pkg: github.com/unxed/tar/arcidx_bench
cpu: Intel(R) Core(TM) i5-6300U CPU @ 2.40GHz
BenchmarkSQLite_Lookup-4                   67192             17711 ns/op             568 B/op         20 allocs/op
BenchmarkFlatBuffer_Lookup-4             2993226               386.5 ns/op            23 B/op          1 allocs/op
BenchmarkSQLite_ReadDir-4                    512           2347333 ns/op           72476 B/op       6015 allocs/op
BenchmarkFlatBuffer_ReadDir-4             412682              3272 ns/op               0 B/op          0 allocs/op
PASS
ok      github.com/unxed/tar/arcidx_bench       17.786s

See also: unxed/tar@9e8fae5

Let me know what you think of the schema layout!

P.S. What do you think about the idea of optionally appending the index directly to the end of the archive during creation? Since standard TAR readers stop reading at the end-of-archive marker (two consecutive zero blocks), and concatenated compressed streams (like GZIP or ZSTD) are natively supported, we could append the index as a separate stream at the very end of a newly generated archive. This would keep everything in a single, self-contained file, solving the common issues of users accidentally forgetting to copy the sidecar index alongside the archive or wondering what the mysterious extra files are in their directories.

[mxmlnkn]

// Deduplicated metadata tuples
struct MetadataTuple {
   mode: uint32;
   uid: uint32;
   gid: uint32;
   mtime: int64;
}

Adding the mtime, which I assume to be almost-unique for every file, makes this metadata tuple, supposed for deduplication, completely useless in regard to deduplication. Instead, it probably should further contain the rarely changing FileNode.{type_flag,is_tar,is_sparse,is_generated,recursion_depth} members.

table Xattr {
  key: string;
  value: [ubyte];
}

Compared to the SQL schema, the key is not deduplicated anymore. I feel like this is a small, downgrade because the set of xattr keys is very often very small.

// Block offsets for ZSTD/BZIP2
struct BlockOffset {
  block_offset: int64;
  data_offset: int64;
}

These should be uint64. What are negative values supposed to be? Same for FileNode.{size,recursion_depth,offset_header,offset_data}.

table ArchiveIndex {
  version: int32 = 1;
  backend_name: string;
  paths: [string];                       // Deduplicated directory paths
  metadata_tuples: [MetadataTuple];      // Deduplicated mode/uid/gid/mtime
  files: [FileNode];                     // Ordered by path_id -> name for binary search
  zstd_blocks: [BlockOffset];
  bzip2_blocks: [BlockOffset];
  gzip_index: [ubyte];                   // Binary GZIDX blob
}

I feel like the version should be unsigned. Probably uint8 suffices. I rarely found a good use for version numbers. Often enough, I simply would prefer checking the existence of keys or the like.

As mentioned in my initial reply, having separate zstd_blocks, bzip2_blocks, gzip_index, etc. does not scale, and encoding the BlockOffset into the archive index also feels restrictive. Instead, everything probably should be a simple [ubyte] in a single member and have another member to specify a backend or the "format" of the compression index, which then would be something like gztool_index, gzidx, indexed_zstd or whatever the formats are called.

P.S. What do you think about the idea of optionally appending the index directly to the end of the archive during creation? Since standard TAR readers stop reading at the end-of-archive marker (two consecutive zero blocks), and concatenated compressed streams (like GZIP or ZSTD) are natively supported, we could append the index as a separate stream at the very end of a newly generated archive. This would keep everything in a single, self-contained file, solving the common issues of users accidentally forgetting to copy the sidecar index alongside the archive or wondering what the mysterious extra files are in their directories.

I have never thought about appending it because ratarmount is a read-only tool. I would never want to modify the original pristine archives. When creating the archives, it is another matter. You might wanna look into how pixz stores its information. Simply appending it might not be ideal. There are use cases where you want to use ratarmount --ignore-zeros or (GNU) tar --ignore-zeros. If you really want to append it, you might wanna look into how PAX headers solve this. Normally these additions on top of USTAR use some bogus path such as %d/PaxHeaders.%p/%f or ././@LongLink. This way, extraction with --ignore-zeros will not fail and extract the index. Note that there are also use cases where you want to directly append to a TAR. An appended index would complicate such use cases. Also, it only works for TAR, not ZIP, RAR, and others. Applying different tricks to all these archives does not scale. A sidecar file feels easier to me.

Addendum: Ordering by path_id only gives $\mathcal O(\log N)$ access, not $\mathcal O(1)$. Some kind of hash map would be even nicer. Creating that index with constant memory overhead would also be another issue. I guess one could write to disk and then "sort on disk" somehow, but it is complicated to get right.

Full filesystem formats might also be an option for getting inspiration, i.e., the ext4 superblock / NTFS format. Full filesystems are probably the gold standard for storing metadata in a quick-to-query, non-duplicated manner. It probably would be a fully traversable tree instead of a single table then.

[unxed]

Oh, thanks for the quick review! I'll come back soon with a better proposal. In the meantime, I have another question.

When designing the format, it makes sense to build in some headroom for future use cases. One application that seems worth considering is indexing long files that are stored as a single compressed chunk inside a ZIP archive. For example, if we wanted to mount a ZIP file via FUSE, we could provide random access only at the file level, not at arbitrary positions within a file. And some files can be enormous.

Thinking about this, I came up with two possible solutions:

1. Compress the data in chunks and store a separate header field containing the chunk index.
2. Generate a ratarmount-compatible index for the DEFLATE stream and store it in a separate field.

Ideally, the format should be compatible with existing approaches to avoid duplicating effort and to save developers time. What do you think?

[unxed]

Here is the revised schema incorporating all of your feedback.

1. Data types: Converted all offsets, sizes, and recursion_depth to unsigned types (uint64 / uint32). version is now uint8.
2. Metadata deduplication: Moved mtime to FileNode (since it's unique per file) and brought type_flag, recursion_depth, and the is_* flags into the MetadataTuple. This should yield massive deduplication ratios.
3. Xattr keys: Extracted keys into a global xattr_keys array at the root level, referencing them by key_id to ensure deduplication.
4. Compression index: Unified the backend-specific blocks into a single compression_blob: [ubyte] and compression_format: string (e.g., gztool_index, indexed_zstd).
5. Appending vs sidecar: You are absolutely right about not modifying the pristine archives. We will stick strictly to .arcidx sidecar files or the ~/.cache directory.
6. O(1) vs O(log N): While binary search is mathematically $O(\log N)$, searching over a contiguous, memory-mapped FlatBuffers vector is extremely CPU-cache friendly (L1/L2). In practice, it takes just a few hundred nanoseconds even for millions of files. It effectively provides $O(1)$ latency for our use case without the massive memory footprint and write-time complexity of generating an on-disk hash map.

Here is the updated .fbs draft:

namespace arcidx;

// Deduplicated metadata tuples. Structs in FlatBuffers are inlined and zero-copy.
struct MetadataTuple {
  mode: uint32;
  uid: uint32;
  gid: uint32;
  recursion_depth: uint32;
  type_flag: ubyte;
  is_tar: bool;
  is_sparse: bool;
  is_generated: bool;
}

table Xattr {
  key_id: uint32;        // Index into ArchiveIndex.xattr_keys
  value: [ubyte];
}

table FileNode {
  path_id: uint32;       // Index into ArchiveIndex.paths
  name: string;
  offset_header: uint64;
  offset_data: uint64;
  size: uint64;
  mtime: int64;          // Moved here as it varies per file
  metadata_id: uint32;   // Index into ArchiveIndex.metadata_tuples
  xattrs: [Xattr];
  acl: [ubyte];
  link_name: string;
}

table ArchiveIndex {
  version: uint8 = 1;
  backend_name: string;
  paths: [string];                       // Deduplicated directory paths
  xattr_keys: [string];                  // Deduplicated xattr keys
  metadata_tuples: [MetadataTuple];
  files: [FileNode];                     // Ordered by path_id -> name for binary search
  compression_format: string;            // e.g., "gzidx", "gztool_index", "indexed_zstd"
  compression_blob: [ubyte];             // Unified binary blob for the compression index
}

root_type ArchiveIndex;

(Regarding my question about ZIP chunking from the previous comment — we can safely put that on hold for now to keep the scope of this baseline index format strictly focused).

Let me know how this refined structure looks to you!