On Mon, Dec 16, 2024 I wrote in [0]: > So as I understand it the trade-off > for WAL error detection is: > > CRC > odd: 100% > even: the collision-avoidance probability of a mediocre hash function > > good hash function: > odd: the collision-avoidance probability of a good hash function > even: the collision-avoidance probability of a good hash function > > Stated this way, it's possible we don't have the best solution, but > it's also not immediately obvious to me that the second way is so much > better that it's worth the effort to change it. > > If we did go to a hash function, It'd be ideal to have the collision > guarantees of an "almost universal" hash function. For any two > messages of length at most 'n', the claimed probability of collision > is at most, for example: > > VHASH [1]: n * 2**-61 > CLHASH [1]: 2.0004 * 2**-64 (for same length strings) > umash [2]: ceil(n / 4096) 2**-55 > polymur hash [3]: n * 2**-60.2 > > ...but these are all 64-bit hashes, and some have further traits that > make them impractical for us. I'm not aware of any 32-bit universal > hashes.
Paul Khuong, the author of UMASH, mentioned two interesting facts to me: 1) It's trivial to reduce a 64-bit universal hash to a 32 (or whatever)-bit universal hash by composing it with another universal hash function -- a convenient example is Dietzfelbinger's multiplicative hash (see section 2.3 in [1]), which is just a multiply and a shift. 2) An XOR-based longitudinal redundancy check (LRC) [2] also detects errors of any odd number of bitflips, and is cheap enough to compute along with the hashing loop such that it's likely free on superscalar CPUs. For WAL we could use e.g. a 31-bit hash plus an LRC reduced to a single parity bit, or keep 32 bits of hash and steal a WAL header padding byte to store a 1-byte LRC (which would additionally detect most 2-bit errors and some burst errors (see section 3.1 in [3]) if we wanted to keep some weaker CRC-type guarantees). 128-bit arithmetic has easier portability than CRC instructions (if we avoid designs that require carryless multiplication), and it'd be nice to get consistent performance across platforms, possibly with better error detection for sector-sized errors. Assuming a suitable function (and licence) can be found. [0] https://www.postgresql.org/message-id/CANWCAZYQnppe%3DXHxXGwYEvuaqx7_v91sHk54kqWYRyinzvhbVA%40mail.gmail.com [1] https://arxiv.org/abs/1504.06804 [2] https://en.wikipedia.org/wiki/Longitudinal_redundancy_check [3] https://users.ece.cmu.edu/~koopman/pubs/maxino09_checksums.pdf -- John Naylor Amazon Web Services
