System and method for implementing cache consistent regional clusters

• US 9,477,598 B2
• Filed: 09/04/2015
• Issued: 10/25/2016
• Est. Priority Date: 02/26/2013
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Song, Yee Jiun, Ajoux, Philippe Vincent, Li, Harry C., Sobel, Jason, Kumar, Sanjeev, Nishtala, Rajesh
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): BIBBEE, JARED M
• Application Number:
  US14/846,409
• Publication Number:
  US 20150378894A1
• Time in Patent Office: 417 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: G06F 2212/1032 Reliability improvement, data loss prevention, degraded operation etc
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

When multiple regional data clusters are used to store data in a system, maintaining cache consistency across different regions is important for providing a desirable user experience. In one embodiment, there is a master data cluster where all data writes are performed, and the writes are replicated to each of the slave data clusters in the other regions. Appended to the replication statements are invalidations for cache values for the keys whose values have been changed in the master data cluster. An apparatus in the master data cluster logs replication statements sent to the slave databases. When a slave database fails, the apparatus extracts the invalidations intended for the failed database and publishes the invalidations to a subscriber in the region of the failed database. The subscriber sends the invalidations to the local caches to cause stale data for those keys to be deleted from the caches.

Claims

1. An apparatus located in a first region of a system, the apparatus comprising:

a memory configured to store database updates performed on a first database cluster in the first region, wherein each database update corresponds to a key; and

a processor configured to;

for each database update,

generate an update statement to update the key in a replica database in a second region remote from the first region, and

append the update statement with a first invalidation associated with the key to generate a modified update statement,

transmit the modified update statements to the replica database to cause the replica database to (a) update the keys in the replica database and (b) execute the first invalidations on caches in the second region,

when the replica database has failed and cannot respond to database updates,

extract the first invalidations from the modified update statements, and

publish a first subset of the first invalidations to a subscriber in the second region, wherein the first subset of the first invalidations are associated with keys having values stored in the replica database, wherein the subscriber is configured to send the first subset of the first invalidations to the caches in the second region to cause values stored in the caches for the keys to be deleted.

2. The apparatus of claim 1, wherein the processor extracts the first subset of the first invalidations from the database updates for publication upon receiving a signal that the replica database has failed.

3. The apparatus of claim 1, wherein databases in the system run a MySQL relational database management system, and MySQL replication statements are used to send the database updates to appropriate replica databases in the system.

4. The apparatus of claim 3, wherein a modified grammar for the MySQL replication statements is used to append the first invalidation to the database updates.

5. The apparatus of claim 1, wherein each database update further includes an optional second invalidation for a marker associated with the key, and wherein a given marker is generated and set in a regional pool in the second region by a web server in the second region upon receiving a write request for a given key to indicate that a given value stored in the caches and the replica database in the second region for the given key associated with the given marker may be stale.

6. The apparatus of claim 5, wherein the replica database, when operational, sends the first subset of the first invalidations to the caches in the second region to cause values stored in the caches for the keys to be deleted and sends the second invalidations to the regional pool to cause the marker to be deleted.

7. A system comprising:

a processor;

a master data cluster in a first region of the system;

a read-only data cluster in a second region remote from the first region, wherein the read-only data cluster is a replica of the master data cluster and comprises one or more slave databases;

an apparatus in the master data cluster, the apparatus configured to;

log database updates performed on the master data cluster, wherein each database update corresponds to a key,

for each database update,

generate an update statement to update the corresponding key in a slave database of the one or more slave databases, and

append the update statement with an invalidation associated with the corresponding key to generate a modified update statement,

transmit the modified update statements to the slave database to cause the slave database to (a) update the keys in the slave database and (b) execute the invalidations on caches in the second region, and

wherein, when the slave database has failed, select the invalidations from the modified update statements sent to the failed database for sending to a subscriber in the second region; and

at least one cache in the second region, wherein the subscriber in the second region is configured to send the invalidations received from the apparatus to the at least one cache to cause the stored values for the keys specified in the invalidations to be deleted from the at least one cache.

8. The system of claim 7, further comprising:

a regional pool in the second region configured for storing markers for keys, wherein each database update further includes an optional marker invalidation for a marker associated with a key for the database update;

one or more web servers in the second region, wherein the one or more web servers are configured to respond to write requests, and to generate a corresponding marker for each write request for storing in the regional pool that indicates to the one or more web servers that values for the associated keys stored in the at least one cache and the read-only data cluster may be stale.

9. The system of claim 8, wherein the one or more slave databases, when operational, sends the optional marker invalidation to the regional pool to cause the marker to be deleted.

10. The system of claim 7, wherein when the at least one cache does not have stored a value for a requested key, the at least one cache is configured to:

generate a token associated with the requested key, and

send the token to a web server requesting the value, and

further wherein after the web server retrieves the value for the requested key from the read-only data cluster and sends the value and the token to the at least one cache for setting the value in the cache, the cache is configured to discard the value if the token has been extinguished,

wherein the token is extinguished when a new value for the requested key has been set in the cache by another web server after the token has been generated and before the token is sent back to the cache by the web server.

11. The system of claim 10, wherein the web server receiving the token from the at least one cache is required to send the token to the cache when sending the value for setting in the cache.

12. The system of claim 7, wherein the one or more slave databases receive respective database updates with appended invalidations from the master database cluster, and further wherein the one or more slave databases, when operational, send the appended invalidations to the at least one cache in the second region to cause the stored values for the keys specified in the appended invalidations to be deleted from the at least one cache.

13. The system of claim 12, wherein databases in the master data cluster and the read-only data cluster run a MySQL relational database management system, and MySQL replication statements are used to send the database updates from the master data cluster to the replica databases in the system.

14. A computer-implemented method comprising:

logging database updates performed on a database in a master data cluster in a first region, wherein each database update corresponds to a key;

for each database update,

generating an update statement to update the key in a slave database in a replica data cluster in a second region remote from the first region, and

appending the update statement with an invalidation associated with the key to generate a modified update statement;

transmitting the modified update statements to the slave database to cause the slave database to (a) update the keys in the slave database and (b) execute the invalidations on caches in the second region to delete values associated with the corresponding keys;

publishing, from a module in the first region, the invalidations to a subscriber in the second region, wherein the invalidations are associated with the keys having values stored in the slave database in the second region, and further wherein the slave database has failed and cannot process the invalidations; and

sending, by the subscriber, the invalidations to the caches in the second region to cause to be deleted values stored in the caches for the keys.

15. The computer-implemented method of claim 14, further comprising upon receiving a signal that the slave database has failed, extracting the selected invalidations from the logged database updates.

16. The computer-implemented method of claim 14, wherein each database update further includes an optional marker invalidation for a marker associated with the key, wherein the marker is generated by a web server in the second region upon receiving a write request from a client, and the web server sets the marker in a regional pool in the second region to indicate to one or more web servers in the second region that values for the associated keys in the caches and the slave database in the second region may be stale.

17. The computer-implemented method of claim 16, wherein the slave database, when operational, sends the optional marker invalidation to the regional pool to cause the marker to be deleted.

18. The computer-implemented method of claim 14, wherein databases in the master data cluster and the replica data cluster run a MySQL relational database management system, and MySQL replication statements are used to send the database updates from the master data cluster to the replica databases in the system.

19. The computer-implemented method of claim 14, further comprising:

receiving at one of the caches a request from a web server for a value for a given key;

upon determining that the value is not stored in the one of the caches, generating a token associated with the given key by the one of the caches;

sending the token to the web server;

setting the value for the given key upon receiving the token and the value from the web server if the token has not been extinguished;

otherwise, discarding the value for the given key.