There are situations where data belonging to a given context are nonetheless scattered among different servers, possibly in separate locations. In such situations, gathering data together is more difficult than dealing with a unified set of tables, where all of them were under the same engine. The challenge is purely technological. It is easy to create a virtual file system, making the database engine believe that all the files are in the same machine, even though they are just a link over the network, perhaps hundreds of miles apart. However, in such a case the performance would be so unfavorable that the whole purpose of having a DBMS would be mystified. Hence, the distributed database studies, which try to find clever ways of reducing the technological gaps and make normal operations look, if not ordinary business, at least affordable.

July 08, 2004
URL:http://drdobbs.com/taming-the-distributed-database-problem/199101871

Taming the Distributed Database Problem: A Case Study Using MySQL

Giuseppe Maxia

There are situations where data belonging to a given context are nonetheless scattered among different servers, possibly in separate locations. In such situations, gathering data together is more difficult than dealing with a unified set of tables, where all of them were under the same engine. The challenge is purely technological. It is easy to create a virtual file system, making the database engine believe that all the files are in the same machine, even though they are just a link over the network, perhaps hundreds of miles apart. However, in such a case the performance would be so unfavorable that the whole purpose of having a DBMS would be mystified. Hence, the distributed database studies, which try to find clever ways of reducing the technological gaps and make normal operations look, if not ordinary business, at least affordable.

Distributed database theoreticians often debate the capability of performing JOIN operations across distant databases. There are some astute methods to achieve such goals, and sometimes with acceptable performance. A JOIN between two tables in different databases, with a WHERE clause involving both systems, could be carried out quite fast. But things are not always that easy. There are some classes of queries that require such a strain and interaction between tables that their cost in a remote call could be prohibitive. As an example, consider a query where we want to find which rows are different in two given tables or which rows are missing from one of them. Performing such a task in a distributed database could be a challenging exercise. In this article, I will examine exactly this kind of query to explore some alternative ways of remote comparison.

Remote Comparison

Comparing tables that belong to different databases implies examining the entities at three levels:

• Table structure
• Amount of data
• Data contents

The importance of the first two levels should be straightforward. It is useless to compare data if we are not sure about the containers (i.e., the tables). If the tables have a different structure, any difference I may find will be meaningless. The same goes for the quantity of data available. If I use some statistical methods to compare the data in two tables, they must have the same number of records for the results to be of any use.

Fortunately, the first two levels are also the easiest to deal with. Comparing two table structures with the features that any DBMS offers is fast and accurate. There are already specialized tools that perform such tasks efficiently, and the row counting part is trivial.

Thus, I am left with the third level -- the one that troubles me most. Before getting into more detail, let me first explain how I got into this perilous field.

Background

Until a few months ago, I was in charge of developing and maintaining a large human resources database. It was a work in progress, being migrated from a legacy system with new features being developed constantly, so I found it useful to install two servers -- one for development, and one for production (Figure 1).

My first encounter with remote comparison was when the new features in the development server needed some adjustments to their structure. Before committing the changes in the production server, I tested the new features in the development one, and I kept a log of the changes, which I then replayed to the main server. There was no problem with this strategy until the day I missed an item in the log file and thus didn't update the main server correctly.

A few weeks later, the whole issue forgotten, it took me several hours to nail down the bug. In the process, I found plenty of tools to compare the structure of two databases and even to produce automatically the necessary ALTER TABLE statements to fill the gaps.

But the problems were not that simple. Besides the development/production duality, I also had a data warehouse to facilitate heavy number crunching for the statistics that the management required on a daily basis. Because the data warehouse needed development, migration, and maintenance, it was also duplicated. This was no big deal at the beginning, but data warehouses naturally grow large very quickly. So I had to devise a mechanism to populate each of them within their respective servers.

Everything went well and the data warehouse produced statistics that never got more than a distracted glance, until one day, 30 minutes before a big meeting, somebody realized that there was a .02% inconsistency in the statistics compared to the previous month. So, of course, I was tasked with fixing it.

I compared the numbers in the development server with the main one and found that the numbers in the test server were correct. I printed the statistics with 19 minutes to spare, but after everyone had left I was still there trying to find out the difference between two huge tables in two different servers. Once all the users had logged out, I copied the tables from the development to the production server, which kept the servers busy for the better part of 3 hours, and then compared the two tables locally and found the culprit.

