US20220335034A1 - Multi-master architectures for distributed databases - Google Patents

Abstract

Data services for workloads are often provided with a service level agreement specifying various performance guarantees (e.g., latency, availability, scalability, and consistency). Single-master architectures, in which updates t the data set are constrained to a single server, may limit the fulfillment of some performance guarantees. Presented herein are multi-master architectures, in which the server set is partitioned into at least two masters are permitted to update the data set and at least one non-master that is not permitted to update the data set. Non-masters that receive a request to update the data set forward the request to a master server for application to the data set. A master that receives the request applies it to the data set and propagates the update to other master and non-master servers. Conflicting updates may be resolved through a variety of conflict resolution techniques, optionally designating one master server as a conflict resolution server.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS
• This application is a Divisional of U.S. patent application Ser. No. 16/207,176, filed on Dec. 2, 2018, which claims priority to U.S. Provisional Patent Application No. 62/668,226, filed on May 7, 2018, the entireties of which are incorporated herein by reference.
BACKGROUND
• Within the field of computing, many scenarios involve a distributed data service that processes data on behalf of various workloads. In such scenarios, the workloads are often constrained by a set of performance criteria, such as low latency, high availability, throughput, scalability to accommodate surges in demand, and/or consistency guarantees of various types and levels. The performance criteria for respective workloads are often formalized in a service level agreement, whereby the provider of the distributed data service provides a guarantee that the distributed data service will satisfy the performance criteria of the workload.
• The distributed data services are often configured to allocate resources to satisfy one or more performance criterion, such as the details of the service level agreement. A notable technique for maintaining a consistency guarantee for a workload involves the identification, among the distributed servers that process the workload, of a single master that is permitted to update the stored data of the workload. By limiting the updates to a single master, the distributed data service avoids the potential of data conflicts that might arise from writing data at multiple locations. The identification of a single master may also provide other advantages, such as a determinable upper bound on the delay in propagating updates across all of the other servers that process the workload, based on the calculable propagation delay from the master server to every other server. As another example, it may be advantageous to choose, as the single master, a server that is in proximity to an anticipated source of the updates, e.g., in order to reduce network transport delays and latency.
SUMMARY
• This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key factors or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.
• The designation of a single master as the sole server in the distributed data service that is permitted to alter the data of a workload may provide some advantages, but may also incur some disadvantages that may be significant for some workloads. As a first example, the single master may present a performance bottleneck; e.g., if write requests arrive at a faster rate than the master can process, writes may be unavoidably delayed. As a second example, latency not be reducible to a desired level, due to the propagation delays of the single master to the entire data set. For particularly latency-sensitive workloads, it may not be possible to identify any server as the single master that is capable of propagating updates over the entire distributed data set, because the rate of update propagation from a single server is unavoidably limited by the speed of light and the maximum achievable transmission rates of contemporary networking equipment. As a third example, the designation of a single server as the sole source of updates may create a single point of failure; e.g., if the single-master server encounters a failure or a network partition, all capability of reliable updates to the data set may have to be postponed until a substitute server is selected, provisioned, and ready to take over as a substitute single master.
• In order to alleviate the limitations of a single-master configuration of the data service, it may be desirable to permit the designation of multiple masters that are permitted to update the data set of a workload. While such designation may enable advances in the properties noted above (e.g., latency reduction, throughput, scalability, availability, and consistency), the designation of multiple masters may raise the prospect of data versioning conflicts, which, if undetected and unhandled, may compromise the integrity and logical validity of the data set.
• Presented herein are techniques for establishing a multi-master server set. In an embodiment, a server is configured to participate in a server set for a data set by receiving a designation selected from a designation set comprising a master of the data set and a non-master of the data set, wherein the server set includes at least one other server that has also been designated as a master. The server receives an update of the data set and processes it based upon its designation. While designated as a non-master, the server forwards the update to a master for application to the data set; and while designated as a master, the server applies the update to the data set and forwards the update to at least one other master or non-master server of the server set.
• In an embodiment, a server is configured to apply a method to participate in a server set that serves a data set. The method involves executing, by a processor of the server, instructions that cause the server to receive a designation of the server for the data set, wherein the designation is selected from a designation set comprising a master of the data set and a non-master of the data set, and wherein the server set includes at least one other server that has also been designated as a master. Execution of the instructions also causes the server to receive an update of the data set and to process the update based upon the designation. While designated as a non-master of the data set, the server forwards the update to a master of the serer set for application to the data set; and while designated as a master of the data set, the server applies the update to the data set and propagates the update to at least one other master or non-master server of the server set.
• In an embodiment, a server set is partitioned into at least two servers that are designated as masters and that are permitted to update the data set, and the remaining servers are designated as non-masters that are permitted to read, but not update, the data set, where the designation of the servers fulfills the performance criteria of the data set. An update of the data set that is received by a non-master is forwarded to one of the masters, which applies it to the data set and propagates it to at least some of the other servers of the server set.
• To the accomplishment of the foregoing and related ends, the following description and annexed drawings set forth certain illustrative aspects and implementations. These are indicative of but a few of the various ways in which one or more aspects may be employed. Other aspects, advantages, and novel features of the disclosure will become apparent from the following detailed description when considered in conjunction with the annexed drawings.
DESCRIPTION OF THE DRAWINGS
• FIG. 1 is an illustration of an example scenario featuring a single-master configuration of a server set.
• FIG. 2 is an illustration of an example scenario featuring a multi-master configuration of a server set in accordance with the techniques presented herein.
• FIG. 3 is a component block diagram illustrating an example server featuring an example system for configuring a server to provide a data set in accordance with the techniques presented herein.
• FIG. 4 is an illustration of an example method of configuring a server of a server set to process a workload in accordance with the techniques presented herein.
• FIG. 5 is an illustration of an example method of configuring a server set to process a workload in accordance with the techniques presented herein.
• FIG. 6 is an illustration of an example computer-readable storage device storing instructions that, when executed by a processor of a server of a multi-master server set, cause the server to provide access to a data set on behalf of a workload in accordance with the techniques presented herein.
• FIG. 7 is an illustration of a set of example scenarios featuring a selection of masters in accordance with the techniques presented herein.
• FIG. 8 is an illustration of a set of example scenarios featuring a dynamic selection of masters in accordance with the techniques presented herein.
• FIG. 9 is an illustration of a set of example scenarios featuring data version conflict resolution techniques for resolving data version conflicts in the data set in accordance with the techniques presented herein.
• FIG. 10 is an illustration of an example set of scenarios featuring the forwarding of requests and propagation of updates among masters and non-masters in accordance with the techniques presented herein.
• FIG. 11 is an illustration of a set of example scenarios featuring a selection of merge masters to resolve a data version conflict in accordance with the techniques presented herein.
• FIG. 12 is an illustration of an example computing environment within which one or more embodiments of the techniques presented herein may be implemented.
DETAILED DESCRIPTION
• The claimed subject matter is now described with reference to the drawings, wherein 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 the claimed subject matter. It may be evident, however, that the claimed subject matter 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 the claimed subject matter.
• A. Introduction
• Modern data services are often distributed over a set of servers in various ways, ranging from local distribution within a rack, server room, building, or campus to regional distribution over a set of cities, countries, or continents. Data services are often provided to process a set of workloads from one or more clients, such as databases that are targeted by a volume of queries.
• A variety of server architecture configurations may be utilized to satisfy the consistency level of a workload. For particularly conflict-sensitive workloads, the server architecture may be selected to ensure that updates are provided in a specific order by restricting all updates of the data set of the workload to a single “master” server. While all servers that service the workload may fulfill requests to read the data, any server except the master server that receives a write request may forward it to the master server for processing. By serving as the single point of writes to the data set, the single master server may apply all updates in a correct order and propagate updates to the other servers of the server set. In this manner, a strong consistency level may be applied to satisfy the data version conflict sensitivity of the workload.
• FIG. 1 is an illustration of anexample scenario100 featuring a single-master configuration of aserver set102. In thisexample scenario100, theserver set102 comprises a set ofservers104 that are distributed over a set of geographic regions, such as afirst server104 and asecond server104 that are deployed in a U.S. region and athird server104 and afourth server104 that are deployed in an Asian region. Theserver set102 may coordinate access to adata set106, comprising a set ofdata items108, on behalf of a client set110 ofclients112, which may also be distributed over a set of regions.Respective clients112 may issuerequests118 to access one ormore data items108 to a selectedserver104 of the server set102 in the context of aworkload114, such as an application, a services platform, or a task. Therequests118 may specify a read operation (such as a get request or a query such as a search) or a write operation (such as a create, update, or delete request, or a merging, splitting, or copying of data items108). Theservers104 may share a copy of thedata set106, such as by deploying an up-to-date copy of thedata set106 to each region for local or at least proximate access by theservers104 in the region, and a selectedserver104 may fulfill a read operation by retrieving information from the local copy of adata item108 and returning it to theclient112 in response to therequest118. However,requests118 that involve write operations that modify one ormore data items108 of thedata set106 may be more difficult to fulfill in a manner that avoids data version conflicts. For example, afirst client112 may transmit afirst request118 to update120 aparticular data item108 to a first value, while asecond client112 may simultaneously submit asecond request118 to update120 thesame data item108 to a second, different value. If bothrequests118 are transmitted to thesame server104, theserver104 may detect theconflicting requests118 and may resolve the conflict in a variety of ways (e.g., selecting onewrite request118 to be committed to thedata set106 as anupdate120 while rejecting theother write request118; rejecting both writerequests118 as mutually conflicting; and/or merging the write requests118 into asingle update120 that reflects both write requests118). However, if thefirst request118 is transmitted to afirst server104 and thesecond request118 is transmitted to asecond server104, eachserver104 may commit therespective request118 and then propagate the resultingupdate120 toother servers104 in theserver set102. Theconflicting updates120 may be detected after-the-fact in a manner that reveals the occurrence of a data version conflict, whereindifferent servers104 ascribe different values to one ormore data items108, where the coexistence of such inconsistent and mutuallyincompatible updates120 causes theservers104 of the server set102 to disagree about the state of thedata set106. As a result, theworkload114 may become logically inconsistent due to theconflicting updates120, which may result in a corruption of thedata set106, a failure of theworkload114, and/or a propagation of the data version conflict to theclients112 that utilize thedata set106 for theworkload114.
• As further illustrated in theexample scenario100 ofFIG. 1, the incidence of data version conflicts and consequences thereof may be avoided or reduced through the use of a single-master configuration, in which eachdata item108 may be updated by only asingle server104 of the server set102 that is designated as amaster116 of thedata item108. In thisexample scenario100, thefirst server104 is designated as thesole master116 for thefirst data item108; thesecond server104 is designated as thesole master116 for thesecond data item108; and thethird server104 is designated as thesole master116 for thethird data item108. Eachserver104 is capable of reading any of thedata items108, but only theserver104 designated as themaster116 of adata item108 is permitted to apply anupdate120 to thedata item108. Thefourth server104 is not designated as amaster116 of any of thedata items108, but is only capable of reading thedata items108. Whenclients112 sendrequests118 involving a read operation, anyserver104 receiving therequest118 may read thedata item108 and return the retrieved data to theclient112. However, when arequest118 involves a write operation involving aparticular data item108, theserver104 receiving therequest118 identifies themaster116 that is designated for thedata item108. If theserver104 receiving therequest118 is also themaster116 for thedata item108 involved in therequest118, theserver104 may apply the requestedupdate120 todata item108 and then propagate theupdate120 toother servers104 of the server set102 (e.g., by forwarding a notification of theupdate120 to theother servers104 and/or by synchronizing a portion of thedata set106, including the updateddata item108, with the other servers104). For example, thefirst server104 receives afirst request118 to update thefirst data item108, and may handle therequest118 by updating thefirst data item108. If thefirst request118 had been sent to anyother server104 that is not thesole master116, theserver104 would have refused therequest118 and/or forwarded therequest118 to theserver104 that is designated as thesole master116. For example, when thethird server104, which is designated as thesole master116 of thethird data item108, receives afourth request118 that requests anupdate120 of thethird data item108, thethird server104 applies theupdate120 to thethird data item108. However, when afourth server104, which is not a master of thethird data item108, receives asixth request118 to update thethird data item108, thefourth server104 does not fulfill therequest118 by applying anupdate120 to thethird data item108, but rather forwards thesixth request118 to thethird server104, which may be permitted to update thethird item108 in accordance with its designation as thesole master116 of thethird data item108.
• The single-master configuration of the server set102 enables theservers104 to coordinate the application ofupdates120 in a manner that may reduce data version conflicts. For example, thesecond server104 is designated as thesole master116 of thesecond data item108, such that allrequests118 that involve updating thesecond data item108 are forwarded to thesecond server104 for evaluation. Thesecond server104 may apply a logic to the evaluation ofrequests118 in order to select and applyupdates120 that preserve the consistency of thedata set106. For example, the logical consistency of thedata set106 may depend upon a monotonically increasing value of thesecond data item108, such that afirst update120 that establishes a selected value of thesecond data item108 is not chronologically followed by asecond update120 of thesecond data item108 with a lower value, such as in the manner of a timestamp or monotonically increasing counter. Because allrequests118 are either received by or forwarded to thesecond server104 as thesole master116 of thesecond data item108, thesecond server104 may evaluate eachrequest118 in a sequence, such as in order of receipt or timestamp, and may verify thatupdates120 to thesecond data item108 are only applied in a manner that achieves a monotonically increasing value for thesecond data item108. If arequest118 is received that involves anupdate120 of thesecond data item108 that causes thedata set106 to be logically inconsistent in view ofpast updates120 and the current state of thesecond data item108, thesecond server104 may choose not to apply theupdate120 and may refuse therequest118. Alternatively, thesecond server104 may be able to initiate a remedial measure that enables the fulfillment of thesecond request118 in a manner that preserves the logical consistency of thesecond data item108. For example, if therequest118 is to update a monotonically increasing value (currently3) to4, but therequest118 is received after an earlier but still pendingrequest118 to update the value to 5, thesecond server104 may reorder the sequence of therequests118 in order to apply the correspondingupdates120 in a manner that enables the value of thesecond data item108 to remain monotonically increasing.
• The designation of thesecond server104 as thesole master116 for thesecond data item108 also avoids data version conflicts that arise due to a set ofrequests118 that represent a logical conflict if applied concurrently to thedata item108. For example, afirst client112 and asecond client112 may each submit arequest118 to update thesecond data item108 to a different value. If therequests118 were received bydifferent servers104 and separately applied to the data set106 (such as in different regions), someservers104 may utilize the first value (e.g., 1) for thesecond data item108 while, concurrently,other servers104 may utilize the second value (e.g., 2) for the samesecond data item108. Such data version conflicts may be avoided or reduced through the designation of thesecond server104 as the sole master of thesecond data item108, since bothrequests118 are either submitted directly to thesecond server104 or forwarded to thesecond server104 from theserver104 that initially received therequest118. Thesecond server104 may identify theconflicting requests118 and may choose one according to a data version conflict resolution technique (e.g., selecting theearlier request118 or thelater request118 according to timestamps associated with eachrequest118, or selecting thefirst request118 or thesecond request118 according to the sequential order in which therequests118 arrived at the second server104), or, alternatively, may choose another resolution that fulfills both requests118 (e.g., applying anupdate120 that sets the value of thesecond data item108 to3).
• The single-master configuration of the server set102 also enablesupdates120 to be propagated from thesole master116 to theother servers104 of the server set102, either directly or through anintermediate server104. For example, when thesecond server104 applies anupdate120 to thesecond data item108 within the local copy of thedata set106, theupdate120 may be immediately visible to thefirst server104, which is collocated with thesecond server104 in the region and utilizes the same copy of thedata set106. Alternatively, thesecond server104 may transmit theupdate120 to thefirst server104 within the same region, which may be facilitated by the proximity of thefirst server104 to thesecond server104 and/or fast and plentiful bandwidth interconnecting thefirst server104 and thesecond server104. Thesecond server104 may also transmit theupdate120 to the Asia region, e.g., by applying theupdate120 to a remote copy of thedata set106 that is viewable to thethird server104 and thefourth server104, or by transmitting theupdate120 to thethird server104 for application to the copy of thedata set106 that is local to theservers104 of the Asia region. Such propagation may continue throughother servers104 and other local copies of the data set106 (e.g., thethird server104 may propagate thesame update120 to thefourth server104, and/or toother servers104 located in other regions). In this manner, theupdate120 of thesecond data item108 by thesecond server104, as thesole master116 of thesecond data item108, is propagated to all copies of thedata set106 and is apparent to allservers104 of theserver set102. The configuration of the server set102 with asingle master116 for eachdata item108 therefore promotes the preservation of the consistency of thedata set106 and reduces or avoids the incidence of data version conflicts caused by mutuallyexclusive requests118.
• However, the single-master configuration may exhibit a number of deficiencies. Such deficiencies particularly relate to the details of theworkload114, and in particular theperformance criteria122 that are expected of thedata set106.
• In many data services, adata set106 may be provided for may serve aworkload114 that is bound by a set ofperformance criteria122. Someworkloads114 may be time-sensitive, where responsiveness is a significant performance criterion of theworkload114; accordingly, the server set102 may be expected to service theworkload114 in a manner that maintains a low latency, such as a response time within five milliseconds for 99% of read requests and a response time within ten milliseconds for 99% of write requests. A variety of configurations of the server set102 may be utilized to satisfy thisperformance criterion122, such as allocatingservers104 for theworkload114 that are proximate to theclients112 that are initiating the requests118 (e.g., provisioningservers104 for a local news server that are close to a source and/or a demand for the news).
• Someworkloads114 may be throughput-sensitive, wherein a particular volume ofrequests118 is anticipated (optionally with periodic fluctuation, such as higher volume during business hours, during the work week, or during traditional holiday months). It may be desirable to configure the server set102 to ensure that theservers104 are capable of satisfying the anticipated volume ofrequests118 at all times. Additionally, someworkloads114 may scale unexpectedly and perhaps rapidly to a greater volume ofrequests118, such as a news service that unexpectedly receives a surge in news submissions during an urgent news event. If the resources allocated by the server set102 for theworkload114 are fixed, then theservers104 may be unable to handle the surge ofrequests118, resulting in a failure of somerequests118 andupdates120 and/or an unavailability to handle theworkload114 for at least someclients112. It may be desirable to configure the server set102 with the capability to scale up within a short time frame in order to handle the surge inrequests118 for theworkload114, that, e.g., ensuring that a request by theworkload114 to scale up the capacity that the server set102 has provided for theworkload114 to a higher level can be accommodated and fulfilled within a few seconds. A variety of configurations of the server set102 may be utilized to satisfy throughput andscalability performance criteria122, such as maintaining a reserve ofservers104 in various geographic regions or clusters that are available on-demand to take on a portion of the processing of theworkload114.
• Someworkloads114 may be availability-sensitive, wherein the vast majority ofrequests118 are to be successfully completed, and wherein an inability to satisfy arequest118 is considered problematic. Availability may also have to be maintained even in the event of a failure of resources of the server set102, such as a hardware or software failure of aserver104 or a partial network outage. A variety of configurations of the server set102 may be utilized to satisfyavailability performance criteria122, such as availability verification techniques that rapidly identify an outage and automated failover techniques that rapidly initiate contingency plans in the event of network failure (e.g., automated techniques for selecting afailover master116 to substitute for a failedserver104, and/or for establishing a configuration of thefailover server104 to accept a transfer of the portion of theworkload114 that was allocated to the failedserver104 as rapidly as possible).
• Someworkloads114 may be consistency-sensitive, whereinupdates120 that are occurring in an inadequately synchronized manner may cause parts of thedata set106 to diverge, such as data version conflicts caused byconflicting updates120 to asingle data item108 or inconsistencies between the values stored in different data items108 (e.g., a foreign key relationship between a first table and a second table, where the inconsistency comprises a key identifier in the first table that does not correspond to any record in the second table). Such inconsistencies may causedifferent servers104 to handle anidentical request118 in different ways due to discrepancies in the local copies of thedata set106 of theworkload114 that are accessed byservers104 in different locations. For example, a banking service may store a record of an individual's account balance that is simultaneously updated by twodifferent servers104 with twodifferent updates120. In some cases, thesimultaneous updates120 may cause oneupdate120 to be overwritten. In other cases, a data version conflict may be detected, but theservers104 may be unable to resolve it, or may have to initiate complex journal review and rollback processes to reverse afirst update120 that was committed but that is inconsistent with an also-committedsecond update120. Becausedifferent workloads114 may have different sensitivities to data version conflicts, aparticular workload114 may be governed by aconsistency performance criterion122, e.g., a description of the consistency expectations of theworkload114 and/or the semantic details of resolving data version conflicts. In some cases, theperformance criterion122 may involve a selection of a particular consistency model for thedata set106, such as a strong consistency model where allupdates120 are guaranteed to be strictly applied in “wall-clock” order across the entire server set102; an eventual consistency model, where data sets106 stored bydifferent servers104 may temporarily diverge, but are eventually and retrospectively reconciled to exhibit adata set106 that is consistent up to a certain time point; and a last-write-wins consistency model, wherein loss of past data updates is tolerable as long as the server set stores and provides the mostrecent update120.
• For aparticular workload114, a data service may formalize some or all of the types ofperformance criteria122 noted above—latency, throughput, availability, throughput, scalability, and consistency level—in a service level agreement. The use of a service level agreement may permit an administrator of aworkload114 to specify theperformance criteria122 of theworkload114 and the expectations of the performance of the server set102, and a guarantee by the providers of the data service of the performance that is to be provided and maintained by the server set102 for theworkload114. A data service may utilize the service level agreement to guide an administrator in selecting and provisioning a set of data service resources to satisfy the guarantees. Alternatively or additionally, a data service may use the service level agreement to inform an automated process that provisions and configures the resources of the server set102 to handle theworkload114. Many distributed data services are multi-tenant, such thatworkloads114 ofvarious clients112 are distributed over and concurrently processed by the server set102, wherein aparticular server104 may consecutively and/or concurrently perform two ormore workloads114 on behalf of two ormore clients112. Such multitenancy scenarios may involve careful configuration of the servers, e.g., to prevent afirst workload114 of afirst client112 from observing and/or interfering with asecond workload114 of asecond client112, and/or to ensure that excessive resource utilization by afirst workload114 does not jeopardize the fulfillment of a service level agreement for asecond workload114.
• Someworkloads114 that are constrained bymultiple performance criteria122. For example, some service level agreements may specifydifferent performance criteria122 for different portions of the workload114 (e.g., different tasks comprising theworkload114, such as different types of queries that have different performance sensitivities) and/or for different contexts in which aworkload114 is performed (e.g., different performance criteria for peak hours vs. off-hours). Alternatively or additionally, some service level agreements may specify a collection ofperformance criteria122, such as both a latency criterion and a consistency level that are both expected of theserver set102. In some cases,different performance criteria122 may present a tradeoff, wherein fulfilling a first performance guarantee affects the capability of the server set102 to fulfill a second performance guarantee. In some instances, the concurrent fulfillment of two performance guarantees may be achievable, but may considerably increase the commitment of computational resources relative to the fulfillment of either performance guarantee alone. In other instances, the concurrent fulfillment of two performance guarantees may not be reasonably achievable, or in some cases may be physically impossible with some data service architectures.
• An example of a performance criteria tradeoff that may be difficult to fulfill is aworkload114 that expects both low latency and a strong consistency level. A server set102 may be configured to satisfy the strong consistency level through a single-master configuration in which allupdates120 are routed to asingle server104 that is designated as themaster116 for thedata item108, such as in theexample scenario100 ofFIG. 1. However, such propagation may involve an unavoidable network transport delay, based upon technical constraints (e.g., the maximum achievable responsiveness of server and networking hardware) and/or physical constraints (e.g., maximum transmission speeds limited by the speed of light). For example, as illustrated in theexample scenario100 ofFIG. 1, aserver104 from the second region may receive an update to thesecond data item108 for which thesecond server104 in the first region is designated as themaster116. However, the delay in forwarding thefourth request118 to thesecond server104 may introduceenough latency124 to violate aperformance criterion122 that allupdates120 are to be committed to thedata set106 of theworkload114 by a within a latency bound, such as ten milliseconds. Ifrequests118 forupdates120 are to be received throughout the world, then the maximum round-trip delay between any selectable server location and the furthest anticipated source ofrequests118 forupdates120 may exceed the maximum desiredlatency124 according to theperformance criterion122 of theworkload114. Inworkloads114 that involve broad-scale geographic distribution and that feature aperformance criterion122 of verylow latency124, it may not be possible to transmitrequests118 from all of the clients to asingle master116 positioned anywhere in the world within the speed-of-light physical constraint. As another example, even if thesecond server104 receives arequest118 from a nearby client112 (such as thesecond request118 transmitted by anearby client112 to the second server104) and applies it nearly instantaneously to thedata set106, the propagation of theupdate120 toservers104 in other regions may involvelatency124 that exceeds a latency threshold as aperformance criterion122 of theworkload114.
• A single-master configuration may also violate other types ofperformance criteria122 of aworkload114 that may be formalized in a service level agreement. As a first such example, a service level agreement may specify an availability-basedperformance criterion122 as an expectation of high availability of theworkload114 even in the event of failures, such as hardware failures and network partitioning. However, a single-master configuration represents a single point of failure; e.g., thesole server104 designated as amaster116 of aparticular data item108 may fail for a variety of reasons, or a network partition may occur between themaster116 of adata item108 and aclient112 that requests to update120 thedata item108. While failover techniques may enable the rapid designation of anotherserver104 as asubstitute master116 for the failedserver104, the transition from theoriginal master116 to thesubstitute master116 may involve a delay, during which requests118 are unfulfilled in violation of theavailability performance criterion122.
• As a second such example, a service level agreement may specify ascalability performance criterion122 as an expectation that additional resources of the server set102 may be allocated to handle a surge inrequests118. However, server set configurations involving the designation of asingle server104 as thesole master116 for adata item108 may be incompatible with such scalability, as the resources of theserver104 designated as themaster116 may be finite. An administrator of the server set102 may be able to add resources to the master116 (such as additional storage or processing capacity), but the available resources that asingle server104 may support may have a fixed limit, such as the maximum clock speed and/or core count of commercially available processors. Alternatively, an administrator may transition the designation of themaster116 from afirst server104 to a second, higher-capacity server104 that may serve as the new (sole)master116. However, such transitions may be difficult to implement rapidly, particularly in order to handle a surge ofrequests118; e.g., thecurrent master116 may be operating near maximum capacity to handle the influx ofrequests118, and may not have spare resources to initiate transitional processes without jeopardizing the fulfillment of therequests118. During such transition, the service may become unavailable, which may occur at a particularly sensitive and urgent time for theworkload114.
• As a third such example, a service level agreement may specify a consistency level, such as a strong consistency level that ensures that allservers104 of the server set102 uniformly agree about the state of adata item108 at a particular time. Such strong consistency may be achieved by a consensus technique in which themaster116 coordinates the propagation of theprospective update120 to allservers104, and the commitment thereby, prior to confirming the application of theupdate120 and the fulfillment of therequest118. However, such consensus may be difficult to achieve through the operation of asingle server104 as themaster116; e.g., if the server set102 includes hundreds or thousands ofservers104, a consistency model that involves concurrent, realtime communication between asingle master116 and hundreds or thousands of other servers distributed over the world may be unachievable, or at least highly inefficient. Moreover, the delay involved in the mediation of asingle master116 with everyother server104 of the server set102 may be incompatible withother performance criteria122, such as the commitment of theupdate120 within a latency threshold.
• Due to such practical constraints, distributed data services based on single-master configurations may be incapable of consistently fulfilling theperformance criteria122 of one ormore workloads114; may violate some performance guarantees, and/or may be unable to offer certain types of service level agreements with performance guarantees that may be violated in some circumstances.
• B. Presented Techniques
• In view of the limitations of single-master server architectures and the potential problems with data version conflicts and/or performance guarantees that may arise with some multi-master server architectures, the present disclosure provides multi-master configurations of server sets102 that may promote the extension and/or fulfillment of service level agreements with guarantees for various types ofperformance criteria122.
• In order to alleviate the performance limitations of a single-master server architecture, aserver set102 may be configured with a multi-master architecture, in which updates120 to aparticular data item108 may be fulfilled by two ormore servers104 of the server set102 that are designated asmasters116 of thedata item108. It may be undesirable to designate allservers104 asmasters116 of thedata item108, such that anyserver104 of the server set102 may apply anupdate120 to it; e.g., the resolution of data version conflicts may become unmanageably complicated if everyserver104 concurrently applies anupdate120 of a different value to thesame data item108. Rather, the designation of a subset of theservers104 asmasters116 of aparticular data item108 may promote the fulfillment ofperformance criteria122, such as latency, scalability, availability, and consistency, without creating complexity and/or inefficiency that may diminish the capability of the server set102 to applyupdates120 to thedata set106. As one example, for each broad geographic region (e.g., Africa, Asia, Europe, and North America), a selectedserver104 may be designated as aregional master116, and allupdates120 received within a particular region may be forwarded to theregional master116 for application to thedata set106.
• The designation of a subset ofservers104 asmasters116 may promote the offering and/or fulfillment ofperformance criteria122 that may not be offered and/or fulfilled in other configurations. For example, alatency performance criterion122 ofupdates120 to thedata set106 may be unattainable with asingle server104 designated as themaster116; e.g., because themaster116 may be overloaded withrequests118 forupdates120 and may not be able to apply anupdate120 within a latency threshold. Moreover, thelatency performance criterion122 may also be unattainable by designating everyserver104 as amaster116, as verifying the commitment of theupdate120 by everyserver104 may also exceed the latency threshold. However, designating a subset of at least twoservers104 pf the server set102 asmasters116 of thedata item108 may balance the availability ofmasters116 to apply anupdate120 to thedata set106 with the expedient verification that theupdate120 has been committed over the server set102 (e.g., verification that the subset ofservers104 designated asmasters116 are in agreement as to the state of thedata item108 before and/or after the update120), thereby fulfillingperformance criteria122 that a single-master server set102 may be unable to offer and/or fulfill.
• FIG. 2 is an illustration of anexample scenario200 featuring a multi-master configuration of aserver set102 in accordance with the techniques presented herein. In thisexample scenario200, aserver set102 is provided that spans three regions, and where the server set102 is organized to serve adata set106 to a client set110 ofclients112 in the context of aworkload114 that is constrained by aperformance criterion122, such as latency, throughput, scalability, availability, and/or consistency. In order to provide theworkload114 in a manner that is consistent with theperformance criterion122, the server set102 may be partitioned, for eachdata item108, into a master subset of at least twoservers104 that are permitted to update thedata item108 and a non-master subset ofservers104 that are not permitted to update thedata item108. For example, among the fiveserver104 illustrated in theexample scenario200 ofFIG. 2, thesecond data item108 may be updated only by thesecond server104 and thethird server104, while thethird data item108 may be updated only by thefourth server104 and thefifth server104.
• When arequest118 is received by aserver104 to read thedata item108, theserver104 may simply access thedata item108 to read thedata item108 and may provide information to theclient112 based on the reading. However, when arequest118 is received by theserver104 to apply anupdate120 to thedata item108, theserver104 may determine the identity of themasters116 of thedata item108 involved in therequest118. If theserver104 determines that it has been designated as amaster116 of thedata item108, theserver104 applies the requestedupdate120 to thedata set106 to fulfill therequest118, and then propagates the update to at least oneother server104 of the server set102 (e.g., forwarding theupdate120 to eachother master116, and/or to at least oneserver104 in each geographic region). Theother servers104 that receive theupdate120 may ensure that theupdate120 is applied to the local copy of thedata set106, and/or may propagate theupdate120 to other servers (e.g., theother servers104 within the same geographic region). If theserver104 determines that it has not been designated as amaster116 of theupdate120, theserver104 forwards therequest118 to amaster116 of the server set102 for thedata item108, and themaster116 applies theupdate120 to theserver set102.
• For example, in theexample scenario200 ofFIG. 2, afirst request118 for anupdate120 of afirst data item108 is sent to afirst server104. Thefirst server104 determines that it has been designated as amaster116 for thefirst data item108, applies theupdate120 to thedata set106 to fulfill therequest118, and propagates theupdate120 to at least oneother server104 of the server set102 (e.g., to oneserver104 in each region, and/or to at least oneother server104 that has been designated as amaster116 for the first data item108). However, when afourth request118 is issued by aclient112 to athird server104 that has not been designated as amaster116 of thefirst data item108, thethird server104 does not apply theupdate120 to thefirst data item108, but rather forwards therequest118 to anotherserver104 that has been designated as amaster116 for the second data item108 (e.g., to thefirst server104 in the first region).
• As another example in theexample scenario200 ofFIG. 2, asecond server104 receives, fromdifferent clients112, asecond request118 and athird request118 to update asecond data item108. Thesecond server104 determines that it has been designated as amaster116 of thesecond data item108, and also that the application of therequests118 may create a data version conflict. Thesecond server104 therefore performs a data version conflict resolution technique to resolve the data version conflict, and selects thethird request118, opting to refuse thesecond request118. Thesecond server104 applies anupdate120 to thedata set106 to fulfill thesecond request118 and propagates theupdate120 to at least oneother server104 of theserver set102.
• As a third example in theexample scenario200 ofFIG. 2, afourth server104 and afifth server104, deployed within different regions, are designated asmasters116 of athird data item108 in thedata set106. Eachmaster116 concurrently receives arequest118 from adifferent client112 to update thethird data item108 to a value. Because eachserver104 is designated as amaster116, theservers104 applyupdates120 to the third data item108 (e.g., each server applying theupdate120 to a local copy of thethird data item108 for the geographic region). Eachmaster116 also propagates itsupdates120 toother servers104 of theserver set102. When one of themasters116 discovers that theother master116 has also applied anupdate120 to thethird data item108, themaster116 compares theupdates120 and determines that adata version conflict202 has arisen: different subsets of theservers104 concurrently perceive thethird data item108 as having different, conflicting values, based on which of theupdates120 has been most recently applied to thethird data item108. Thedata version conflict202 may arise, e.g., because thefourth server104 commits thefifth update120 to of the local copy of thethird data item108 for the EU region, while, concurrently, the fifth server commits thesixth update120 to the local copy of thethird data item108 for the Asia region. As another example, the updates may have both been committed, but in a different order; e.g., the EU region and the Asia region may both commit thefifth update120 of thethird data item108 before thesixth update120, but theservers104 in the U.S. region may have been notified of theupdates120 in a reverse order, and may have applied thesixth update120 before thefifth update120 to the local copy of thethird data item108 for the U.S. region. Moreover, thedata version conflict202 does not reflect an ordinary and ephemeral discrepancy that is resolvable within a latency threshold; rather, because the sequence ofupdates120 applied to one version of thethird data item108 differs from the sequence ofupdates120 applied to another version of thedata item108, the discrepancy reflects a genuine inconsistency among the versions of thethird data item108 in the distributeddata set106. Accordingly, one of themasters116 applies a data version conflict resolution technique to choose among the competing updates120 (e.g., a selection of oneupdate120 and a discarding of anotherupdate120; a canonical sequence in which theupdates120 are to be applied; and/or asuperseding update120 that merges and takes precedence over all such updates120). Alternatively, themaster116 may request a rollback of allsuch updates120 and revert thethird data item108 to its state before either of the committed updates120. In this manner, themaster116 may enable a rapid resolution of thedata version conflict202, and may propagate the data version conflict resolution outcome to one or more of theother servers104 for application to thedata set106 to resolve thedata version conflict202. In this manner, the server set102 may be organized to provide access to thedata set106 on behalf of the client set110 in the service of theworkload114 in accordance with the techniques presented herein.
• C. Technical Effects
• The organization of a server set in accordance with the techniques presented herein may enable a variety of technical effects in some embodiments thereof.
• A first example of a technical effect that may be achieved through the multi-master techniques presented herein involves the provision of aserver set102 that is capable of fulfillingperformance criteria122 that may not be achieved by single-master server sets102.
• As a first example, a multi-master server set102 may be capable of offering and fulfilling alatency performance criterion122, such as a maximum latency threshold within which updates120 are to be applied. By providing at least twomasters116 that are permitted to update adata item108 of thedata set106, the server set102 is capable of initiating the application of anupdate120 to thedata set106 by multiple servers, one of which is likely to be closer to theclient112 initiating therequest118 for theupdate120, and/or one of which is less likely to be completing a computational load that forestalls the initiation of theupdate120. Additionally, the provision ofmultiple masters116 may enable theupdate120 to be committed across theentire data set106 more rapidly (e.g., eachmaster116 may serve as a transaction coordinator for the local copy of thedata set106 in a geographic region, and/or may coordinate the propagation of the update to theother servers104 within the region). Such concurrent commitment of theupdate120 to the various copies of thedata set106 and propagation to allservers104 of the server set102 is likely to be faster than the commitment of theupdate120 by asingle master116 to all local copies of thedata set106 through all regions, and/or the propagation of theupdate120 from thesingle master116 to allother servers104 of theserver set102. Conversely, the designation of only someservers104 asmasters116 for a particular data item (wherein at least oneserver104 is designated as a non-master that is not permitted to update the data item108) reduces the number ofmasters116 that are involved in the commitment, and may therefore be faster than an all-master server configuration. In this manner, the partitioning of the server set102 into a master subset (comprising at least two masters116) and a non-master subset (comprising at least one non-master server104) for aparticular data item108 may promote compliance with a latency threshold, whereas other configurations may be incapable of doing so.
• As a second such example, a multi-master server set102 may be capable of offering and fulfilling athroughput performance criterion122, such as an anticipated volume ofrequests118 forupdates120 to be handled within a particular unit of time. The designation of at least twomasters116 enablesupdates120 of adata item108 to be concurrently applied bymultiple servers104, and may therefore be capable of greater overall volume and throughput than a single-server configuration in which allupdates120 are applied by asole master116. In this manner, multi-master server configurations may enable a parallelized application ofupdates120 to thedata set106, in a manner that raises the throughput of the server set102 for updating therespective data items108 of thedata set106, as compared with a single-master server set102.
• As a third such example, a multi-master server set102 may be capable of offering and fulfilling ascalability performance criterion122, such as a capability of the server set102 to scale up the resources provided for theworkload114 to handle a surge inrequests118. A single-master server set architecture may exhibit limited options for responding to such surges, e.g., offloadingother workloads114 performed by thesingle master116, increasing its computational capacity to a maximum (e.g., maximizing the clock rate and/or core count of processors), and/or by allocating more resources to thesingle master116, such as more plentiful network capacity or a more comprehensive network cache. However, the scalability options are limited to the maximum throughput of thesingle master116, which may have hard limits established by the microarchitecture of theserver104, such as a maximum processor clock rate or core count, a maximum of installed physical memory, and a maximum bus capacity between the processor and peripheral devices. By contrast, a multi-master server set may respond to a surge inrequests118 not only by expanding the resources of theindividual masters116 of the master subset, but also by adjusting the partitioning between the master subset and the non-master subset for thedata item108, e.g., allocatingadditional masters116 for adata item108, and/or by moving a designation ofmasters116 for adata item108 to locations that are nearer the sources of therequests118. Such allocation may occur while the previously designatedmasters116 continue to fulfillrequests118, thereby maintaining the current capacity of the server set102 while, concurrently,new masters116 are being provisioned to alleviate the existingmasters116 of surging demand. In this manner, the multi-master server set102 may be more capable of scaling up to meet a surge in demand for theworkload114 than single-master configurations of theserver set102.
• As a fourth such example, a multi-master server set102 may be capable of offering and fulfilling anavailability performance criterion122, such as a maximum uptime for the server set102 to fulfillrequests118 to update theworkload114. A single-master configuration presents a single point of failure; e.g., if thesole master116 for adata item108 experiences a failure, the server set102 incurs a delay in detecting and resolving the unavailability of thesole master116, during which the service provided to or by theworkload114 is unavailable to theclients112. A multi-master configuration comprising at least twomasters116 of therespective data items108 is resilient to the failure of amaster116; in the event of a failure of one or evenseveral masters116, at least onemaster116 remains available to applyupdates120 to thedata item108. That is, other than a scenario in which all of themasters116 for aparticular data item108 fail, the consequence of a failure of amaster116 is not a failure of availability, but a modest increase in latency as theother masters116 for thedata item108 handle the volume ofrequests118 that the failedmaster116 have been fulfilling, while asubstitute master116 is provisioned and instantiated to take the place of the failedmaster116. In this manner, the multi-master server set102 may therefore capable of offering and fulfilling stricter availability performance criteria than a single-master server set102.
• As a fifth such example, a multi-master configuration of aserver set102 may be capable of offering and fulfilling a consistency performance guarantee, such as a consistency model that is difficult to achieve in a single-master set. For instance, a strong consistency model may involve a strict commitment ofupdates120 across the entire server set102, such as a unanimous agreement by allservers104 that anupdate120 has been applied to thedata item108 to bring it to a final state, before providing a response to aclient112 that therequest118 for theupdate120 has succeeded. A single-master configuration may be quite difficult to fulfill a strong consistency model, e.g., due to the difficulty of positioning asingle master116 as a global transaction coordinator for hundreds or even thousands ofservers104 comprising a widely distributedserver set102. However, a multi-master server configuration may enable the master subset ofservers104 designated as masters116 (e.g., for each geographic region) to perform a local commit of theupdate120 to a local copy of thedata set106 in conjunction with a selection of the non-master servers104 (e.g., thenon-master servers104 within the same geographic region), and themasters116 may then perform a second-level distributed consensus to verify the commitment by eachmaster116. The enhanced parallelism of the distributed commitment of theupdate120 across the entire server set102 may be more readily achievable than coordination by asingle master116. As another example, a session-based consistency model may involve a commitment ofupdates120 to adata item108 that is consistent within a session, although versions of thedata item108 may vary between sessions. Such an intermediate consistency model may be stricter than an eventual consistency model in which updates120 are only guaranteed to settle into consistency at an indefinite future time point, and yet less rigorous than a strong consistency model, such thatrequests118 may be fulfilled within a tighter latency threshold, enabling thedata set106 and theworkload114 to be more responsive to the client set110. A single-master server set may be difficult to reconcile with a session-based consistency model, but a multi-master server set, in whichrespective masters116 may maintain the state of a session for a group ofnon-master servers104, may be suitable for such a consistency model.
• These andother performance criteria122 may be satisfied by aserver set102 configured in accordance with the techniques presented herein. Moreover, the server set102 may be testable and demonstrable of being consistently capable of satisfyingvarious performance criteria122, such that a guarantee of such capabilities may be extended to a provider of aworkload114 that depends uponsuch performance criteria122. Moreover, confidence in the reliability of a guarantee may promote the formulation of a service level agreement that sets forth theperformance criteria122 upon which theworkload114 depends, and the server set102 may be offered as a platform that is capable of providing guarantees of the satisfaction ofsuch performance criteria122. Such features are promoted by the multi-master configuration of the server set102 in accordance with the techniques presented herein.
• A second example of a technical effect that may be achieved through the multi-master techniques presented herein involves the resolution of data version conflicts202 that may arise within thedata set106. The configuration of the server set102 withmultiple masters116 may avoid some sources of data version conflicts202, such as multiple, potentially conflictingrequests118 that are routed to the same master116 (such as thesecond request118 and thethird request118 that are resolved by thesecond server104 as amaster116 for the second data item108). However, multi-master server configurations raise the prospect of suchconflicting requests118 arriving atdifferent masters116, each of which commits anupdate120 to thedata set106 that conflicts with the commit by theother master116 in response to theother request118. In some cases, the concurrently appliedupdates120 may be mutually compatible; e.g., thedata item108 may store an unordered set of added items, andconcurrent updates120 may result in the addition of allsuch updates120 to the unordered set that produces different, but logically equivalent, versions of thedata item108 bydifferent servers104. In other cases, the mutually appliedupdates120 may be mutually incompatible and may create adata version conflict202. Each of themultiple masters116 may be configured to detect and resolve data version conflicts202 through a variety of data version conflict resolution techniques, which identify a data version conflict resolution outcome and propagate the same throughout the sever set102 (e.g., propagating a notification of thedata version conflict202 and the elected outcome thereof to the at least oneother master116 of the server set102 for the selected data item108). The organization of the server set102 as a partitioning of theservers104 into a master subset with at least twomasters116 and a non-master subset with at least onenon-master server104, in accordance with the techniques presented herein, may reduce the incidence of data version conflicts202 by consolidating updates into the subset ofmaster servers104, and by limiting the number of concurrent and mutuallyinconsistent updates120 that are being applied by theserver set102.
• Additionally, in some embodiments, the multi-master architecture may be extended to provide a mechanism for detecting and resolving data version conflicts202, such as demonstrated by thefourth server104 and thefifth server104 as masters of thethird data item108 in theexample scenario200 ofFIG. 2. In some embodiments, among themasters116 in the master subset for adata item108, onesuch master116 may be designated as a merging master that applies data version conflict resolution techniques to resolve data version conflicts202; e.g.,other masters116 may notify the mergingmaster116 of a detecteddata version conflict202 and may rely on the mergingmaster116 to resolve thedata version conflict202. The merging master may do so by identifying a data version conflict resolution outcome, such as asuperseding update120 to thedata item108 that resolves thedata version conflict202, and may propagate the data version conflict resolution outcome to theother masters116 for application to thedata set106 to resolve thedata version conflict202 throughout theserver set102. Such techniques may leverage the multi-master organization provided in accordance with the techniques presented herein.
• A third example of a technical effect that may be achieved through the multi-master techniques presented herein involves the administration and load-balancing of the server set102 to handle theworkload114. In single-master configurations, the server set102 routes allrequests118 forupdates120 to adata item108 through asingle server104 that is designated as themaster116. If thedata item108 is frequently updated, the computational load of processing allsuch updates120—particularly in a manner that reduces or avoids data version conflicts202, and particularly if the schema of thedata set106 is complex, which may involve a complex logic for determining whether anupdate120 presents adata version conflict202—may be substantial. Even if the volume ofsuch updates120 is large, a single-master configuration of the server set102 is not compatible with a distribution of the load over a subset of theservers104. In accordance with the present disclosure, a multi-master configuration may enable the selection ofmasters116 that distribute the computational load, while also providing a mechanism to detect and resolve data version conflicts. Moreover, the multi-master capability enables a selection ofmasters116 in locations that are closely related to anticipated demand for theworkload114, such as identifying locations that are likely to be high-volume sources ofrequests118 and selecting one ormore masters116 that are geographically near such locations. In some embodiments, the selection ofmasters116 may be dynamic, such that changes in load, both anticipated (e.g., according to a predictable schedule or event) and/or or unanticipated (e.g., according to an unforeseen event) may enable a proactive and/or reactive repartitioning of the server set102 to add or relocate one ormore masters116 toservers104 that are nearer the new sources ofupdates120. Such flexibility may be greater than for
• A third example of a technical effect that may be achieved through the multi-master techniques presented herein involves the quality of service provided todifferent clients112 of a client set110 of theworkload114. In some scenarios, such as online gaming, updates120 bydifferent clients112 may be competitive, and the order in which requests118 are processed may confer an advantage upon afirst client112 whoserequests118 are processed faster and a disadvantage upon asecond client112 whoserequests118 are processed slower. In single-master configurations, the selection of the location of theserver104 designated as themaster116 for adata item108 may have a differential impact upon the client set110, whereclients112 that are geographically near themaster116 may haveupdates120 processed rapidly and successfully, but updates120 requested byclients112 that are geographically distant from themaster116 may be processed withsubstantial latency124 and possibly a significant rate of failure (e.g., ifupdates120 are processed in the order received by themaster116,updates120 submitted bydistant clients112 may be processed afterupdates120 bynearby clients112 that are simultaneously generated but transmitted more quickly to themaster116. In scenarios where the timing ofupdates120 is a significant factor, including scenarios in which updates120 bydifferent clients112 are competitive (e.g., in online gaming),clients112 may perceive an unintended and possibly unfair advantage or disadvantage based on distance to thesingle master116. Multi-master configurations may enable the subset ofservers104 designated asmasters116 to be selected such that thelatency124 experienced by eachclient112 in the processing ofrequests118 is more consistent across the client set110, reducing unintended advantages and disadvantages based on proximity ofclients112 toservers104. Many such technical effects may be achieved through multi-master configurations of server sets102 in accordance with the techniques presented herein.
• D. Primary Embodiments
• The techniques presented herein may be implemented as various embodiments that may take many forms. Some example embodiments are illustrated inFIGS. 3-6.
• FIG. 3 is an illustration of an example scenario featuring embodiments of the techniques presented herein, including anexample server302 that is configured to provide access to adata set106 in accordance with the techniques presented herein and anexample system308 that causes anexample server302 to provide access to adata set106 in accordance with the techniques presented herein. Theexample server302 may comprises, e.g., aprocessor304 and a volatile or nonvolatile memory306 (e.g., a volatile system memory circuit, a platter of a hard disk drive, a solid-state storage device, and/or an magnetic and/or optical computer-readable medium), wherein thememory306 stores instructions components of anexample system308 that cause theexample server302 to implement at least a portion of the techniques presented herein. Theexample system308 may comprise, e.g., instructions stored in a volatile or nonvolatile memory306 (e.g., a volatile system memory circuit, a platter of a hard disk drive, a solid-state storage device, and/or an magnetic and/or optical computer-readable medium), wherein the execution of the instructions by aprocessor304 of theexample server302 causes the instantiation of a set of components, wherein respective components of theexample system308 implement a portion of the techniques presented herein, and wherein the interoperation of the components causes theexample server302 to operate in accordance with the techniques presented herein.
• In thisexample scenario300, aserver set102, comprising theexample server302 and asecond server104, provides access to adata set106 comprising a set ofdata items108 on behalf of aworkload114, which may depend upon one ormore performance criteria122, such as a latency threshold; an expected volume ofrequests118; a scalability capability of handling an expected or unexpected surge inrequests118; an availability threshold; and/or a consistency level, including a consistency model. Theworkload114 may also define a set of logical constraints of thedata set106, such as criteria by which the logical consistency and/or inconsistency of thedata set106 is to be evaluated, such as a schema of thedata set106 or a set of business logic or rules to validate thedata set106. The server set102 provides access to thedata set106 to aclient112 that issues a series ofrequests118 that involvevarious data items108 of thedata set106, and theexample server302, together with thesecond server104, endeavors to fulfill therequests118 in accordance with the techniques presented herein.
• Theexample system308 of theexample server302 comprises adesignation receiver310, which receives adesignation316 of the server forrespective data items108 of thedata set106. Thedesignations316 for therespective data items108 are selected from a designation set comprising amaster116 that is permitted to update thedata item108 and a non-master318 that is not permitted to update thedata item108. In accordance with the multi-master configuration of the server set, for therespective data items108, at least oneother server104 of the server set102 has been designated as asecond master116 that is also permitted to update thedata item108. In thisexample scenario300, thedata set106 comprises threedata items108, and theexample server302 has been designated as amaster318 for the first andsecond data items108 and as a non-master for thethird data item108. Additionally, thesecond server104 has been designated as amaster116 for the first andthird data items108 and as a non-master for thesecond data item108.
• Theexample server302 receives a set of threerequests118 from theclient112. Thefirst request118 involves anupdate120 of thefirst data item108. In accordance with the techniques presented herein, theexample server302 examines itsdesignations316 and determines that it has been designated as amaster116 for thefirst data item108. Accordingly, theexample server302 fulfills therequest118 by invoking amaster request evaluator312 of theexample system308, which applies anupdate120 of thefirst item108 to thedata set106. Themaster request evaluator312 also propagates320 theupdate120 of thefirst data item108 to thesecond server104, which, as it is also amaster116 of thefirst data item108, may compare theupdate120 withother updates120 of thefirst data item108 that it has previously or concurrently applied in order to detect a data version conflict, which may be resolved by a variety of techniques, some of which are also presented herein. Additionally (and optionally before or after verifying that data version conflicts do not exist or have been resolved), theexample server302 may notify theclient112 of the successful application of theupdate120 of thefirst data item108.
• Theexample server302 also receives asecond request118 from theclient112 that involves a read of thethird data item108. Since therequest118 only involves a read operation and not a write operation, theexample server302 is permitted to fulfill therequest118 irrespective of itsdesignation316 as amaster116 or non-master318 with respect to thethird data item108. Accordingly, theexample server302 applies a readoperation322 to thedata set106 to retrieve the requested portion of thethird data item108 and returns the data to theclient112.
• Theexample server302 also receives athird request118 form theclient112 that involves an update of thethird data item108. The example server examines itsdesignations316 and determines that it has been designated as a non-master318 for thethird data item108, and therefore is not permitted to fulfill the request by updating thethird data item108. Instead, thenon-master request evaluator312 of theexample system308 identifies anotherserver104 of the server set102 that has been designated as amaster116 of thethird data item108—i.e., thesecond server104—andforwards324 therequest118 to thesecond server104. In accordance with its designation as amaster116 of thethird data item108, thesecond server104 applies theupdate120 to thethird data item108. Thenon-master request evaluator314 may receive from thesecond server104 an acknowledgment of theupdate120 of thethird data item108 and/or may examine thedata set106 to verify that theupdate120 has been applied to thethird data item108, and may therefore report the fulfillment of therequest118 to theclient112. In this manner, theexample server302 provides access to thedata set106 on behalf of the workload as a member of a multi-master server set102 configured in accordance with the techniques presented herein.
• FIG. 4 is an illustration of anexample method400 of configuring aserver104 of aserver set102 to provide access to adata set106 on behalf of aworkload114 in accordance with the techniques presented herein. Theexample method400 may be implemented, e.g., as a set of instructions stored in a volatile or nonvolatile memory of a server, such as a system memory circuit, a platter of a hard disk drive, a solid-state storage device, and/or an magnetic and/or optical computer-readable medium, wherein execution of the instructions by aprocessor304 of theserver104 causes theserver104 to operate in accordance with the techniques presented herein.
• Theexample method400 begins at402 and involves executing404 the instructions by theprocessor304 of theserver104. In particular, execution of the instructions causes theserver104 to receive406 adesignation316 of adata item108 of thedata set106, wherein thedesignation316 is selected from a designation set comprising amaster designation408 as amaster116 that is permitted to update thedata item108 and anon-master designation410 as a non-master318 that is not permitted to update thedata item108, and wherein the server set102 comprises at least oneother server104 has been designated as asecond master116 of thedata item108. Execution of the instructions also causes theserver104 to receive412 arequest118 to update thedata item108. Execution of the instructions also causes theserver104 to, while designated as anon-master318 of thedata item108, forward414 therequest118 to anotherserver104 of the server set102 that has been designated as amaster116 of thedata item108, so that themaster116 may update120 thedata item108 to fulfill therequest118. Execution of the instructions also causes theserver104 to, while designated416 as amaster116 of thedata item108, update418 thedata item108 according to therequest118, and propagate420 theupdate120 of thedata item108 to at least oneother server104 of theserver set102. In this manner, theexample method400 causes theserver104 to operate in accordance with the techniques presented herein, and so ends at422.
• FIG. 5 is an illustration of anexample method500 of configuring aserver set102 to provide access to adata set106 on behalf of aworkload114 in accordance with the techniques presented herein, wherein theworkload114 involves a set of one ormore performance criteria122. Theexample method500 may be implemented, e.g., as a set of instructions stored in a volatile or nonvolatile memory of one ormore servers104, such as a system memory circuit, a platter of a hard disk drive, a solid-state storage device, and/or an magnetic and/or optical computer-readable medium, wherein execution of the instructions by aprocessor304 of theserver104 causesrespective servers104 to operate in accordance with the techniques presented herein.
• Theexample method500 begins at502 and involves, forrespective data items108 of thedata set106, partitioning504 the server set102 into amaster subset506 comprising at least twoservers104 designated asmasters116 that are permitted to update thedata item108 and anon-master subset508 comprising at least oneserver104 designated as a non-master318 that is not permitted to update thedata item108, and wherein thepartitioning504 enables the server set102 to fulfill theperformance criteria122 of theworkload114. Theexample method500 further comprises configuring510 theservers104 that have been designated asnon-masters318, respectively, to receive512 arequest118 to update120 thedata item108 and forward514 therequest118 to anotherserver104 of the server set102 that has been designated as amaster116 of thedata item108. Theexample method500 further comprises configuring516 the at least twomasters116, respectively, to receive518 therequest118 to update120 thedata item108;update520 thedata item108 according to therequest118; and propagate522 theupdate120 of thedata item108 to at least oneother server104 of thedata set102. In this manner, theexample method500 ofFIG. 5 enables the server set102 to provide access to thedata set106 on behalf of theworkload114 in accordance with the techniques presented herein, and so ends at524.
• Still another embodiment involves a computer-readable medium comprising processor-executable instructions configured to apply the techniques presented herein. Such computer-readable media may include various types of communications media, such as a signal that may be propagated through various physical phenomena (e.g., an electromagnetic signal, a sound wave signal, or an optical signal) and in various wired scenarios (e.g., via an Ethernet or fiber optic cable) and/or wireless scenarios (e.g., a wireless local area network (WLAN) such as WiFi, a personal area network (PAN) such as Bluetooth, or a cellular or radio network), and which encodes a set of computer-readable instructions that, when executed by a processor of a device, cause the device to implement the techniques presented herein. Such computer-readable media may also include (as a class of technologies that excludes communications media) computer-computer-readable memory devices, such as a memory semiconductor (e.g., a semiconductor utilizing static random access memory (SRAM), dynamic random access memory (DRAM), and/or synchronous dynamic random access memory (SDRAM) technologies), a platter of a hard disk drive, a flash memory device, or a magnetic or optical disc (such as a CD-R, DVD-R, or floppy disc), encoding a set of computer-readable instructions that, when executed by a processor of a device, cause the device to implement the techniques presented herein.
• An example computer-readable medium that may be devised in these ways is illustrated inFIG. 6, wherein theimplementation600 comprises a computer-readable memory device602 (e.g., a CD-R, DVD-R, or a platter of a hard disk drive), on which is encoded computer-readable data604. This computer-readable data604 in turn comprises a set ofcomputer instructions606 that, when executed on aprocessor304 of aserver610, provide anembodiment608 that causes theserver610 to operate according to the principles set forth herein. For example, the processor-executable instructions606 may encode a system that causes aserver104 to provide access to adata set106 on behalf of aworkload114, such as theexample server302 and/or theexample system308 ofFIG. 3. As another example, the processor-executable instructions606 may encode a method of providing access to adata set106 on behalf of aworkload114, such as theexample method400 ofFIG. 4 and/or theexample method500 ofFIG. 5. Many such embodiments may implement various portions of the techniques presented herein.
• E. Variations
• The techniques discussed herein may be devised with variations in many aspects, and some variations may present additional advantages and/or reduce disadvantages with respect to other variations of these and other techniques. Moreover, some variations may be implemented in combination, and some combinations may feature additional advantages and/or reduced disadvantages through synergistic cooperation. The variations may be incorporated in various embodiments to confer individual and/or synergistic advantages upon such embodiments.
• E1. Scenarios
• As a first variation of this first aspect, the currently presented techniques may be utilized with various types ofservers104 and server sets102. For example, the presented techniques may be utilized with a variety ofservers104, such as workstations, laptops, consoles, tablets, phones, portable media and/or game players, embedded systems, appliances, vehicles, and wearable devices. The server set102 may comprise a collection of server units, such as a collection of server processes executing on a device; a personal group of interoperating devices of a user; a local collection of server units comprising a computing cluster; and/or a geographically distributed collection of server units that span a region, including a global-scale distributed database.Such servers104 may be interconnected in a variety of ways, such as locally wired connections (e.g., a bus architecture such as Universal Serial Bus (USB) or a locally wired network such as Ethernet); locally wireless connections (e.g., Bluetooth connections or a WiFi network); remote wired connections (e.g., long-distance fiber optic connections comprising Internet); and/or remote wireless connections (e.g., cellular communication).
• As a second variation of this first aspect, the currently presented techniques may be utilized with a variety ofdata sets106 andworkloads114 that are processed by theserver set102.Such data sets106 may include databases of various types, including relational databases such as SQL, object graph databases, and key/value store databases, as well as mixed-modality databases that support various data structures and/or query languages. The presented techniques may be utilized with a variety ofdata sets106 featuring a variety of data models, such as a relational database comprising tabular data organized into tables comprising sets of attributes and sets of rows presenting values for the respective attributes; graph data comprising a graph of nodes with interconnecting edges; key/value pairs of keys and associated values; and documents provided as structured or unstructured collections of entities. Somedata sets106 may comprise a hybrid of several data models, which may be aggregated in a horizontal manner (e.g., a collection of items of which some items are provided and/or requested in a first native item format, such as relational data, and other items are provided and/or requested in a second native item format, such as entities within documents) and/or non-horizontal manner (e.g., a collection of items in a first native item format, such as entities within documents, may be described by metadata represented by other items provided in a second native item format, such as relational data). Theworkloads114 utilizingsuch data sets106 may include, e.g., websites; web services; microservices; computing environments provided to various devices; data processing services, such as image processing, data mining, and/or artificial intelligence services; and/or local or remote applications, such as games.Such data sets106 andworkloads114 may be used in a variety of circumstances, such as data warehousing; content provided through a content system such as a webserver; and object systems for an application or operating system. Additionally,such data sets106 andworkloads114 may be provided by, provided for, accessed by, and/or processed on behalf of a variety ofclients112, such as a client process on a server storing the data set; other servers within the server set; and/or various client devices that utilize the server set on behalf of one or more users and/or other devices. Many such scenarios may be identified in which the techniques presented herein may be advantageously utilized.
• As a second variation of this first aspect, the currently presented techniques may be utilized with a variety ofperformance criteria122, which may be formalized in service level agreements.Such performance criteria122 may include, e.g., latency criteria; availability criteria; throughput criteria; scalability criteria; and consistency level criteria, which may be defined by consistency models such as strong consistency, bounded staleness consistency, session consistency, prefix consistency, and/or eventual consistency. Other types ofperformance criteria122 may also be involved, such as a redundancy criterion122 (e.g., a number of replicas over which new or updated data is replicated to preserve the data in case one orseveral servers104 fail or lose data); a versioning criterion122 (e.g., a number of version ofdata items108 that are preserved to enable rollback in case of data corruption); a geographic disposition criterion122 (e.g., a placement ofservers104 and/or designation ofmasters116 that includes, excludes, or is limited to selected regions); and/or a security criterion (e.g., an isolation ofdata sets106 and/orworkloads114 to ensure thatservers104 are isolated and dedicated for use for adata set106,workload114, and/or client112). Some service level agreements may specifydifferent performance criteria122 for different portions of thedata set106 and/or workload114 (e.g., different tasks comprising different portions of thedata set106 and/or different types ofworkloads114, such as queries that have different performance sensitivities); for different types of clients112 (e.g.,workloads114 executed by or on behalf of a first class ofclients112 may involve a first set ofperformance criteria122, andworkloads114 executed by or on behalf of a second class ofclients112 may involve a different set of performance criteria122); and/or for different contexts in which adata set106 is utilized and/or aworkload114 is performed (e.g., different performance criteria for peak hours vs. off-hours). Many such variations may be included in variations of the techniques presented herein.
• E2. Master Designation and Server Set Partitioning
• A second aspect that may vary among embodiments of the techniques presented herein involves the designation ofmultiple masters116 among theservers104 that are permitted to update adata item108 of thedata set106, and the partitioning of the server set102 into a master subset of at least twomasters116 and a non-master subset of at least onenon-master318. Some of these variations are illustrated inFIG. 7.
• As a first variation of this second aspect, the server set102 may be partitioned to designate a master subset of at least twomasters116 that are permitted to update anydata item108 of thedata set106 and a non-master subset of at least one non-master318 that is not permitted to update anydata item108 of thedata set106. Alternatively, thedata set106 may be partitioned into a first data subset and a second data subset, and the partitioning may involve partitioning the server set102 into a first set ofmasters116 and non-masters for the first data subset and a second, non-redundant set ofmasters116 and non-masters318 for the second data subset. The subsets of thedata set106 for which different partitions of the server set102 are selected may involve, e.g., different regions over which the server set102 and/ordata set106 is distributed; different types ofdata sets106 and/orservers104; and/ordifferent workloads114 and/orclients112 for whom thedata set106 is provided.
• As a second variation of this second aspect, partitioning the server set102 may involve a designation ofmasters116 on a regional basis; e.g., aserver set102 may be distributed over at least two geographic regions, and the partitioning may involve designating at least oneserver104 in each region as amaster116 of at least somedata items108 of thedata set106. In some embodiments, such designation may be further performed based on determined and/or expected sources ofrequests118 forupdates120 to thedata set106, and the partitioning may involve identifying a geographic location as a source ofrequests118 to update thedata set106 and designating aserver104 of the server set102 that is proximate to the geographic location as amaster116 of thedata items108 that are anticipated to be updated byclients112 near the geographic location.
• As a third variation of this second aspect, the partitioning of the server set102 intomasters116 andnon-masters318 may be based upon the particular types ofperformance criteria122 for theworkload114. That is, different types ofperformance criteria122 may involve different heuristics and/or strategies for partitioning the multi-master server set102 in a manner that promotes the consistent fulfillment of theperformance criteria122.
• FIG. 7 is an illustration of a set ofexample scenarios700 in which aserver set102 for adata set106 is partitioned between a master subset of at least twomasters116 and a non-master subset of at least one non-master318 based upon theparticular performance criteria122 involved in theworkload114.
• A first example shown inFIG. 7 involves aperformance criterion122 comprising alatency threshold702, e.g., a 10-millisecond maximum duration in which anupdate120 is expected to propagate throughout theserver set102. A single-master partitioning704 may be identified as involving a maximum latency of 18 milliseconds, due to the worst-case path by which arequest118 may be forwarded to the selected single master116 (e.g., a selection of asingle master116 located in the United States may involve a lengthy transmission delay fromclients112 located in Asia). Conversely, an all-master partitioning708, in which allservers104 are identified asmasters116, may also involve a high maximum latency due to the extensive coordination involved in propagating theupdate120 to everyserver104 of theserver set102. Amulti-master partitioning706 may present a balancing point in which each non-master318 is relatively proximate to a master116 (thus reducing the forwarding delay in forwardingrequests118 forupdates120 from a non-master318 to a master116), and also limiting the number ofmasters116 to which anupdate120 has to be propagated to ensure further propagation to the entire server set102 as well as verification of the absence of data version conflicts. Themulti-master partitioning706 may therefore provide a placement ofservers104 and/or partitioning betweenmasters116 andnon-masters318 that provides a worst-case latency that is within thelatency threshold702 comprising theperformance criterion122.
• A second example shown inFIG. 7 involves a partitioning of the server set based on aperformance criterion122 specified as an availability of theworkload114 to theclients112. Afirst partitioning710 may be provided for aworkload114 that depends upon high availability, such as a service that has to remain available to receive and process updates120 even in the event of multiple server failures, a wide-scale network partitioning, or a regional catastrophic event, such as a communication platform for first responders or government agencies. The partitioning may therefore involve a designation of a large number ofmasters116, such that anyclient112 that is able to connect to a network such as the Internet is guaranteed to find at least somemasters116 that are available to receive and process updates120. However, thefirst partitioning710 may exhibit high latency in confirmingupdates120 across the entire server set102 and/or may raise the likelihood of data version conflicts. On the other hand, asecond partitioning712 may be provided for a service that involves aperformance criterion122 only involving a low availability forprocessing updates120, such as a relatively static distribution of content that may be widely available for reading but where temporary unavailability forupdates120 and a modest delay in propagatingupdates120 may be tolerable.Such workloads114 may be satisfied by allocating aserver set102 comprising a significant number ofservers104 but designating only afew masters116, such that the majority of theservers104 are non-masters318 that provide read-only access to thedata set106. Such designation may reduce the administrative complexity and the resource allocation in view of therelaxed performance criteria122 of theworkload114. Athird partitioning714 may be provided for aworkload114 specifying aperformance criterion122 of an intermediate availability, where thethird partitioning714 may involve a designation of a modest but not excessive number of masters116 (e.g., onemaster116 in each of several broad geographic regions, such as continents) to provide a balance between availability of theworkload114 toclients112 in the event of localized networking or server failures and the resource costs of the partitioning of theserver set102.
• A third example shown inFIG. 7 involves a partitioning of the server set based on aperformance criterion122 specified as a consistency model. Afirst workload114 may present aperformance criterion122 involving a strong consistency model, such as a condition that a requestedupdate120 is to be committed over the entire server set102 before being reported to aclient112 as a fulfillment of arequest118. Such strong consistency may be appropriate, e.g., for financial transactions that depend upon complete guarantees of reliability. The server set102 in this case may involve a first partitioning716 of the server set102 that involves a strong level of consistency, wherein the first partitioning716 comprises the designation of twomasters116, which may confer with one another to verify and guarantee the absence of data version conflicts involving anupdate120 before reporting the fulfillment of therequest118 to theclient112, where the two-master configuration provides a measure of availability in case one of themasters116 fails or becomes inaccessible. Asecond partitioning718 may involve an intermediate level of consistency, such as session consistency in which eachmaster116 provides a view of thedata set106 that is consistent within a session provided to respective groups ofclients112, though the sessions may differ from one another. Thesecond partitioning718 may involve the selection of onemaster116 for each such group ofclients112, wherein data version conflicts amongupdates120 may result in acceptable differences in versions of adata item108 as perceived by different sessions, and wherein themasters116 may resolve such differences in a relaxed manner to maintain the session consistency of eachmaster116 and group ofnon-masters318. Athird partitioning720 may involve an eventual consistency model, in which eachserver104 may reflect a series ofupdates120 that are temporarily inconsistent with respect to theentire data set106, and whereinupdates120 are eventually received and reorganized by eachserver104 to present a consistent view of thedata set106. Athird partitioning720 may be provided in which allservers104 are designated asmasters116, and in which all servers may eventually propagateupdates120 throughout thedata set102 on an indeterminate but unconstrained basis. In this manner, variations in the types ofperformance criteria122 may inform the designation ofmasters116 and the partitioning of the server set102 in accordance with the techniques presented herein.
• As a fourth variation of this second aspect, a variety of techniques may be used to verify that the partitioning of the server set102 into a master subset and a non-master subset is sufficient to fulfill theperformance criteria122 of theworkload114, such as may be specified in and/or guaranteed by a service level agreement. As a first such example, the capabilities of various partitions of the server set102 may be prospectively evaluated through estimation, prediction, and/or heuristics (e.g., estimating the latency and/or throughput ofrespective servers104 in a selected partitioning of the server set102 and comparing the estimates with a latency threshold and/or estimated volume of the workload114) and compared with a similarly evaluated computational demand in providing theworkload114 according to theperformance criteria122. Alternatively or additionally, a partitionedserver set102 may be subjected to a computational load, either of theworkload114 or of a simulation thereof, and the performance of the partitionedserver set102 may be measured and compared with the performance criteria to verify that the partitionedserver set102 fulfills theperformance criteria122 of thedata set106 and theworkload114. For example, aworkload114 may involve aperformance criterion122 comprising a latency threshold for propagation ofupdates120 to thedata set106, and an embodiment may observe the performance of the server set102 during the commitment ofupdates120 tovarious data items108 in order to verify that theupdates120 of the partitioned server set are completed within the latency threshold. In an embodiment, the evaluation may be performed for a task of theworkload114 by identifying a set of paths through the server set102 by which the task is performed; among the set of paths, identify a worst-performing path (e.g., the longest network path, by distance and/or number of nodes, over which the server set102 communicates regarding anupdate120 of the data set106) and verifying that the worst-performing path fulfills theperformance criterion122.
• As a fifth variation of this second aspect, the designation ofservers104 asmasters116 and non-masters318 and the partitioning of the server set102 into a master subset and a non-master subset—as well as the redesignation and repartitioning, as further discussed herein—may be achieved in a variety of ways. As a first such example, the designation and partitioning may be performed by a user such as an administrator, either via direct selection ofservers104 and designation asmasters116 ornon-masters318, or via the provision of a logic, such as rules or conditions under whichrespective servers104 are to be designated asmasters116 ornon-masters318. As a second such example, the designation and partitioning may be determined in an automated manner, e.g., via rules or heuristics (e.g., a rule that twoservers104 in each region are to be designated asmasters116, such as the twoservers104 that exhibit the lowest update latency and/or that are centrally located, that the rest of theservers104 in the respective regions are to be designated as non-masters318), or via simulation, such as generating a set of candidate partitions of the server set102 and comparing simulated and/or measured performance metrics to identify a partition that may satisfy theperformance criteria122 of a service level agreement. Such comparison may be guided by heuristics, such as genetic selection of candidate partitions, or may be performed by sampling a substantial portion of the search space of the candidate partitions, optionally performing such testing to the exhaustion of the search space. Such searches may also be informed by prior instances of partitions of the server set102 for the same orother data sets106 and/orworkloads114. As a third such example, the partitioning may be performed in a centralized manner (e.g., a single user or process determines the partitioning) or a decentralized manner (e.g.,respective servers104 elect to serve as amaster116 or anon-master318 of adata item108, and conflicts such as too many or twomasters116 are resolved via vote-based consensus). As a fourth such example, the partitioning may be informed by and/or performed according to the details of the server set102 (e.g., designating someservers104 as non-masters that lack the computational resources to applyupdates120 in accordance with a performance criterion122), thedata set106, theworkload114, and/or the client set110 (e.g., examining thedata set106 and the usage by theworkload114 to identify a consistency level and a latency threshold according to the semantics of theworkload114 and/or the geographic distribution of the client set110). As a fifth such example, designation and partitioning may be performed at various levels of granularity (e.g., the designation of aserver104 as amaster116 may apply to alldata items108 of thedata set106, or only to aselect data item108 or even a portion thereof; and the designation of theserver104 as amaster116 may apply to all data sets used byworkloads114 of a particular user or application, or even to all data sets used byworkloads114 of several or even all users or applications). Some embodiments may utilize a combination of such techniques; e.g., an administrator may specify a few heuristics, and an automated process may be applied to choose a partitioning that satisfies theperformance criteria122 in addition to the heuristics. Conversely, an automated process may be utilized to generate a small number of candidate partitions, optionally with varying tradeoffs (e.g., a first partition that presents lower latency but higher consistency than a second partition), and an administrator may be presented with the set of candidate partitions (optionally describing the relative advantages of each) and allow the administrator to choose the partitioning of the server set102 for thedata set106 andworkload114. Many such variations may arise within the range of scenarios within which the currently presented techniques may be utilized.
• E3. Forwarding Requests and Propagating Updates
• A third aspect that may vary among embodiments of the techniques presented herein involves the forwarding324 ofrequests118 fromnon-masters318 tomasters116 and thepropagation320 ofupdates120 frommasters116 toother servers104 of theserver set102. Some of these variations are illustrated inFIG. 8.
• As a first variation of this third aspect, the partitioning of the server set102 into a master subset ofmasters116 and a non-master subset ofnon-masters318 may also involve a designation of communication routes among theservers104. As a first such example, the partitioning may include a designation of routes by whichrespective non-masters318 of adata item108forward requests118 forupdates120 of thedata item108 to masters.Respective servers104 that are designated as anon-master318 of thedata item108 may identify a selectedmaster116 of the master subset for forwardingsuch requests118, and may store the selectedmaster116 in order to facilitate the routing ofrequests118 that the non-master318 is not permitted to fulfill. Later, when arequest118 to update120 thedata item108 is received, the non-master318 may retrieve the stored identification of the selectedmaster116 for thedata item108 and may forward theupdate120 to the identifiedmaster116. As a second such example, the partitioning may include a designation of routes by whichrespective masters116 of adata item108 propagateupdates120 of thedata item108 toother servers104 of theserver set102. For example, amaster116 that updates adata item108 of thedata set106 may first propagate theupdate120 to theother masters116 of thedata item108, e.g., in order to detect and address data version conflicts202 involving mutuallyexclusive updates120 to thedata item108 that one of theother masters116 may have committed. In the absence of such data version conflicts202, eachmaster116 may propagate theupdate120 to a subset ofnon-masters318, e.g., a regional subset of theserver set102. Other routes are also possible; e.g., afirst master116 may propagate theupdate120 to asecond master116, which may in turn propagate theupdate120 to athird master116, etc. In some embodiments, the propagation may specifically include transmitting theupdate120, or a notification thereof, to non-masters318 (e.g., so that a non-master318 servingclients112 that are subscribed toupdates120 of thedata item108 may be promptly notified and may in turn promptly notify the subscribed clients112). In other embodiments, the propagation may be limited to themasters116 of thedata item108, each of which may apply theupdate120 to a local copy of thedata set106, and non-masters318 may receive theupdate120 upon querying thedata item108 or examining a change feed of thedata set106.
• FIG. 8 is an illustration of a set ofexample scenarios800 featuring a variety of techniques for forwarding324requests118 and propagating320updates120 in accordance with the techniques presented herein. As a second variation of this third technique, forwardingtechniques802 may be utilized that involvestatic routing804, whereinrespective non-masters318 store a designation of one or moreselected masters116, among a set ofmasters116 for aparticular data item108, to whom requests118 to update thedata item108 are forwarded. Alternatively, forwardingtechniques802 may be utilized that involve an ad-hoc selection of one of themaster318 for adata item108 in order to forward arequest118 to update thedata item108. In one such ad-hoc forwarding technique806,respective masters116 for adata item108 may report a currentcomputational load808, andnon-masters318forward requests118 to update thedata item108 to themaster116 with the lowest currentcomputational load808, thereby distributing the computational demands of applyingupdates120 to thedata item108 in a load-balanced manner. An embodiment of the currently presented techniques may utilize a combination ofsuch forwarding techniques802, e.g., typically static forwarding with an ad-hoc fallback mechanism if the statically assignedmaster116 exhibits acomputational load808 above a computational load threshold.
• FIG. 8 also presents some examples of a third variation of this third aspect involvingpropagation techniques810 for propagatingupdates120 throughout theserver set102. A first propagation technique involves anotification broadcast812, wherein amaster116 that applies anupdate120 to adata item108 generates abroadcast notification814 that thedata item108 has changed.Such broadcast notifications814 may include the entire server set102 or a propagation subset thereof, such asother masters116 of the updateddata item108 and/ornon-masters318 within a logical group.Respective servers104 may choose to receive orbroadcast notifications814, e.g., through a local filter. Although presenting a comparatively inefficient mechanism,broadcast notifications814 may be asuitable propagation technique810 fordata sets106 that are small or that are not frequently updated, and/or where the server set102 is fluid such thatnon-masters318 that may be interested inupdates120 to thedata set106 may frequently join or depart. A second propagation technique involves a publication/subscription model816, wherein selectedservers104 that are interested in and/or utilizing aparticular data item108 may subscribe818 to receive notifications ofupdates120 applied to thedata item108. Amaster116 that applies anupdate120 to thedata item108 may publish820 a notification to theservers104 that have subscribed818 to receive such notifications. This variation may be more efficient than notification broadcasts812, particularly fordata sets106 that are large and/or that change frequently, as well as scenarios in which the urgency of communicatingupdates120 to a dynamic set ofinterested servers104 is significant. A third propagation technique involves anupdate feed822 stores a series ofupdates824 to thedata set106, in the manner of a journal or log, andother servers104 of the server set102 may examine the update feed822 to receive notifications ofupdates120 to thedata set106. An update feed822 may provide a more persistent record ofupdates120 than may be achieved through typically transient network-based notifications, and may therefore be advantageous, e.g., in sporadically or occasionally connected scenarios in whichservers104 that initially connect or reconnect to the server set102 review the update feed822 to view the history and sequence ofupdates120.Propagation techniques810 may An embodiment of the currently presented techniques may utilize a combination ofsuch propagation techniques810, e.g., a subscription-based model with anupdate feed822 that enables new subscribers of adata item108 to review the history ofupdates120 to thedata item108.
• FIG. 8 also presents a fourth variation of this third aspect that involves a combined forwarding and propagation technique based onregional routing826, whereinregional groups828 are established that define geographic partitions ofservers104 of the server set102, such as a firstregional group828 forservers104 located in North America, South America, and Antarctica; a secondregional group828 forserver104 located in Europe and Africa; and a thirdregional group828 forservers104 located in Asia and Australia. For therespective data items108 of thedata set106, eachregional group828 is partitioned into a master subset of at least onemaster116 and a non-master subset of at least onenon-master318, wherein the multi-master configuration of the server set102 is achieved through the coordination between themasters116 across theregional groups828. A non-master318 that receives arequest118 to update thedata item108 may forward830 therequest118 to themaster116 of thedata item108 within theregional group828 that has been designated for thedata item108. Themaster116 receiving therequest118 may update120 thedata item108 and then communicate with themasters116 of the otherregional groups828 to perform data version conflict detection832 (e.g., determining whether theupdate120 conflicts with anotherupdate120 of thesame data item108 committed by anothermaster116, and either resolving thedata version conflict202 or verifying that nodata version conflict202 exists). Following completion of the dataversion conflict detection832, therespective masters116 may propagate834 theupdate120 to thenon-masters318 within theregional group828. In this manner,regional groups828 may be selected to organize both the forwarding324 ofrequests118 and thepropagation320 ofupdates120.
• As a fifth variation of this third aspect, the partitioning of the designation ofservers104 asmasters116 may also be used to promote the propagation ofupdates120 throughout the server set102 using a variety of transactional and consensus techniques. For example,respective masters116 may be designated as a local transaction coordinator to update thedata set106 as a local consensus of the server subset, and themaster116 may be designated to coordinate with at least oneother master116 as a distributed transaction coordinator to propagateupdates120 as a distributed consensus of theserver set102. That is, anupdate120 may be performed upon thedata set106 by initiating a localized transaction among each server subset by amaster116 designated for the server subset, and a second-level consensus may be performed among themasters116 to establish the propagation of theupdate120 throughout theserver set102. This technique may enable the completion of a nested consensus regarding anupdate120 over a broad set ofservers104 and in a parallelized manner, which may promote the fulfillment of alatency performance criterion122 such as a latency threshold forupdates120 to thedata set106. Many such forwarding and propagation techniques may be utilized in variations of the techniques presented herein.
• E4. Dynamic Master Designation and Repartitioning
• A fourth aspect that may vary among embodiments of the techniques presented herein involves a dynamic master designation, wherein the partitioning of the server set102 into a master set ofmasters116 and a non-master set ofnon-masters318 varies over time. Some of these variations are illustrated in the example set900 ofFIG. 9.
• As a first variation of this fourth aspect, the initial partitioning of the server set102, for therespective data items108, into a master subset and a non-master subset may comprise a dynamic partitioning that is defined as varying according to particular conditions.Respective servers104 are designated as amaster116 of thedata item108 while a master condition is satisfied, and as anon-master318 of thedata item108 while the master condition is not satisfied. The master conditions may be prescriptive, such as a periodic schedule (e.g., wherein aserver104 is designated as amaster116 for aparticular data item108 during a master period of a time cycle, and is designated as a non-master318 for portions of the time cycle outside of the master period), or contingent, such as a reorganization of the server set102 in the event of a scenario such as an overloading of theserver set102.
• FIG. 9 presents an illustration of an exampledynamic partitioning schedule902 based on a circadian cycle. In this exampledynamic partitioning schedule902, theworkload114 involvesupdates120 to aparticular data item108 of adata set106 that occur primarily during business hours (e.g., 8:00 am through 6:00 pm), andperformance criteria122 such as low-latency updates are well-served by positioning one ormore masters116 of thedata item108 near the sources of updates. Since business hours occur at different times around the world in accordance with a circadian cycle, the designation ofmasters116 also changes. At afirst time904 corresponding to 08:00 GMT, business hours occur for both western Europe (CET) and east Asia (JST), but not the west coast of North America (PST); accordingly,servers104 in western Europe and east Asia are designated asmasters116 for thedata item108, andservers104 elsewhere in the world are designated asnon-masters318 that forward updates to either western Europe or east Asia. At asecond time906 corresponding to 16:00 GMT, business hours are occurring on the west coast of North America, but not in east Asia; accordingly, the server set102 is reconfigured to designate amaster116 of thedata item108 on the west coast of North America, while themaster116 in east Asia is redesignated as a non-master318. At athird time908 corresponding to 00:00 GMT, business hours have resumed in east Asia but have concluded in western Europe; accordingly, thewestern Europe master116 is redesignated as a non-master318 for thedata item108, and theeast Asia server104 is again promoted to the designation ofmaster116 for thedata item108. In this manner, the server set102 may be repartitioned in accordance with adynamic selection schedule902 in accordance with the techniques presented herein.
• As a second variation of this fourth aspect, the designation ofmasters116 may change as the server set102, thedata set106, and/or theworkloads114 changes. As a first such example, if anew server104 is added to the server set102, thenew server104 may be added to the partitioning of the server set102 by designation as amaster116 of one ormore data items108 and/or anon-master318 of one ormore data items108. Such designation may also involve redesignating other servers104 (e.g., designating thenew server104 as amaster116 and redesignating aprevious master116 as a non-master318, or designating thenew server104 as a non-master318 and redesignating aprevious non-master318 as a master116). Conversely, if aserver104 is removed from the server set102, the remainingservers104 may be redesignated (e.g., a removal of amaster116 of aparticular data item108 may cause a non-master116 to be designated as amaster116 at least for the particular data item108). As a second such example, the details and circumstances of theservers104 may change, and may prompt a redesignation ofsuch servers104. For example, afirst server104 that has been designated as amaster116 for adata item108 may experience a higher-than-expected computational load, which may jeopardize its ability to service theworkload114 in satisfaction of aperformance criterion122, and asecond server104 that has been designated as a non-master318 may be redesignated as amaster116 of thedata item108, either substituting for or supplementing the master designation of thefirst server104. As a third such example, thedata set106 may be expanded to includeadditional data items108, and/or existingdata items108 may be divided, andservers104 may be designated asmasters116 and non-masters318 for thenew data items108. Conversely, thedata set106 may be reduced to remove and/or consolidatedata items108, and the former designation ofservers104 asmasters116 andnon-masters318 may be removed; optionally, aserver104 that was designated as amaster116 for afirst data item108 that is removed from thedata set106 may be redesignated as amaster116 for asecond data item108. As a fourth such example, theworkload114 involving thedata set106 may change, such as increasing or decreasing volume ofrequests118, fluctuation in the client set110, and/or increasing or decreasing complexity in the logical evaluation of therequests118, and an initial partitioning of the server set102 intomasters116 andnon-masters318 may be adjusted to accommodate the changes to theworkload114 and/or client set110.
• As a third variation of this fourth aspect, the server set102 may be redesignated in response to a comparison of the performance of the server set102 with aperformance criterion122, such as a latency threshold. An initial partitioning of the server set102 into a master subset and a non-master subset for aparticular data item108 may be based on estimates and/or prior metrics of the achievable performance of the partitionedserver set102, such as the anticipated maximum latency arising over the worst-case path in applying anupdate120 to thedata item108, wherein the estimates and/or prior metrics indicate that the partitioning is likely to be sufficient to satisfy theperformance criteria122. However, the actual performance of the server set102 may vary from the estimates and/or prior metrics, e.g., due to inaccuracies in the estimates or variations in the logistics of the server set102 between prior metrics and current metrics. In an embodiment, the server set102 may be subjected to a performance metric, such as a measurement of latency ofvarious updates120 using simulations, test data, or production data. The performance of the server set102 may be measured to determine that the performance metric of the server set jeopardizes the performance criterion122 (e.g., that the maximum latency may, in at least some circumstances, exceed a latency threshold). In response to such detection, the server set102 may be repartitioned in a manner that reduces the jeopardy of violating theperformance criterion122, such as by reducing the latency of the worst-case path.
• FIG. 9 is an illustration of an exampledynamic partitioning910 of aserver set102 in order to balance the load, which particularly involves an evaluation of the current load in order to inform the selection of a more advantageous partition of theserver set102. In this example scenario, aninitial partition912 involves a regional designation ofmasters116, possibly established by the use of a rule or heuristic. Thedata set106 and/orworkload114 may be constrained by aperformance criterion122 including an update latency threshold of 10 milliseconds. It may be discovered that theoriginal partitioning912 exhibits an undesirably high update latency of 12 milliseconds, which exceeds the update latency threshold. In order to promote the fulfillment of theperformance criterion122, a repartitioning of the server set102 may be undertaken; however, the nature of the latency may affect whether respective repartitionings exhibit lower update latency, the same update latency, or even higher update latency than theinitial partition912. For example, the update latency may be caused by a firstupdate latency source914 involving delays in the forwarding324 ofrequests118 fromnon-masters318 tomasters116. These conditions may reflect long distances and/or poor bandwidth betweennon-masters318masters116. Alternatively, update latency may reflect the computational load ofmasters116 that are delayed in receiving andprocessing requests118 forupdates120; even if themasters116 are only moderately loaded and are exhibiting a typical processing delay, such typical processing delay may exacerbate a protracted propagation delay between themaster116 and a particularlyremote client112 ornon-master318. In this scenario, the latency may be addressed by a first repartitioning916 that involves the addition ofmasters116, e.g., by addingnew servers104 to the server set102 for thedata set106 anddata item108 or by redesignating somenon-masters318 asmasters116. Thefirst repartitioning916 may address the firstupdate latency source914 of the update latency and may enable the update latency to satisfy the update latency threshold. Conversely, in a second scenario, a secondupdate latency source918 may involve the duration of propagatingupdates120 among themasters116 about anupdate120, i.e., verifying the absence of data version conflicts202 and/or resolving any data version conflicts202 that may arise. These types of latency may reflect an excessive number ofmasters116, which may make data version conflicts202 more likely; increasing the complexity of resolving data version conflicts202, such as the number ofmasters116 with conflicting updates that have to be reversed; and/or involving an excessive intercommunication delay among a larger number ofmasters116. In these scenarios, asecond repartitioning920 may be selected with fewer masters116 (e.g., redesignating somemasters116 asnon-masters318 of thedata item108 and/or removing somemasters116 from the server set102 for the data set106). This second repartitioning920 may consolidateupdates120 through a smaller number ofmasters116, thereby reducing the incidence of data version conflicts202, the complexity of resolving data version conflicts202, and/or the communication delay among themasters116 to propagateupdates120. It is to be appreciated that such analysis of the source of update latency may lead to divergent and even opposite types of repartitioning of theserver set102. In this manner, an analysis of the cause of update latency may inform the dynamic repartitioning of the server set102 to promote the fulfillment ofperformance criteria122 in accordance with the techniques presented herein.
• As a fourth variation of this fourth aspect, aserver set102 may be repartitioned to accommodate failures of the server set102, such as server hardware or software failures, data corruption, network outages, or emergency outages such as fire, flood, and electrical surges, and power failures. The server set102 may respond to such events in a reactive manner; e.g., responsive to a failure, the server set102 may be repartitioned to maintain the availability of thedata set106 the servicing of theworkload114, and the receipt and processing ofrequests118 fromclients112. For example, when a selectedserver104 that is designated as amaster116 for aparticular data item108 becomes inaccessible, the server set102 may be repartitioned by adding asubstitute server104 and designating it as amaster116, and/or by identifying an existingserver104 that has been designated as a non-master318 for thedata item108 and redesignating it as amaster116 for thedata item108.
• As a fourth variation of this fourth aspect, in addition to partitioning the server set102 intomasters116 andnon-masters318, the partitioning may include a designation of one ormore servers104 as an auxiliary master for a selectedmaster116 to address a computational overload of the selectedmaster116. Theserver104 designated as anauxiliary master116 may typically operate as anon-master318 of thedata item108, e.g., by receivingrequests118 to update thedata item108 and forwarding324such requests118 to the selectedmaster116 or anothermaster116 of theserver set102. However, when the selectedmaster116 becomes inaccessible or inadequate (e.g., while a computational load of the selectedmaster116 exceeds a computational load threshold), the auxiliary master may switch to operating as amaster116 of thedata item108, e.g., by responding torequests118 to update thedata item108 by updating thedata set106 according to therequest118 and propagating320 theupdate120 to at least oneother server104 of theserver set102. In this manner, theauxiliary master116 may supplement the update processing capabilities of the selectedmaster116 during periods of high computational load by directly handling somerequests118 to update120 thedata item108. The offloading of at least a portion of the computational load of the selectedmaster116 may enable it to reduce its computational load to below the computational load threshold.
• The designation ofauxiliary masters116 may vary in numerous respects. As a first such example, the designation as an auxiliary master may be performed, e.g., by the selected master116 (e.g., eachmaster116 of thedata set106 for adata item108 may identify and/or select a non-master318 to serve as itsauxiliary master116 for the data item108); by the non-master318 (e.g., as a voluntary designation by the non-master318); and/or by an administrator of theserver set102. In some scenarios, a pool of one or more non-masters318 may be identified as members of an auxiliary master pool, such that excessive computational load exhibited by anymaster116 may result in the selection of a member of the auxiliary master pool to serve as the auxiliary server for the selectedmaster116. As a second such example, the designation as an auxiliary master for the selectedmaster116 may occur proactively (e.g., as part of the initial partitioning of the server set102, including the initial designation of theserver104 as a non-master318 for the data item108) and/or reactively (e.g., in response to the determination that the selectedmaster116 is subjected to an excessive computational load). As a third such example, a pool of one or more non-masters318 may be identified as members of an auxiliary master pool, such that a computational overload anymaster116 may result in the selection of a member of the auxiliary master pool to serve as an auxiliary server for the selectedmaster116. As a fourth such example, thesame non-masters318 are designated asauxiliary masters116 for a selectedmaster116 forseveral data items108 of thedata set106, optionally including alldata items108 of thedata set106, to assist with the processing of the computational load of the selectedmaster116. Alternatively,different non-masters318 may be selected asauxiliary masters116 for a selectedmaster116 fordifferent data items108, which may enable an excessive computational load of the selectedmaster116 to be distributed over thenon-masters318 of an auxiliary master pool. As a fourth such example, the selection ofauxiliary masters116 fordifferent data items108 for which a selectedmaster116 is so designated may occur simultaneously (e.g., when a computational threshold is exceeded by the selectedmaster116,auxiliary masters116 may be activated for several or alldata items108 for which the selectedmaster116 is so designated). Alternatively, the designations may vary; e.g., a firstauxiliary master116 may be activated for afirst data item108 when the computational load of the selectedmaster116 exceeds a first computational threshold, and a firstauxiliary master116 may be activated for asecond data item108 when the computational load of the selectedmaster116 exceeds a second, greater computational threshold. As a fifth such example, when the computational load of the selectedmaster116 is restored to within the computational load threshold, theauxiliary master116 may continue operating as an auxiliary master116 (e.g., continuing to offload at least a portion of the computational load of the selectedmaster116, optionally for a brief duration to ensure that the computational load of the selectedmaster116 does not promptly exceed the computational load threshold again); or theauxiliary master116 may be redesignated as a non-master318, and may refrain from further applyingupdates120 to thedata item108 in thedata set106; or theauxiliary master116 may permanently substitute for the selectedmaster116, which may be redesignated as a non-master318 for thedata item108.
• As a fifth variation of this fourth aspect, in addition to partitioning the server set102 intomasters116 andnon-masters318, the partitioning may include a designation of one ormore servers104 as a failover master for a selectedmaster116 to address a failure or inaccessibility of the master116 (e.g., a hardware or software failure, data corruption, an electrical surge or power failure, or a network partitioning). When the selectedmaster116 is operational, theserver104 may operate as a non-master318, e.g., by forwardingrequests118 to update thedata item108 to amaster116 of thedata item108, optionally the selectedmaster116. However, responsive to a failure of the selectedmaster116 that causes the selectedmaster116 to become inaccessible, theserver104 may transition to a designation as afailover master116 for thedata item108, e.g., fulfillingrequests118 to update120 thedata item108 by directly updating thedata item108 in thedata set106. In the event that the selectedmaster116 processed receivedrequests118 and appliedupdates120 of thedata item108 to local copy of thedata set106 during the period in which the selectedmaster116 was inaccessible, theupdates120 to thedata item108 may be compared to determine and resolve the presence of data version conflicts202 of thedata item108, or to verify the absence thereof.
• The designation offailover masters116 may vary in numerous respects. As a first such example, the designation as a failover master may be performed, e.g., by the selected master116 (e.g., eachmaster116 of thedata set106 for adata item108 may identify and/or select a non-master318 to serve as itsfailover master116 for the data item108); by the non-master318 (e.g., as a voluntary designation by the non-master318); by a consensus of the server set102 (e.g., themasters116 of the server set102 for aparticular data item108 may determine by consensus that the selectedmaster116 is unavailable, and may choose the non-master318 as a failover master116); and/or by an administrator of theserver set102. As a second such example, the designation as a failover master for the selectedmaster116 may occur proactively (e.g., as part of the initial partitioning of the server set102, including the initial designation of theserver104 as a non-master318 for the data item108) and/or reactively (e.g., in response to the determination that the selectedmaster116 is inaccessible). As a third such example, a pool of one or more non-masters318 may be identified as members of a failover master pool, such that the failure of anymaster116 may result in the selection of a member of the failover master pool to serve as the failover server for the selectedmaster116. As a fourth such example, thesame non-masters318 are designated asfailover masters116 for a selectedmaster116 forseveral data items108 of thedata set106, optionally including alldata items108 of thedata set106, which may enable a mass transfer of responsibility in the event of a failure of the selectedmaster116. Alternatively,different non-masters318 may be selected asfailover masters116 forrespective data items108 for which the selectedmaster116 is designated as amaster116, which may result in a distribution of the computational load of the failedmaster116 over a set ofnon-masters318. As a fifth such example, when a selectedmaster116 that has failed becomes accessible again (e.g., due to a recovery or replacement of failed hardware or software, a correction of corrupted data, or a restoration of power and/or network connectivity), thefailover master116 may be redesignated as a non-master318, and may refrain from further applyingupdates120 to thedata item108 in thedata set106 in lieu of the selectedmaster318; or thefailover master116 may permanently substitute for the selectedmaster116, which may be redesignated as a non-master318 for thedata item108.
• FIG. 9 includes an illustration of an exampledynamic partitioning922 that includes two variations in the designation offailover masters116. In this example scenario, anoriginal designation924 of the server set102 involves a partitioning for aparticular data item108 of thedata set106, wherein the partitioning comprises a master subset of one ormore masters116 designated for each geographic region and a non-master subset comprising the remainingservers104 in each region asnon-masters318.
• FIG. 9 depicts a first example of this fifth variation of this fourth aspect, in which afailover master pool926 is identified that comprises a subset of thenon-masters318 that are held in reserve to participate asfailover masters116 in the event of a failure of amaster116. When a selectedmaster116 fails, thefailover master pool926 may be examined to identify and choose anon-master318 of thefailover master pool926 that is to server as thefailover master116 in place of the selectedmaster318. Such selection may involve, e.g., choosing thenearest non-master318 that is not already serving as afailover master116 for anothermaster116 that has previously failed (which may occur, e.g., with a particularlylarge server set102 in which more than onemaster116 may fail at any particular time, or in response to a large-scale event such as a regional power outage or network partition that causes at least twomasters116 to become concurrently inaccessible), and/or according to the computational load and/or network latency of the non-masters318. The establishment of afailover master pool926 may provide flexibility to choosenon-masters318 that substitute formasters116 in the event of the failure ofnumerous masters116, as well as a measure of redundancy that may support an availability guarantee (e.g., a statement that everymaster116 in the server set102 is backed by at least sixnon-masters318 that may serve as failover masters116).
• FIG. 9 also depicts a second example of this fifth variation of this fourth aspect, in which the partitioning of the server set102 intomasters116 andnon-masters318 includesfailover routes928, e.g., identified succession paths in which non-masters318 are to serve asfailover masters116 in the event of a failure of a selectedmaster116. For example, the partitioning may identify a selectedmaster116 for thedata item108 in a particular region, as well as afirst non-master318 that serves as thefirst failover master116 in case the selectedmaster116 is inaccessible, and asecond non-master318 that serves as thesecond failover master116 in case both the selectedmaster116 and thefirst failover master116 are inaccessible. The establishment offailover routes928 may promote certainty in the transition of mastership from a failed selectedmaster116 to a non-master318 serving as afailover master116, which may promote rapidity in the substitution ofservers104 to address server failures or inaccessibility. Many such techniques may be utilized to repartition the server set102 betweenmasters116 and non-masters318 for adata item108 in embodiments of the techniques presented herein.
• E5. Data Version Conflict Detection and Resolution
• A fifth aspect that may vary among embodiments of the presented techniques involves the detection and resolution of data version conflicts202 due to the multi-master configuration of the server set102, wherein mutuallyincompatible updates120 of adata item108 may be committed bydifferent masters116 of thedata item108 and may causedifferent servers104 to perceive different versions of thedata set106.
• As an example of such adata version conflict202, thedata item108 may comprise a counter with an initial value of 10; thefirst update120 may specify an increase in the value of the counter from 10 to 12; and thesecond update120 may specify an increase in the value of the counter from 10 to 14. The final value of the counter may vary depending on how theupdates120 are received and processed bydifferent masters116. Afirst master116 may receive and apply the first update120 (making the value 12), and may then receive thesecond update120 but may reject thesecond update120 as inapplicable since the value of the counter is no longer 10. Asecond master116 may receive and apply the second update120 (making the value 14), and may then receive thefirst update120 but may reject thefirst update120 as inapplicable since the value of the counter is no longer 10. Athird master116 may concurrently receive both updates120 (e.g., receiving oneupdate120 while theother update120 is still pending, or even receiving bothupdates120 simultaneously), may identify the potential for adata version conflict202, and may reject bothupdates120, leaving thedata item108 in its initial state with a value of 10. Afourth master116 may receive and commit thefirst update120, may then receive thesecond update120 and identify the potential for adata version conflict202, and may initiate a rollback of thefirst update120—such that that the counter briefly exhibits thevalue 12, but then reverts to thevalue 10. Afifth master116 may receive and commit thesecond update120, may then receive thefirst update120 and identify the potential for adata version conflict202, and may initiate a rollback of thesecond update120—such that that the counter briefly exhibits the value 14, but then reverts to thevalue 10. Asixth master116 may receive bothupdates120 and determine that thefirst update120 requests a value increase of two, and thesecond update120 requests a value increase of four, and, by applying thefirst update120 and then thesecond update120, such that the value of thedata item108 is briefly 12 and then ends at 16. Aseventh master116 may follow a similar process, but may receive and apply theupdates120 in the opposite order—such that the value of thedata item108 is briefly 14 and then ends at 16. In this manner, the processing of twoupdates120 of a single, relativelysimple data item108 may result in a variety of data versions that reflect differences in the processing performed by eachmaster116 in a multi-master configuration. The details may become even more complicated, e.g., if more than twoupdates120 and/or more than twomaster116 are involved, resulting in more than two data versions; if anupdate120 involvesseveral data items108, such as a transfer of value from afirst data item108 to asecond data item108, and moreover wherein therespective data items108 may have different sets ofmasters116; and/or if the complexity of thedata item108 is substantial.
• As noted, the configuration of aserver set102 withmultiple masters116 may introduce or increase the prospects of data version conflicts202 involvingconflicting updates120 bydifferent masters116. A variety of techniques may be utilized to detect and resolve such data version conflicts.
• As a first variation of this fifth aspect, the detection of adata version conflict202 may occur in many ways. As a first such example, afirst master116 that endeavors to apply anupdate120 to adata item108 may find that a previously applied and/or concurrently pendingupdate120 by asecond master116 produces a different version of thedata item108, such that applying theupdate120 by themaster116 may leave thedata item108 in an inconsistent state. As a second such example, afirst master116 may apply afirst update120 to thedata item108, and may subsequently receive asecond update120 of thedata item108 propagated by asecond master116 that conflicts with thefirst update120. As a third such example,respective masters116 may applyupdates120 to local copies of thedata set106, and a synchronization process that endeavors to synchronize the local copies of the data set106 (e.g., on a periodic basis) may identify adata version conflict202 involving different versions of thedata item108 in different local copies of thedata set106. As a fourth such example, a process may scan thedata set106 and may discover the presence of data version conflicts202 therein; e.g., the data version conflicts may involve a violation of a constraint of thedata set106, such as a violation of a schema of thedata set106 or a broken relationship, such as where afirst master116 creates a relationship of a first record to a second record while asecond master116 deletes the second record.
• As a second variation of this fifth aspect, the resolution of thedata version conflict202 may take many forms. As a first such example, a resolution of adata version conflict202 may comprise, e.g., a selection of one or more of theupdates120 that together provide a canonical state of thedata item108, wherein at least onenon-selected update120 is to be discarded and/or rolled back from thedata set106. As a second such example, where thedata version conflict202 involves a discrepancy among themasters116 as to a sequential order in whichvarious updates120 are to be applied to thedata item108, the data version conflict resolution outcome may comprise, e.g., a canonical ordering in which theupdates120 are to be applied to thedata item108. As a third such example, the data version conflict resolution may involve a provision of anew update120 to thedata item108 that represents the canonical state of thedata item108 after taking into account theconflicting updates120. In some cases, thenew update120 may not be selected from any of theupdates120, but may rather be asuperseding update120 generated by the conflict resolution technique.
• As a third variation of this fifth aspect, conflict resolution may be performed using a selected conflict resolution technique for anydata item108 of thedata set106. Alternatively, the server set102 may comprise a conflict resolution technique set comprising a set of conflict resolution techniques that, respectively, evaluate adata version conflict202 between two or moreconflicting updates120 of adata item108 to identify a data version conflict resolution outcome; and therespective data items108 of thedata set106 may indicate the selected data version conflict resolution technique to be invoked when data version conflicts202 involving the selecteddata item108 arise. This variation may enable data version conflicts202 involving different portions of thedata set106 to be resolved using different data version conflict resolution techniques, which may be suitable formany data sets106 that involvedata items108 of different types, semantic uses, and/or rules for resolving data version conflicts202. When adata version conflict202 is detected, the data version conflict resolution technique that is associated with at least one of thedata items108 involved in thedata version conflict202 may be selected and invoked to resolve thedata version conflict202.
• In some variations, different portion of thedata set106 may be associated, e.g. in a static manner, with a particular data conflict resolution technique. For instance, certain sections, tables, paths, and/or data element types of thedata set106 may be associated with a first data version conflict resolution technique, while other sections, tables, paths, and/or data element types of the data set of a workload may be associated with a different data version conflict resolution technique. Alternatively or additionally, a portion of thedata set106 may be associated with multiple data version conflict resolution techniques, which may be selected in combination (e.g., to identify a consensus in the data version conflict resolution among the various data version conflict resolution techniques) and/or in a priority order (e.g., invoking a first data version conflict resolution technique, and either applying it if the first data version conflict resolution technique produces a high-confidence output, or invoking a second data version conflict resolution technique if the first data version conflict resolution technique produces a low-confidence output). In some embodiments, the particular data version conflict resolution technique to be applied to a portion of thedata set106 may be specified by aclient112. In some embodiments, the particular data version conflict resolution technique to be applied to a portion of thedata set106 may be determined on an ad-hoc basis (e.g., an API may be called with the details of thedata version conflict202, and may therefore choose a data version conflict resolution technique to resolve the data version conflict202). In some embodiments, the particular data version conflict resolution technique to be applied to a portion of thedata set106 may be inferred, e.g., based on the context in which thedata version conflict202 arises, such as the type of conflict and/or the type ofdata item108 involved in the conflict.
• FIG. 10 is an illustration of anexample set1000 of examples demonstrating a few data version conflict resolution techniques.
• FIG. 10 presents, as a first such example, a resolution of adata version conflict202 using a manualconflict resolution technique1002. When a data version conflict arises within a portion of thedata set106, aserver104 may register the data version conflict202 (e.g., in a data version conflict log) and/or notify aclient112, such as a user or process that manages thedata set106 and/or the workload, as a request to resolve the data version conflict. In some embodiments, theserver104 may send a dataversion conflict notice1010 to theclient112 that asks theclient112 to resolve the conflict, e.g., by deleting one of the conflicting data versions and/or selecting one of the data versions as the controlling data version. In some embodiments, theserver104 may assist theclient112 in resolving thedata version conflict202, e.g., by identifying and describing thedata version conflict202 and/or by presenting selectable options to theclient112 to resolve the conflict, optionally including details about the consequences of selecting each such option (such as presenting a view of the data set if each option is selected). In some embodiments, theserver104 may provide additional resources to enable theclient112 to resolve the conflict, e.g., executing code provided by the client to evaluate and/or resolve thedata version conflict202. Theselection1012 that theclient112 provides in response to the data version conflict202 (e.g., the selected value that is to be applied in lieu of one, several, or all of the conflicting data versions) may be applied by themaster116 to thedata item108 in thedata set106 to resolve thedata version conflict202.
• FIG. 10 presents, as a second such example, a resolution of adata version conflict202 using a write priority data versionconflict resolution technique1004, such as a last-writer-wins policy. For example, a particular workload may be significantly based on a latest version of thedata set106, with little or no interest in maintaining past versions of thedata set106, such that data version conflicts202 may be resolved by automatically choosing the latest update and overwriting previous versions of thedata item108, including earlier writes presented by data version conflicts202. In such embodiments, themaster116 may automatically resolve data version conflicts by identifying and choosing the latest write. “Latest” may be determined in a variety of ways; e.g., if the distributed servers share a synchronized clock,respective updates120 may be compared by timestamp, but if the distributed servers to not share a synchronized clock, theupdates120 may be compared by logical sequence numbers. In some variations, thelatest update120 may be selected whileconflicting updates120 are simply discarded; in other variations, theconflicting updates120 may not be applied to thedata set106, but may be recorded in a log, used to update a logical sequence number of the updates, etc. Other variations that involve a relatively simple comparison and selection include: first-writer-wins (e.g., subsequent conflicting writes are discarded and may be reinitiated based on the updated data set); prioritization (e.g., updates120 received and/or applied by afirst master116, or initiated by afirst client112, or of a certain value, may takewrite priority1014 overupdates120 received and/or applied by adifferent master116, initiated by adifferent client112, or of a different value); and/or side-effects (e.g., updates120 that require little or no rollback ofother updates120 may be selected over writes that require extensive rollback of other updates120). In some instances, data version conflicts202 may be selected arbitrarily (e.g., based on random number selection) and/or consensus (e.g.,different masters116 may vote on which of the conflicting data versions to accept). In some cases, multipleconflicting updates120 may all be applied to resolve the data version conflict202 (e.g., a first update that involves incrementing a data element and a second update that involves decrementing a data element may both be applied without conflict to the data element, and/or may be identified as canceling each other and therefore both dropped). Amaster116 may receive from the write priority data versionconflict resolution technique1004 the one ormore updates120 provided as the data versionconflict resolution outcome1016 and apply such updates to resolve thedata version conflict202.
• FIG. 10 presents, as a third such example, a resolution of adata version conflict202 using a stored logic data versionconflict resolution technique1006. Aclient112 may specify that aparticular logic1022 is to be used to evaluate and/or resolve any data version conflicts202 that arise within a particular portion of thedata set106. Thelogic1022 may be stored, e.g. as a stored procedure that is triggered whenever adata item108 of thedata set106 is updated and/or whenever adata version conflict202 is identified. When amaster116 identifies adata version conflict202 involving multiple data versions of adata item108 applied bydifferent masters116, themaster116 may retrieve and invoke1018 thelogic1022 with the collection of conflicting data versions of thedata item108; thelogic1022 may provideoutput1020 comprising a selection of one or more data version of thedata item108 to accept; and themaster116 may apply the selected data version and discard the conflicting data versions. In some circumstances, thelogic1022 may be stateful (e.g., recording the incidence of data version conflicts, and/or resolving a current data version conflict in view of past data version conflicts) and/or may generate reports for theclient112 of the workload. In some embodiments, the stored logic data versionconflict resolution technique1006 may be limited to an examination of the conflicting data versions (e.g., in order to expedite resolution of the data version conflict202). In other embodiments, the stored logic data versionconflict resolution technique1006 may be permitted to inspect other aspects of thedata set106 in the context of evaluating and resolving the data version conflict (e.g., determining the consequences of choosing each data version on the overall integrity of thedata set106 of the workload). In some embodiments, amaster116 may invoke thelogic1022 within a snapshot isolation (e.g., thelogic1022 may be presented with a view of thedata set106 at the time thedata version conflict202 arose and/or was detected); in other embodiments, amaster116 may apply thelogic1022 to a live, dynamic version of the data set106 (e.g., the stored logic data versionconflict resolution technique1006 may be presented with a current view of the data set106). In some embodiments, thelogic1022 may be invoked on an ad-hoc basis, e.g., to evaluate and resolve an identified and currently pendingdata version conflict202. Alternatively or additionally, thelogic1022 may be invoked on a prospective and/or proactive basis (e.g., alogic1022 that scans thedata set106 of a workload to identify as-yet-undetected data version conflicts202, and/or that examines pending transactions or activities to identify emerging instances of data version conflicts).
• FIG. 10 presents, as a fourth such example, a resolution of adata version conflict202 involving a conflict resolution data type (CRDT)technique1008. A conflict resolution data type schema and/or specification may be provided that indicates the semantics of data version conflict resolution for any and alldata items108 of respective conflict resolution data types. For example, adata item108 may be identified as an array. Data version conflicts may take the form of concurrent requests to add an item to the array while it is in a particular state (e.g., both afirst master116 and asecond master116 may agree that the array currently has three elements, but bothmasters116 may initiate requests to submit different items as the fourth element in the array). The conflict resolution data type schema may be consulted to determine that such data version conflicts202, in the context of an array, may be resolved by appending both items into the array, and optionally a selected appending order. As a second example, adata item108 element may be identified as a value that is modified in a relative manner. For example, a counter-type integer with an initial value of 10 may be the subject ofconflicting updates120 of a data item108: afirst update120 that indicates a value of 12 and asecond update120 that indicates a value of 15. Theconflicting updates120 may be interpreted as requests to increment the value by 2 and 5, respectively, and both updates may be applied by incrementing the value by 7 and writing the new value of 17. Alternatively, a value-type integer with an initial value of 10 may be the subject of conflicting updates120: afirst update120 that requests a value of 12 and asecond update120 that requests a value of 15. In this case, theupdates120 may be identified as mutually exclusive—i.e., thedata item108 may comprise a reference to an identifier of anotherdata item108, and can only comprise either the value 12 (referencing a second data element) or value 15 (referencing a third data element), but not any other value. A selection may be made, or at least a pending data conflict may be registered. In some scenarios,clients112 may be permitted to define one or more conflict resolution data types (CRDTs) and/or the semantics of updating such data types and resolving data version conflicts202 thereof. In some scenarios, the conflict resolution data types ofvarious data items108 may be specified by aclient112, such as metadata annotations of the data elements according to the data types specified in the CRDT schema (e.g., “this integer is a counter” vs. “this integer is a reference”). Alternatively or additionally, the conflict resolution data types ofrespective data items108 may be inferred, e.g., from the data item108 (such as its name); from the access and/or usage patterns of thedata item108; and/or from similarities withother data items108 for which conflict resolution data types have previously been identified. In some scenarios, the CRDT may be formalized as an application programming interface (API) that accepts adata version conflict202 and other factors, such as the circumstances in which thedata version conflict202 arose, and that determines and applies an appropriate conflict resolution data type for theinvolved data item108. In some embodiments (particularly inferences), the selected conflict resolution data type and associated resolution technique may be automatically applied (e.g., where the confidence in the inference is high) either permanently or tentatively; and/or the selected conflict resolution type and associated resolution technique may merely be identified and presented as a suggestion, e.g., to a client, a workload, and/or a conflict resolution delegate process.
• As a fourth variation of this fifth aspect, aserver set102 may permit further access to thedata item108 while adata version conflict202 involving thedata item108 is pending (e.g., responding to read requests by indicating the existence of the pending data version conflict and/or specifying the content of different data versions, and/or by selecting a default or tentative data version conflict that is to be tentatively considered the current state of the data element until the data version conflict is resolved). In other embodiments, the server set102 may restrict access to thedata item108 while thedata version conflict202 is pending (e.g., quarantining thedata item108 fromupdates120 and optionally even requests118 to read thedata item108 until thedata version conflict202 has been resolved).
• As a fifth variation of this fifth aspect, the selection and invocation of a data version conflict resolution technique to resolve adata version conflict202 may be performed by anymaster116 of theserver set102. Such variations may be significant, e.g., to reduce or avoid scenarios in which two ormore masters116 of adata item108 detect the incidence of adata version conflict202 and concurrently initiate data version conflict resolution techniques. For instance, eachmaster116 may concurrently apply anupdate120 to thedata item108, and eachmaster116 may forward itsupdate120 to theother master116. Responsive to receiving theupdate120 from theother master116, eachmaster116 may identify adata version conflict202 involving the mutual exclusivity of the receiveupdate120 and itsown update120. Accordingly, eachmaster116 may, concurrently with theother master116, invoke a data version conflict resolution technique to resolve thedata version conflict202. In some cases, such concurrent invocation may lead to identical or equivalent results by bothmasters116, thus presenting an inefficiency and a duplication of effort. In other cases, such concurrent invocation may lead to a different data version conflict resolution by eachmaster116, thus resulting in a potential exacerbation of thedata version conflict202 and further divergence of thedata set106, particularly as eachmaster116 may operate as if thedata version conflict202 has been detected and resolved.
• In some embodiments, amaster116 that detects thedata version conflict202 may automatically select and invoke the data version conflict resolution technique, and may apply anupdate120 generated thereby to resolve thedata version conflict202, as well as propagate theupdate120 toother servers104 of theserver set102. Alternatively, it may be advantageous to choose aparticular master116 to select and invoke the data version conflict resolution technique for a particulardata version conflict202. In some embodiments, the server set102 may include amaster318 that is further identified as a data versionconflict resolution master318 for at least a portion of thedata set106. Aserver104 that identifies adata version conflict202 and/or that is designated as amaster116 for adata item108 involved in adata version conflict202 may further determine whether or not it has been designated as the data version conflict resolution master for thisdata version conflict202. If so, it may select, from a conflict resolution technique set, a conflict resolution technique that evaluates theupdates120 comprising thedata version conflict202; may invoke the conflict resolution technique set to generate a data versionconflict resolution outcome1016; may apply the data versionconflict resolution outcome1016 to thedata set106; and/or may propagate the data versionconflict resolution outcome1016 toother masters116 of thedata set106. Alternatively, if theserver104 determines that asecond server104 of the server set102 has been designated as the data version conflict resolution master for thisdata version conflict202, theserver104 may notify thesecond server104 of thedata version conflict202 and may await resolution by thesecond server104.
• FIG. 11 is an illustration of someexample scenarios1100 featuring a designation of a data versionconflict resolution master1112 to resolve adata version conflict202.FIG. 11 presents, as a first such example1102, adesignation1108 of a data versionconflict resolution master1112 in a static master; e.g.,respective data items108 of thedata set106 may havedesignations1108 of both themasters116 of thedata item108 and the data versionconflict resolution master1112 for thedata item108. When aserver104 identifies adata version conflict202 involving aparticular data item108, theserver104 may identify the data versionconflict resolution master1112 that has been designated for thedata item108 and may notify the data versionconflict resolution master1112 of thedata version conflict202.
• FIG. 11 presents, as a second such example1104, adesignation1108 of a data versionconflict resolution master1112 in a dynamic manner. In this second example1104, among themasters116 in each of several geographic regions, a data versionconflict resolution master1112 is identified for each such region. In response to adetection1110 of adata version conflict202, adesignation1108 of a data versionconflict resolution master1112 for thedata version conflict202 may be performed, e.g., by identifying themaster116 that has been designated as a data versionconflict resolution master1112 for the geographic region in which thedata version conflict202 is initially detected. Thedata version conflict202 may be forwarded to the data versionconflict resolution master1112 for the region for resolution.
• FIG. 11 presents, as a third such example,1106, an ad-hoc designation1108 of a data versionconflict resolution master1112. In this third example1106, at the time of adata version conflict202,different masters116 that may serve as a data versionconflict resolution master1112 may be subjected to an evaluation of a currentcomputational load1114. Themaster116 currently exhibiting the lowestcomputational load1114 amongsuch masters116 may be designated as the data versionconflict resolution master1112 for thedata version conflict202. Many such data version conflict resolution techniques may be selected and applied to various portions of the data set of a workload in accordance with the techniques presented herein.
• F. Example Computing Environment
• FIG. 12 and the following discussion provide a brief, general description of a suitable computing environment to implement embodiments of one or more of the provisions set forth herein. The operating environment ofFIG. 12 is only one example of a suitable operating environment and is not intended to suggest any limitation as to the scope of use or functionality of the operating environment. Example computing devices include, but are not limited to, personal computers, server computers, hand-held or laptop devices, mobile devices (such as mobile phones, Personal Digital Assistants (PDAs), media players, and the like), multiprocessor systems, consumer electronics, mini computers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like.
• Although not required, embodiments are described in the general context of “computer readable instructions” being executed by one or more computing devices. Computer readable instructions may be distributed via computer readable media (discussed below). Computer readable instructions may be implemented as program modules, such as functions, objects, Application Programming Interfaces (APIs), data structures, and the like, that perform particular tasks or implement particular abstract data types. Typically, the functionality of the computer readable instructions may be combined or distributed as desired in various environments.
• FIG. 12 illustrates anexample scenario1200 featuring a system comprising acomputing device1202 configured to implement one or more embodiments provided herein. In one configuration,computing device1202 includes at least oneprocessing unit1206 andmemory1208. Depending on the exact configuration and type of computing device,memory1208 may be volatile (such as RAM, for example), nonvolatile (such as ROM, flash memory, etc., for example) or some combination of the two. This configuration is illustrated inFIG. 4 by dashedline1204.
• In other embodiments,device1202 may include additional features and/or functionality. For example,device1202 may also include additional storage (e.g., removable and/or non-removable) including, but not limited to, magnetic storage, optical storage, and the like. Such additional storage is illustrated inFIG. 4 bystorage1210. In one embodiment, computer readable instructions to implement one or more embodiments provided herein may be instorage1210.Storage1210 may also store other computer readable instructions to implement an operating system, an application program, and the like. Computer readable instructions may be loaded inmemory1208 for execution byprocessing unit1206, for example.
• The term “computer readable media” as used herein includes computer storage media. Computer storage media includes volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions or other data.Memory1208 andstorage1210 are examples of computer storage media. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, Digital Versatile Disks (DVDs) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed bydevice1202. Any such computer storage media may be part ofdevice1202.
• Device1202 may also include communication connection(s)1216 that allowsdevice1202 to communicate with other devices. Communication connection(s)1216 may include, but is not limited to, a modem, a Network Interface Card (NIC), an integrated network interface, a radio frequency transmitter/receiver, an infrared port, a USB connection, or other interfaces for connectingcomputing device1202 to other computing devices. Communication connection(s)1216 may include a wired connection or a wireless connection. Communication connection(s)1216 may transmit and/or receive communication media.
• The term “computer readable media” may include communication media. Communication media typically embodies computer readable instructions or other data in a “modulated data signal” such as a carrier wave or other transport mechanism and includes any information delivery media. The term “modulated data signal” may include a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal.
• Device1202 may include input device(s)1214 such as keyboard, mouse, pen, voice input device, touch input device, infrared cameras, video input devices, and/or any other input device. Output device(s)1212 such as one or more displays, speakers, printers, and/or any other output device may also be included indevice1202. Input device(s)1214 and output device(s)1212 may be connected todevice1202 via a wired connection, wireless connection, or any combination thereof. In one embodiment, an input device or an output device from another computing device may be used as input device(s)1214 or output device(s)1212 forcomputing device1202.
• Components ofcomputing device1202 may be connected by various interconnects, such as a bus. Such interconnects may include a Peripheral Component Interconnect (PCI), such as PCI Express, a Universal Serial Bus (USB), Firewire (IEEE 1394), an optical bus structure, and the like. In another embodiment, components ofcomputing device1202 may be interconnected by a network. For example,memory1208 may be comprised of multiple physical memory units located in different physical locations interconnected by a network.
• Those skilled in the art will realize that storage devices utilized to store computer readable instructions may be distributed across a network. For example, acomputing device1220 accessible vianetwork1218 may store computer readable instructions to implement one or more embodiments provided herein.Computing device1202 may accesscomputing device1220 and download a part or all of the computer readable instructions for execution. Alternatively,computing device1202 may download pieces of the computer readable instructions, as needed, or some instructions may be executed atcomputing device1202 and some atcomputing device1220.
• G. Usage of Terms
• Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.
• As used in this application, the terms “component,” “module,” “system”, “interface”, and the like are generally intended to refer to a computer-related entity, either hardware, a combination of hardware and software, software, or software in execution. One or more components may be localized on one computer and/or distributed between two or more computers.
• Furthermore, the claimed subject matter may be implemented as a method, apparatus, or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof to control a computer to implement the disclosed subject matter. The term “article of manufacture” as used herein is intended to encompass a computer program accessible from any computer-readable device, carrier, or media. Of course, those skilled in the art will recognize many modifications may be made to this configuration without departing from the scope or spirit of the claimed subject matter.
• Various operations of embodiments are provided herein. In one embodiment, one or more of the operations described may constitute computer readable instructions stored on one or more computer readable media, which if executed by a computing device, will cause the computing device to perform the operations described. The order in which some or all of the operations are described should not be construed as to imply that these operations are necessarily order dependent. Alternative ordering will be appreciated by one skilled in the art having the benefit of this description. Further, it will be understood that not all operations are necessarily present in each embodiment provided herein.
• Any aspect or design described herein as an “example” is not necessarily to be construed as advantageous over other aspects or designs. Rather, use of the word “example” is intended to present one possible aspect and/or implementation that may pertain to the techniques presented herein. Such examples are not necessary for such techniques or intended to be limiting. Various embodiments of such techniques may include such an example, alone or in combination with other features, and/or may vary and/or omit the illustrated example.
• As used in this application, the term “or” is intended to mean an inclusive “or” rather than an exclusive “or”. That is, unless specified otherwise, or clear from context, “X employs A or B” is intended to mean any of the natural inclusive permutations. That is, if X employs A; X employs B; or X employs both A and B, then “X employs A or B” is satisfied under any of the foregoing instances. In addition, the articles “a” and “an” as used in this application and the appended claims may generally be construed to mean “one or more” unless specified otherwise or clear from context to be directed to a singular form.
• Also, although the disclosure has been shown and described with respect to one or more implementations, equivalent alterations and modifications will occur to others skilled in the art based upon a reading and understanding of this specification and the annexed drawings. The disclosure includes all such modifications and alterations and is limited only by the scope of the following claims. In particular regard to the various functions performed by the above described components (e.g., elements, resources, etc.), the terms used to describe such components are intended to correspond, unless otherwise indicated, to any component which performs the specified function of the described component (e.g., that is functionally equivalent), even though not structurally equivalent to the disclosed structure which performs the function in the herein illustrated example implementations of the disclosure. In addition, while a particular feature of the disclosure may have been disclosed with respect to only one of several implementations, such feature may be combined with one or more other features of the other implementations as may be desired and advantageous for any given or particular application. Furthermore, to the extent that the terms “includes”, “having”, “has”, “with”, or variants thereof are used in either the detailed description or the claims, such terms are intended to be inclusive in a manner similar to the term “comprising.”

Claims (20)

What is claimed is:

1. A method of configuring a server from a server set, the method comprising:

receiving a designation of the server for a data item of a data set, the designation causing the server to be designated as a master having permission to update the data item, wherein a second server from the server set has also been designated as a second master that has permission to update the data item;

receiving a request to update the data item of the data set; and

based on receiving the request to update the data item and based on the server being designated as a master:

updating the data set according to the request; and

propagating the update to the second server of the server set also designated as the second master.

2. The method ofclaim 1, wherein receiving the request to update the data item of the data set includes receiving a forwarded request from another server of the server set that originally received the request and forwarded the request based on the another server being designated as a non-master that does not have permission to update the data item, a designation of the another server including an identification of the server as one of a plurality of masters having permission to update the data item.

3. The method ofclaim 1, wherein the designation as a master further identifies a propagation subset of servers of the server set, and wherein the method further comprises propagating the update further comprises propagating the update specifically to the propagation subset of the server set.

4. The method ofclaim 1, wherein the designation of the server further comprises a designation of the server as a master of the data set based on a master condition being satisfied.

5. The method ofclaim 4, wherein the master condition comprises a master period within a time cycle, and wherein the designation of the server as a master occurs only within the master period of the time cycle.

6. The method ofclaim 1,

wherein the designation as a master is a designation as an auxiliary master,

wherein updating the data set according to the request and propagating the update to the second server of the server set also designated as the second master occurs when a load of the server designated as an auxiliary master exceeds a load threshold, and

wherein the method includes forwarding the request to the second server having also been designated as the second master when the load of the server designated as an auxiliary master does not exceed a load threshold.

7. The method ofclaim 1, further comprising:

detecting a failure of the server designated as the master; and

in response to detecting the failure of the first server, initiating a transition of the designation of the server as the master to a failover master of the data set.

8. The method ofclaim 1, wherein the designation as the master further identifies the server as a conflict resolution master of the data set, and wherein the method further comprises:

identifying a data version conflict involving at least two updates of the data set;

selecting, from a conflict resolution technique set, a conflict resolution technique that evaluates the at least two updates to identify a data version conflict resolution outcome;

invoking the conflict resolution technique set to generate the data version conflict resolution outcome; and

propagating the data version conflict resolution outcome to other masters of the data set.

9. A system, comprising:

at least one processor;

memory in electronic communication with the at least one processor; and

instructions stored in the memory, the instructions being executable by the at least one processor to:

receive a designation of a server of a server set for a data item of a data set, the designation causing the server to be designated as a master having permission to update the data item, wherein a second server from the server set has also been designated as a second master that has permission to update the data item;

receive a request to update the data item of the data set; and

based on receiving the request to update the data item and based on the server being designated as a master:

update the data set according to the request; and

propagate the update to the second server of the server set also designated as the second master.

10. The system ofclaim 9, wherein receiving the request to update the data item of the data set includes receiving a forwarded request from another server of the server set that originally received the request and forwarded the request based on the another server being designated as a non-master that does not have permission to update the data item, a designation of the another server including an identification of the server as one of a plurality of masters having permission to update the data item.

11. The system ofclaim 9, wherein the designation as a master further identifies a propagation subset of servers of the server set, and further comprising instructions being executable by the at least one processor to propagate the update further comprises propagating the update specifically to the propagation subset of the server set.

12. The system ofclaim 9, wherein the designation of the server further comprises a designation of the server as a master of the data set based on a master condition being satisfied.

13. The system ofclaim 12, wherein the master condition comprises a master period within a time cycle, and wherein the designation of the server as a master occurs only within the master period of the time cycle.

14. The system ofclaim 9,

wherein the designation as a master is a designation as an auxiliary master, and

wherein updating the data set according to the request and propagating the update to the second server of the server set also designated as the second master occurs when a load of the server designated as an auxiliary master exceeds a load threshold, and

further comprising instructions being executable by the at least one processor to forward the request to the second server having also been designated as the second master when the load of the server designated as an auxiliary master does not exceed a load threshold.

15. The system ofclaim 9, further comprising instructions being executable to:

detect a failure of the server designated as the master; and

in response to detecting the failure of the first server, initiate a transition of the designation of the server as the master to a failover master of the data set.

16. The system ofclaim 9, wherein the designation as the master further identifies the server as a conflict resolution master of the data set, and further comprising instructions being executable by the at least one processor to:

identify a data version conflict involving at least two updates of the data set;

select, from a conflict resolution technique set, a conflict resolution technique that evaluates the at least two updates to identify a data version conflict resolution outcome;

invoke the conflict resolution technique set to generate the data version conflict resolution outcome; and

propagate the data version conflict resolution outcome to other masters of the data set.

17. A non-transitory computer readable medium storing instructions thereon that, when executed by at least one processor, causes a computing device to:

receive a designation of a server of a server set for a data item of a data set, the designation causing the server to be designated as a master having permission to update the data item, wherein a second server from the server set has also been designated as a second master that has permission to update the data item;

receive a request to update the data item of the data set;

based on receiving the request to update the data item and based on the server being designated as a master:

update the data set according to the request; and

propagate the update to the second server of the server set also designated as the second master.

18. The non-transitory computer readable medium ofclaim 17, wherein receiving the request to update the data item of the data set includes receiving a forwarded request from another server of the server set that originally received the request and forwarded the request based on the another server being designated as a non-master that does not have permission to update the data item, a designation of the another server including an identification of the server as one of a plurality of masters having permission to update the data item.

19. The non-transitory computer readable medium ofclaim 17, wherein the designation of the server further comprises a designation of the server as a master of the data set based on a master condition being satisfied, wherein the master condition comprises a master period within a time cycle, and wherein the designation of the server as a master occurs only within the master period of the time cycle.

20. The non-transitory computer readable medium ofclaim 17,

wherein the designation as a master is a designation as an auxiliary master,

wherein updating the data set according to the request and propagating the update to the second server of the server set also designated as the second master occurs when a load of the server designated as an auxiliary master exceeds a load threshold, and

further comprising instructions that, when executed by the at least one processor, causes the computing device to forward the request to the second server having also been designated as the second master when the load of the server designated as an auxiliary master does not exceed a load threshold.

Images