Patent ID: 12189653

DETAILED DESCRIPTION

Various technologies pertaining to a geo-replication computing architecture are now described with reference to the drawings, where like reference numerals are used to refer to like elements throughout. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of one or more aspects. It may be evident, however, that such aspect(s) may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to facilitate describing one or more aspects. Further, it is to be understood that functionality that is described as being carried out by certain system components may be performed by multiple components. Similarly, for instance, a component may be configured to perform functionality that is described as being carried out by multiple components.

Moreover, the term “or” is intended to mean an inclusive “or” rather than an exclusive “or.” That is, unless specified otherwise, or clear from the context, the phrase “X employs A or B” is intended to mean any of the natural inclusive permutations. That is, the phrase “X employs A or B” is satisfied by any of the following instances: X employs A; X employs B; or X employs both A and B. In addition, the articles “a” and “an” as used in this application and the appended claims should generally be construed to mean “one or more” unless specified otherwise or clear from the context to be directed to a singular form.

Further, as used herein, the terms “component,” “system,” and “module” are intended to encompass computer-readable data storage that is configured with computer-executable instructions that cause certain functionality to be performed when executed by a processor. The computer-executable instructions may include a routine, a function, or the like. It is also to be understood that a component or system may be localized on a single device or distributed across several devices. Further, as used herein, the term “exemplary” is intended to mean serving as an illustration or example of something and is not intended to indicate a preference.

Described herein are various technologies pertaining to a geo-replication computing architecture, where updates to a database are to be replicated across computing systems that belong to the architecture. In contrast to conventional approaches for updating a database record in such an architecture, a first computing system, when transmitting an indication to a second computing system that an update to a record is to be made to the database record, transmits a partial vector clock for the record to the second computing system (rather than a full vector clock). Transmittal of the partial vector clock conserves network resources when compared to the conventional approaches. In addition, rather than a full vector clock being stored in metadata for each record, a single global change number (GCN) is stored in the metadata, resulting in a reduction in use of disk space when compared to conventional approaches. Still further, a computing system in the geo-replication architecture can construct local vector clocks and remote vector clocks based upon a relatively small amount of information that is maintained in memory; accordingly, the computing system need not read from record metadata stored on disk when constructing vector clocks, resulting in updates being written more quickly to the database. These features are described in greater detail below.

Referring now toFIG.1, a functional block diagram of a geo-replication computing architecture100is illustrated. The architecture100includes computing system A102, computing system B104, and computing system C106, where the computing systems102-106are each in communication with one another. Thus, in the architecture100, the computing systems102-106are fully connected.

The computing systems102-106store and update a database that is to be replicated across the computing systems102-106, where updates to the database occur asynchronously. Specifically, computing system A includes a first disk108, computing system B includes a second disk110, and computing system C includes a third disk112. The disks108-112store a database114that is replicated across the computing systems102-106; thus, when the database114is updated on the first disk108, the database114is to be updated on the second disk110and the third disk114. While the computing architecture100is illustrated as including the computing systems102-106, it is to be understood that the computing architecture100can include many more than three computing systems, where the computing systems can be located in different geographic regions.

The task of asynchronously updating the database114across the computing systems102-106such that the database114is replicated across the computing systems102-106is non-trivial. For example, first computing devices116-118are in communication with computing system A102, where the first computing devices116-118and computing system A102are co-located in a first geographic region. Computing system A can receive requests to update the database114from any of the computing devices in the first computing devices116-118at arbitrary times. Further, second computing devices120-122are in communication with computing system B104, where the second computing devices120-122and computing device B104are co-located in a second geographic region. Computing system B104can receive requests to update the database114from any of the computing devices in the second computing devices120-122at arbitrary times. Still further, third computing devices124-126are in communication with computing system C106, where the third computing devices124-126and computing system C106are co-located in a third geographic region. Computing system C106can receive requests to update the database114from any of the computing devices in the third computing devices124-126at arbitrary times.

In the computing architecture100, there is no predefined sequence that identifies an order that the computing systems102-106are to update the database114. Thus, when computing system A102receives an update request from one of the first computing devices116-118, computing system A102updates the database114in the first disk108and then transmits an update notification to computing system B104and computing system C106. Similarly, when computing system B104receives an update request from one of the second computing devices120-122, computing system B updates the database114in the second disk110and then transmits an update notification to computing system A102and computing system C106. In the architecture100, then, conflicts may arise, where two computing systems update a same portion of the database114at approximately the same time.

