Dynamic data partitioning for stateless request routing

Dynamic data partitioning for stateless request routing may be implemented. Respective partitions of data and corresponding mapping information may be maintained at partition hosts. A repartitioning event may be detected for the data to move a portion of data from a source partition host to a destination partition host. In response, the mapping information at the source partition host may be updated to indicate that the portion of data is located at the destination partition host for subsequent access requests received at the source partition host. The portion of the data may be copied from the source partition host to the destination partition host. Upon completion of the copy of the portion of the data, the mapping information at the destination partition host may be updated to indicate that the portion of the data is located at the destination partition host and is available for access.

BACKGROUND

Distributed systems have created great opportunities for implementing more efficient and available system architectures. Systems may no longer be limited by the capabilities of an individual computing system, but may instead share the workload for performing complex computing tasks, maintaining and storing data, or implementing various applications or services among multiple different computer systems. For example, in some distributed systems respective partitions or versions of data may be maintained among a collection of different systems in order to provide greater reliability and availability in the face of individual system failures.

The ability to leverage the capabilities of multiple different systems, however, can increase the complexity of ensuring that common data or other information maintained or shared among multiple systems is consistent. If, as in the previous example, different partitions of data are maintained in different locations, a change to the location of data from one partition to another may precipitate costly operations to make the various request routing systems that provide access to the partitions of the data aware of the change in location. As the need to automatically or dynamically partition data grows, consistency schemes to account for these failure scenarios when making changes to common data or other information maintained or shared may prove challenging to design or implement.

While embodiments are described herein by way of example for several embodiments and illustrative drawings, those skilled in the art will recognize that the embodiments are not limited to the embodiments or drawings described. It should be understood, that the drawings and detailed description thereto are not intended to limit embodiments to the particular form disclosed, but on the contrary, the intention is to cover all modifications, equivalents and alternatives falling within the spirit and scope as defined by the appended claims. The headings used herein are for organizational purposes only and are not meant to be used to limit the scope of the description or the claims. As used throughout this application, the word “may” is used in a permissive sense (i.e., meaning having the potential to), rather than the mandatory sense (i.e., meaning must). The words “include,” “including,” and “includes” indicate open-ended relationships and therefore mean including, but not limited to. Similarly, the words “have,” “having,” and “has” also indicate open-ended relationships, and thus mean having, but not limited to. The terms “first,” “second,” “third,” and so forth as used herein are used as labels for nouns that they precede, and do not imply any type of ordering (e.g., spatial, temporal, logical, etc.) unless such an ordering is otherwise explicitly indicated.

Various components may be described as “configured to” perform a task or tasks. In such contexts, “configured to” is a broad recitation generally meaning “having structure that” performs the task or tasks during operation. As such, the component can be configured to perform the task even when the component is not currently performing that task (e.g., a computer system may be configured to perform operations even when the operations are not currently being performed). In some contexts, “configured to” may be a broad recitation of structure generally meaning “having circuitry that” performs the task or tasks during operation. As such, the component can be configured to perform the task even when the component is not currently on. The circuitry that forms the structure corresponding to “configured to” may include hardware circuits. In some contexts, the structure may be implemented as part of a general purpose computing device that is programmed to perform the task or tasks according to programming instructions.

DETAILED DESCRIPTION

Various embodiments of dynamic data partitioning for stateless request routing are described herein. Access to partitioned data across multiple partition hosts that maintain data partitions may be implemented via one or more request routers. In order to direct access requests to the appropriate partition host for an access request, a request router may need to understand the locations of different data partitions (as well as rules that govern mapping of each request to a specific partition).

Typically, such mapping is accomplished by examining a well-defined property of each request (usually referred to as partition or sharding key), and applying a deterministic transformation to it to arrive at the appropriate data partition. For instance, a partition key may be hashed, and then modded into one of the available data partitions. Such an approach may be stateless, as no mapping information may need to be maintained. However, distributed systems commonly rearrange or redistribute data amongst partition hosts (e.g., to alleviate performance stress or other optimizations). As data is located deterministically, a single change or movement of data may result in the movement of several portions of data to fit a new deterministic model that accommodates the original data move. Alternatively, global persistent mapping information may be maintained for request routers, that maps individual partition keys (or ranges of keys) with specific partitions. Yet, this global persistent mapping information (i.e., state-based routing) may need to be consistently maintained (as a result of changes to the location of data among partition hosts) so that multiple request routers may consistently direct requests to the same locations.

