This document describes how files are uploaded in the Xet protocol to the Content Addressable Storage (CAS) service. The flow converts input files into chunks, applies deduplication, groups chunks into xorbs, uploads xorbs, then forms and uploads shards that reference those xorbs. Content addressing uses hashes as stable keys for deduplication and integrity verification.
A chunk is a slice of data from a real file.
A chunk has an associated hash computed through the chunk hashing process and its data is determined by finding chunk boundaries following the chunking algorithm defined in chunking.md.
A chunk is ~64KiB of data with a maximum of 128KiB and minimum of 8KiB. However, the minimum chunk size limit is not enforced for the last chunk of a file or if the file is smaller than 8KiB.
A Xorb is composed of a sequence of chunks.
Chunks in a xorb are not simply concatenated but instead compressed and appended after a header as described in xorb.md. Chunks are collected in a xorb for more efficient upload and downloads of "ranges" of chunks. Each chunk has an associated index (beginning at 0) and chunks may addressed from xorbs using through an end exclusive chunk index range i.e. [0, 100).
Xorbs are created by grouping sequences of chunks from files and are referenced in file reconstructions to provide instructions to rebuild the file.
Xorbs have an associated hash computed according to the instructions for the xorb hashing process.
Xorbs are always less than or equal to 64MiB in length and on average contain 1024 chunks, but this number is variable.
A file reconstruction is a "recipe" to recreate a file using data from xorbs.
Each file reconstruction is made of a series of "terms" where each term contains a xorb hash and a chunk index range. To reconstruct a file, a user needs will need the chunks at the specified range for each term, deserialized and decompressed and concatenated in term order.
Shards are serialized representations of file information and xorb metadata.
A shard may contain multiple file reconstructions or none. A shard may also contain information about xorbs, particularly what chunks are in a particular xorb.
Shards are used to communicate a "file upload" or registering the file in the CAS (Content Addressed Store) as well as registering groups of xorbs associated with the same upload.
Shards are also used to communicate xorb metadata that can be used for deduplication using the Global Deduplication API.
The shard format is specified in shard.md.
In xet-core the shard format is used to keep a local cache with fast lookup of known chunks for deduplication, other implementors of the xet protocol may choose to reuse the shard format for that purpose as well, however that is not a requirement of the protocol.
Using the chunking algorithm described in chunking.md first split the file into variable sized chunks. Each chunk should have a unique hash computed as described in the Chunk Hashing section. This chunk hash will be used to attempt to deduplicate any chunk against other known chunks.
Given a chunk hash, attempt to find if the chunk already exists in the Xet system.
To deduplicate a chunk is to find if the current chunk hash already exists, either in the current upload process, in a local cache of known chunks or using the Global Deduplication API.
When a chunk is deduplicated it does not need to be re-uploaded to the CAS (by being included in a xorb in the next step), but when rebuilding the file, the chunk needs to be included by referencing the xorb that includes it and the specific chunk index.
Note that Deduplication is considered an optimization and is not a required component of the upload process, however it provides potential resource saving.
For more detail visit the deduplication document
Contiguous runs of chunks are collected into xorbs (roughly 64 MiB total length per xorb), preserving order within each run. See formation rules: xorb.md. The xorb's content-addressed key is computed using the chunks in the xorb. See: hashing.md.
Given the xorb hash chunks in the xorb can be referred in file reconstructions.
Each xorb is serialized into its binary representation as defined by the xorb format. See: xorb.md. The client uploads each new xorb via the Xorb upload API.
The serialization and upload steps are separated from collecting chunks and hashing as these steps can be done independently while still referencing the xorb in creating file reconstructions. However a xorb must be uploaded before a file reconstruction that references it is uploaded in a shard.
Map each file to a reconstruction using available xorbs, the file reconstruction should point to ranges of chunks within xorbs that refer to each chunk in the file. Terms for chunks that are deduplicated using results from the Global Dedupe API will use xorb hashes that already exist in CAS.
Then for each file:
With these components it is now possible to completely serialize a file info block in the shard format.
In addition to the file info information, it is also necessary to collect all metadata for new xorbs that were created. This metadata is the xorb hash, the hash and length of each chunk, the serialized length of the xorb and the sum of the chunk lengths for a xorb. With these components it is now possible to serialize for each xorb a CAS Info block.
Given the information collected in the previous section, serialize a shard for a batch of files following the format specified in the shard spec.
The client uploads the shard via the shard upload endpoint on the CAS server. For this to succeed, all xorbs referenced by the shard must have already completed uploading.
This API registers files as uploaded.
For a large batch of files or a batch of large files if the serialized shard will be greater than 64 MiB you will have to break up the content into multiple shards.
After all xorbs and all shards are successfully uploaded, the full upload is considered complete. Files can then be downloaded by any client using the download protocol.
There are some natural ordering requirements in the upload process, e.g. you must have determined a chunk boundary before computing the chunk hash, and you must have collected a sequence of chunks to create a xorb to compute the xorb hash etc.
However there is one additional enforced requirement about ordering: all xorbs referenced by a shard must be uploaded before that shard is uploaded. If any xorb referenced by a shard is not already uploaded when the shard upload API is called, the server will reject the request. All xorbs whose hash is used as an entry in the cas info section and in data entries of the file info section are considered "referenced" by a shard.
sequenceDiagram
autonumber
participant Client
participant CAS as CAS Server
Client->>Client: Chunking: split file into chunks and compute chunk hashes
Note right of Client: 2) Local deduplication (optional)
loop For each chunk if chunk % 1024 == 0<br/>(global dedupe eligible)
opt Global deduplication (optional)
Client->>CAS: GET /v1/chunks/default-merkledb/{chunk_hash}
CAS-->>Client: 200 dedupe information or 404 not found
end
end
Client->>Client: Xorb formation (group chunks ~64 MiB), hashing, serialization
loop For each new Xorb
Client->>CAS: POST /v1/xorbs/default/{xorb_hash}
CAS-->>Client: 200 OK
end
Client->>Client: Shard formation (files -> reconstructions) and serialization
Client->>CAS: POST /v1/shards
CAS-->>Client: 200 OK
Note over Client,CAS: All referenced Xorbs must be uploaded before Shard upload.<br/>Endpoints are idempotent by content-addressed keys.