As noted above, vector clocks have been used as a mechanism to detect conflicts in geo-replication architectures. For a computing architecture that has N computing systems, the vector clock has N Global Change Numbers (GCNs), with one GCN for each computing system in the architecture. A GCN identifies a computing system and is further indicative of when a computing system that corresponds to the GCN most recently initiated an update for the record. For instance, the GCN includes a timestamp. In another example, the GCN is a value that is incremented each time that the computing system updates the record. Conventionally, each computing system in a geo-replication architecture stores a vector clock for each record of a database that is to be replicated across several computing systems, where a vector clock is stored on disk as metadata for a record. Then, when a computing system updates a record in the database, the computing system transmits the vector clock stored for that record to the other computing systems in the architecture. When a computing system receives a vector clock from another computing system, the computing system retrieves the vector clock stored on the disk of the computing system and compares the two vector clocks (the vector clock received from the another computing system and the vector clock retrieved from disk) to determine whether an update conflict exists with respect to the record. The inventors identified several technical deficiencies with this approach: 1) transmittal of a vector clock for each update consumes a relatively large amount of network resources, particularly when updates are frequent and there are a relatively large number of computing systems in the architecture; 2) storing a vector clock for each record in a database consumes a relatively large amount of space in disk; and 3) reading a vector clock from disk each time an update request is received results in slow writes to disk, as switching between reads and writes to disk is inefficient.

Technologies described herein address these technical deficiencies in geo-replication architectures, such as the architecture100depicted inFIG.1. As illustrated inFIG.1, the database114includes M records128-130. Referring briefly toFIG.2, a schematic200depicting the database114as stored in the first disk108at a particular point in time is illustrated. The database114includes the M records128-130and metadata stored in correlation with the M records128-130. Specifically, the database114includes first metadata202stored in correlation with the first record128and Mth metadata204stored in correlation with the Mth record130. The metadata for a record includes a GCN that identifies a computing system from amongst the computing systems102-106that initiated a most recent update to the record.

Therefore, the first metadata202includes a GCN that identifies a computing system that initiated a most recent update to the first record128and further includes information that is indicative of when the computing system identified by the GCN initiated the update. In an example, when computing system A102updated the first record128based upon an update request received from a computing device in the first computing devices116-118, the GCN stored in the first metadata202identifies computing system A102(e.g., GCN_A). The Mth metadata204includes a GCN that identifies a computing system that initiated a most recent update to the Mth record130and further includes information that is indicative of when the computing system identified by the GCN initiated the update. For instance, when computing system A102updated the Mth record130based upon an update notification from computing system B104, the GCN stored in the Mth metadata204identifies computing system B102(e.g., GCN_B).

The records128-130further include respective keys206-208and respective data210-212that can be updated. Thus, the M records128-130have M keys206-208and M pieces of data210-212that can be updated by computing system A102, where computing system A102can update the data in the records128-130in response to receiving an update request from a computing device in the first computing devices116-118or in response to receiving an update notification from another computing system in the architecture100.

In contrast to conventional approaches used for conflict detection in geo-replication architectures, a single GCN is stored in the metadata for a record. Thus, the first metadata202includes a single GCN and the Mth metadata204includes a single GCN. In conventional technologies, the first metadata202includes an entire vector clock and the Mth metadata204includes an entire vector clock. This can be a relatively large reduction in an amount of disk storage needed to store the database114, particularly when vector clocks are relatively long (e.g., when there are a large number of computing systems in the geo-replication architecture100). In some embodiments described herein, however, the database114can include full vector clocks for each record.

Returning toFIG.1, operation of computing system A102is now set forth with respect to updating the database114in the first disk108, transmitting update notifications to other computing systems in the architecture100, and receiving update notifications from other computing systems in the architecture100and checking for update conflicts. Computing system A102includes a processor132and memory134, where the memory134stores instructions that are executed by the processor132and information that is accessible to the processor132. Computing system A can receive a request to update a record (e.g., the first record128) in the database114from a computing device in the first computing devices116-118. Based upon the request, computing system A102can update the first data210in the first record128and then transmit a partial vector clock for the first record128to computing system B104and computing system C106. The partial vector clock includes only values that have changed since the last time that computing system A102transmitted a partial vector clock for the first record128to computing system B104and computing system C106.