Dynamic data partitioning for stateless request routing may be implemented to provide low cost repartitioning (e.g., movement of data across partitions) and avoid the need to maintain a globally consistent shared state for request routers. Each data partition may also maintain mapping information to indicate the corresponding data maintained as part of the data partition. Initial partitioning assignments of data to partition hosts may be done manually by an operator, when a new partition comes online, or may be automated according to various tools or schemes to distribute data equally (e.g., a hashing scheme). Request routers may have access to a bootstrap list of all available partitions maintaining data. Request routers may then obtain mapping information from partition hosts as needed in order to direct access requests to data partitions. The mapping information of a request router need not be consistent with current locations of data among partition hosts as request routers may discover changes to mapping information as needed.

FIGS. 1A-1Hare a series of block diagrams illustrating dynamic data partitioning for stateless request routing, according to some embodiments. As illustrated inFIG. 1A, request router100may be stateless, with no persistently maintained mapping information102(e.g., upon startup). Request routers may obtain mapping information104from partition hosts120,130, and140, each of which maintain respective mapping information124,124, and144describing the data in the data partitions122,132, and142. For example, partition key values may be described, such as key ranges 0-33, 34-66, and 67-99. As illustrated inFIG. 1B, request router now has mapping information102obtained from the partition hosts120,130, and140, which describe partition keys corresponding to the respective data partitions122,132, and142. Although not illustrated, in at least some embodiments, some partition keys and corresponding data may be maintained at multiple partition hosts.

A repartitioning event may be an event that triggers or causes the movement of data from one partition to another. Repartitioning events may be automatically/dynamically determined, or detected as the result of a manual request to move data. The repartitioning event may trigger the movement of a portion of data from one data partition to another. For example, as illustrated inFIG. 1B, the mapping information may be updated152to move a portion of data by data manager150. Data manager150may, in various embodiments, perform the techniques described below with regard toFIGS. 3-5to perform dynamic data partitioning for stateless request routing. InFIG. 1B, the updated mapping information124identifies that data partition host120now processes access requests for data corresponding to keys1-27, and also maintains a redirect instruction to redirect access requests for keys28-33to partition host130maintaining data partition132. Data manager150may direct the copy of the portion of data154to data partition host132from source partition host120to destination partition host130. InFIG. 1D, data manager150updates mapping information156at partition host130to indicate that the portion of data is now located at partition host130, upon completion of the copy operation154.

As ofFIG. 1E, request router100is unaware of the changes to the location of data corresponding to keys28-33. Mapping information102is not consistent with mapping information among the partition hosts120,130and140. However, request router100may discover and update changes to mapping information as needed. Even though request routers maintain the mapping information, mapping information inconsistencies, errors, or even total mapping information data loss may be corrected. Thus, request routers may perform stateless request routing without having to maintain state consistently, effectively performing stateless request routing, in various embodiments. For example, if access request160is received at request router100for key29, request router100may determine that key29data is located at partition host120which maintains partition122according to mapping information102. Thus, request router100may send access request162to partition host120for key29data. As illustrated inFIG. 1F, partition host may follow or perform a redirect instruction for keys28-32, and respond164to the request indicating a new location for key29, at data partition132, along with new location information for the other keys28-32that have moved. As illustrated inFIG. 1G, request router100may update mapping information102to indicate that partition132maintains the portion of data corresponding to keys28-33. Based on this information, request router100may send the access request166for key29to partition host130. As partition host130maintains in mapping information n134an indication that key29is within the range of maintained keys, then as illustrated inFIG. 1Hpartition host130may provide access168in response to the access request166.

Please note that the previous example provides a logical illustration of dynamically data partitioning for stateless routing and is not intended to be limiting as to the number of partition hosts, requests, routers, data layout, and/or mapping information maintained.

The specification first describes an example of a distributed system, such as a distributed storage system that stores data for different storage clients. The distributed system may store data/maintain state for many different types of clients, in various embodiments. For example, one such client may be a database, or other application, system or service which partitions data amongst different partition hosts which may access the data partitions through one or more request routers. Included in the description of the example distributed system are various examples of distributed system systems or devices which may implement dynamic data partitioning for stateless request routing. The specification then describes a flowchart of various embodiments of methods for implementing dynamic data partitioning for stateless request routing. Next, the specification describes an example system that may implement the disclosed techniques. Various examples are provided throughout the specification.

