Distributed-state-information-based distributed computing systems and methods and protocols for managing distributed state information
View Patent ↗Various embodiments of the present invention are directed to distributed data-storage systems that provide non-distributed-data-storage-device-like interfaces to host computers that access the distributed data-storage systems. Distributed data-storage systems generally rely on state information used for execution of commands, received from host computers, by component data-storage systems. Command-executing component data-storage systems may access and modify state information shared among many or all of the component data-storage systems. Embodiment methods of the present invention provide methods for partitioning state information within a distributed data-storage system as well as communications protocols and methods for managing shared state information among the component data-storage systems within a distributed data-storage system. In certain embodiments of the present invention, state information is partitioned into one or more of: (1) local state information that is managed, accessed, and modified separately by each component data storage system; (2) shared state information that is locally cached on component data storage systems for immediate read access, that is periodically refreshed, but that is kept globally consistent among component data storage systems by distributing state-modifying operations; and (3) continuously consistent, shared state information.
1. A method for managing state information in a distributed computing system composed of component computing systems, the method comprising:
for each component computing system,
assigning each unit of state information to one of three partitions including
a local state information partition,
a distributed, shared, locally cached, but globally consistent state information partition, and
a distributed, shared state information partition; and
during operation of the distributed computing system,
when units of state information are assigned to the local state information partition, independently managing, on each component computing system, local state information,
when units of state information are assigned to the distributed, shared, locally cached, but globally consistent state information partition, managing each unit of distributed, shared, locally cached, but globally consistent state information among two or more component computing systems using a distributed-but-locally-cached-storage-register protocol, and
when units of state information are assigned to the distributed, shared, state information partition, managing each unit of distributed, shared state information using a distributed-storage-register protocol, wherein the distributed-storage-register protocol provides quorum-based READ and WRITE operations directed to a distributed storage register comprising distributed-storage-register values locally stored on each component computing system, and wherein the distributed-but-locally-cached-storage-register protocol provides operations directed to a distributed, but locally cached, storage register including, in addition to the operations provided by the distributed-storage-register protocol, a local READ operation and a STATE WRITE operation.
2. The method of claim 1 wherein the local READ operation returns a locally stored value for the distributed, but locally cached, storage register, rather than a quorum-based value, provided that a local lease on the distributed, but locally cached, storage register is valid and processing is not delayed.
3. The method of claim 1 wherein the STATE WRITE operation succeeds when all component computing systems update their locally stored values for the distributed, but locally cached, storage register, but when one or a minority of the component computing systems fail to update their locally stored values for the distributed, but locally cached, storage register, the remaining component computing systems delay using their updated, locally stored values for the distributed, but locally cached, storage register until the leases of the one or a minority of the component computing system for the distributed, but locally cached, storage register can be expected to have expired.
4. The method of claim 1 wherein a locally stored value for the distributed, but locally cached, storage register on each component computing system is periodically refreshed by a quorum-based READ operation.
5. The method of claim 1 wherein the distributed-but-locally-cached-storage-register protocol provides an additional ATOMIC STATE UPDATE operation that allows a distributed, but locally cached, storage register to be read and then modified by a component computing system without intervening access by any other component computing system.
6. The method of claim 1 wherein a unit of distributed, shared, locally cached, but globally consistent state information or distributed, shared state information may comprise one of:
a byte;
a computer word;
a field comprising a number of computer words;
a record comprising a number of computer words;
a data structure comprising a number of computer words; and
an access control comprising one or more bytes that controls access to additional state information.
7. The method of claim 1 wherein the distributed computing system is a distributed data storage system comprising a number of component data-storage systems that together provide a consistent data-storage interface to one or more host computer systems.
8. Computer instructions encoded in a computer-readable medium, for, according to the method of claim 1 :
independently managing, on each component computing system, local state information;
managing each unit of distributed, shared, locally cached, but globally consistent state information among two or more component computing systems using a distributed-but-locally-cached-storage-register protocol; and
managing each unit of distributed, shared state information using a distributed-storage-register protocol.
9. A distributed data-storage system comprising:
one or more communications media;
a number of data-storage systems interconnected by the one or more communications media;
a consistent, data-storage interface provided by the number of data-storage systems using distributed, shared, locally cached, but globally consistent state information and distributed, shared state information;
a distributed-but-locally-cached-storage-register protocol for managing distributed, shared, locally cached, but globally consistent state information; and
a distributed-storage-register protocol for managing distributed, shared state information, wherein each unit of distributed, shared, locally cached, but globally consistent state information is stored in a distributed, but locally cached, storage register and each unit of distributed, shared state information is stored in a distributed storage register, wherein the distributed-storage-register protocol provides quorum-based READ and WRITE operations directed to a distributed storage register comprising distributed-storage-register values locally stored on each component computing system, and wherein the distributed-but-locally-cached-storage-register protocol provides operations directed to a distributed, but locally cached, storage register including, in addition to the operations provided by the distributed-storage-register protocol, a local READ operation and a STATE WRITE operation.
10. The distributed data-storage system of claim 9 wherein the local READ operation returns a locally stored value for the distributed, but locally cached, storage register, rather than a quorum-based value, provided that a local lease on the distributed, but locally cached, storage register is valid and processing is not delayed.
11. The distributed data-storage system of claim 9 wherein the STATE WRITE operation succeeds when all component computing systems update their locally stored values for the distributed, but locally cached, storage register, but when one or a minority of the component computing systems fail to update their locally stored values for the distributed, but locally cached, storage register, the remaining component computing systems delay using their updated, locally stored values for the distributed, but locally cached, storage register until the leases of the one or a minority of the component computing system for the distributed, but locally cached, storage register can be expected to have expired.
12. The distributed data-storage system of claim 9 wherein a locally stored value for the distributed, but locally cached, storage register on each component computing system is periodically refreshed by a quorum-based READ operation.
13. The distributed data-storage system of claim 9 wherein the distributed-but-locally-cached-storage-register protocol provides an additional ATOMIC STATE UPDATE operation that allows a distributed, but locally cached, storage register to be read and then modified by a component computing system without intervening access by any other component computing system.
14. The distributed data-storage system of claim 9 wherein a unit of distributed, shared, locally cached, but globally consistent state information or distributed, shared state information may comprise one of:
a byte;
a computer word;
a field comprising a number of computer words;
a record comprising a number of computer words;
a data structure comprising a number of computer words; and
an access control comprising one or more bytes that controls access to additional state information.
15. The distributed data-storage system of claim 9 wherein the consistent, data-storage interface provided by the number of data-storage systems using distributed, shared, locally cached, but globally consistent state information and distributed, shared state information ensures that the effects of commands issues to the distributed data-storage system by host computers are serialized, so that a later executed command does not access stale state information subsequently modified by a earlier executed command.