In an example, at time T0, the local vector clock for the first record128at computing system A102is [A100; B100; C100]. At time T1, computing system A102updates the first data210in the first record128, updates the local vector clock to be [A101; B100; C100], and transmits a first update notification to the computing systems104-106. The first update notification includes a partial vector clock [A101] and the update made to the first data210in the first record128. The partial vector clock is limited to include values that have changed since the last time that computing system A102transmitted a partial vector clock for the first record128. In an embodiment, computing system A102further updates the GCN in the first metadata202to be A101. At time T2, computing system A102receives a second update notification from computing system B104(where the update notification includes a partial vector clock from computing system B104); based upon the second update notification, computing system A102updates the local vector clock to be [A101; B101; C100]. In an embodiment, computing system A102updates the GCN in the first metadata202to be B101. At time T3, computing system A102receives an update request from computing device116, updates the first data210in the first record128based upon such update request, and updates the local vector clock for the first record128to be [A102; B101; C100]. Computing system A102then transmits a third update notification to the computing systems104-106, where the third update notification includes the partial vector clock [A102; B101] and the update made to the first data210. The partial vector clock includes A102and B101(but not C100), as A102and B101are changes when compared to corresponding values in the last partial vector clock for the first record128transmitted by computing system A102(i.e., A101to A102and B100to B101).

Transmitting partial vector clocks amongst computing systems in the architecture100rather than full vector clocks conserves network resources, particularly when the computing architecture100includes a relatively large number of computing systems. In addition, a first computing system in the architecture100that receives a partial vector clock from a second computing system can accurately reconstruct the full (remote) vector clock of the second computing system based upon the partial vector clock and state information that is indicative of previous vector clock values transmitted by the second computing system.

Computing system A102(and additionally the computing systems104-106) can also store information in memory134that allows for local and/or remote vector clocks to be retrieved, computed or estimated without reading data from the disk108, thereby allowing for updates to be written more quickly to the disk108when compared to conventional approaches (as frequent reads between writes result in writes being completed more slowly). The memory134includes local vector clock information136that includes information that can be used to estimate local vector clocks for records in the database114. As described above, metadata for a record may not include a full vector clock for the record, but instead may include a single GCN that identifies the computing system that initiated the update for the record and includes data that is indicative of when the update for the record was made. Instead of maintaining a per-record vector clock, the local vector clock information136stored in the memory134includes vector clock information for a key in the database114.

In an example, the computing system A receives an update notification for a record from another computing system in the architecture100. For instance, computing system A102receives an update notification from computing system B104that indicates that the first record128is to be updated in the database114stored in the first disk108. The update notification includes the first key206for the first record128(FIG.2), a partial vector clock that includes a GCN of computing system B104that is indicative of when computing system B104updated the database114in the second disk110, and data that is to replace the first data210in the first record128(or a computer-executable instruction that causes the first data210to be updated in the first record128). The partial vector clock can also include GCNs of other computing systems that have relatively recently updated the first record128in their respective disks (where such updates occurred prior to computing system B104transmitting the update notification).

To detect a potential conflict with respect to the received update request, the computing system A102compares a remote vector clock for the first record128corresponding to computing system B to an estimate of the local vector clock for the first record128. The computing system A102includes a remote vector clock generator module142. The remote vector clock generator module142computes the remote vector clock for the first record128, where the remote vector clock for the first record128is an estimate of the vector clock of computing system B104for the first record128. In various embodiments, remote vector clocks for all records in the database114can be retained in memory134as remote vector clock information140. In such embodiments, the remote vector clock of computing system B for the first record128can be computed by retrieving the existing remote vector clock from the remote vector clock information140and updating the remote vector clock based upon the partial vector clock included in the update notification.

It can be ascertained, however, that it may be impractical to retain remote vector clocks for all records in the database114and for all computing systems in the architecture100. Remote vector clocks of computing systems that have recently updated records can be maintained in a cache (e.g., included in the remote vector clock information140retained in the memory134). Therefore, in this example, when computing system B104recently transmitted a first update notification to computing system A102for the first record128, computing system A102computes a remote vector clock for the first record128and computing system B104and temporarily stores the remote vector clock in cache. When computing system B104transmits a second update notification to computing system A102for the first record128, computing system A102retrieves the remote vector clock from the cache and updates the remote vector clock based upon information in the second update notification. Computing system A102can then store the updated remote vector clock in the cache. When computing system B104has not recently transmitted an update notification to computing system A102for the first record128the remote vector clock for the first record128for computing system B may not be stored in cache. In such instances, computing system A102can retrieve the remote vector clock from remote vector clock information141that is stored on the first disk108.