FIG. 2is a block diagram illustrating a distributed system that implements dynamic data partitioning for stateless request routing to data maintained in the distributed system, according to some embodiments. Distributed system200may provide storage for data for a plurality of clients250in data tier220distributed across partition hosts222a,222b,222c, and so on that may make up different groups of partition hosts storing different data for clients250. For example data maintained in a partition group may be network address allocation information for a provider network service that includes distributed system200, in some embodiments. Clients250may interact with distributed system200via a network260. Clients250may be internal to distributed system200(e.g., as part of a provider network that includes distributed system200or other larger distributed system) or external to distributed system200(e.g., external to a provider network that includes distributed system200). Access requests may be directed to request routing tier210, which may include request routers212a,212b,212cand so on, which may perform request routing to partition data without relying upon strongly consistent mapping information maintained in the request routing tier210, effectively providing stateless request routing. Instead, request routers212may discover the location of requested data based on mapping information maintained at and obtained from partition hosts222in order to direct access requests from client250received via network260to the appropriate partition host. Management tier230may include partitioning manager232and partition host membership234to facilitate partitioning and repartitioning of data (e.g., moving data) among partition hosts222. It is noted that where one or more instances of a given component may exist, reference to that component herein may be made in either the singular or the plural. However, usage of either form is not intended to preclude the other.

In various embodiments, the components illustrated inFIG. 2may be implemented directly within computer hardware, as instructions directly or indirectly executable by computer hardware (e.g., a microprocessor or computer system), or using a combination of these techniques. For example, the components ofFIG. 2may be implemented by a system that includes a number of computing nodes (or simply, nodes), each of which may be similar to the computer system embodiment illustrated inFIG. 7and described below. In various embodiments, the functionality of a given system component (e.g., a component of the distributed system) may be implemented by a particular node or may be distributed across several nodes. In some embodiments, a given node may implement the functionality of more than one system component (e.g., more than one storage system component).

In at least some embodiments, distributed system200may implement a distributed system control plane management tier230including partitioning manager232and partition host membership234. Partitioning manager232may perform the various techniques described below with regard toFIGS. 3-6to provide dynamic data partitioning of data for stateless request routing via request routing tier210. For instance, in various embodiments, partition manager232may detect repartitioning events for data, select portions of data to move, select source and/or destination partition hosts222, direct the updating of mapping information at partition hosts222, direct the transfer or copying of data from partition host to partition host, and/or perform any other action to move portions of data among partition hosts222while maintaining mapping information in data tier220which may be used by request routing tier210to discover the location of particular portions of data. Partition host membership234may act as an authoritative source for partition hosts belong to a particular group of partition hosts that maintain data for a particular client. In some embodiments, partition host membership234may provision additional partition hosts to add to a group or remove partition hosts from a group. Request routers212may access or obtain partition host group membership from partition host membership234in various embodiments.

Distributed system200may, in various embodiments, implement data tier220, including multiple partition hosts, such as partition hosts222a,222b,222c, and so on, to provide distributed storage for storing data for clients250. Different groups of partition hosts222may make up a set storage nodes that provide a distributed system for a particular client250. In at least some embodiments, partition hosts222may store data for different clients as part of a multi-tenant storage service. Each partition host222may be configured to perform various operations to process access requests from clients250according to respective mapping information maintained at the partition host for the data, such as performing various reads, writes, gets, puts, and/or other modifications to data. For instance, a partition host222may only allow access (e.g., read or write access) to portions of the data that are indicated as maintained at the partition host222in the mapping information. Even if the requested data is physically located at the partition host222, partition host222may deny the access request if the mapping information does not indicate that the data is residing at the partition host222. Partition hosts222may have attached storage devices for persistent storage, such as hard disk drives, solid state drives, or various storage devices to store data partitions and mapping information. In some embodiments, partition hosts may provide volatile storage for caching or temporary storage for updates to a portion of data, such as log or history of changes to the portion of data for synchronization with a copy of the portion of the data at another partition host.

