Skip to main content Link Search Menu Expand Document (external link)

ZEP 2 - Sharding storage transformer

Authors:

Status: Draft

Type: Specification

Created: 2022-08-02

This ZEP is accompanied by the sharding extension specification [SHARDINGSPEC]. A public review of the specification is done in PR #@152 of the zarr-specs repo.

Abstract

This ZEP proposes to add a sharding storage transformer to the Zarr specification version 3. This permits combining multiple chunks into storage keys, enabling the usage of larger arrays with Zarr.

Motivation and Scope

Currently, Zarr maps one array chunk to one storage key. This becomes a bottleneck as storing large arrays usually requires a large number of chunks, which becomes inefficient or impractical to store when a chunk is mapped directly to files or objects in the underlying storage. For example, the file block size and maximum inode number restrict the usage of numerous small files for typical file systems, also cloud storage such as S3, GCS, and various distributed filesystems do not efficiently handle large numbers of small files or objects.

Increasing the chunk size works only up to a certain point, as chunk sizes need to be small for read and write efficiency requirements, for example to stream data in browser-based visualization software.

Therefore, chunks may need to be smaller than the minimum size of one storage key. In those cases, it is efficient to store objects at a more coarse granularity than reading chunks.

Sharding solves this by allowing to store multiple chunks in one storage key, which is called a shard:

sharding schema

The following example illustrates the need for sharding:

The dataset has a shape of (25000, 18000, 6000) and a dtype of uint8. This makes for a total size of 2.4TB. For efficient reads and fast streaming of the data, e.g. to a browser-based interface, chunk sizes should be of max. (64, 64, 64). For this dataset that would result in 10.3M chunks, and without sharding also to 10.3M files. Considering having multiple of these datasets, the number of files becomes impractical. With sharding, one could use (32, 32, 32) chunks per shard, so that each shard has a size of (2048, 2048, 2048) voxels. That would reduce the number of files to ~300 while maintaining a practical write granularity.

To allow interoperability between different stores and Zarr implementations, we propose to standardize sharding as a storage transformer specification.

Usage and Impact

Sharding allows storing very large, chunked arrays, which currently would have inefficient access characteristics or might even be impossible to store as generic Zarr arrays.

Image datasets in the biomedical, geo-science, and general data-science communities are steadily growing. In recent years, peta-scale datasets have been made publicly available. Although peta-scale datasets are still infrequent, tera-scale datasets are acquired routinely and rapidly grow in size further.

Currently, these large-scale datasets are made available through tool-specific formats, such as neuroglancer-precomputed or webknossos-wrap, which support sharding. While the data is accessible and explorable in individual software tools, wider interoperability with other software tools is limited. Whereas it has been possible to convert smaller datasets to work in different tools, it becomes infeasible for large-scale datasets. The choice of tool-specific formats is in part a result of the lack of a standard format that makes storage and processing of very large datasets practical. Providing sharding in Zarr would allow Zarr to become the standard format also for tera- and peta-scale array data and future-proofing it as a standard for the requirements of growing data sizes in the scientific community.

Backward Compatibility

This ZEP introduces a Zarr extension for Zarr version 3. The sharding extension is optional for data producers, and only necessary when reading arrays that are written using the sharding extension. It corresponds to a minor version change in semantic versioning, adding functionality in a backward compatible manner.

As storage transformers are specified in the array metadata, Zarr clients without implementation for the sharding extension should infer that they are lacking support for the specific array, as all storage transformers are required, non-optional extensions.

Detailed description

Combining regular blocks of chunks in a shard

To add sharding to Zarr, data that was stored previously as separate objects must be combined. Different strategies can be considered when sharding array data, such as:

  1. sharding across single dimensions,
  2. sharding by regular n-dimensional blocks of data, and
  3. sharding random combinations of chunks via hashing.

All of those strategies only shard the array data and not the metadata, since the latter is not big enough to warrant sharding and also because the sharding configuration itself is stored in the metadata.

Strategy 2 is a strict super-set of strategy 1, as sharding across a single dimension can be produced by sharding with n-dimensional blocks where all blocks consist of single chunks except for the selected dimension.

Strategy 3 permits balancing loads better between shards than the other two strategies. Since all shards will often be served via the same underlying storage, load-balancing does not have a high priority in this use case.

This ZEP proposes to use strategy 2, using regular n-dimensional blocks of chunks as sharding units, as it combines multiple chunks that are close to each other. This has the benefit of co-locating data that is usually accessed together or in short succession.

Shardings as a storage transformer extension

Sharding can be an optional addition to the current Zarr features, as it is primarily important for very large arrays. Therefore it should be added as an extension, which can enhance different Zarr implementations.

Sharding by combining different chunks can only be implemented in logical units operating after chunking and indexing are done. Therefore it could be implemented directly in the storage layer, but this could result in different sharding implementations between different stores and Zarr implementations, compromising the core Zarr benefit of interoperability.

Therefore, sharding should rather be implemented as a storage transformer, which permits consistently addressing array data across different stores and ensures compatibility across implementations, by specifying an authoritative specification.

Configuration

