Externally caching file metadata

[sydduckworth]

An issue we're running into with ASDF files is that they are missing certain metadata that could significantly speed up reading/processing. In general this metadata is either available from an external source (e.g. schema definitions) or can be reconstructed from the ASDF file itself (e.g. block layouts).

Rather than adding to or changing the format of ASDF files themselves, we could instead store additional metadata external to the ASDF files to improve reader performance.

Supplemental Information

Below is a non-exhaustive list of additional information that would speed up reading/validating ASDF files if available.

Cached Validation

Currently the reader needs to re-validate an ASDF file every time it is read. We could avoid some (ideally most) validations by storing some record of previous validation that can be checked by the reader.

One way this could work is:

• Store a checksum file alongside the ASDF file.
• The reader checks the "last modified" property of the ASDF file and the checksum file.
• If the checksum file is newer than the ASDF file then the reader can skip validation.
• If the checksum file is older than the ASDF file then the reader re-computes the checksum from the ASDF file.
• If the checksums match then the reader can just "touch" the checksum file to update its timestamp and then skip validation.
• If the checksums don't match then the reader needs to perform traditional validation on the ASDF file.
• If the file is valid then the reader writes a new checksum file (this would also happen if the checksum file is missing).

Schema Definitions

The reader needs access to schema definitions in order to validate the structure of an ASDF file. Currently (for the Python library) this requires installing a Python package that provides a resource mapping for the schema. If we had a way to store schemas alongside the ASDF files then files could be validated without needing additional packages.

It's also worth noting that whereas all of the other metadata described in this section is per-file, schemas could potentially be shared across multiple files to avoid duplication.

Block Index

ASDF files already contain a block index, but they aren't required and it isn't guaranteed to be correct. Additionally there's not a direct way to locate the start of a block index: readers either have to search backward from the end of the file or forward from the last block.

If we stored a block index externally it would be easier to locate and could also be updated if needed without rewriting the original file. Primarily, though, the benefit is that it would facilitate the other layers of additional metadata described below.

Tag Index / Block Mapping

ASDF's YAML-based tree structure works well for some queries but there are other queries that could be sped up by storing information about the tree structure in a different format.

One example would be block lookups. If I already know I want to read an array at a specific path in the tree (e.g. tree["foo"]["bar"]) the reader has to read the entire tree in order to parse it, then find the associated block and read that as well.
If we had a mapping of blocks to their hierarchical paths in the tree it could be possible to speed up queries in situations where the user only wants a single array from the file.

Another example: in the future we're hoping to define standard structures for astronomical data in ASDF (similar to FITS). For certain tools (e.g. visualizers) it could be useful to have a flat index of which structures appear in a given file rather than potentially needing to walk the entire tree to locate all of them.

Block Chunk Layout

ASDF currently doesn't have good support for reading a slice of an array stored in a block. It's possible to compute the byte range of a slice for uncompressed blocks but not for compressed blocks. For most of the compression formats you're required to read and decompress the entire block because all of the data is stored in a single chunk. For LZ4 compression the data is stored in a sequence of 4MB chunks so it is possible to only read part of a block, but there is currently no way to map an uncompressed byte range to a set of chunks.

If we cached the locations of each chunk along with their corresponding uncompressed byte offsets then readers could efficiently read slices from LZ4 compressed blocks.

Array Metadata

ASDF files store the information needed to read and decompress a block in the block header. However, the primary use case for blocks is to store ndarrays, in which case array metadata like shape and dtype are stored in the YAML tree.

If we're already storing supplemental block/chunk layout information as described above it would be trivial to also include ndarray metadata such as dtype and shape. We wouldn't even need a special case for ndarrays since blocks that aren't ndarrays can still be represented as a flat uint8 ndarray.

All together this added information would allow efficient reading of array slices with no additional metadata needed from the ASDF file itself.

[sydduckworth]

Implementation Thoughts

Below are some thoughts I had about what a potential implementation could look like.
This assumes we want to cache schemas as well as at least some of the other metadata discussed above.

In this scenario the validation checksum and all other metadata would exist in a single .meta file for each ASDF file.

Cloud Layout

s3://mybucket/my-dataset/
 ├ file-1.asdf
 ├ file-1.asdf.meta
 ├ file-2.asdf
 ├ file-2.asdf.meta
 └ .asdf/schema/
    │ # https://example.com/schema/myschema-1.0
    ├ aHR0cHM6Ly9leGFtcGxlLmNvbS9zY2hlbWEvbXlzY2hlbWEtMS4w
    │ # https://example.com/schema/otherschema-1.1
    └ aHR0cHM6Ly9leGFtcGxlLmNvbS9zY2hlbWEvb3RoZXJzY2hlbWEtMS4x

