NESTS - Named Entities in Simple Tiered Spaces

Some practical limitations imposed by the technology

NB: This is a temporary working document under continual revision as coding progresses. The documents and the initial implementation are co-evolving continually, so expect to find some duplications and occasional inconsistencies (all of which will be removed over time). (See page footer for most recent revision.)

Building an OM-compliant solution upon the provisions already made available in Unix-like systems does bring limitations. How important these are depends upon how and where the solution is deployed.

Implications of operating systems limitations

A deployment of NESTS to support OM services may be easiest using either a dedicated virtual machine or a container. This opens up the choice of OS.

Although most Unix-like systems may be suitable, at this time only four stand out as obvious choices - mostly for reasons of maturity, stability, familiarity and portability. Despite their commonalities, each brings its own advantages and limitations.

These operating systems follow Unix conventions and allow any 8-bit characters other than '/' or NUL to be used.

However, since the intention is to allow for the use of any UTF-8 character set at the user interface, a simple and obvious solution is to map the human-readable names to internal filenames using a hash function. Therefore in practice the names internally will appear as hex strings. The limitations on the allowed filename length will therefore help to determine the choice of hash algorithm. As the length of the hash output decreases, the risk of a collision increases - but that problem can be addressed by other means.


Table 1: Limits imposed by different filesystems ext4 [1] FFS [2] ZFS [3]
Username maximum length 32 [1] 31 [2] 16 [4]
Filename maximum length 255 bytes (255 ASCI characters [5])
Maximum number of UID or GID 2 x 109 (probably) [6]
Maximum number of supplementary GID to which a UID can belong 64K [7] 16 [7] unknown [8]
Minimum block size 1024 [10] 4096 ? [11] unknown
Maxumum number of inodes 232 ? [11] unknown
Minimum inode size 256 [10] ? [11] unknown
Notes
  1. Linux

  2. OpenBSD

  3. FreeBSD, Linux, NetBSD, Solaris (and derivatives)

  4. The FreeBSD default maximum username length is 16 characters but the kernel can be recompiled to support up to 128.
    https://www.freebsd.org/doc/handbook/users-synopsis.html recommends a maximum of 8 characters.
    (See also https://www.freebsd.org/cgi/man.cgi?query=passwd)

  5. Fewer where multi-byte characters are allowed.

  6. This may be ~ 4 x 109 given that UID and GID are represented as 32-bit unsigned values.

  7. See https://www.j3e.de/ngroups.html

  8. Assumed to be at least as large as that of ext4 and far greater than any requirements NESTS might have.

  9. https://en.wikipedia.org/wiki/Comparison_of_file_systems

  10. Assuming ext4, see man mkfs.ext4 for details.
    Valid block sizes are 1024, 2048 or 4096 bytes.
    The minimum inode size is 128 bytes (default is 256 bytes).
    The maximum number of inodes is ∼ 4.295×109 (ext4).
    The number of bytes per inode should not be less than the block size.

  11. See https://man.openbsd.org/inode.5 and https://man.openbsd.org/newfs.8.

  12. See https://nixdoc.net/man-pages/FreeBSD/newfs.8.html.

With portability in mind, Table 1 suggests the following:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.


Notes

  1. William Stallings, "Cryptography and Network Security" 4e, 2006, Pearson Prentice Hall
    https://en.wikipedia.org/wiki/List_of_hash_functions
    https://en.wikipedia.org/wiki/Hash_function
  2. Two benchmark tables (1 and 2) comparing the read and write speed of several associative array libraries for managing key:value pairs both suggest TinyCDB to be the fastest option among those compared.
    https://en.wikipedia.org/wiki/Cdb_(software)
    http://www.corpit.ru/mjt/tinycdb.html
    https://www.matrixscience.com/msparser/help/tools_tinycdb_8py-example.html
    http://cr.yp.to/cdb.html

Version 0.4a - 2024-09-12 22:20 - Copyright © 2024, 2023, 2022 John Waters


home