More transparent directory structure in local environments and index

[tilowiklundSensmetry]

The current structure used in both sysand_env and for remote HTTP indices is the following

/entries.txt
/<hash-of-IRI_1>/versions.txt
/<hash-of-IRI_1>/<version_1>.kar
/<hash-of-IRI_1>/<version_2>.kar
...
/<hash-of-IRI_2>/versions.txt
/<hash-of-IRI_2>/<version_1>.kar
...

Where entries.txt contains verbatim (as UTF-8 strings) entries IRI_1, IRI_2, ... and directories are hex-encoded SHA256-hashes of these IRIs considered as UTF-8 byte arrays.

While straightforwardly safe, this representation has a number of usability issues:

1. the structure is difficult for humans to navigate in, for example, a graphical file browser or command line shell),
2. when opening or seeing a file path or URL it is difficult to tell what usage the corresponding file or archive corresponds to

We would like to have a mapping that alleviates the above issues at least for the most typical use cases:

1. projects identified by "name", using urn:kpar:<name> IRIs
2. projects identified by direct resolvable HTTP(S) URLs

[tilowiklundSensmetry]

Related to #6 it would be nice if urn:kpar:<name> IRIs could map as closely as possible to just <name>. For users relying mostly on standard index infrastructure and referring to projects by name this would lead to a structure similar to that used by, for example, python virtual environments.

[tilowiklundSensmetry]

One proposal would be to have separate top level directories for different IRI schemes, and then use scheme-specific (statistically injective) mapping for each scheme. In particular, it would allow us to have: urn:kpar:<FullName> maps to by_full_name/FullName.

For someone following our proposed conventions (using only simple names and referring to usages only by urn:kpar:-IRIs) this would then simply look like

• env/by_full_name/name1
• env/by_full_name/name2
• ...

[tilowiklundSensmetry]

Another proposal, compatible with the above, is to replace long_hash(name) by either ascii_version(name)<separator>short_hash(name) or ascii_version(name)/short_hash(name). In particular short_hash can be chosen such that it is an empty string for ascii strings.

[tilowiklundSensmetry]

There's also a request to flatten package/[versions.txt|version.kpar] into something like package-version.kpar|package-versions.txt.

[andrius-puksta-sensmetry]

Proposal for human-readable package IDs and package registry format

Local environments and registry

Use different structures for local package environment and package registry. Motivation:

• in local env, it is useful to have semantically meaningful names
• in registry, it matters much less (see Unresolved problems for considerations)
• in local env, there will not be many packages, and most packages will have one version only
• in registry, there will (or at least much more likely to) be many packages with many versions

Local environment

Package IDs

Package IDs are human-readable names in the common cases and hashes in all others. sysand should warn when creating a package whose name will be ugly.

We must be mindful of the filename length limits, which on (older) Windows is around 260 bytes.

IRIs are kind of case sensitive. Case sensitivity of various parts depends on the exact scheme used. If IRI is also an URI, then the everything up to the host part is case insensitive, e.g. http://example.invalid is case insensitive, but any components after this are case sensitive (this depends on the scheme; for HTTP, everything after host is case sensitive, but for other schemes it might not be). A total nightmare, unless we implement case normalization for at least the common schemes (http[s], [s]ftp[s] and kpar).

Therefore, we have to be even more restrictive about which IRIs can be used for paths, this is critical for case insensitive filesystems.

This is also not ideal from user perspective, because to add a project from CLI they have to specify the exact name using the same casing as the actual package name, or otherwise the names/hashes will not match.

Package ID is determined as follows:

1. If the package IRI in UTF-8 is longer than 100 bytes or contains upper case or non-ASCII characters, package ID is a hash of the IRI (see below for exact hashing steps).
2. If the package IRI is of the format urn:kpar:<name>, where <name> is an ASCII-only string, then the package ID is percent-encoded <name>, with exactly the following characters percent-encoded: <>:"/\|?*%, in addition to ASCII codes 0-31 (non-printable characters). This preserves compatibility with at least the common filesystems on Windows, Linux and macOS.
3. If the package IRI is of any other format, package ID is percent-encoded IRI (same encoding as in 2.)

Directory structure

/package_ID_1-version_1.kpar
/package_ID_2-version_1.kpar
...

Package registry structure

Package registry always uses hash of the complete IRI as the package ID. To reduce the number of directories in server root, root contains directories named after three letter prefixes of package IDs. Those directories contain all the packages with the same ID prefix. Using hashes for IDs helps here, as it ensures a random distribution of packages between the directories. This gives 16^3 = 4096 possible top level directories.

/packages.txt # lists the complete package IDs
/prefix_1/package_ID_1/versions.txt
/prefix_1/package_ID_1/version_1.kpar
/prefix_1/package_ID_1/version_2.kpar
...
/prefix_1/package_ID_2/versions.txt
/prefix_1/package_ID_2/version_1.kpar
/prefix_1/package_ID_2/version_2.kpar
...
/prefix_2/package_ID_3/versions.txt
/prefix_2/package_ID_3/version_1.kpar
/prefix_2/package_ID_3/version_2.kpar

Unresolved problems:

• Registry website has terrible URLs for packages. This is relevant for humans visiting the website, link sharing, etc. This can be solved by having a server in front of the index that does the mapping.
• Very long names. Maybe truncate the hash to 128 bits and use that as a name?
• Package search (esp. fuzzy search) from client side. Maybe have a file with package IRIs or list IRIs instead of hashes in packages.txt?
• Additional package metadata (index) has to be stored somewhere. A possible solution is to use a git repo or something similar for that. Then the registry would consist of both the file server and the metadata repo. Index repo could also be used for package search from client side. If using a separate index packages.txt could be removed.

When sysand wants to retrieve a package, it asks for the package file directly, including the prefix directory. This allows the registry to be a "dumb" server. packages.txt is only for getting all available packages in the registry and should not be retrieved for normal sysand operation.

Hashing package IRIs

blake3-256 is chosen as the name hash function. It's a cryptographic hash function (can't think of a reason why we would need it, but it doesn't hurt) that is very fast. In the future, it could also potentially be used for detecting file changes. Hashes of IRIs are produced as follows:

• treat IRI as UTF-8 bytes
• hash the resulting byte array with blake3-256
• base16-encode the hash value

[andrius-puksta-sensmetry]

The proposed design sadly removes the ability to expose sysand_env as a registry, as in #75.

[andrius-puksta-sensmetry]

The proposal makes the assumption that number of packages in a registry can reach tens of thousands, which would create problems on certain filesystems if all packages are in server root.

[andrius-puksta-sensmetry]

Proposal 2

Desirable properties of local index:

• can act as a package registry
• human readable package names
• flat directory structure
• can contain many thousands of packages

References

• Package IDs here refer to local environment package IDs from previous proposal.
• IRI hashing is also taken from previous proposal.
• prefix means the same 3 letter hash prefix

Package index structure

Use the same structure for local and remote package indices. The structure is as follows:

/packages.txt
/prefix_1/package_ID_1-versions.txt
/prefix_1/package_ID_1-version_1.kpar
/prefix_1/package_ID_1-version_2.kpar
...
/prefix_1/package_ID_2-versions.txt
/prefix_1/package_ID_2-version_1.kpar
/prefix_1/package_ID_2-version_2.kpar
...
/prefix_2/package_ID_3-versions.txt
/prefix_2/package_ID_3-version_1.kpar
/prefix_2/package_ID_3-version_2.kpar

packages.txt contains percent-encoded IRIs of all packages, one per line. Percent-encoding is needed due to possibility of newlines in IRIs.

Problems

• Packages may have many versions. This means many files in the same hash-prefix directory. A separate directory for each package could be used instead to resolve this. The path length would remain the same.

[tilowiklundSensmetry]

I think it's perfectly fine to not solve the problem of having too many projects in the root. As you say, it is unlikely to happen in a local environment, and servers that implement access over HTTP for such very large indices can have their own specialised rewrite rules (separating how things are accessed on HTTP from how they are actually stored on disk or object storage).

This way it's still possible to just naively expose an environment over HTTP, assuming it is not huge.

[andrius-puksta-sensmetry]

Proposal 3

Same as proposal 2, but the structure is:

/packages.txt
/package_ID_1/versions.txt
/package_ID_1/version_1.kpar
/package_ID_1/version_2.kpar
...
/package_ID_2/versions.txt
/package_ID_2/version_1.kpar
/package_ID_2/version_2.kpar
...
/package_ID_3/versions.txt
/package_ID_3/version_1.kpar
/package_ID_3/version_2.kpar

Each package has its own directory to avoid having multiple files with almost the same name.

EDIT: after discussion with Tilo, this is the proposed package_ID format:

1. If the package IRI in UTF-8 is longer than 100 bytes or contains upper case ASCII characters or non-ASCII characters, package ID is a hash of the IRI with 0x_ prepended to the hash (see below for exact hashing steps).
2. If the package IRI is of the format urn:something:<name>, where <name> is an ASCII-only string, then the package ID is urn_something_<name_pc>, where <name_pc> is <name>, with the following characters percent-encoded: <>:"/\|?*%, in addition to ASCII codes 0-31 (non-printable characters). This preserves compatibility with at least the common filesystems on Windows, Linux and macOS.
3. If the package IRI is of any other format scheme:<something>, package ID is scheme_<something_pc>, where <something_pc> is percent-encoded <something> (same encoding as in 2.)

EDIT 2: kpar_ will not be used as a prefix shorthand for urn:kpar:, because it is technically possible to use kpar: directly as IRI scheme, and these two usages would generate the same package IDs. Therefore, I propose to use a shorthand scheme for any urn:something: IRI: urn_something_ instead of urn_something%XY (: is percent-encoded in case of generic IRIs). Therefore, use urn_kpar_ to refer to urn:kpar:, same as any other URN scheme. This still means that in the common case we get nice names without percent-encoding any non-user-controllable parts of it, e.g. urn_kpar_pkg1 instead of urn_kpar%XYpkg1, which is ugly.
Also, use SHA-256 as a hash function for IRIs.

[andrius-puksta-sensmetry]

Still not sure what to do about client side package search. Maybe ignore this for now, we can always add it later by including a file like metadata.toml, which contains metadata of all packages, in index root.

[tilowiklundSensmetry]

Still not sure what to do about client side package search. Maybe ignore this for now, we can always add it later by including a file like metadata.toml, which contains metadata of all packages, in index root.

Yea, don't worry about search, we'll treat that as a separate proposal. There's nothing stopping a client from fetching a whole repository skeleton should they really want to.