Finding difference in a big live (almost identical) databases

Question

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.

Answer 1

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?

Answer 2

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.

Answer 3

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.