Distributed system200may implement request routing tier210which may implement multiple different request routers, such as request routers212a,212b,212c, and so on, so that requests for data partition among partition hosts222may be routed to the appropriate partition host222. Request routers may be implemented by one or more computing devices or servers, such as computing system1000described below with regard toFIG. 7. Request routers212may implement the various techniques described below with regard toFIG. 6to direct requests to partition hosts and update mapping information maintained at request routers212(e.g., in system memory). Request routers212amay be stateless, performing request routing without persistently maintaining any mapping information or other information to direct access requests, in some embodiments.

Clients250may encompass any type of client configurable to access data maintained for the client in distributed system200. Clients250may be individual components, applications, or devices, or alternatively may be other distributed systems, such as a distributed database system that utilizes distributed system200to store data for databases managed at the distributed database system. Clients250may submit access requests to request routers212for access to data in data tier220according to an interface for distributed system200, such as an application programming interface (API). For example, a given client250may format update requests to write data to particular portions of data according to a command line interface utilizing the API. Similarly, read requests may also be formatted according to the API. Responses and acknowledgments from the request routers212and partition hosts222may also be formatted according to the API. Clients250may encompass an application such as a database application (or user interface thereof), a media application, an office application or any other application that may make use of storage resources to store and/or access one or more stored data in distributed system200. In some embodiments, such an application may include sufficient protocol support for generating and processing requests to the data according to the API.

Clients250may convey access requests to and receive responses/acknowledgments from request routers212via network260. In various embodiments, network260may encompass any suitable combination of networking hardware and protocols necessary to establish network-based-based communications between clients250and distributed system200. For example, network260may generally encompass the various telecommunications networks and service providers that collectively implement the Internet. Network260may also include private networks such as local area networks (LANs) or wide area networks (WANs) as well as public or private wireless networks. For example, both a given client250and distributed system200may be respectively provisioned within enterprises having their own internal networks. In such an embodiment, network260may include the hardware (e.g., modems, routers, switches, load balancers, proxy servers, etc.) and software (e.g., protocol stacks, accounting software, firewall/security software, etc.) necessary to establish a networking link between given client250and the Internet as well as between the Internet and distributed system200. It is noted that in some embodiments, clients250may communicate with distributed system200using a private network rather than the public Internet. For example, clients250may be provisioned within the same enterprise as a distributed system (e.g., a system that implements both clients250and distributed system200). In such a case, clients250may communicate with distributed system200entirely through a private network260(e.g., a LAN or WAN that may use Internet-based communication protocols but which is not publicly accessible).