Sharding can be configured per array in the array metadata by specifying the following array metadata keys:

  • extension must always be "https://purl.org/zarr/spec/storage_transformers/sharding/1.0" for this extension.
  • type specifies a binary shard format. In this version, the only binary format is the indexed format.
  • configuration contains only the following configuration key:
    • chunks_per_shard is an array of integers providing the number of chunks that are combined in a shard for each dimension of the Zarr array, where each chunk may only start at a position that is divisible by chunks_per_shard per dimension, e.g. starting at the zero-origin. The length of the array must match the length of the array metadata shape entry. For example, a value [32, 2] indicates that 64 chunks are combined in one shard, 32 along the first dimension, and for each of those 2 along the second dimension. Some valid starting positions for a shard in the chunk-grid are therefore [0, 0], [32, 2], [32, 4], [64, 2] or [96, 18].

Binary shard format

The following part is cited from the accompanying sharding extension specification [SHARDINGSPEC]:

The only binary format is the indexed format, as specified by the type configuration key. Other binary formats might be added in future versions.

In the indexed binary format chunks, are written successively in a shard, where unused space between them is allowed, followed by an index referencing them. The index is placed at the end of the file and has a size of 16 bytes multiplied by the number of chunks in a shard, for example 16 bytes * 64 = 1014 bytes for chunks_per_shard=[32, 2]. The index holds an offset, nbytes pair of little-endian uint64 per chunk, the chunks-order in the index is row-major (C) order, for example for chunks_per_shard=[2, 2] an index would look like:

| chunk (0, 0)    | chunk (0, 1)    | chunk (1, 0)    | chunk (1, 1)    |
| offset | nbytes | offset | nbytes | offset | nbytes | offset | nbytes |
| uint64 | uint64 | uint64 | uint64 | uint64 | uint64 | uint64 | uint64 |

Empty chunks are denoted by setting both offset and nbytes to 2^64 - 1. The index always has the full shape of all possible chunks per shard, even if they are outside of the array size.

The actual order of the chunk content is not fixed and may be chosen by the implementation as all possible write orders are valid according to this specification and therefore can be read by any other implementation. When writing partial chunks into an existing shard no specific order of the existing chunks may be expected. Some writing strategies might be

  • Fixed order: Specify a fixed order (e.g. row-, column-major or Morton order). When replacing existing chunks larger or equal-sized chunks may be replaced in-place, leaving unused space up to an upper limit that might possibly be specified. Please note that for regular-sized uncompressed data all chunks have the same size and can therefore be replaced in-place. > *
  • Append-only: Any chunk to write is appended to the existing shard, followed by an updated index. If previous chunks are updated, their storage space becomes unused, as well as the previous index. This might be useful for storage that only allows append-only updates.
  • Other formats: Other formats that accept additional bytes at the end of the file (such as HDF) could be used for storing shards, by writing the chunks in the order the format prescribes and appending a binary index derived from the byte offsets and lengths at the end of the file.

Any configuration parameters for the write strategy must not be part of the metadata document, they need to be configured at runtime, as this is implementation specific.

Use-cases and access strategies

Reading data per chunk

Reading single chunks can be done in two ways, depending on the capabilities of the underlying storage:

    • Downloading the complete corresponding shard,
    • reading the index and
    • afterwards reading the relevant chunk.
    • Downloading only the index of the corresponding shard,
    • identifying the relevant byte-range for the requested chunk,
    • only downloading this byte-range from the same shard.

The first method might especially be useful when caching not only the requested chunks but the whole shard, which will save bandwidth if subsequent chunk-requests are close to the previous chunks.

Storing a stream of data slices

Many image acquisition techniques produce slice-wise data, such as timeseries or z-slicing. This data can be written slice-wise using one of the following techniques:

  1. Using a chunk-size and shard-size of 1 for the sliced dimension effectively disables chunking and sharding for this dimension.
  2. Slice-wise data with a chunk-size of 1 for the sliced dimension can be appended to a shard, only wasting the space for the index that was written before.
  3. When using no compression, chunk-sizes are constant, and shard indices can be known ahead of time, allowing to write partial chunks of a shard. Therefore, a chunk-size of 1 can be used for the sliced dimension, in addition to a higher shard-size for this dimension. This is beneficial if later access typically consists of blocks with multiple slices.
  4. Strategy 3 can be combined with compression by writing the compressed chunks in the order they arrive, overwriting the old index and appending the updated index including the new chunks.

Updating chunks

Updating chunks can be done with different strategies, depending on the byte-length of the chunks and therefore depending on the compression:

  • Uncompressed chunks can be rewritten in-place, since their size is constant and the index does not need to be updated.
  • When updating compressed chunks one can also update the chunk in-place if there is enough unused space between the chunk and the following chunk (or index). However, the index must still be updated if the byte-length of the chunk changed.
  • When the compressed chunk is larger than before and no unused space is available, it might either
    • be appended to the shard, leaving the previous space unused, or
    • rewriting the shard, moving also other chunks.

Implementation

A Python implementation is drafted in the zarr-python PR #1111.

The following proof of concept implementations explored similar approaches:

Discussion

  1. Discussions for the specification:
  2. Initial issue in zarr-python:
  3. Other related discussions:

References and Footnotes

License

CC0
To the extent possible under law, the authors have waived all copyright and related or neighboring rights to ZEP 2.