The cache is relatively small, however, and therefore oftentimes a local vector clock for a record that is to be updated will not be stored in the cache. The local vector clock information136can be employed by computing system A102to generate estimates of local vector clocks for the records128-130in the database114. The local vector clock information136, in summary, includes local vector clock information for different “buckets” of keys, where a bucket of keys includes several (but not all) keys of the records128-130of the database114. While not shown, the memory134of computing system A102includes a hash function, and the keys206-208of the records128-130are provided as input to the hash function. The hash function outputs hash values for the keys206-208, where the hash function can output a same hash value for several keys, thus forming several buckets of keys. The local vector clock information136can include these hash values and respective local vector clocks assigned to the hash values. In another example, the local vector clock information136includes a mapping between keys and buckets of keys, as well as respective local vector clocks assigned to the buckets of keys. Therefore, in an example, when the database114includes 1000 records, and each bucket of keys includes 10 keys, the local vector clock information136can include 100 local vector clocks (rather than 1000 local vector clocks). Using this approach, the local vector clocks assigned to the buckets of keys can be retained in the memory134. The number of buckets of keys (and keys to include in the buckets) can be determined empirically and selected to minimize false positive conflicts subject to a constraint imposed by available space in the memory134.

The local vector clock generator module138can generate estimates of local vector clocks in response to receipt of update notifications from computing systems in the architecture100. Continuing with the example above where computing system A102receives an update notification for computing system B104to update the first record128, the local vector clock generator module138identifies the first key206in the update notification and identifies a remote vector clock that corresponds to the first key206in the local vector clock information136. In an example, the local vector clock generator module136provides the first key206as input to the hash function, and the hash function outputs a hash value for the first key206. The local vector clock generator module138obtains the local vector clock assigned to the hash value from the local vector clock information136. The local vector clock is an estimate of the local vector clock for the first record128. Effectively, the estimate of the local vector clock is a summary of the local vector clocks for all keys belonging to the same key bucket as the first key206.

Responsive to determining that no conflict exists with respect to the update (e.g., based on consistency between the updated remote vector clock for the first record128and the estimate of the local vector clock for the first record128), the local vector clock generator module138updates the local vector clock assigned to the hash value. The local vector clock generator module138updates the local vector clock based upon GCN(s) identified in the partial vector clock in the update notification. By way of example, the local vector clock generator module138updates the local vector clock assigned to the hash value. Computing system A can further update the metadata202associated with the first record128to include the GCN of computing system B with respect to the first record128.

Pursuant to an example, a key bucket can include the first key206and the Mth key208. In the local vector clock information136, at time T0, the local vector clock for the key bucket can be [A150; B155; C160]. At time T1, computing system A102receives a first update notification from computing system B104, where the first update notification includes the first key206, the partial vector clock [B158], and data that is to be included in the first record128. The local vector clock generator module138identifies the key bucket based upon the first key206included in the first update notification, retrieves the local vector clock from the local vector clock information136that is assigned to the key bucket, and updates the local vector clock to be [A150; B158; C160]. Subsequently, at time T2, computing system A102receives a second update notification from computing system C106, where the second update notification includes the Mth key208, the partial vector clock [C165], and data that is to be included in the first record128. The local vector clock generator module138identifies the key bucket based upon the Mth key208included in the second update notification, retrieves the local vector clock [A150; B158; C160] that is assigned to the key bucket, and updates the local vector clock to be [A150; B158; C165]. Therefore, the remote vector clock included in the remote vector clock information140includes GCNs that correspond to updates made to two different records having two different keys.

Computing system A102further includes a conflict detector module144that detects update conflicts based upon estimated local vector clocks output by the local vector clock generator module138and remote vector clocks output by the remote vector clock generator module142. An update conflict occurs when two or more computing systems in the architecture have updated a record without knowledge that other computing system(s) have updated the record. Put differently, an update conflict occurs when two or more computing systems update a same record at approximately a same point in time. Continuing with the example where computing system A102receives the update notification from computing system B104that computing system B104has updated the first record128, the conflict detector module144retrieves the estimated local vector clock for the first record128(e.g., a local vector clock for a key bucket that includes a key assigned to the first record128, as described above). The conflict detector module144retrieves and updates the remote vector clock of computing system B for the first record128(included in the remote vector clock information140or the remote vector clock information141, as described above) in response to computing system A102receiving the update notification.

