hundredwatt
Joined 18 years ago
Karma
681
Submissions
89
Member since
Jan 29
Recent submissions
Comment · 1 year ago
> To be pedantic, not guaranteed. The xor of multiple elements may erroneously have a passing checksum, resulting in an undetected false decode
The false decodes can be detected. During peeling, deleting a false decode inserts a new element with the opposite sign of count. Later, you decode this second false element and end up with the same element in both the A / B and B / A result sets (as long as decode completes without encountering a cycle).
So, after decode, check for any elements present in both A / B and B / A result sets and remove them.
--
Beyond that, you can also use the cell position for additional checksum bits in the decode process without increasing the data structure's bit size. i.e., if we attempt to decode the element X from a cell at position m, then one of the h_i(x) hash functions for computing indices should return m.
There's even a paper about a variant of IBFs that has no checksum field at all: https://arxiv.org/abs/2211.03683. It uses the cell position among other techniques.
Comment · 1 year ago
The graph constructed by using bloom filter-style hash functions supports a decoding process called "peeling" where you:
1. Find a batch with 1 missing element 2. Delete that element from its other assigned partitions 3. Repeat, as the modified batches may now be recoverable
This iterative process (surprisingly!) succeeds with very high probability as long as the number of partitions is 1.22x larger than the number of missing elements with k=3 hash functions.
Comment · 1 year ago
You don't lose absolute guarantees, but the probabilistic nature means the process may fail (in a guaranteed detectable way) in which case you can try again with a larger parameter.
The "bloom filter" name is misleading in regard to this.
Comment · 1 year ago
A neat trick to make the accumulator both collision-resistant and self-diagnosing.
For every normalized link id x:
y = (x << k) | h(x) # append a k-bit hash to the id
acc ^= y
If acc is non-zero, split it back into (x', h'):
* Re-compute h(x').
* If it equals h', exactly one link is unpaired and x' tells you which one (or an astronomically unlikely collision). Otherwise there are >= 2 problems.
This has collision-resistance like the parent comment and adds the ability to pinpoint a single offending link without a second pass or a hash table.
Comment · 1 year ago
The recently released sqlite_rsync utility uses a version of the rsync algorithm optimized to work on the internal structure of a SQLite database. It compares the internal data pages efficiently, then only syncs changed or missing pages.
Nice tricks in the article, but you can more easily use the builtin utility now :)
I blogged about how it works in detail here: https://nochlin.com/blog/how-the-new-sqlite3_rsync-utility-w...
Comment · 1 year ago
It’s meant to run in or alongside the pipeline continuously.
Not planning to open source, working on a commercial offering but haven’t launched anything publicly yet.
Would love to hear any more thoughts on the concepts here or my email is in bio
Comment · 1 year ago
I'm building a new tool for end-to-end data validation and reconciliation in ELT pipelines, especially for teams replicating data from relational databases (Postgres, MySQL, SQL Server, Oracle) to data warehouses or data lakes.
Most existing solutions only validate at the destination (dbt tests, Great Expectations), rely on aggregate comparisons (row counts, checksums), or generate too much noise (alert fatigue from observability tools). My tool:
* Validates every row and column directly between source and destination * Handles live source changes without false positives * Eliminates noise by distinguishing in-flight changes from real discrepancies * Detects even the smallest data mismatches without relying on thresholds * Performs efficiently with an IO-bound, bandwidth-efficient algorithm
If you're dealing with data integrity issues in ELT workflows, I'd love to hear about your challenges!
[ my public key: https://keybase.io/hundredwatt; my proof: https://keybase.io/hundredwatt/sigs/sAhvC-zN-G30cPShxbXA7UC-0MmpSWpit0N0CNOtDME ]