Expand description
Scionic Merkle trees.
A tree holds a folder of files, or one file, under one root hash. A file is a list of chunks, a folder is a list of names, and the root covers all of it. Identical chunks, files and folders have identical hashes wherever they are, so a store keeps each of them once. A sender can show a part of a tree without the rest: one name in a folder, one chunk of a file, or a stretch of a file’s bytes.
spec/FORMAT.md in this repository says exactly what each hash covers.
Modules§
- tree
- The classic tree over a list.
Structs§
- Accepted
- What became of a frame that an intake accepted.
- Build
Options - How a tree is built from disk.
- Builder
- Builds a tree part by part: files from their bytes, folders from their entries, and at the end the record.
- Chunk
Ref - One item of a file’s list: a chunk’s hash, and how many bytes it holds.
- Entries
- A branch of a folder’s entries, as a peer showed it and as it was checked.
- Entry
- One entry of a folder: a name, the file or folder under it, and extra data.
- Extra
Data - A small set of named values, kept beside a name in a folder or in a tree’s record. It holds at most 32 values. A value’s name is 1 to 64 bytes, and a value is at most 1,024 bytes.
- File
Branch - A branch of a file’s list, with the nodes that stand for the rest of it.
- File
List - A file: the list of its chunks, in the file’s order.
- Folder
Branch - A branch of a folder’s list, with the nodes that stand for the rest of it. A branch of an empty folder shows nothing, and carries nothing.
- Folder
List - A folder: the list of its entries, sorted by name, with no name twice.
- Hash
- A SHA-256 hash: of a chunk’s bytes, or of the bytes that describe a file, a folder or a tree.
- HaveMap
- Which chunks of a file a peer holds: one bit a chunk, in the file’s order. A peer says this about itself, and nothing proves it.
- Intake
- Takes one tree into a store, checking every part as it arrives.
- Memory
Store - A store in memory.
- Open
File - A file’s list with its tree kept, for showing many parts of it, and for finding the chunks that hold a stretch of bytes.
- Open
Folder - A folder’s list with its tree kept, for showing many parts of it.
- Record
- A tree’s record: the file or folder on top, the tree’s totals, and its extra data. The hash of the record is the tree’s root.
- Remote
- Reads parts of one tree straight from a peer, with nothing kept.
- Responder
- Answers requests from a store.
- Root
- The root of a tree: the hash of its record. It is what a tree is known by.
- Stream
Peer - A peer at the other end of a connection, where
serveanswers. - Summary
- A tree that is whole and checked.
- Target
- A file or a folder as the thing above it names it: its kind, its hash, and how many bytes of file content it holds.
- Totals
- What a tree says about itself as a whole: how much a store has to keep for it. Each counts a thing once, however often the tree uses it.
- Verify
Options - How a held tree is checked, beyond what is always checked.
- Write
Options - How far writing a tree out may go.
Enums§
- Arrived
- What a frame turned out to be, once its hash was worked out.
- Change
- One difference between an old tree and a new one.
- Chunking
- How a tree’s files are split into chunks.
- Error
- Frame
- A frame, read.
- Kind
- Whether an entry is a file or a folder.
- Links
- What a builder does with a link or a special file that it finds in a folder. Neither is stored in a tree, and a link is never followed: it could lead out of the folder that is being built.
- Refusal
- Why a peer does not answer.
- Request
- What a receiver asks a peer for.
- Stored
- The kinds of thing a store keeps.
Constants§
- BUNDLE_
MAGIC - What starts a bundle: a tree written out as one stream of frames.
- CHUNKING_
FASTCDC_ V1 - How a tree says that its files were chunked by content.
- CHUNKING_
KEY - The extra value of a record that says how the tree’s files were chunked.
- DEFAULT_
MAX_ CHANGES - The most changes that
difflists. - DEFAULT_
MAX_ WRITTEN_ ENTRIES - The most files and folders that
write_to_diskmakes unless it is told otherwise. - FASTCDC_
GEAR_ SEED_ PREFIX - Frozen derivation seed for the gear table below:
- FASTCDC_
LOOSE_ MASK - Selects the top 19 bits (boundary ⇔ h < 2^45). Used for positions at or
after
FASTCDC_TARGET_SIZE. The loose mask is a subset of the strict. - FASTCDC_
MAX_ SIZE - Forced-cut ceiling. It exists to bound worst-case chunk size (record framing, transport batching), not as a size anyone chooses: with normalized chunking a forced cut is rare, degenerate-content territory.
- FASTCDC_
MIN_ SIZE - Cut-point skipping floor: no boundary test runs inside the first
FASTCDC_MIN_SIZEbytes of a chunk, and those bytes are not hashed at all. Interior chunks are therefore at leastFASTCDC_MIN_SIZE + 1bytes; only a final tail chunk may be smaller. - FASTCDC_
STRICT_ MASK - Selects the top 23 bits of the rolling hash (boundary ⇔ h < 2^41).
Used for positions before
FASTCDC_TARGET_SIZE. - FASTCDC_
TARGET_ SIZE - Normalization switch: the strict mask judges positions before it, the loose mask after it, squeezing the chunk-size distribution toward the target.
- FRAME_
CHUNK - A chunk’s bytes.
- FRAME_
FILE_ BRANCH - A branch of a file’s list, with the nodes that stand for the rest.
- FRAME_
FILE_ LIST - A file’s whole list.
- FRAME_
FOLDER_ BRANCH - A branch of a folder’s list, with the nodes that stand for the rest.
- FRAME_
FOLDER_ LIST - A folder’s whole list.
- FRAME_
HAVE - Which chunks of a file a peer holds.
- FRAME_
RECORD - A tree’s record. The frame is the record itself, whose first byte this is.
- FRAME_
REFUSED - The peer does not answer, and why.
- LIST_
ITEM_ BYTES - How many bytes one item of a file’s list takes: a hash and a length.
- MAX_
CARRIED_ NODES - The most nodes a branch may carry: 40 on each side of what it shows.
- MAX_
CHUNK_ BYTES - The most bytes a chunk may hold: 8 MiB.
- MAX_
ENTRY_ BYTES - The most bytes a folder’s entry may take: its fixed part, the longest name, and extra data that is as full as it can be.
- MAX_
EXTRA_ BYTES - The most bytes a set of extra data may take: how many values it has, and 32 values that are as long as they can be.
- MAX_
EXTRA_ NAME_ BYTES - The most bytes the name of an extra value may hold.
- MAX_
EXTRA_ VALUES - The most values a set of extra data may hold.
- MAX_
EXTRA_ VALUE_ BYTES - The most bytes an extra value may hold.
- MAX_
FOLDER_ DEPTH - The most folders that may sit inside one another, the top one counted.
- MAX_
NAME_ BYTES - The most bytes a name may hold.
- MAX_
RECORD_ BYTES - The most bytes a record may take: its fixed part, and extra data that is as full as it can be.
- MAX_
REQUEST_ BYTES - The most bytes a request may take. The longest one asks for a name in a folder: its first byte, the folder’s hash, and the longest name with its length.
- REQUESTS_
AHEAD_ BYTES - How many bytes of requests a
StreamPeersends ahead of their answers. It is small on purpose. The other end answers one request before it reads the next, so requests that are sent ahead wait in the connection, and a connection that could not hold them would leave both ends waiting for each other. Every connection holds this much. - TIMESTAMP_
KEY - The extra value of a record that says when the tree was built.
Traits§
- Peer
- Something that answers requests: a connection to another machine, or a
Responderin this one. - Store
- A place that keeps bytes under hashes.
Functions§
- build
- Builds the tree of the folder or the file at
pathintostore, and gives its root. - build_
with - Builds a tree as
builddoes, and asksentry_extrafor the extra data of every entry. - check_
name - Checks a name: 1 to 255 bytes, no
/, no zero byte, and not.or... - chunk_
frame - The frame for a chunk’s bytes.
- diff
- The differences between two trees that a store holds, sorted by path. Both trees must have a folder on top, or be the same tree.
- diff_
within - The differences between two trees, as
diffgives them, where more thanmostchanges are an error. - export
- Writes a whole tree to
outas one stream: the bundle’s first bytes, the record, and then every list and every chunk once, each after what names it.importreads it back. - fetch
- Takes the whole tree with this root from a peer into a store.
- file_
branch_ frame - file_
hash - The hash of a file with
countchunks andsizebytes, whose list’s tree hasliston top. - file_
list_ frame - The frame for a file’s whole list.
- file_of
- The list of a file’s chunks.
- folder_
branch_ frame - folder_
hash - The hash of a folder with
countentries andsizebytes of file content, whose list’s tree hasliston top. - folder_
list_ frame - The frame for a folder’s whole list.
- folder_
of - The entries of a folder.
- have_
frame - import
- Reads a bundle that
exportwrote, and takes the tree with this root from it into a store. Every frame goes through the same checks as a frame from a peer, and the tree must be whole when the stream ends. A frame for something the store holds already is passed over. A frame that nothing in the tree names is an error. - lookup
- What is at
pathin a tree: names with/between them, as inweights/model.safetensors. Nothing is there when a name on the way is missing, or is a file. A path that leads through more folders than a tree may have is an error. - read_
file - Writes all of a file’s bytes to
out. - read_
file_ to_ vec - A file’s bytes, in memory.
- read_
frame - Reads one frame from a stream, or nothing when the stream has ended. A
frame longer than
limitis refused before any of it is read, and a stream that ends inside a frame is an error. - read_
open - Writes
lengthbytes of a file whose list is open, from byteoffset, toout. It does whatread_rangedoes, and finds the chunks without a pass over the list. - read_
range - Writes
lengthbytes of a file, from byteoffset, toout. - record_
of - The record of the tree with this root.
- refused_
frame - serve
- Answers the requests that come in on a connection, until it ends.
- unwritable
- Why this system cannot hold a name as it is, if it cannot.
- unwritable_
on_ windows - Why Windows cannot hold a name as it is, if it cannot.
- verify
- Checks a whole tree that a store holds: every list, every chunk’s bytes, the depth of its folders and the totals in its record. It is the same set of checks that a tree goes through when it is taken in.
- verify_
with - Checks a whole tree that a store holds, with more checks switched on.
- write_
frame - Writes one frame to a stream: its length as four bytes, then the frame.
- write_
to_ disk - Writes a tree out to disk: its top folder as the new folder
dest, or its top file as the new filedest. - write_
to_ disk_ with - Writes a tree out to disk as
write_to_diskdoes, within other limits.
Type Aliases§
- Entry
Extra - Gives the extra data for one entry: its path on disk, its name, and whether it is a file or a folder.
- Result