I have a replicated database (not SQL, a triple store, but specifics should not matter too much) running on several hosts. Each of them holds a copy of the database which is updated by feeding from certain outside source, and the copies should be identical. However, turns out they are not exactly identical - there is a variance in record count between the databases. Each database has about 2 billion entries, and the difference is comparatively small - about 0.05% - but that means there's about a million records that are somehow wrong. Probably due to some bug in update process, but I have hard time finding what exactly is wrong. The change is not due to replication lag, since the lag is small (seconds) and the number of records updated per second (~tens, maybe a couple of hundreds if things get busy) is much smaller then the size difference.
It would be very helpful to know which records do not match, but I'm not exactly sure how one compares 2 billion records in a production DBs that change every second. If I just make a dump - which can take a long time, hours at least - and compare it to another DB - which also will take time - the difference may be just because the DBs has changed since then.
So, I'm looking for ideas on how to find those different records. I do not need all of them - having even one instance would already be helpful - but I'm not sure how to efficiently find even one.