The conflict detector module144performs a comparison between the estimated local vector clock and the (updated)remote vector clock and outputs an indication as to whether a potential conflict exists with respect to the update notification based upon the comparison. When each value in the estimated local vector clock is less than or equal to its corresponding value in the remote vector clock, the conflict detector module144outputs an indication that no conflict exists with respect to the update notification. In an example, the estimated local vector clock is [A0; B158; C0], while the remote vector clock o is [A150; B158; C160]. Because each value in the estimated local vector clock is less than or equal to its corresponding value in the remote vector clock, the conflict detector module144outputs an indication that no conflict has been detected. Thereafter, computing system A102can write the update included in the update notification to the first disk108. It is noted that computing system A102can write to the first disk108to update the database114without having to read from the first disk108to identify a potential conflict; this greatly increases speed at which updates can be written to the database114stored in the first disk108.

Alternatively, when the conflict detector module144determines that one value in the estimated local vector clock is greater than its corresponding value in the remote vector clock, the conflict detector module144can output an indication that a potential conflict exists. Because the determination of a conflict is based upon estimated local vector clocks (e.g., vector clocks pertaining to key hash buckets), it is possible that the detected conflict is a false positive (e.g., the conflict detector module144has detected a conflict where no conflict exists). In an example, the estimated local vector clock for a key bucket pertaining to a record is [A150; B150; C10], while the remote vector clock of the record is [A150; B140; C10]. In this case, the conflict detector module144determines that a potential conflict exists, as B150is greater than B140. In such a case, the conflict detector module144can refine the estimated local vector clock by retrieving the GCN assigned to the first record128from the first metadata202.

It is noted that the conflict detector module144need not read the entirety of the first record128from the first disk108; instead, the conflict detector module144can read only the first metadata202and retrieve the GCN included therein in connection with refining the estimated local vector clock. In an example, the GCN included in the first metadata202is B130; therefore, the conflict detector module144can refine the estimated local vector clock to be [A150; B130; C10]. The conflict detector module144performs a comparison between the (refined) estimated local vector clock ([A150; B130; C10]) and the remote vector clock ([A150; B150; C10]); in this example, there is actually no conflict, and computing system A102updates the first record128based upon data included in the update notification received from computing system B104. When the conflict detector module144confirms that a conflict does in fact exist, conventional conflict resolution techniques can be employed (e.g., the first data210can be read from the database114and a merge operation can be performed with respect to the first data210and the data included in the updated notification).

Returning briefly to construction of estimated local vector clocks, a similar approach for constructing estimated local vector clocks is employed by the local vector clock generator module138to generate partial vector clocks for records when computing system A102updates a record in the database114in response to an update request from a computing device in the first computing devices116-118. In an example, computing system A102receives an update request for the first record128from the computing device116. The update request identifies a key for the first record128. The local vector clock generator module138identifies a key bucket corresponding to the key, and retrieves the vector clock corresponding to the key bucket. Computing system A102updates the first record128in the database114and adds a GCN for computing system A102to the first metadata202for the first record128(indicating that computing system A is the computing system in the architecture100that initiated the update and an approximate time when the update was made). The local vector clock generator module138constructs a partial vector clock based upon the vector clock corresponding to the identified key bucket, and then updates the partial vector clock to include the GCN for computing system A102. Computing system A102then transmits the partial vector clock to other computing systems in the architecture100.

While the description above has referred to operations of computing system A102, it is understood that computing system B104and computing system C106also perform such operations in response to receiving update requests from computing devices and/or in response to receiving update notifications from other computing systems in the architecture. Therefore, computing system B104and computing system C106include local vector clock information, a local vector clock generator module, remote vector clock information, a remote vector clock generator module, and a conflict detector module. As noted previously, the computing architecture100exhibits various technical advantages over conventional computing architectures, including reduction in disk space for storing metadata for records in a geo-replicated database, reduction in use of network bandwidth when transmitting vector clock information between computing systems, and faster writing of updates to the database114stored in the disks108-112.

