Proposal for CASL (Content-Addressed Storage Layout) specification

[johnbenac]

I'm already using some components from DASL in my project, and needed to shard and store some blobs, so I tried to do it the IPFS way! I'm documenting my approach, and suggesting that it be a new standard. Here is the proposed standard:

CASL defines a deterministic mapping from a CID ([[cid]]) to a sharded storage path, suitable for filesystems and object stores that need to store large numbers of content-addressed payloads. CASL standardizes only the “where does this CID live in the store?” question; it does not define chunking, DAG layouts, replication, or transport.
Introduction

Storing hundreds of thousands (or millions) of CID-addressed resources in a single directory (or under a small number of object-store prefixes) is operationally expensive and can become a performance bottleneck. CASL provides a deterministic sharding rule so that independent implementations can store and locate content-addressed payloads consistently.

The key words “MUST”, “MUST NOT”, “SHOULD”, “SHOULD NOT”, and “MAY” are to be interpreted as described in RFC 2119 ([[rfc2119]]).

CASL is intentionally narrow in scope. It does not define block chunking, Merkle DAG layout, or retrieval/replication behavior. CASL is only about mapping a CID to a storage path.
Terminology

Storage root
An implementation-defined directory or object-store prefix under which CASL paths are constructed.
CASL key
A deterministic string derived from the CID’s multihash bytes. It is used for sharding and for the leaf name by default.
Shard
A short string used as a directory (or prefix) component to distribute objects across buckets.

Deriving a CASL Key

CASL sharding operates over a CASL key, derived from the CID’s multihash bytes. CASL does not shard on the CID’s string form.

Use the following steps to derive a CASL key:

Accept a CID in either string form or bytes form ([[cid]]).
Decode the CID to obtain its multihash bytes (hash function code, digest length, and digest) ([[cid]]).
Base32-encode the multihash bytes using the base32 algorithm from RFC 4648 ([[rfc4648]]) with:
    the RFC 4648 alphabet (A–Z and 2–7),
    no padding characters,
    and an uppercase output.
Store the resulting string in key.
Return key.

NOTE: This style of key is compatible with the character restrictions used by FlatFS-style filesystem datastores (e.g. the FlatFS implementation used by Kubo).
Sharding

CASL’s default sharding rule is next-to-last/2: it takes the two characters immediately preceding the last character of the CASL key.

Use the following steps to compute a next-to-last shard:

Accept a string key and an integer suffixLen.
If suffixLen is less than 1, throw an error.
If the length of key is less than suffixLen + 1, prepend _ characters to key until its length is suffixLen + 1.
Return the substring of key that consists of the suffixLen characters immediately preceding the final character of key.

Use the following steps to derive a CASL shard:

Let key be the result of running the steps to derive a CASL key.
Let shard be the result of running the steps to compute a next-to-last shard with suffixLen set to 2.
Return shard.

NOTE: The next-to-last/2 rule matches the FlatFS default sharding function used in Kubo’s FlatFS block storage (as defined by the FlatFS implementation’s default shard constant).
Path Construction

A CASL path is constructed from a storage root, a shard, and a leaf name.

Use the following steps to construct a CASL path:

Accept a string root and a CID cid.
Let key be the result of running the steps to derive a CASL key on cid.
Let shard be the result of running the steps to derive a CASL shard on key.
Let name be key. Implementations MAY append a deterministic, store-wide extension (for example, .data), but if they do, it MUST be applied consistently for all objects in that store.
Return the concatenation: <root>/<shard>/<name>.

Example

Given CID: bafkreifn5yxi7nkftsn46b6x26grda57ict7md2xuvfbsgkiahe2e7vnq4

The CASL key (base32 of the multihash bytes, uppercase, no padding) is: CIQK33ROR62ULHE3Z4D5PV4NCGB36QFH6YHVPJKKDEMUQAOJUJ7K3BY
The CASL shard (next-to-last/2) is: 3B
The CASL path (for some chosen root) is: <root>/3B/CIQK33ROR62ULHE3Z4D5PV4NCGB36QFH6YHVPJKKDEMUQAOJUJ7K3BY

[darobin]

Thanks! I've flagged this up for discussion at the next DASLing Group. If you're able to attend to explain your thinking, that would be great, but if not we'll do our best.