This incident led me to more serious thinking about remote comparison, and here are the results. Remote comparison is also useful for purposes such as establishing a mirror database or checking the correctness of a replication engine. You never know when such a need will arise -- unless, of course, you are developing a distributed database system -- and therefore these notes may turn out to be useful.

Brute Force Attacks

I used a brute force approach on my data warehouse (Figure 2a), which is not recommended, because it transfers all the records from one server to another. So, if your table has one million records, you move all of them across the network. Additionally, the receiving server might have to recreate the tables from raw data, depending on the method you choose to do the transfer.

Another common approach, though, may be even worse. When this problem pops up in a programming forum, usually somebody suggests querying both servers and comparing the data sets in the client (Figure 2b). What they don't realize is that they are moving two million records across the network, making two unhappy DBAs and an unhappy sys admin in the bargain.

Comparing Other Things

There is something to learn from the methods used to compare things other than database tables. For instance, let's see how to compare two binary files.

Unless you want to pass the file data from one computer to another, there is a commonly used procedure to make sure that a file in your machine is the same as the one that's in a distant server. It happens, for example, when you download a large file, such as a CD ISO image, from a Web site. Besides the file, the site may provide the MD5 signature of the file (a 128-bit number), which is usually provided as a 32-character string. Once you have downloaded the file, you can calculate locally the MD5 for it and compare the result with the one in the site. If these match, you know that the download was successful. The benefit of this method is that you can compare a small amount of data that represents the real stuff instead of sending large chunks of bytes across a network to perform a comparison.

A similar approach is feasible to compare one single row in a database table. You can either send all the row fields and then compare each one, or you can calculate some sort of CRC for the row data and compare just that. Once more, the MD5 function is a preferred choice for the task:

SELECT MD5(CONCAT(field1, field2, field3, field4)) as signature from MYTABLE;

SELECT SUM(
   CONV(
     SUBSTRING(
       @CRC:=MD5(CONCAT_WS('/',field1, field2, field3 ...)),
     1, 8),
   16, 10)) AS sig1,
   SUM(CONV(SUBSTRING(@CRC,  9, 8), 16, 10)) AS sig2,
   SUM(CONV(SUBSTRING(@CRC, 17, 8), 16, 10)) AS sig3,
   SUM(CONV(SUBSTRING(@CRC, 25, 8), 16, 10)) AS sig4
FROM
   mytable;

CREATE TABLE shadow_table (
    signature char(32) not null primary key,
    sig1 BIGINT not null,
    sig2 BIGINT not null,
    sig3 BIGINT not null,
    sig4 BIGINT not null,
    PK int not null,
    unique key PK(PK));

INSERT INTO shadow_table
SELECT
  @CRC:=MD5(
  CONCAT_WS('/',employee_code,gender,name,DOB,salary,dept_code,loc_code)),
  CONV(SUBSTRING(@CRC, 1,8),16,10),
  CONV(SUBSTRING(@CRC, 9,8),16,10),
  CONV(SUBSTRING(@CRC,17,8),16,10),
  CONV(SUBSTRING(@CRC,25,8),16,10),
  employee_code
FROM employees;

SELECT
  SUM(sig1), SUM(sig2), SUM(sig3), SUM(sig4)
FROM
  shadow_table;

SELECT
  SUM(sig1), SUM(sig2), SUM(sig3), SUM(sig4)
FROM
  shadow_table
WHERE
  PK BETWEEN 1 AND 512;

CREATE TABLE shadow_table
  (signature CHAR(16) NOT NULL PRIMARY KEY,
  PK BIGINT NOT NULL,
  span BIGINT UNSIGNED NOT NULL,
  UNIQUE KEY PK(PK),
  KEY span (span));

INSERT INTO
   shadow_table (signature, PK, span)
SELECT
   MD5(CONCAT_WS('/',
   employee_code,gender,name,DOB,salary,dept_code, loc_code)),
   employee_code, employee_code / 1024
FROM
   employees;

SELECT
    span, COUNT(*) as cnt,
    CONCAT(SUM(CONV(SUBSTRING(signature,1,8),16,10)),
    SUM(CONV(SUBSTRING(signature,9,8),16,10)),
    SUM(CONV(SUBSTRING(signature,17,8),16,10)),
    SUM(CONV(SUBSTRING(signature,25,8),16,10))) as sig