Turning now toFIG.3, a schematic that depicts content of the local vector clock information136is presented. The local vector clock information136includes identifiers for key buckets302-304, where each key bucket represents a respective (non-overlapping) set of keys. That is, a key is included in one and only one key bucket. As described above, a hash function can be employed to place keys into key buckets. The local vector clock information136also includes local vector clocks306-308assigned to the respective key buckets302-304.

With reference toFIG.4, a functional block diagram that depicts operation of the local vector clock generator module138is presented. The local vector clock generator module138receives an update notification from computing system B104, where the update notification includes the first key206and a partial vector clock. The local vector clock generator module138identifies the first key206in the update notification and identifies an appropriate key bucket based upon the first key206. As indicated above, the local vector clock generator module138can provide the first key206as input to the hash function and can identify the first key bucket302based upon a hash value for the first key206output by the hash function.

The local vector clock generator module138retrieves the local vector clock306for the first key bucket302from the local vector clock information140. The local vector clock306includes N values for the N computing systems in the architecture100. If no conflict has been detected by the conflict detector module144between the partial vector clock and the local vector clock306, the local vector clock generator module138updates the local vector clock306to include values identified in the partial vector clock

Now referring toFIG.5, a functional block diagram that illustrates operation of the conflict detector module144in response to receipt of the update notification from computing system B104is shown. The conflict detector module144retrieves the estimated local vector clock306and a remote vector clock502(e.g., from the remote vector clock information140) and performs a comparison between the two clocks. In the vast majority of situations, the conflict detector module144determines that there is no update conflict with respect to the update notification. In such case, the update is written to the database114in the first disk108without requiring any reading from the first disk108. When the conflict detector module144detects a conflict based upon the comparison, the conflict detector module144confirms the conflict by reading the GCN included in the metadata for the record that is being updated and updating the estimated local vector clock306to include such GCN. For instance, when the first record128is to be updated and the conflict detector module144detects a potential conflict, the conflict detector module144obtains the GCN from the first metadata206and updates the estimated local vector clock306to include such GCN. The conflict detector module144can confirm whether or not a conflict exists by performing a comparison between the updated estimated local vector clock306and the remote vector clock502. When the conflict detector module144determines that the initial conflict determination was a false positive, the conflict detector module144can output an indication that there is no update conflict for the update notification and computing system A102writes the update to the first record128. In contrast, when the conflict detector module144confirms that a conflict exists based upon the aforementioned comparison, the conflict detector module144initiates a conventional conflict resolution procedure (e.g., by performing a merge with respect to data stored in the first record128and information included in the update notification).

FIGS.6-8illustrate exemplary methodologies relating to conflict detection in geo-replication architectures. While the methodologies are shown and described as being a series of acts that are performed in a sequence, it is to be understood and appreciated that the methodologies are not limited by the order of the sequence. For example, some acts can occur in a different order than what is described herein. In addition, an act can occur concurrently with another act. Further, in some instances, not all acts may be required to implement a methodology described herein.

Moreover, the acts described herein may be computer-executable instructions that can be implemented by one or more processors and/or stored on a computer-readable medium or media. The computer-executable instructions can include a routine, a sub-routine, programs, a thread of execution, and/or the like. Still further, results of acts of the methodologies can be stored in a computer-readable medium, displayed on a display device, and/or the like.

Referring solely toFIG.6, a method600performed by a computing system (e.g., computing system A102) in a geo-replication computing architecture is illustrated. The method600starts at602, and at604an update notification for a database record is received from a remote computing system that is included in the geo-replication architecture. The update notification includes a value for a key for the database record, a partial vector clock, and an update to the database record that has been made by the remote computing system. The partial vector clock includes a GCN generated by the remote computing system. The partial vector clock may include a second GCN generated by a second remote computing system that previously updated the database record at the second remote computing system.

At606, an estimated local vector clock for the database record is retrieved or constructed based upon a value of a key in the update notification. At608, a remote vector clock for the database record is generated based upon the key and the partial vector clock included in the update notification.

At610, a comparison is performed between the estimated local vector clock constructed at606and the remote vector clock constructed at608. At612, a determination is made as to whether a conflict may exist with respect to the update notification based upon the comparison. When it is determined at612that a conflict may exist, the method600proceeds to614, where metadata assigned to the database record is read from computer-readable storage (e.g., a solid state drive or a hard disk drive) that stores the database. The metadata includes a GCN that identifies a computing system that most recently updated the database record. The GCN also is indicative of when the computing system updated the database record.

