Finding Changes between 2 HUGE zone (text) files

Question

I have access to the .com zone files. A zone file is a text file with a list of domain names and their nameservers. It follows a format such as:

mydomain NS ns.mynameserver.com.
mydomain NS ns2.mynameserver.com.
anotherdomain NS nameservers.com.
notinalphadomain NS ns.example.com.
notinalphadomain NS ns1.example.com.
notinalphadomain NS ns2.example.com.

As you can see, there can be multiple lines for each domain (when there are multiple nameservers), and the file is NOT in alpha order. These files are about 7GB in size.

I'm trying to take the previous file and the new file, and compare them to find:

1. What domains have been Added
2. What domains have been Removed
3. What domains have had nameservers changed

Since 7GB is too much to load the entire file into memory, Obviously I need to read in a stream. The method I've currently thought up as the best way to do it is to make several passes over both files. One pass for each letter of the alphabet, loading all the domains in the first pass that start with 'a' for example. Once I've got all the 'a' domains from the old and new file, I can do a pretty simple comparison in memory to find the changes.

The problem is, even reading char by char, and optimizing as much as I've been able to think of, each pass over the file takes about 200-300 seconds, with collecting all the domains for the current pass's letter. So, I figure in its current state I'm looking at about an hour to process the files, without even storing the changes in the database (which will take some more time). This is on a dual quad core xeon server, so throwing more horsepower at it isn't much of an option for me. This timing may not be a dealbreaker, but I'm hoping someone has some bright ideas for how to speed things up... Admittedly I have not tried async IO yet, that's my next step.

Thanks in advance for any ideas!

Answer 1

Preparing your data may help, both in terms of the best kind of code: the unwritten kind, and in terms of execution speed.

cat yesterday-com-zone | tr A-Z a-z | sort > prepared-yesterday
cat today-com-zone | tr A-Z a-z | sort > prepared-today

Now, your program does a very simple differences algorithm, and you might even be able to use diff:

diff prepared-today prepared-yesterday

---

Edit:

And an alternative solution that removes some extra processing, at the possible cost of diff execution time. This also assumes the use of GnuWin32 CoreUtils:

sort -f <today-com-zone >prepared-today
sort -f <yesterday-com-zone >prepared-yesterday
diff -i prepared-today prepared-yesterday

The output from that will be a list of additions, removals, and changes. Not necessarily 1 change record per zone (consider what happens when two domains alphabetically in order are removed). You might need to play with the options to diff to force it to not check for as many lines of context, to avoid great swaths of false-positive changes.

You may need to write your program after all to take the two sorted input files and just run them in lock-step, per-zone. When a new zone is found in TODAY file, that's a new zone. When a "new" zone is found in YESTERDAY file (but missing in today), that's a removal. When the "same" zone is found in both files, then compare the NS records. That's either no-change, or a change in nameservers.