FIG. 3is a sequence diagram illustrating the interactions among a partitioning manager, a source partition host, and a destination partition host, according to some embodiments. A repartitioning event may be detected to move a portion of data from source partition host310to destination partition host320. Partitioning manager232may communicate with source partition host310and/or destination partition host320according to one or more networking protocols (e.g., Hypertext Transfer Protocol (HTTP)), interfaces (e.g., programmatic (Application Programming Interface (API) or command line interface), or other communication techniques. Partitioning manger232may update (or direct the update) of mapping information330to indicate destination partition host320as the location of the portion of the data to be moved (e.g., including a redirect instruction to the destination partition host320). Partitioning manager232may direct the copy of the portion of the data332to the destination partition host320, in various embodiments. For example, the partitioning manager may issue an API command to source partition host310that begins a copy operation334from source partition host of the portion of the data to destination partition host320. In some embodiments, partitioning manager232may obtain the portion of the data from source partition host310and directly transfer the data from partition manager232to destination partition host320(not illustrated). As illustrated inFIG. 3, an acknowledgement336of the completion of the copy may be received, in some embodiments. In response to the completion of the copy, partitioning manager232may update the mapping information338at destination partition host320to indicate that the portion of the data is located at the destination partition host320. At some time after the update to the mapping information at destination partition host320, partition manager232may remove the redirect instruction340from partitioning manager232. Please note that the above diagram is provided as an example of dynamic data partitioning, and thus other orderings, such as the techniques discussed below with regard toFIG. 5may be performed by partitioning manager as well.

The techniques described above with regard toFIGS. 1A-3may be implemented for many diverse distributed systems which partition data among partition hosts. For example, a single copy of the data may be maintained at different partitions of the data at different partition hosts. While in other examples, multiple copies of data may be maintained at different partition hosts so that more than one partition host may provide access to portions of the data (e.g., in read-only systems without concurrency concerns). Therefore, the possibilities of dynamic data partitioning for stateless request routing are not limited to the examples given above. Moreover, although these examples are given with regard to a distributed system (e.g., distributed system200inFIG. 2), the previously described techniques are not limited to such systems.FIG. 4is a high-level flowchart illustrating methods and techniques to implement dynamic data partitioning for stateless request routing, according to some embodiments.

As indicated at410, data respectively partitioned across different partition hosts may be maintained. The data may be any size or type of data set which may be divided for partitioned access. Multiple copies of the same portion of data may be maintained at different partition hosts, providing redundant storage for the data. In at least some embodiments, the partition hosts maintaining a respective partition of the data may process access requests to the respective partition. Access requests may be any request to read, write, modify, get, put, obtain, or otherwise access a portion of the data. Partition hosts may also maintain mapping information which indicates the portions of data in a partition at a partition host. For example, in some embodiments, partition key ranges or other identifiers may be maintained as part of mapping information to identify the portions of data corresponding to the keys or identifiers maintained or stored at the partition host. In at least some embodiments, the same partition key may be maintained at multiple partition hosts (and thus the data corresponding to the partition key may be maintained the multiple partition hosts). If the mapping information does not indicate that the portion of data is located at the partition host, then the partition host may, in some embodiments, deny the access request.

As indicated at420, a repartitioning event may be detected, in various embodiments, to move a portion of the data from the respective partition of a source partition host to a data partition host. For example, a repartitioning event may be triggered by an automated or dynamic partitioning mechanism that monitors various utilization and performance metrics of partition hosts. In one instance, the processing utilization or throughput utilization (e.g., Input/Output Operations per Second (IOPS)) of a partition host may be measured. If the measured utilization exceeds a utilization capacity or threshold, then a repartitioning event may be triggered to move a portion of data from the resource host that triggered the repartitioning event. In some embodiments, the repartitioning even may be triggered by current data storage utilization exceeding a storage capacity threshold. A request to repartition or move a certain portion of data or identify a certain partition host may be received, in some embodiments. For example, a change to the software and/or hardware underlying a partition host may be made, and requests to repartition or move data to the new partition host may be made in order to test the functionality of the new partition host. Various other reasons for requests to repartition may exist, whether automatically determined by another system, service, or device, or via manual input according to a user interface (e.g., command line or graphical user interface). Once the repartitioning event is detected, the portion of data to be moved may be determined, in some embodiments. For example, a portion of data that is causing a partition to exceed a utilization or capacity threshold may be identified for movement.

In response to detecting the repartitioning event, the respective mapping information maintained at the source partition host may be updated to return the location of the portion of the data at the destination partition host in response to access requests received for the portion of the data at the source partition host, as indicated at430, in various embodiments. For example, a redirect instruction or other record may be recorded or stored at the source partition host, which may direct the host to return access requests for the portion of the data to a requestor (e.g., a request router such as discussed below with regard toFIG. 6) indicating the new location of the portion of the data. For example, an HTTP 302 Found response, or other redirection response, may be sent from the source partition host to requests received at the source partition host for the portion of the data. In at least some embodiments, the partition keys or other mapping information identifying the portion of the data may be removed from the source partition host.

As indicated at440, the portion of the data may be copied from the source partition host to the destination partition host, in various embodiments. For example, various File Transfer Protocols (FTPs), data transfer protocols, encryption, compression, or any other transmission techniques may be implemented to copy the portion of the data from the source partition host to the destination partition host. Upon completion of the copy of the portion of the data, the respective mapping information at the destination partition host may be updated to indicate that the partition of the data is located at the destination partition host and is available for processing access requests. For instance, the partition keys or identifiers of the portion of the data may be added to the mapping information.

The techniques described above with regard toFIG. 4may be repeatedly performed to dynamically repartition data across partitioning hosts, for various reasons, as frequently as desired. As the mapping information is maintained at the different partition hosts, any request routers or other systems, components, or devices attempting access data may discover the changes in data location as needed. For example, the same portion of data could move multiple times, and a request router following the new location responses would eventually discover a current location for the portion of the data. In at least some embodiments, a redirect instruction may be removed or reclaimed from a source partition host subsequent to the update of mapping information at the destination partition host. For example, the redirect may be retained until a refresh window for mapping information of request routers has passed (which provides a period of time during which each request router may ask for an update of mapping information from the partition hosts) so that every request router can discover the change in data location. In addition to repartitioning data amongst current partition hosts, the previous techniques may be performed to move data to a new partition host added to the group of partition hosts maintaining data, or conversely to remove data from a partition host that is to be removed from a the group of partition hosts maintaining the data. Partition host group changes, as discussed above with regard toFIG. 2, may be recorded in an authoritative data store, which may be consistently maintained. This authoritative data store may be access by request routers occasionally to learn, confirm, or otherwise discover active partition hosts in a group of partition hosts.

Dynamic data partitioning allows for various implementations of updating mapping information and moving data amongst partition hosts. In some embodiments, such as the example discussed above with regard toFIGS. 1A-1H and 4, requests for portions of data may be directed to a destination partition host before a partition host has completely received the portion of the data from the source partition host. In such a scenario, the access requests sent to the destination partition host may fail or timeout until copying is complete. Thus, alternative orderings or techniques may be implemented to minimize client access impact to data that is being moved.FIG. 5is a high-level flowchart illustrating methods and techniques to implement updating mapping information and copying data between source partition hosts and destination partition hosts, according to some embodiments.

As indicated at510, a repartitioning event may be detected to move a portion of data from a source partition host to a destination partition host, in some embodiments. In response to detecting the repartitioning event, the portion of the data to be moved may begin copying or transferring from the source partition host to the destination partition host, as indicated at520(according to one of the various techniques described above with regard toFIG. 4). During the copying of the portion of the data, the source partition host may continue to process access requests to the portion of data. In some embodiments, the source partition host may lock the portion of the data as read-only, while in other embodiments, changes to the portion of the data may continue to be applied. Upon completion of the copy, a redirect instruction may be recorded as part of the mapping information at the source partition host in order to identify the location of the portion of the data at the destination partition host, as indicated at530, in some embodiments. For example, a number or range of keys or identifiers of data may be indicated as redirected to the destination partition host. In this way, the source partition host may no longer process access requests to the portion of the data. As indicated at540, partition key(s) corresponding to the portion of the data may be removed from the mapping information at the source partition host, in at least some embodiments.

During the time between the completion of the copy, element520, and the recordation of the redirect instruction, element530, one or more changes to the portion of the data may be received as access requests at the source partition host and applied to the portion of the data, in some embodiments. For example, a particular data value may be overwritten or incremented. The portion of the data as it exists in the destination partition host does not reflect these changes. Thus, if changes to the portion of the data between copying the data and recording the redirect exist, as indicated by the positive exit from550, then the changes may be applied to the portion of the data the destination partition, as indicated at560, in some embodiments. For example, a change log or other history of changes to the portion of data may be maintained for the interval between completion of the copy operation and the recording of the redirect instruction. The change log or history may be replayed to update the portion of the data that is maintained in the destination partition host, in some embodiments. Various other synchronization techniques may be used to apply the changes to the portion of the data at the destination partition host, and thus the previous example is not intended to be limiting. Once the changes are applied (or as indicated by the negative exit from element550no changes are applied), the partition key(s) corresponding to the portion of the data may be added to the mapping information maintained at the destination partition host, as indicated at570, in some embodiments. In this way, a synchronized version of the portion of the data may be made available when the partition keys of the mapping information indicate that the destination partition node now process access requests to the portion of the data.

As noted above, request routers may direct access requests to partition hosts based on mapping information obtained from the partition hosts. In this way, the request routers can direct access requests without a requirement that the request router maintain a current or consistent view of the locations of data among the partition hosts. For example, in a scenario where multiple routers are directing requests to partitions of data among different partition hosts, some request routers may have a different view or understanding of the location of data (as the request router may have discovered repartitioning of data before other request routers). In this way, request routers may discover repartitioning of data without relying upon access to a centralized repository of mapping information, but may incrementally update the mapping information used at a particular request router as needed.FIG. 6is a high-level flowchart illustrating methods and techniques for processing access requests at stateless request routers, according to some embodiments.

As indicated at610, a request to access a portion of data partitioned across different partition hosts may be received at a request router. For example, a read or write request may be received to obtain or modify a portion of the data. The access request may, in various embodiments, indicate the particular portion of data to be accessed based on a partition key or other identifier which may be used to indicate the desired portion of data.

In response to receiving the access request, a partition host to send the access request may be identified according to mapping information obtained from the different partition hosts, as indicated at620, in some embodiments. For example, in at least some embodiments, a request router may periodically (or aperiodically) query the partition hosts identified as maintaining the data for updated mapping information. Mapping information may also be updated according to previously received new location responses, as discussed below. The mapping information may, for instance, map partition keys to one or multiple partition hosts which maintain a partition of the data that includes the portion of the data corresponding to the included partition key or identifier of the access request. In various embodiments, mapping information may not be persistently be maintained, but instead may be maintained in volatile and/or transitory memory (e.g., system memory). If a request router fails or restarts, the request router may obtain the list of partition hosts and request mapping information from the partition hosts. Once identified, the access request may be sent to the identified partition host, as indicated at630. For example, the particular write, read, get, put, or other type of request may be sent to the particular partition host. The access request may, in some embodiments, be translated or transformed from one type of request to another (e.g., converting a request from one API format to another API format or protocol). In at least some embodiments, the access request may be sent to an identified partition host according to Hypertext Transfer Protocol (HTTP).

A response may not be received, and the request retried according to some timeout window or threshold. In various embodiments, a response to the access request may be received from the identified partition host. If the response indicates that the access request was successful (e.g., returning the appropriate data or acknowledgment), then as indicated by the negative exit from640, the request router may acknowledge the request to a client as complete, as indicated at670. For example, the request router may re-translate or re-transform the acknowledgement according to a same protocol, format, or API in which the original request was received. If, however, as indicated by the positive exit from640, a response is received at the request router indicating a new location for the portion of the data, then the mapping information at the request router may be updated to indicate the new location, as indicated at650. For example, an HTTP 302 FOUND response may be returned indicating the partition host that currently stores the requested portion of data. In some embodiments, the new location may include a range of partition keys, or other identifiers of mapping information which may be used to update the mapping information at the request router (as discussed above with regard toFIGS. 1F and 1G). The access request may then be resent to the partition host identified as the new location of the portion of the data, as indicated at660, in various embodiments. Similar to the discussion above, the request may timeout or receive no answer, and the access request may be resent. For instance, as discussed above with regard toFIGS. 4 and 5, in some embodiments, the copying of the portion of the data to the destination partition host may not yet be complete, and therefore the identified partition host may be unable process the access request. However, as indicated by the return arrow to element640if a response that is not a new location response is received then the request may be acknowledged as complete. Please note, that in some embodiments a complete response does not indicate that the access request was successful as partition hosts may implement various concurrency schemes, such as locking mechanisms, in scenarios where multiple readers and/or writers may access the portion of data. Therefore, the previous example is not intended to be limiting as to the type of successful response to an access request.

FIG. 7is a block diagram illustrating a computer system configured to implement at least a portion of the various nodes, systems, or components of the distributed systems, such as the example distributed system described herein, according to various embodiments. For example, computer system1000may be configured to implement various storage nodes of a distributed storage system that stores data on behalf of clients, in different embodiments, or more generally implement any of the various types of nodes or components that may be implemented as part of a distributed system. Computer system1000may be any of various types of devices, including, but not limited to, a personal computer system, desktop computer, laptop or notebook computer, mainframe computer system, handheld computer, workstation, network computer, a consumer device, application server, storage device, telephone, mobile telephone, or in general any type of computing device.

Computer system1000includes one or more processors1010(any of which may include multiple cores, which may be single or multi-threaded) coupled to a system memory1020via an input/output (I/O) interface1030. Computer system1000further includes a network interface1040coupled to I/O interface1030. In various embodiments, computer system1000may be a uniprocessor system including one processor1010, or a multiprocessor system including several processors1010(e.g., two, four, eight, or another suitable number). Processors1010may be any suitable processors capable of executing instructions. For example, in various embodiments, processors1010may be general-purpose or embedded processors implementing any of a variety of instruction set architectures (ISAs), such as the x86, PowerPC, SPARC, or MIPS ISAs, or any other suitable ISA. In multiprocessor systems, each of processors1010may commonly, but not necessarily, implement the same ISA. The computer system1000also includes one or more network communication devices (e.g., network interface1040) for communicating with other systems and/or components over a communications network (e.g. Internet, LAN, etc.). For example, a client application executing on system1000may use network interface1040to communicate with a server application executing on a single server or on a cluster of servers that implement one or more of the components of the database systems described herein. In another example, an instance of a server application executing on computer system1000may use network interface1040to communicate with other instances of the server application (or another server application) that may be implemented on other computer systems (e.g., computer systems1090).

In the illustrated embodiment, computer system1000also includes one or more persistent storage devices1060and/or one or more I/O devices1080. In various embodiments, persistent storage devices1060may correspond to disk drives, tape drives, solid state memory, other mass storage devices, or any other persistent storage device. Computer system1000(or a distributed application or operating system operating thereon) may store instructions and/or data in persistent storage devices1060, as desired, and may retrieve the stored instruction and/or data as needed. For example, in some embodiments, computer system1000may host a storage system server node, and persistent storage1060may include the SSDs attached to that server node.

Computer system1000includes one or more system memories1020that are configured to store instructions and data accessible by processor(s)1010. In various embodiments, system memories1020may be implemented using any suitable memory technology, (e.g., one or more of cache, static random access memory (SRAM), DRAM, RDRAM, EDO RAM, DDR 10 RAM, synchronous dynamic RAM (SDRAM), Rambus RAM, EEPROM, non-volatile/Flash-type memory, or any other type of memory). System memory1020may contain program instructions1025that are executable by processor(s)1010to implement the methods and techniques described herein. In various embodiments, program instructions1025may be encoded in platform native binary, any interpreted language such as Java™ byte-code, or in any other language such as C/C++, Java™, etc., or in any combination thereof. For example, in the illustrated embodiment, program instructions1025include program instructions executable to implement the functionality of a distributed system node or client of a distributed system. In some embodiments, program instructions1025may implement multiple separate clients, nodes, and/or other components.

In some embodiments, system memory1020may include data store1045, which may be configured as described herein. For example, the information described herein as being stored by the storage system described herein may be stored in data store1045or in another portion of system memory1020on one or more nodes, in persistent storage1060, and/or on one or more remote storage devices1070, at different times and in various embodiments. Similarly, the information described herein as being stored by the storage system may be stored in another portion of system memory1020on one or more nodes, in persistent storage1060, and/or on one or more remote storage devices1070, at different times and in various embodiments. In general, system memory1020(e.g., data store1045within system memory1020), persistent storage1060, and/or remote storage1070may store data blocks, replicas of data blocks, metadata associated with data blocks and/or their state, database configuration information, and/or any other information usable in implementing the methods and techniques described herein.

Network interface1040may be configured to allow data to be exchanged between computer system1000and other devices attached to a network, such as other computer systems1090(which may implement one or more storage system server nodes, database engine head nodes, and/or clients of the database systems described herein), for example. In addition, network interface1040may be configured to allow communication between computer system1000and various I/O devices1050and/or remote storage1070. Input/output devices1050may, in some embodiments, include one or more display terminals, keyboards, keypads, touchpads, scanning devices, voice or optical recognition devices, or any other devices suitable for entering or retrieving data by one or more computer systems1000. Multiple input/output devices1050may be present in computer system1000or may be distributed on various nodes of a distributed system that includes computer system1000. In some embodiments, similar input/output devices may be separate from computer system1000and may interact with one or more nodes of a distributed system that includes computer system1000through a wired or wireless connection, such as over network interface1040. Network interface1040may commonly support one or more wireless networking protocols (e.g., Wi-Fi/IEEE 802.11, or another wireless networking standard). However, in various embodiments, network interface1040may support communication via any suitable wired or wireless general data networks, such as other types of Ethernet networks, for example. Additionally, network interface1040may support communication via telecommunications/telephony networks such as analog voice networks or digital fiber communications networks, via storage area networks such as Fibre Channel SANs, or via any other suitable type of network and/or protocol. In various embodiments, computer system1000may include more, fewer, or different components than those illustrated inFIG. 7(e.g., displays, video cards, audio cards, peripheral devices, other network interfaces such as an ATM interface, an Ethernet interface, a Frame Relay interface, etc.)