[johnbenac]

Thanks! I've flagged this up for discussion at the next DASLing Group. If you're able to attend to explain your thinking, that would be great, but if not we'll do our best.

It's on my calendar!

[darobin]

Some notes:

• I understand why using the end of the CID for the shard key is good, but I don't understand the next-to-last choice.
• I think it may be good to define two strategies: Kubo and DASL. This can include a small heuristic to detect the difference (just look for uppercase letters). My thinking there is that if I'm in a DASL universe I don't really want to have to decode and re-encode CIDs for every lookup. Being Kubo-compatible is good for that case, but it's a big cost to impose for a thing that could be used in systems that have never seen Kubo.
• Please drop the RFC 2119 boilerplate.
• Small thing, but it'll need to pick a colour in the DASL set and probably an emoji (🏰?)

[johnbenac]

The next to last has to do with the encoding of the characters with CID. The last character has less entropy than the other characters. like, there are just more possibilities for what any other character other than the last character could be. And I'm not talking about how lots of files end with the newline character (although many do). And lots of files start the same way, with a header, for example, so using the first character would also skew the distribution toward some characters more than others. The next to last character is a simple rule that pretty much ensure that the sharding distribution happens equally across all possible characters.

I think the biggest difference with how Kubo does sharding and CIDs is the case sensitivity. So I think a better question than "complicated verses simple" is "case sensitive verses case insensitive" With CIDs, we want to have shorter CID (shorter URLs), and case sensitivity is ok. With sharding files, I think its ok to have longer filenames, and some file systems really dont want to fuss with case sensitivity. If this standard can be used with multiple languages and file systems, I would think that we err on the side of interoperability, even if it takes a bit of compute to go back and forth between CIDs and these keys.

My vote is that case sensitivity is a bad thing.

I agree to drop the RFC 2119 boilerplate. And the 🏰 works great! Where do the colors get used?

[darobin]

Next to last: ah, that makes a lot of sense, thanks.

For casing, I think the problem is more about performance than anything else.

[johnbenac]