At616, the estimated local vector clock is refined based upon the retrieved GCN, and at618the remote vector clock constructed at606is compared with the refined local vector clock constructed at616. At620, a determination is made as to whether the conflict remains based upon the comparison performed at618. When it is determined that the conflict remains, at622a conflict resolution routine is executed. Subsequent to executing the conflict resolution routine, the method600proceeds to623where a determination is made whether the update notification indicates that an update is to be made to the record in the database. Furthermore, when it is determined at either612or620that there is no conflict, the method600proceeds to623. If it is determined at623that an update is to be made to the record, the method proceeds to624, and the record in the database is updated based upon content of the update notification received at604and the methodology completes at626. If it is determined that an update is not to be made, the method proceeds to626and completes.

Turning toFIG.7, a flow diagram depicting a method700for constructing an estimated local vector clock (e.g., act606of method600) is illustrated. The method700starts at702, and at704a key bucket in a table in memory is identified, where the table includes identifiers for key buckets and local vector clocks for those key buckets. The key bucket identifiers can be or be based upon output of a hash function when provided with keys as input. The key bucket is identified based upon the key value in the update notification received at604of the method600.

At706, the local vector clock assigned to the key bucket is retrieved from the table. At708, the local vector clock retrieved at706is returned as the estimated local vector clock for the database record. The method700completes at712.

Reference is now made toFIG.8, which depicts a method800for transmitting a partial vector clock to remote computing systems in a geo-replication architecture. In an example, the method800is performed by a local computing system in the geo-replication architecture that is in network communication with the remote computing systems. The method800starts at802, and at804a record of a database stored in computer-readable storage of the local computing system is updated based upon an update request received by the local computing system. The update request can be received from a computing device that is in a geographic region (e.g., city, state, country, etc.) with the local computing system. The update request can alternatively be received from another computing system in the geo-replication architecture (e.g., a computing system in a different geographic region than the local computing system). At806, a partial vector clock is computed or retrieved from an accumulated GCN that is associated with the record and is stored in memory of the local computing system. In exemplary embodiments, the accumulated GCN can include GCNs for all computing systems from which updates to the record have been received since a last time the local computing system transmitted a partial vector clock pertaining to the record. At808a determination is made whether the update to the record must be transmitted to other remote computing systems in the geo-replication architecture. For instance, if the update request received at804is from a computing system in the geo-replication architecture in a region different from the local computing system, it is determined that the update to the record need not be transmitted to remote computing systems, and the methodology800proceeds to814, whereupon the method800ends. If the update request received at804is from a computing device in the same geographic region as the local computing system, it is determined at808that the update to the record must be transmitted to other remote computing systems (e.g., outside of the geographic region) in the geo-replication architecture. If it is determined at808that the update to the record must be transmitted to remote computing systems, the method800proceeds to810, and the accumulated GCN is transmitted as a partial vector clock for the record. The accumulated GCN/partial vector clock is cleared (e.g., re-initialized or set to zero)812, and the method800completes at814.

An example is now set forth by way of illustration, and not by limitation. The accumulated GCN for a record can initially be empty (cleared). The following GCNs can be received by the local computing system where A represents the local computing system and B-D represent remote computing systems (e.g., computing systems in different geographic regions than A): B20, C30, B30, A10, B40, at times T0, T1, T2, T3, T4, respectively. At T0, A updates the accumulated GCN, denoted by InMem VC, to InMem VC=(B20), and A does not transmit the partial vector clock (e.g., because B originated the update to the record). At T1, A updates InMem VC to InMem VC=(B20, C30), and A does not transmit the partial vector clock. At T2, A updates InMem VC to InMem VC=(B30, C30), and A does not transmit the partial vector clock. At T3, A updates InMem VC to InMem VC=(A10, B30, C30), A sends the partial vector clock (A10, B30, C30) to remote computing systems in the geo-replication architecture (e.g., computing systems B-D), and A then clears the partial vector clock, whereupon InMem VC=(empty). At T4, A updates InMem VC to InMem VC=(B40), and does not transmit the partial vector clock.

