-
Name hashing and FPH hashing
The hash function to map human-readable UTF-8 names to strings of 7 or 8
bit (1 byte) characters should probably produce a hash of no more than
128 bits if FreeBSD is to remain included without the need to recompile
the kernel.
In any case, OpenBSD will restrict the maximum hash length to 248 bits.
After comparing a few options, the xxHash fast non-cryptographic hash
algorithm (https://cyan4973.github.io/xxHash/) was chosen, being able to
produce hash strings from 32 to 128 bits in length.
Collisions are unavoidable (in theory) but detectable. In any case, they
may be sufficiently rare to justify requiring user intervention (i.e.
choosing a different name) in the event of detection, in which case use
of a 64-bit hash may be acceptable.
Assuming the hash function has a very regular distribution, the
probability of one or more collisions among k hashes is approximately
$$
P \approx 1 - e^{\frac{-k(k-1)}{2N}}
$$
where N is the hash length (see
birthday
problem).
However, there is little if any overhead (other than in the storage space
required) in using 128-bit hashes and their use makes the risk of hash
collision almost negligible.
The hash function used to map human-readable entity names to their
corresponding internal directory names (in the FIP), and from the
FIP to the FPH, was changed recently from xxhash64 to
xxh3_128. This decreased the already miniscule probability of
collision (by an enormous value) with no appreciable loss of speed.
However, this doubled the length of the internal directory names and that
of the FPH (neither of which is in any way a problem).
The xxh_64, xxh3_64 and xxh3_128 versions were
compared crudely using the
xxhash_tests.py
script and no appreciable loss of performance was observed. In fact, the
128-bit version appears to run very slightly faster.
-
Inverse mapping: name hash to entity name
For each mapping:
name → hash
an inverse mapping:
hash → name
will be needed at times.
The simple solution chosen is to maintain a copy of the human-readable
name (UTF-8) within the entity directory.
-
FPH>FIP mapping
Each human-readable name(space) string corresponds directly to
a directory path (FIP - the Full Internal Path, a string of
32-character character name hashes. It is enormously more convenient to
represent each entity by a fixed length string, so the same
128-bit hash function is used to map each FIP to a corresponding (and
effectively unique) FPH (its Full Path Hash). The inverse
mapping (FPH>FIP) is achieved using a fast associative array.
Originally, CDB2 was used, but this has now
been replaced by the traditional Unix DBM which was found to be almost as
fast for reading and enormously more convenient for both writing and
deletion.
-
Unix user accounts
The option to assign each user a Unix account and a private
directory under /home/ remains valid. However, this is most likely to be
of use for open measure applications and for users running
commands over SSH.
This may be a convenient location in which to hold the SSH public key for
the user (if needed), although that is more likely to be kept in
a primid's .properties file (JSON).
maximum number of users
Where such an approach is used, limitations on the number of GID
associated with an UID eliminate the option to assign one GID to each
namespace. Fortunately that is not a decisive problem.
-
storage requirements
The NESTS tree contain a large number of (mostly) very small files, so it
might be best to have this on a dedicated partition containing a
filesystem with the smallest possible block size.
For an ext4 filestem this could be:
block size: 1024 bytes
inode size: 128 bytes
bytes per inode: 1024
total size of partition: 4.398×1012 (∼ 4.4Tb)
For BSD systems the situation is less straightforward, and a larger
partition size may be necessary even if the number of inodes can be
matched. this seems unlikely to be present problem.
For open measures applications (in contrast to open
money) a much higher capacity may be needed. ZFS may be an option
but limits the choice of OS.