You could be suffering from what is known as data drift.

QUERIES

This can happen if there are queries that are unsafe for replication.

One of the more common types is running UPDATE or DELETE using LIMIT. Using LIMIT on DML can work just fine on a Master. On a Slave, the rows selected (and perhaps certain ORDER BY choices) may not be the same set being updated or deleted as the set on the Master. See the MySQL Documentation for a Comprehensive Description of Unsafe Statements that can affect MySQL Replication.

Baron Schwartz once dealt with this and had to refactor his query to get around this

The following hypothetical scenario illustrates one way to introduce data drift:

BINLOGS

Master

• 20 DB Connections writing changes (INSERTs,UPDATEs,DELETEs)
• The I/O thread from a Slave has to serialize the SQL coming from the 20 DB Connections
• The serializing of the queries into the binary logs may be in an order different from when each DB Connection executed its change.
• sync_binlog set to 0 (default), which leaves the responsibility of flushing binlogs to disk in the hands of the OS

Slave

• I/O Thread reads binlog events in the order the Master wrote them
• SQL Thread executes binlog events in the order the Master wrote them

Observation

If binlogs are not flushed to Disk in a timely, predictable manner, any binlog events the Slave needs could easily be bypassed. This could cause data simply not exist on the Slave. Depending on the data recorded or not recorded, Replication's SQL Thread could break because of missing data or data that should be missing.

EPILOGUE

Not every Slave can be affected this way. Masters keep a list of all Slave I/O Threads and transmits binlog events to the Slave in order by ProcessID on the Master. I can see later slaves being victimized first.

If sync_binlog is indeed an issue, perhaps all Slaves have data drift and we just don't know of it yet.

The only way to tell is to download one of the following

• mk-table-checksum
• mk-table-sync

or

• pt-table-checksum
• pt-table-sync

and checksum everything on every Slave against the Master. You may find more data drift problems than you think. Just run the sync scripts to correct them.

CAVEAT

You suggested that network latency could be at issue. With binlogs not being flushed by the OS yet, any disconnect and reconnect of MySQL Replication due to latency or dropped packets is worth looking over as well. It could also be a major contributor to data drift.

Also to be noted is what network route the new Slave is communicating with back to the Master. If it is not the same route as the older Slaves (perhaps passing through a different switch, over public IP, etc.) needs to be investigated.

The Error Message you received

Last_SQL_Error: Could not execute Delete_rows event on table test.pruning; Can’t find record in ‘pruning’, Error_code: 1032; handler error HA_ERR_KEY_NOT_FOUND; the event’s master log mysql-bin.000002, end_log_pos 1448

This message can come up when doing a DELETE query with row-based replication. Unfortunately, it is one of the disadvantages to row-based replication:

• Disadvantages of row-based replication

RBR can generate more data that must be logged. To replicate a DML statement (such as an UPDATE or DELETE statement), statement-based replication writes only the statement to the binary log. By contrast, row-based replication writes each changed row to the binary log. If the statement changes many rows, row-based replication may write significantly more data to the binary log; this is true even for statements that are rolled back. This also means that taking and restoring from backup can require more time. In addition, the binary log is locked for a longer time to write the data, which may cause concurrency problems.

I have addressed something similar (error 1032 in my answer to MySQL master master replication, safe to delete rows on both masters?) where doing a DELETE query was the issue.

In your case, since the Slave is using STATEMENT, the row change is expected to be a precise match of PRIMARY KEYs between Master and Slave. On many occassions, it may not be the case. That is why error 1032 exists.

To play it safe,

• use binlog_format=ROW on both Master and Slave
• use binlog_format=MIXED on both Master and Slave
• use binlog_format=STATEMENT on both Master and Slave
• You could experiment with Master MIXED and Slave ROW. At the very least, avoid STATEMENT on the Slave if the Master is not STATEMENT.