Referring now toFIG.9, a high-level illustration of an exemplary computing device900that can be used in accordance with the systems and methodologies disclosed herein is illustrated. For instance, the computing device900may be used in a geo-replication architecture, where the computing device900can transmit partial vector clocks to other computing devices in the geo-replication architecture. By way of another example, the computing device900can be used in a system that detects conflicts in a geo-replication architecture. The computing device900includes at least one processor902that executes instructions that are stored in a memory904. The instructions may be, for instance, instructions for implementing functionality described as being carried out by one or more components discussed above or instructions for implementing one or more of the methods described above. The processor902may access the memory904by way of a system bus906. In addition to storing executable instructions, the memory904may also store vector clocks, partial vector clocks, GCNs, a table that includes identifiers for key buckets and local vector clocks assigned to the key buckets, etc.

The computing device900additionally includes a data store908that is accessible by the processor902by way of the system bus906. The data store908may include executable instructions, records of a database, metadata assigned to the records, etc. The computing device900also includes an input interface910that allows external devices to communicate with the computing device900. For instance, the input interface910may be used to receive instructions from an external computer device, from a user, etc. The computing device900also includes an output interface912that interfaces the computing device900with one or more external devices. For example, the computing device900may display text, images, etc. by way of the output interface912.

It is contemplated that the external devices that communicate with the computing device900via the input interface910and the output interface912can be included in an environment that provides substantially any type of user interface with which a user can interact. Examples of user interface types include graphical user interfaces, natural user interfaces, and so forth. For instance, a graphical user interface may accept input from a user employing input device(s) such as a keyboard, mouse, remote control, or the like and provide output on an output device such as a display. Further, a natural user interface may enable a user to interact with the computing device900in a manner free from constraints imposed by input device such as keyboards, mice, remote controls, and the like. Rather, a natural user interface can rely on speech recognition, touch and stylus recognition, gesture recognition both on screen and adjacent to the screen, air gestures, head and eye tracking, voice and speech, vision, touch, gestures, machine intelligence, and so forth.

Additionally, while illustrated as a single system, it is to be understood that the computing device900may be a distributed system. Thus, for instance, several devices may be in communication by way of a network connection and may collectively perform tasks described as being performed by the computing device900.

Various functions described herein can be implemented in hardware, software, or any combination thereof. If implemented in software, the functions can be stored on or transmitted over as one or more instructions or code on a computer-readable medium. Computer-readable media includes computer-readable storage media. A computer-readable storage media can be any available storage media that can be accessed by a computer. By way of example, and not limitation, such computer-readable storage media can comprise RAM, ROM, EEPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage devices, or any other medium that can be used to carry or store desired program code in the form of instructions or data structures and that can be accessed by a computer. Disk and disc, as used herein, include compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disk, and Blu-ray disc (BD), where disks usually reproduce data magnetically and discs usually reproduce data optically with lasers. Further, a propagated signal is not included within the scope of computer-readable storage media. Computer-readable media also includes communication media including any medium that facilitates transfer of a computer program from one place to another. A connection, for instance, can be a communication medium. For example, if the software is transmitted from a website, server, or other remote source using a coaxial cable, fiber optic cable, twisted pair, digital subscriber line (DSL), or wireless technologies such as infrared, radio, and microwave, then the coaxial cable, fiber optic cable, twisted pair, DSL, or wireless technologies such as infrared, radio and microwave are included in the definition of communication medium. Combinations of the above should also be included within the scope of computer-readable media.

Alternatively, or in addition, the functionally described herein can be performed, at least in part, by one or more hardware logic components. For example, and without limitation, illustrative types of hardware logic components that can be used include Field-programmable Gate Arrays (FPGAs), Program-specific Integrated Circuits (ASICs), Program-specific Standard Products (ASSPs), System-on-a-chip systems (SOCs), Complex Programmable Logic Devices (CPLDs), etc.

What has been described above includes examples of one or more embodiments. It is, of course, not possible to describe every conceivable modification and alteration of the above devices or methodologies for purposes of describing the aforementioned aspects, but one of ordinary skill in the art can recognize that many further modifications and permutations of various aspects are possible. Accordingly, the described aspects are intended to embrace all such alterations, modifications, and variations that fall within the spirit and scope of the appended claims. Furthermore, to the extent that the term “includes” is used in either the detailed description or the claims, such term is intended to be inclusive in a manner similar to the term “comprising” as “comprising” is interpreted when employed as a transitional word in a claim.