FROM
    shadow_table
GROUP BY
    span;

# first server
SELECT signature FROM shadow_table WHERE span = XX;
# I get signatures "A2F", "B4E", "C1D", etc  

#second server
SELECT
    gender, name, DOB, salary
FROM
    shadow_table
    INNER JOIN employees ON (PK=employee_code)
WHERE
    span = XX
    AND signature NOT IN ("A2F", "B4E", "C1D", ... );

my $columns = $sth1->fetchall_arrayref();
my $query = qq{SELECT PK FROM check_table WHERE span = $_ AND
signature NOT IN (}
  . (join(",", map {"'$_->[0]'"} @$columns ))
  . ")";

CREATE PROCEDURE rangeCRC()
BEGIN
    DECLARE done INT DEFAULT 0;
    DECLARE CONTINUE HANDLER FOR SQLSTATE '02000'
        SET done = 1;
    DECLARE c1 CURSOR FOR
        SELECT MD5(CONCAT_WS('/',
        employee_code,gender,name,DOB,salary,dept_code, loc_code)) FROM employees;
    DECLARE tmpCRC CHAR(32) ;
    
    OPEN c1;
    SET @globalCRC = repeat('0',32);
    
    REPEAT
        FETCH c1 INTO tmpCRC;
        IF NOT done THEN
            SET @globalCRC = MD5(concat(@globalCRC, tmpCRC));
        END IF;  
    UNTIL done
    END REPEAT;
    CLOSE c1;
    # Now @globalCRC contains the range CRC for table employees
END;

Planning for a Distributed Database Server

If you have gone through all the above steps, you must have realized that remote comparison is not rocket science. The complication arises from the engine that is not equipped for such a task.

An automatic CRC signature for each record (MySQL has it already) and an appropriate function to access its value would make the shadow table redundant. And, a built-in function to calculate range CRCs would speed up the process even further, besides making it more accurate.

This method needs to be organized and made compatible with the rest of the existing engine, perhaps making the CRC optional, in order to reduce the overhead when this feature is not needed, but it is not impractical. A real distributed DBMS could be really around the corner.

Notes

Thanks to Vahe Sarkissian and Alan Ferrency for commenting an early draft of this document and for their valuable advice.

To compare the structure of two databases, you can use a tool developed by Adam Spiers -- http://search.cpan.org/author/ASPIERS/MySQL-Diff-0.33/

Giuseppe Maxia is a freelance database consultant and CTO of an Italian company specializing in Open Source solutions (www.stardata.it). He is widely known in the Perl and MySQL community through his articles and software contributions.

Figure 1 A sample working environment

Figure 2a A brute force comparison schema

Figure 2b The most inefficient brute force comparison schema

Figure 3 Structure of an employees table

Figure 4 A SQL binary search for remote tables

Figure 5 Range search provides the most efficient results

Listing 1 compare_table_CRC.pl: Tells if two tables in two remote databases are different

#!/usr/bin/perl -w
# compare_table_CRC
# (C) Giuseppe Maxia 2003
#
# Compares two tables in two remote databases
# and checks for any difference, by comparing a global CRC
# of all the records.
# Does not return individual different records. Use the 
# find_differences script for such purposes
use strict;
use DBI;

# This script is for educational purposes only.
# Parameters are embedded in the script itself.
# For production, it woyld be better to use either
# a config file or any Getopt::XX modules
my $host1 = "localhost";
my $host2 = "192.168.59.9";
my $db1 = "xcompany";
my $db2 = "xcompany";
my $tablename = "employees";
my ($user1, $password1) = ('myuser', 'secret');
my ($user2, $password2) = ('myuser', 'secret');

my $dbh1 =  DBI->connect("DBI:mysql:$db1;"
    . "host=$host1;port=3306",
    $user1, 
    $password1, 
    {RaiseError => 1, PrintError =>0}) 
    or die "can't connect : $DBI::errstr";

my $dbh2 =  DBI->connect("DBI:mysql:$db2;"
    . "host=$host2;port=3306",
    $user2, 
    $password2, 
    {RaiseError => 1, PrintError =>0}) 
    or die "can't connect : $DBI::errstr";

unless (grep {$_ eq $tablename} $dbh1->tables()) {
    die "$tablename not found in $db1\n"
}

unless (grep {$_ eq $tablename} $dbh2->tables()) {
    die "$tablename not found in $db2\n"
}

my $fields = get_fields($dbh1, $tablename);

my $check_table = qq{
   SELECT 
   COUNT(*) AS cnt, 
   CONCAT(SUM(CONV(SUBSTRING(\@CRC:=MD5(CONCAT_WS('/##/',$fields)),1,8),16,10)),
    SUM(CONV(SUBSTRING(\@CRC, 9,8),16,10)),
    SUM(CONV(SUBSTRING(\@CRC,17,8),16,10)),
    SUM(CONV(SUBSTRING(\@CRC,25,8),16,10))
    ) AS sig 
    FROM $tablename 
    };

print $check_table,$/;

my $probe1 = $dbh1->selectall_arrayref($check_table);
my $probe2 = $dbh2->selectall_arrayref($check_table);

print "$db1\t $probe1->[0]->[0]\t $probe1->[0]->[1]\n";
print "$db2\t $probe2->[0]->[0]\t $probe2->[0]->[1]\n";

my $result = (($probe2->[0][0] ne $probe1->[0][0]) 
    or ($probe2->[0][1] ne $probe1->[0][1])) ?
        "DIFFERENCE FOUND" :  "NO DIFFERENCE" ; 
 
print "$result\n";

# returns the list of fields, ready to insert into the CRC query
sub get_fields {
    my ($dbh, $tablename) = @_;
    my $sth = $dbh->prepare(qq{describe $tablename});
    $sth->execute();
    my @fields=();
    while (my $row = $sth->fetchrow_hashref()) {
        # discards TIMESTAMP fields from the comparison
        next if lc $row->{Type} eq 'timestamp';
        my $field ="`$row->{Field}`";
        # if the field is nullable,
        # then a COALESCE function is used
        # to prevent the whole CONCAT from becoming NULL
        if (lc $row->{Null} eq 'yes') {
            $field = qq[coalesce($field,"#NULL#")];
        }
        push @fields, $field;
    }
    return join ",", @fields; 
}

Listing 2 make_shadow_table.pl: Creates the auxiliary structure for remote comparison

#!/usr/bin/perl -w
# make_shadow_table
# (C) Giuseppe Maxia 2003
#
# Creates a shadow table with a CRC signature and 
# the corresponding primary key.
# 
use strict;
use DBI;

my $skip_timestamp = 1;

my ($host, $db, $table) = @ARGV ;
$table or die
        "syntax: make_signatures host database table\n";

my @signature_queries = (
        
  ['drop signatures',   qq{
    DROP TABLE IF exists shadow_table
    }],
  ['create signatures', qq{
CREATE TABLE shadow_table ( 
    signature CHAR(32) NOT NULL PRIMARY KEY,
    span BIGINT UNSIGNED NOT NULL,
    PK !PK_TYPE! NOT NULL,
    UNIQUE KEY PK(PK),
    KEY span (span)
    )}],
   ['insert signatures', qq{
INSERT INTO 
    shadow_table (signature, PK, span) 
SELECT 
    MD5(CONCAT_WS('/#/',!COLUMN_NAMES!)),
    !PK_NAME!,
    !PK_NAME! / 512
FROM 
    !TABLE_NAME! 
}]
);

sub make_signatures {
    my $dbh = shift;
    my $table = shift;
    my $key_pos = 3;
    my $description = $dbh->selectall_arrayref(qq{describe $table});
    my ($version) =  @{$dbh->selectcol_arrayref(qq{select version()})};
    if ($version =~ /4\.1/) {
            $key_pos = 4;
    }
    my @pkeys = grep {$_->[$key_pos] eq "PRI"} @$description;
    die "can't make signatures. Table $table has no primary key.\n" 
        unless scalar @pkeys ;
    my ($primary, $pk_type) =();
    if (scalar @pkeys > 1) { # composite PK
        $primary = join "," , map  {"`$_->[0]`"} @pkeys;
        $primary = "MD5(CONCAT_WS('/#/'," . $primary . "))";
        $pk_type = "CHAR(40)";
    }
    else {
        ($primary, $pk_type) = map {'`' . $_->[0] . '`', $_->[1]} @pkeys;
    }
    my $columns ='';
    for (@$description) {
        next if $skip_timestamp && ($_->[1] =~ /timestamp/i);
        my $column = "`$_->[0]`";
        $columns .= ',' if $columns;
        if (($_->[2] eq 'YES') && 
            ((not $_->[$key_pos]) || (($_->[$key_pos]) && \

              ($_->[$key_pos]) ne 'PRI'))) {
            $column = "COALESCE($column, '#NULL#')"
        }
        $columns .= $column;
    }
    
    for (@signature_queries) 
    {
        my $query = $_->[1];
        $query =~ s/!PK_TYPE!/$pk_type/;
        $query =~ s/!PK_NAME!/$primary/g;
        $query =~ s/!TABLE_NAME!/$table/;
        $query =~ s/!COLUMN_NAMES!/$columns/;
        print "#$_->[0] $query\n"; 
        $dbh->do ($query);
    }
}

my $dbh = DBI->connect("DBI:mysql:$db;host=$host", "myuser","secret",{RaiseError=>1});

make_signatures ( $dbh, $table);

Listing 3 find_differences.pl: Implementation of the range search algorithm

#!/usr/bin/perl -w
# find_differences
# (C) Giuseppe Maxia 2003
# 
# Compare two tables in two remote databases, looking for different records.
# Requires a "shadow table", created by make_shadow_table
# 
use strict;
use DBI;

# This script is for educational purposes only.
# Parameters are embedded in the script itself.
# For production, it woyld be better to use either
# a config file or any Getopt::XX modules
my $db1 = "xcompany";
my $db2 = "xcompany";
my $host1 = "localhost";
my $host2 ="192.168.59.9";
my ( $user1, $password1 ) = ( 'myuser', 'secret' );
my ( $user2, $password2 ) = ( 'myuser', 'secret' );

my $dbh1 =  DBI->connect("DBI:mysql:$db1;host=$host1",
    $user1, $password1, 
    {RaiseError => 1, PrintError =>0}) 
    or die "can't connect to $host1 : $DBI::errstr";

my $dbh2 =  DBI->connect("DBI:mysql:$db2;host=$host2",
    $user2, $password2, 
    {RaiseError => 1, PrintError =>0}) 
    or die "can't connect to $host2 : $DBI::errstr";

$dbh1->do(qq{set SQL_LOG_OFF=1 }); # prevents writing on the general log file
$dbh2->do(qq{set SQL_LOG_OFF=1 }); # which can become quite big if you 

                                   # have many records

my @probes =();

my $initialprobe = qq{
  SELECT 
    span, COUNT(*) AS cnt, 
    CONCAT(SUM(CONV(SUBSTRING(signature,1,8),16,10)), 
    SUM(CONV(SUBSTRING(signature,9,8),16,10)),
    SUM(CONV(SUBSTRING(signature,17,8),16,10)),
    SUM(CONV(SUBSTRING(signature,25,8),16,10))) AS sig 
  FROM 
    shadow_table 
  GROUP BY 
    span };

my $probe1 = $dbh1->selectall_arrayref($initialprobe);
my $probe2 = $dbh2->selectall_arrayref($initialprobe);
my @totest = ();
my $maxdiff = 0;

for (0.. @{$probe1} -1) {
    if ($probe1->[$_]->[2] ne $probe2->[$_]->[2]) {
        push @totest, $probe1->[$_]->[0];
        $maxdiff += $probe1->[$_]->[1];
    }
}
my $get_probe_sig = qq{SELECT signature from shadow_table where span = ?};
my $sth1 = $dbh1->prepare($get_probe_sig);

for (@totest) {
    $sth1->execute($_);
    my $columns = $sth1->fetchall_arrayref();
    my $query = qq{SELECT PK FROM shadow_table WHERE span = $_ AND
    signature NOT IN (}
    . (join(",", map {"'$_->[0]'"} @$columns ))
    . ")";
    my $sth2 = $dbh2->prepare($query);
    $sth2->execute();
    while (my $different = $sth2->fetchrow_arrayref()) {
        print "$different->[0]\t";
    }
}

print "\n";

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.