False negatives from pt-table-checksum

I’ve dug further into this, and this problem is serious. It turns out it has nothing to do with replication; the query that pt-table-checksum is using to calculate chunk checksums is flawed.

The checksum query, as extracted from a binary log, is:
SELECT ‘schema name’, ‘table name’, ‘1’, NULL, NULL, NULL, COUNT(*) AS cnt, COALESCE(LOWER(CONV(BIT_XOR(CAST(CRC32(CONCAT_WS(’ #', id)) AS UNSIGNED)), 10, 16)), 0) AS crc FROM schema.table;

Now, let’s look at a sample table. Let’s say it has this set of rows on server 1:

±—±-------±-------------±-----------+
| id | lbc_id | rebill_depth | percentage |
±—±-------±-------------±-----------+
| 21 | 1 | 1 | 100 |
| 23 | 1 | 2 | 100 |
| 25 | 1 | 3 | 100 |
| 27 | 1 | 4 | 100 |
| 29 | 1 | 5 | 100 |
±—±-------±-------------±-----------+

And this set on server 2:

±—±-------±-------------±-----------+
| id | lbc_id | rebill_depth | percentage |
±—±-------±-------------±-----------+
| 21 | 1 | 1 | 100 |
| 22 | 1 | 2 | 100 |
| 24 | 1 | 3 | 100 |
| 26 | 1 | 4 | 100 |
| 28 | 1 | 5 | 100 |
±—±-------±-------------±-----------+

Notice that the data values are the same, but the row IDs are different.

Now, let’s take that query starting from the inside. We’ll skip a few steps and go as far as select CAST(CRC32(CONCAT_WS(‘#’, id)) AS UNSIGNED) FROM schema.table.
Server 1:

±----------------------------------------------+
| CAST(CRC32(CONCAT_WS(‘#’, id)) AS UNSIGNED) |
±----------------------------------------------+
| 4252452532 |
| 326707096 |
| 4196041389 |
| 336913281 |
| 4088188550 |
±----------------------------------------------+

Server 2:

±----------------------------------------------+
| CAST(CRC32(CONCAT_WS(‘#’, id)) AS UNSIGNED) |
±----------------------------------------------+
| 4252452532 |
| 1685985038 |
| 2367533627 |
| 1662243607 |
| 2225864208 |
±----------------------------------------------+

OK, this is as we expect. The first row checksum matches, and the remaining four don’t. So now let’s go out one set of braces and perform the BIT_XOR.

Server 1:

±-------------------------------------------------------+
| BIT_XOR(CAST(CRC32(CONCAT_WS(‘#’, id)) AS UNSIGNED)) |
±-------------------------------------------------------+
| 4088188550 |
±-------------------------------------------------------+

Server 2:

±-------------------------------------------------------+
| BIT_XOR(CAST(CRC32(CONCAT_WS(‘#’, id)) AS UNSIGNED)) |
±-------------------------------------------------------+
| 4088188550 |
±-------------------------------------------------------+

Ummmmmmmmmmmm… Houston, WE HAVE A PROBLEM.

I note that CRC32 is being used here, and pt-table-checksum itself warns that CRC32 “is too prone to hash collisions”. But CRC32 is not the problem here. We are getting distinct sets of checksums out of CRC32. The problem is that we are getting distinct sets of CRC32 checksums that BIT_XOR to the same result. And from then on, everything outside that BIT_XOR doesn’t matter.

As a footnote, if we compare only the first FOUR rows of the table, we get different BIT_XOR results as we expect we should. But with five rows, the data values turn out to be just right to return the same BIT_XOR for both sets of rows. BIT-XOR is effectively being used here as a hash function itself, and it is a terribly, terribly weak one.

This is JUST ONE example table for which this occurs. The customer I am working with has numerous such tables.

It should also be noted that using a stronger hash function such as MD5 or murmur will GREATLY REDUCE the chance of a BIT_XOR collision, but will not eliminate it. But it is vital to understand that it is not actually the “real” hash function that is the weakness being demonstrated here — it is the XOR used as a hash function. It should also be noted that the smaller the number of rows in the table, the more likely an XOR collision is.