hash-cache

Caches of data by its hash: in memory, in a folder of a file system, and in tiers of both. The caches do not depend on a hash function: they take one, and check what they return against it.

Note: this project is mostly AI coded. Its code, tests and documentation were largely written by an AI assistant, and reviewed and directed by a human maintainer.

npm install @k13engineering/hash-cache

Example

import {
  createFileSystemHashCache,
  createNodeHashCacheFileSystem,
  createRamHashCache,
  createSystemTimers,
  createTieredHashCache,
  type THash
} from "@k13engineering/hash-cache";

const sha256: THash = {
  name: "sha256",
  digest: async ({ data }) => {
    const digest = new Uint8Array(await crypto.subtle.digest("SHA-256", data));
    return [...digest].map((byte) => byte.toString(16).padStart(2, "0")).join("");
  }
};

const limits = { maxSize: 256 * 1024 * 1024, maxCount: 100_000, maxPendingSize: 16 * 1024 * 1024 };

const disk = await createFileSystemHashCache({
  hash: sha256,
  fileSystem: createNodeHashCacheFileSystem({ root: "/var/cache/my-app" }),
  timers: createSystemTimers(),
  ...limits
});
const ram = createRamHashCache({ hash: sha256, ...limits, maxSize: 32 * 1024 * 1024 });
const cache = createTieredHashCache({ hash: sha256, tiers: [ram, disk], maxPendingSize: limits.maxPendingSize });

cache.store({ data });                       // a hint: returns right away, and may be dropped
const { error, hit } = await cache.lookup({ hash });
// error: e.g. an I/O error; hit: undefined, or { data } that hashes to hash

await disk.close();                          // waits for the writes still running

examples/tiered-cache.ts runs this in a temporary folder: node examples/tiered-cache.ts.

The interface

type THash = {
  name: string;
  digest: (args: { data: Uint8Array }) => Promise<string>;
};

type THashCache = {
  lookup: (args: { hash: string }) => Promise<TLookupResult>;
  store: (args: { data: Uint8Array }) => void;
  put: (args: { hash: string, data: Uint8Array }) => void;
  evict: (args: { hash: string }) => void;
};

type TLookupResult = { error: Error, hit: undefined } | { error: undefined, hit: { data: Uint8Array } | undefined };

• Hashes are at least 3 lowercase letters and digits, [0-9a-z], such as hex. Lookups of other hashes fail, and other hashes are never stored. Hashes cannot name paths, so a cache in a file system never leaves its folder.
• What a lookup returns hashes to its hash. A lookup started after a store returns the stored data or nothing; one started after an evict may still return the data.
• store, put and evict are hints. They return right away and may be dropped, e.g. when more than maxPendingSize bytes are still being stored. store computes the hash of the data; put takes a hash the caller knows, and the caller guarantees that the data hashes to it.
• Data is not copied. Data given to a cache, and data it returns, must not be modified.
• Errors are values: a lookup reports I/O errors, failures of the hash function, data that no longer hashes to its hash, and invalid hashes as error. A cache that does not have the data reports neither error nor hit.

Every cache takes maxSize, the most bytes of data it keeps, counting the data only; maxCount, the most entries it keeps; and maxPendingSize, the most bytes of data that are still being stored, beyond which stores are dropped. Beyond its limits, a cache evicts the least recently used entries.

The caches

createRamHashCache({ hash, maxSize, maxCount, maxPendingSize })

A cache in memory. It keeps references to the data it is given and returns them, and it trusts the hashes put gets, so it never hashes on lookup.

createFileSystemHashCache({ hash, fileSystem, timers, maxSize, maxCount, maxPendingSize, scanIntervalMs? })

A cache in a folder, which it opens asynchronously, and which has close(): that waits for the writes still running, after which the cache does nothing and fails lookups.

• The folder must be empty or hold a cache of the same layout and hash: hash-cache.json tells its format, version 1, and the name of the hash. Any other folder is refused, so the cache never works on a folder that is not its own.
• Layout: each entry is a file named by its full hash, in two layers of folders of the first and the second character, e.g. c/0/c08d33….
• Writes go to <hash>.tmp next to the entry, which is then hard linked to the entry. Writers of the same hash write the same bytes, so they can share the file, and an entry never appears unfinished. A write that did not finish, e.g. in a crash, is written over by the next store of the hash.
• Lookups hash what they read: data that does not hash to its hash is removed and reported.
• What the folder holds from before the cache was opened is found by a slow scan in the background, one folder every scanIntervalMs (100 ms by default), with the timers given. It removes the files of writes that did not finish, and leaves files alone that are not entries of the cache. Entries it finds are evicted before those used since opening. Lookups find entries the scan did not reach yet.
• Several caches may use the same folder. Each of them only knows the entries it stored, looked up or found by its scan, so together they can keep more than their limits, and evict an entry another one just stored. Until the scan is through, a single cache can keep more than its limits, too.
• Memory: the cache keeps the hash and size of every entry it knows, about 100 bytes each.

fileSystem is a small interface, with paths relative to the folder of the cache:

type THashCacheFileSystem = {
  readFile: (args: { path: string }) => Promise<Uint8Array>;            // fails with code "ENOENT" for missing files
  overwriteFile: (args: { path: string, data: Uint8Array }) => Promise<void>;
  link: (args: { existingPath: string, newPath: string }) => Promise<void>;   // fails with code "EEXIST" if newPath exists
  unlink: (args: { path: string }) => Promise<void>;
  mkdir: (args: { path: string }) => Promise<void>;
  readdir: (args: { path: string }) => Promise<string[]>;
  stat: (args: { path: string }) => Promise<{ size: number }>;
};

overwriteFile creates the file or writes over it from offset 0 without truncating it first, and then sets its length. createNodeHashCacheFileSystem({ root }) implements it for a folder of the disk with node:fs.

createTieredHashCache({ hash, tiers, maxPendingSize })

Caches in tiers, the fastest first. Lookups ask one tier after another, and put what they find into the faster tiers. A tier that fails does not stop the lookup: its error is only returned if no tier has the data. Stores hash the data once and put it into every tier, and evicts go to every tier. The tiered cache has no close: close the tiers that have one.

createSystemTimers()

The timers of the platform, for the scan of createFileSystemHashCache.

Development

npm ci
npm run build
npm run type-check
npm test
npm run lint

The tests are deterministic: they use a file system in memory, which can fail and hold each operation, and timers that run when a test says so. npm test fails unless the coverage is 100%.

License

LGPL-2.1-only