For ASDF files in cloud storage the metadata and schema would be stored alongside the ASDF files themselves.

The metadata sidecar for <file>.asdf would be stored in <file>.asdf.meta.

The schemas for the files in a given directory (or bucket, or other granularity level) would be stored in an .asdf/schema subdirectory.
Each schema file's name would be the base64-encoded schema URI. This allows direct lookups by URI while avoiding potentially invalid file URLs.

Local Layout

~/my-dataset/
 ├ file-3.asdf
 ├ file-3.asdf.meta
 ├ file-4.asdf
 └ file-4.asdf.meta

~/.cache/asdf/
 ├ schema/
 │ │ # https://example.com/schema/myschema-1.0
 │ ├ aHR0cHM6Ly9leGFtcGxlLmNvbS9zY2hlbWEvbXlzY2hlbWEtMS4w
 │ │ # https://example.com/schema/otherschema-1.1
 │ └ aHR0cHM6Ly9leGFtcGxlLmNvbS9zY2hlbWEvb3RoZXJzY2hlbWEtMS4x
 │
 └ meta/remote/
   │ # s3://mybucket/my-dataset/file-1.asdf
   ├ czM6Ly9teWJ1Y2tldC9teS1kYXRhc2V0L2ZpbGUtMS5hc2Rm
   │ # s3://mybucket/my-dataset/file-2.asdf
   └ czM6Ly9teWJ1Y2tldC9teS1kYXRhc2V0L2ZpbGUtMi5hc2Rm

For local files the layout is largely the same, except that the schemas are cached in a single central directory for all files.

We also add a central cache for remote file metadata. The sidecar file names are the base64-encoded remote file URIs.

One potential problem with this approach is that local files are much more likely to be moved or renamed than remote files, which may result in them losing their sidecar files.
If we wanted to avoid this we could instead store all of the metadata files in a central location and index them by file hash, but this would add additional overhead.

Metadata File Format

In my opinion the two most relevant formats for the metadata sidecar files are JSON and Flatbuffers.

JSON

JSON has the advantages of being self-describing and being supported by basically every programming language.
Its primary disadvantage is that it is a text-based format, meaning it isn't particularly space-efficient and it is much slower to deserialize than a binary format.

JSON is used by Zarr and fsspec's Kerchunk.

Flatbuffers

Flatbuffers is a binary format like Protobuf but with zero-copy deserialization.
Compared to JSON it is much more space-efficient (both on disk and in memory) and faster to deserialize (based on the Rust serialization benchmark about twice as fast).
Flatbuffer's primary disadvantage compared to JSON is that is isn't human-readable. How much this matters for ephemeral cache files is questionable.

Flatbuffers is used by Icechunk and is also the container format for Apache Arrow IPC.

[zacharyburnett]

I like the idea of zero-copy deserialization; does flatbuffers implementations across languages change any behavior? It looks like from their website that all of their language implementations are first-party so I would assume it would be interchangeable

[sydduckworth]

I'm not aware of any language-specific differences with flatbuffers, but I've also mostly used it with Rust.

Another zero-copy option if we were okay with it being Rust only (e.g. if we wanted to have a single core implementation of the feature that the different languages wrap) is rkyv, which according to the serialization benchmark is several times faster than flatbuffers.

[zacharyburnett]

regarding .asdf/schema/, would it be feasible to search for .asdf/ in parent directories going up the tree? Or does that make it more complicated than necessary

~/dataset-1/
 ├ needs-a.asdf
 ├ needs-a.asdf.meta
 ├ needs-a+b.asdf
 ├ needs-a+b.asdf.meta
 ├ dataset-2/
   ├ needs-b.asdf
   └ needs-b.asdf.meta
 ├ dataset-3/
   ├ needs-c.asdf
   ├ needs-c.asdf.meta
   └ .asdf/schema/
     └ schema-c
 └ .asdf/schema/
   ├ schema-a
   └ schema-b

[sydduckworth]

Yeah I think it would be good to support searching at least a few directories above the current one (possibly configurable).

Probably makes sense to have a priority ranking for paths, e.g. first search ~/.cache/asdf then the directory containing the file, then the parent directory, etc.