Dirhash

Last updated

Dirhash is a feature of FreeBSD that improves the speed of finding files in a directory. Rather than finding a file in a directory using a linear search algorithm, FreeBSD uses a hash table. [1] [2] The feature is backwards-compatible because the hash table is built in memory when the directory is accessed, and it does not affect the on-disk format of the filesystem, in contrast to systems such as Htree. Free space for new entries is also tracked in-memory, allowing addition of new entries without having to scan the directory.

Dirhash was implemented by Ian Dowse early in 2001 as an addition to UFS, operating in parallel with higher-level file system caching. It was imported into FreeBSD in July 2001. [3] It was subsequently imported into OpenBSD in December 2003 and NetBSD in January 2005.

Related Research Articles

ext2, or second extended file system, is a file system for the Linux kernel. It was initially designed by French software developer Rémy Card as a replacement for the extended file system (ext). Having been designed according to the same principles as the Berkeley Fast File System from BSD, it was the first commercial-grade filesystem for Linux.

In computer security, an access-control list (ACL) is a list of permissions associated with a system resource. An ACL specifies which users or system processes are granted access to resources, as well as what operations are allowed on given resources. Each entry in a typical ACL specifies a subject and an operation. For instance,

The Unix file system (UFS) is a family of file systems supported by many Unix and Unix-like operating systems. It is a distant descendant of the original filesystem used by Version 7 Unix.

<span class="mw-page-title-main">Defragmentation</span> Rearrangement of sectors on a hard disk into contiguous units

In the maintenance of file systems, defragmentation is a process that reduces the degree of fragmentation. It does this by physically organizing the contents of the mass storage device used to store files into the smallest number of contiguous regions. It also attempts to create larger regions of free space using compaction to impede the return of fragmentation. Some defragmentation utilities try to keep smaller files within a single directory together, as they are often accessed in sequence.

tmpfs is a temporary file storage paradigm implemented in many Unix-like operating systems. It is intended to appear as a mounted file system, but data is stored in volatile memory instead of a persistent storage device. A similar construction is a RAM disk, which appears as a virtual disk drive and hosts a disk file system.

<span class="mw-page-title-main">File system</span> Computer filing system

In computing, a file system or filesystem governs file organization and access. A local file system is a capability of an operating system that services the applications running on the same computer. A distributed file system is a protocol that provides file access between networked computers.

Filesystem in Userspace (FUSE) is a software interface for Unix and Unix-like computer operating systems that lets non-privileged users create their own file systems without editing kernel code. This is achieved by running file system code in user space while the FUSE module provides only a bridge to the actual kernel interfaces.

The proc filesystem (procfs) is a special filesystem in Unix-like operating systems that presents information about processes and other system information in a hierarchical file-like structure, providing a more convenient and standardized method for dynamically accessing process data held in the kernel than traditional tracing methods or direct access to kernel memory. Typically, it is mapped to a mount point named /proc at boot time. The proc file system acts as an interface to internal data structures about running processes in the kernel. In Linux, it can also be used to obtain information about the kernel and to change certain kernel parameters at runtime (sysctl).

Extended file attributes are file system features that enable users to associate computer files with metadata not interpreted by the filesystem, whereas regular attributes have a purpose strictly defined by the filesystem. Unlike forks, which can usually be as large as the maximum file size, extended attributes are usually limited in size to a value significantly smaller than the maximum file size. Typical uses include storing the author of a document, the character encoding of a plain-text document, or a checksum, cryptographic hash or digital certificate, and discretionary access control information.

The following tables compare general and technical information for a number of file systems.

Extendible hashing is a type of hash system which treats a hash as a bit string and uses a trie for bucket lookup. Because of the hierarchical nature of the system, re-hashing is an incremental operation. This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes.

Btrfs is a computer storage format that combines a file system based on the copy-on-write (COW) principle with a logical volume manager, developed together. It was founded by Chris Mason in 2007 for use in Linux, and since November 2013, the file system's on-disk format has been declared stable in the Linux kernel.

The Orlov block allocator is an algorithm to define where a particular file will reside on a given file system (blockwise), so as to speed up disk operations.

Toybox is a free and open-source software implementation of over 200 Unix command line utilities such as ls, cp, and mv. The Toybox project was started in 2006, and became a 0BSD licensed BusyBox alternative. Toybox is used for most of Android's command-line tools in all currently supported Android versions, and is also used to build Android on Linux and macOS. All of the tools are tested on Linux, and many of them also work on BSD and macOS.

<span class="mw-page-title-main">Unix filesystem</span> Directory structure used by a Unix-like operating system

In Unix and operating systems inspired by it, the file system is considered a central component of the operating system. It was also one of the first parts of the system to be designed and implemented by Ken Thompson in the first experimental version of Unix, dated 1969.

The Advanced Disc Filing System (ADFS) is a computing file system unique to the Acorn computer range and RISC OS-based successors. Initially based on the rare Acorn Winchester Filing System, it was renamed to the Advanced Disc Filing System when support for floppy discs was added and on later 32-bit systems a variant of a PC-style floppy controller.

F2FS is a flash file system initially developed by Samsung Electronics for the Linux kernel.

Shardmap is a directory index design by Daniel Phillips who created the HTree and PHTree tree data structures and the Tux3 file system.

HAMMER2 is a successor to the HAMMER filesystem, redesigned from the ground up to support enhanced clustering. HAMMER2 supports online and batched deduplication, snapshots, directory entry indexing, multiple mountable filesystem roots, mountable snapshots, a low memory footprint, compression, encryption, zero-detection, data and metadata checksumming, and synchronization to other filesystems or nodes. It lacks support for extended file attributes (xattr).

References

  1. Recent Filesystem Optimisations in FreeBSD, by Ian Dowse and David Malone
  2. Recent Filesystem Optimisations in FreeBSD, by Ian Dowse and David Malone, 2002 FREENIX Track Technical Program
  3. Commit message for dirhash