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.

  • I'd add a timestamp of insertion to every row (sth like createdAt DATETIME NOT NULL DEFAULT NOW()) If you now dump the DBSs you can drop all records from the copy that are newer than the moment of invoking the dump. How you then achieve the actuall Diff depends on your data structure
    – marstato
    Commented Apr 26, 2017 at 22:28
  • Unfortunately, adding timestamps to a triple store is not easy.
    – StasM
    Commented Apr 26, 2017 at 22:30
  • Does ist have an equivalent of auto increment primary keys? Harder to utilize for this purpose but could possibly do the trick
    – marstato
    Commented Apr 26, 2017 at 22:33
  • 1
    Nope, sorry, no primary keys (separate from the data content) either. That's what makes it tricky - one has to compare data items, and comparing 2b data items is time-consuming.
    – StasM
    Commented Apr 26, 2017 at 22:38
  • 1
    Do you have a storage level snapshot capability at all (e.g. virtual machine disk snapshot, RAID or LVM snapshot, btrfs snapshot). If you have any of those technology capable of doing copy-on-write snapshots (taking a snapshot is usually atomic, so your data store may do crash recovery but shouldn't have corrupted/inconsistent data, when restoring from a live snapshot). You can then spawn a read-only instance of the data store from the snapshot. You'd then be able to make the comparison at a more leisurely pace (just watch for remaining disk space).
    – Lie Ryan
    Commented Apr 27, 2017 at 2:13

3 Answers 3


There is more than one way to do it, and there are probably practical constraints to doing it that you haven't mentioned. Given the small information, here's how I would do it.

Let's start with some assumptions:

  • This database is in moderately heavy usage, adding some load is acceptable but placing a heavy load on the system is not.
  • You care that you that you quickly find any record actually requested that does not match.
  • The records are just normal records, meaning you can look compare the records from both stores without additional work.
  • You can find a sequence number of each record when you read it, e.g., 'this is record 1,242,423,231 or 3,234,422,413'. Many, but not all, databases will support this.
  • This is a one-time thing and is important.

So, here's one solution:

  • There are only a few billion entries, so we can fit a bit set of all records checked into a bit set in RAM. 4 billion bits is about half a gigabyte of RAM. Initially set to zero, these will be set to one if the records have ever been compared.
  • Each time you fetch a record, fetch the equivalent record from the other datastore, compare them, and, assuming all is well, set the 'checked this one' bit to one. Over time, fewer of the common records will need to be checked this way.
  • Whenever the load is 'lower', start pulling random or sequential unchecked records from the database. If your store has an unused weekend, then you will check a lot of records.

Here's another solution without record numbers:

  • First, trigger the comparison whenever you ask for a live record. This keeps your data integrity up.
  • Second, start the slow scan on any comprehensive index.

Finally, here's my recommended solution.

  • Stop. Go get coffee. Think hard about how it could have happened. Write down assumptions that could be wrong. Think about logs for records modified during replication. See if you can solve it.
  • Do the back-of-the-envelop of time this will require. Reading the entire contents of a disk, over your network, even for a couple terabytes may take forever. Can you make adhoc networks and check rack by rack? How bad is it?
  • Yes, the system would tolerate some additional load. Not huge one, but scanning through the data couple of times is definitely ok. Unfortunately, records don't have unique ID, but the bitmask idea is not bad, I probably could synthesize some kind of an ID, maybe some kind of hash. If I reduce search space enough I could just zero in on suspicious data items and investigate them, looking at 100 items is much better than looking for it in 2bn haystack :)
    – StasM
    Commented Apr 27, 2017 at 3:58
  • Hmmm..... First check. Does the record count guarantee to be accurate for your database? Are you looking through haystacks without needles? Commented Apr 28, 2017 at 17:57

It appears that perhaps all you have as other metadata is the record count in each database?

Using just that, perhaps you can, on each round of updates from the external sources, see if the record counts diverge (more than they already are). If they do, then at least you have a suspect record (update) set that should be closely examined in each database to see if those records made it in both. If necessary, you might have to slow down the updates so you can get the record count from each update set, to narrow down a bad update.

  • It's kind of hard to do it on each update since due to how production networking is set up the copies aren't supposed to be able to talk to each other (normally, they have no reason to). But maybe just recording the counts and seeing when they diverge would help. The problem is updates a batched in large groups, so when I'd know only something like "count diverged on one of the 500 updates here". Still better than nothing I assume...
    – StasM
    Commented Apr 27, 2017 at 3:51

you can't load them into memory, 2 billion records of 100 bytes esach would be almost 200GB of ram.

The way you would typically compare sets like this is by looking at them in pages based on a certain sorting. For example if i had a phone book then i could sort them based on phone number (or last name it doesn't really matter which sorting you take)

Database 1         | Database 2
555- 1234 anderson | 555 - 1234 anderson
555  1235 smith    | 555 - 1235 johnson
555  1236 miller   | 555 - 1236 miller

Now load a page (say 1000 records or something somewhat reasonable) and then go through them linearly. You just keep a pointer and compare 1 phonenumber against the other.

Note: be don't just look at the index of the pointer because there might be an insertion, if the ydiffer just print out the difference and increment the pointer left & right.

Note: you said your records don't have a unique ID. you still need to determine when they talk about the same record. For example lastname + birth date might be considered identifying a person and you are looking for change in addresses that havn't been processed correctly.

  • I think you misunderstand bitsets; you want a marker of one bit per record not the whole record. Commented Apr 28, 2017 at 18:00
  • The question suggested that we wanted to find already present differences. And doing 2 billion separate queries/updates, even over time, is more than needed. This was a suggestion how you could go over your data once and print out the difference
    – Batavia
    Commented Apr 29, 2017 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.