Thanks for the feedback during the DASLing Group today! I'll look closer at using the CID directly, rather than a CASL key, and hopefully by next month I'll have it implemented and demonstrated on OurBox. (https://github.com/techofourown/sw-ourbox-os). If I can make it work with the CID, then I will!

I dont want to take up more of the group's valuable time than necessary, although I do want to act on some of the points brought up, namely, simplifying and using the CID, rather than a CASL key (however aligned a CASL key might be with Kubo).

I have more information about my particular implementation plan for CASL in my system, which includes aspects that are not generally applicable to a DASL standard, but which could provide insight into why the CASL standard is they way that it is.

With regard to partial file transfers, and streaming, this document describes the deliberate limitation of OurBox for streaming

"Negative

No piecewise resume/progress: failed transfers may restart from the beginning rather than resuming mid-stream.
No partial/intra-file dedupe: two similar large files do not share storage unless their full bytes match.
Not an IPFS “file CID” model: because we are not using Merkle DAG/UnixFS representations, these CIDs should not be assumed to match the CIDs produced by IPFS “add file” workflows.

"

So OurBox does not attempt to stream, and the standard that I am proposing does not attempt to stream or chunk, but the standard does not preclude chunking.

Lets consider the difference between sharding and chunking.

Sharding is all about where to place things. Chunking is all about how to break things up.

CASL is all about sharding. It doesnt preclude chunking. It just says, if you are going to break up blobs, that is outside of the scope of where to shard the blob chunks.

I can imaging a different DASL standard, someday (probably not submitted by me, or associated with OurBox) that deals with chunking, and streaming.

CASL, as with all (or most?) of the DASL standards, should not be about integrated system functioning, rather, it should be about little bite sized chunks. ahem pieces, not chunks.

Please remind me if there were any other feedback that I should consider in the meantime.

In the meantime, I'm happy to be a pathfinder for whatever new "process" we are going to follow for implementing new DASL standards, like Robin mentioned he could create.

[bumblefudge]

Discussed a little on an internal call. Some thoughts:

• It's odd that there isn't already an IPIP for Kubo's internal usage of flatfs? Some non-UnixFS implementations (like DASL/ATP) might want this specified and testable for, e.g., sharding/querying giant distributed k/v stores. As Robin mentioned above, I can see DASL usage and IPFS usage diverging a bit, some maybe there's two flavors or two profiles, idunno. Either way tho, IPFS specs live in IPIP and it kinda makes sense to me that you could just add a "doing this in a DASL context without the extra CID work" section to the longer IPIP version instead of having two distinct specs
  • curiously, the only appearance of the term flatfs in ipfs/specs is this issue from 2015!
  • by "testable" i mean, pretty please throw in some test vectors? once they're there, it's trivial to confirm that this is sharding the same way kubo does internally, if that's a valuable cross-test to run.
  • if it were an IPIP, rather than being another **SL spec, it could just be an example in MASL of a kind of metadata that links to the IPIP...

[vmx]

• you could just add a "doing this in a DASL context without the extra CID work"

There won't be much overlap. It would be a different spec (I can expand on that if anyone wants details).

There are always trade-offs and I don't think there's a single best way of doing it. Hence I lean towards making a descriptive specification of IPFS FlatFS, which describes the about the current behaviour. This adds value to IPFS and can also be used outside of it as in @johnbenac use case. I don't think it's worth thinking about optimizations that a theoretic ATProto use case might benefit of.

I really believe in re-using things that already work, even if it might only matches 90% compared to a green field version for your use case.

Given the ties to IPFS FlatFS I think it makes sense to specifying it as an IPIP. I would then suggest having some "related specs that might be of interest" section on the DASL site that links to it.

[vmx]

• you could just add a "doing this in a DASL context without the extra CID work"

There won't be much overlap. It would be a different spec (I can expand on that if anyone wants details).

I slept on it, and of course you can do it. In case of DASL CIDs, you know that the CID has a 2 byte prefix. You can directly work on the base32 encoded string and do some bit shifts. Without going through the full decoding and encoding. So that case is also covered.

[bumblefudge]

(the post-sleep clarity describes what Robin said on the call better than my hasty summary, so I think you independently arriving at the same conclusion is a good validation! i should hastily mis-summarize robin more often.)

[johnbenac]

This is the simplified version that just uses the CID, rather than a "CASL Key"

---

CASL

CASL defines a deterministic mapping from a CID to a sharded storage path.

CASL answers only one question: where does this CID live in the store? It does not define chunking, DAG layout, replication, or transport.

Terminology

storage root
An implementation-defined directory or object-store prefix under which CASL paths are constructed.

shard
A short string used as a directory or prefix component to distribute objects across buckets.

Using the CID directly

CASL uses the CID itself for both sharding and the leaf name.

For deterministic interoperability, CASL is defined over the canonical CID string form: CIDv1 rendered in lowercase base32 with no padding. If an implementation receives the CID in bytes form or in some other textual form, it first converts it to that CID string and stores the result in cid.

Sharding

CASL’s default sharding rule is next-to-last/2: it takes the two characters immediately preceding the last character of the CID string.

To compute a next-to-last shard:

1. Accept a string cid and an integer suffixLen.
2. If suffixLen is less than 1, throw an error.
3. If the length of cid is less than suffixLen + 1, prepend "_" characters to cid until its length is suffixLen + 1.
4. Return the substring of cid consisting of the suffixLen characters immediately preceding the final character of cid.

To derive the default CASL shard, compute a next-to-last shard with suffixLen set to 2.

Path construction

A CASL path is constructed from a storage root, a shard, and a leaf name.

To construct a CASL path:

1. Accept a string root and a CID cidInput.
2. Convert cidInput to the canonical CID string form and store the result in cid.
3. Let shard be the result of computing a next-to-last shard on cid with suffixLen set to 2.
4. Let name be cid. An implementation may append a deterministic, store-wide extension such as ".data", but it must do so consistently for all objects in that store.
5. Return the concatenation: //.

Example

Given CID:
bafkreifn5yxi7nkftsn46b6x26grda57ict7md2xuvfbsgkiahe2e7vnq4

The CASL shard is:
nq

The CASL path is:
/nq/bafkreifn5yxi7nkftsn46b6x26grda57ict7md2xuvfbsgkiahe2e7vnq4

---

It's pretty short!