HashedPath.php

<?php
/*
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */
/**
 * Italix Storage - HashedPath
 *
 * @package Italix\Storage
 */

declare(strict_types=1);

namespace Italix\Storage;

/**
 * `{folder}/{ab}/{cd}/{sha256}.{ext}` — the default.
 *
 * ## Choosing the depth
 *
 * Measured on ext4 with `dir_index`: looking a *known path* up degrades only
 * ~2.3x between 100 and 100,000 entries in one directory — the htree does its
 * job. What collapses is **listing**, from 0.2 ms to 375 ms across the same
 * range, roughly 1,800x. Listing is what backups, `rsync`, `du`, deletion
 * sweeps and every `glob()` do, so that is the number the depth is chosen
 * against, not read speed.
 *
 * | depth | directories | at 1M files | at 16M files |
 * |-------|-------------|-------------|--------------|
 * | 0     | 1           | 1,000,000   | 16,000,000   |
 * | 1     | 256         | 3,906 each  | 62,500 each  |
 * | **2** | **65,536**  | **15 each** | **244 each** |
 * | 3     | 16,777,216  | 0.06 each   | 1 each       |
 *
 * Depth 3 is the tempting mistake: an empty directory costs 4 KB and an inode,
 * so 16.7M of them is ~67 GB of metadata before any content, to hold about one
 * file each. It trades a directory that is too full for a tree that is too wide.
 *
 * **The depth must be sized against files per _folder_, not files in total.**
 * Under a per-tenant prefix, a tenant with a thousand documents at depth 2 gets
 * roughly one directory per file. That is the case depth 0 and 1 exist for, and
 * why 1.x refusing depth 0 was wrong.
 */
final class HashedPath implements PathStrategy
{
    public const DEFAULT_DEPTH_N = 2;

    private int $depth_n;

    /**
     * @param int $depth_n levels of two-hex-character directory, 0-4
     */
    public function __construct(int $depth_n = self::DEFAULT_DEPTH_N)
    {
        if ($depth_n < 0 || $depth_n > 4) {
            throw new StorageException(
                "A shard depth of {$depth_n} is outside 0-4. Depth 2 suits one large corpus, "
                . '0 or 1 suits a per-tenant prefix; see the class docblock for the measurements.'
            );
        }

        $this->depth_n = $depth_n;
    }

    public function path_for(string $folder, string $sha256_c, string $extension_c): string
    {
        $shards = '';

        for ($level = 0; $level < $this->depth_n; $level++) {
            $shards .= substr($sha256_c, $level * 2, 2) . '/';
        }

        return ($folder === '' ? '' : $folder . '/') . $shards . $sha256_c . '.' . $extension_c;
    }

    public function depth_n(): int
    {
        return $this->depth_n;
    }

    public function describe(): string
    {
        $shards = str_repeat('{xx}/', $this->depth_n);

        return "{folder}/{$shards}{sha256}.{ext} (depth {$this->depth_n}, "
            . number_format(256 ** $this->depth_n) . ' leaves)';
    }
}