Wikipedia / Rolling hash
Wikipedia / Rolling hash
A rolling hash (also known as recursive hashing or rolling checksum) is a hash function where the input is hashed in a window that moves through the input.
A few hash functions allow a rolling hash to be computed very quickly—the new hash value is rapidly calculated given only the old hash value, the old value removed from the window, and the new value added to the window—similar to the way a moving average function can be computed much more quickly than other low-pass filters; and similar to the way a Zobrist hash can be rapidly updated from the old hash value.
One of the main applications is the Rabin–Karp string search algorithm, which uses the rolling hash described below. Another popular application is the rsync program, which uses a checksum based on Mark Adler's adler-32 as its rolling hash. Low Bandwidth Network Filesystem (LBFS) uses a Rabin fingerprint as its rolling hash. FastCDC (Fast Content-Defined Chunking) uses a compute-efficient Gear fingerprint as its rolling hash.
At best, rolling hash values are pairwise independent or strongly universal. They cannot be 3-wise independent, for example.
Polynomial rolling hash
The Rabin–Karp string search algorithm is often explained using a rolling hash function that only uses multiplications and additions:
,
are the input characters (but this function is not a Rabin fingerprint, see below).
values, all math is done modulo is typically a prime number. See linear congruential generator for more discussion.
can be chosen to have a multiplicative inverse can be multiplied to get the result of the division without actually performing a division.
Rabin fingerprint
The Rabin fingerprint is another hash, which also interprets the input as a polynomial, but over the Galois field GF(2). Instead of seeing the input as a polynomial of bytes, it is seen as a polynomial of bits, and all arithmetic is done in GF(2) (similarly to CRC-32). The hash is the remainder after the division of that polynomial by an irreducible polynomial over GF(2). It is possible to update a Rabin fingerprint using only the entering and the leaving byte, making it effectively a rolling hash.
Because it shares the same author as the Rabin–Karp string search algorithm, which is often explained with another, simpler rolling hash, and because this simpler rolling hash is also a polynomial, both rolling hashes are often mistaken for each other.
Cyclic polynomial
Hashing by cyclic polynomialsometimes called Buzhashis also simple and it has the benefit of avoiding multiplications, using circular shift instead. It is a form of tabulation hashing: it presumes that there is some substitution function, essentially a lookup table (each of the 32 bit-positions of the values of s be bitwise rotation be the bitwise exclusive or be the window size in use.
for removing the contribution of a byte that is out of the window:
The hash values is defined as the following recurrence relation:
All values of H. This recurrence relation describes the way to compute the hash in a rolling fashion:
Hash is initialized at 0.
.
.
The value of H is a left-shift.
In addition, the authors of borg note that w should not be a multiple of 2L if a seed is used to modify s[] by XORing each value with the seed.
Gear hashing
Gear chunking is another type of tabulation hashing. Let s be an unchanging table of 256 random unsigned 32-bit integers, H be the hash accumulator (unsigned integer, at least 32 bits), and f be the left-shift operator. The recurrence relation is:
Compared to the cyclic polynomial hash, the left-rotate operation is replaced by left-shift, which removes the need to remove the contribution of an out-of-window byte. Xor is also replaced by addition. Chunking is done based on the top bits of H. This type of chunking generates results comparable with the Rabin fingerprint in one-third of the time. However, in practice the distribution of split-sizes were wider than Rabin, making deduplication results about 1% poorer for the typical cases and 6% poor for the worst case.
Using the bottom bits is also acceptable but reduces the effective sliding-window size. The largest effective size appears when the mask samples a number of non-consecutive bits from a relatively wide "span" of H.
Content-based slicing using a rolling hash
One of the interesting use cases of the rolling hash function is that it can create dynamic, content-based chunks of a stream or file. This is especially useful when it is required to send only the changed chunks of a large file over a network: a simple byte addition at the front of the file would normally cause all fixed size windows to become updated, while in reality, only the first "chunk" has been modified.
A simple approach to making dynamic chunks is to calculate a rolling hash, and if the hash value matches an arbitrary pattern (e.g. all zeroes) in the lower N bytes. This approach ensures that unmodified data (more than a window size away from the changes) will have the same boundaries. Once the boundaries are known, the chunks need to be compared by cryptographic hash value to detect changes.
Such content-defined chunking (CDC) or content-based chunking (CBC) is often used for data deduplication. The hash function used can be any rolling-hash algorithm. Some examples are:
Chunking on the least-significant bits
An unweighted sum (rsyncrypto)
Rabin-Karp polynomial rolling hash
Rabin fingerprint, as used in the backup software restic (with blob size varying between and and 64-byte window).
Chunking on any consecutive bits
Cyclic polynomial (buzhash), as used in the backup software Borg. Borg provides a customizable chunk size range for splitting file streams, based on varying the N, by default between and ). It uses a 4095-byte window and non-balanced substitution function.
Chunking on any collection of bits
A gear hash. Gear-based CDC has been successively optimized, yielding FastCDC, RapidCDC, and QuickCDC.
Content-based chunking has the advantage that in most cases, local changes to a file only affects the chunk it is in and possibly the next chunk, but no other chunk. Different choices of algorithms and hashes offer different strengths of this guarantee.
Content-based slicing using moving sum
Several programs, including gzip (with the --rsyncable option) and rsyncrypto, do content-based slicing based on this specific (unweighted) moving sum:
where
of the file,
.
Shifting the window by one byte simply involves adding the new character to the sum and subtracting the oldest character (no longer in the window) from the sum. Because of the properties of modulo arithmetic, the storage required is only 12 bits.
.
FastCDC
FastCDC optimizes Gear-based CDC mainly by adding a "kickstart" loop for bytes before the desired minimal size. By skipping the check for cutting, performance is improved while also adding a feature that allows for controlling the minimum size. The new scheme approximately doubles the speed over the olg Gear-based algorithm and is 10 as fast as the Rabin-based CDC approach.
The basic version pseudocode is provided as follows:
algorithm FastCDC
input: data buffer src,
data length n,
output: cut point i
MinSize ← 2KB // split minimum chunk size is 2 KB
MaxSize ← 64KB // split maximum chunk size is 64 KB
Mask ← 0x0000d93003530000 // 13 bits set -> desired average size is 2^13 bytes = 8 KB
fp ← 0 // uint64
i ← 0
// buffer size is less than minimum chunk size
if n ≤ MinSize then
return n
if n ≥ MaxSize then
n ← MaxSize
// Skip the first MinSize bytes, and kickstart the hash
while i < MinSize do
fp ← (fp << 1 ) + Gear[src[i]]
i ← i + 1
while i < n do
fp ← (fp << 1 ) + Gear[src[i]]
if !(fp & Mask) then
return i
i ← i + 1
return iWhere the Gear array is equivalent to the s table above.
An advanced version uses two different masks derived from the above Mask, one with 15 set bits and the other with 11 set bits. The former is used when i < 8 KB; afterwards the latter takes over. This tightens the chunk-size distribution around the desired average and improves deduplication.
Computational complexity
All rolling hash functions can be computed in linear time bitwise exclusive ors and circular shifts.