Data access optimization in distributed database

1. A computer-implemented method for querying a database distributed across a set of clusters, each cluster including a set of nodes, the computer-implemented method comprising, by a node:

receiving an instruction to write or read data, the instruction comprising a key specifying a location for the data within the database, the database including a keyspace defined by attoshards, each attoshard being a segment of the keyspace having a size, in keys, proportional to a total number of nodes in the database, each attoshard comprising keys for a plurality of cluster segments at predefined positions within the attoshard, each cluster segment corresponding to one cluster of the plurality of clusters;

hashing the key to generate a token;

performing a modulo operation on the token using the total number of nodes in the database to compute a remainder value;

determining a cluster segment of an attoshard based on a position in the attoshard defined by the remainder value;

determining a cluster of the set of clusters for the instruction corresponding to the determined cluster segment; and

executing the instruction to write or read the data at the determined cluster.

2. The computer-implemented method of claim 1 , wherein each cluster segment is a portion of the attoshard proportional to the overall size of the attoshard according to a ratio of nodes in the cluster corresponding to the cluster segment to the total number of nodes in the database.

3. The computer-implemented method of claim 1 , wherein executing the instruction to write or read the data at the determined cluster comprises:

identifying a specific node from the set of nodes of the determined cluster by evaluating the token using a token ring of the determined cluster; and

executing the instruction at the specific node of the determined cluster.

4. The computer-implemented method of claim 1 , further comprising identifying the attoshard as corresponding to a current configuration of the database based on:

determining a matching database configuration of a set of database configurations based on a time of last write for the key, wherein each database configuration corresponds to a time range; and

retrieving the attoshard corresponding to the matching configuration.

5. The computer-implemented method of claim 4 , further comprising:

detecting a change in size of the database, the change in size of the database comprising at least one of a change in a number of nodes in a cluster and a change in a number of clusters in the cluster set;

generating a new attoshard corresponding to the change in size, wherein the new attoshard comprises at least one of a new size in keys and a new number of cluster segments;

receiving a second instruction to read or write data; and

using the attoshard to identify a cluster to which to send the second instruction.

6. The computer-implemented method of claim 1 , wherein sending the instruction to the determined cluster comprises sending the instruction exclusively to the determined cluster.

7. The computer-implemented method of claim 1 , wherein determining a cluster segment of an attoshard based on a position in the attoshard defined by the remainder value comprises:

advancing the remainder value number of keys into the attoshard to identify a particular key, wherein an initial key of the attoshard corresponds to a remainder value of zero; and

identifying a particular cluster segment including the particular key.

8. The computer-implemented method of claim 1 , wherein the instruction is a read instruction, and executing the instruction to read the data at the determined cluster further comprises:

reading the data exclusively from the determined cluster.

9. A non-transitory computer-readable storage medium comprising computer program instructions executable by a processor to perform operations for querying a database distributed across a set of clusters, each cluster including a set of nodes, the operations comprising, by a node:

receiving an instruction to write or read data, the instruction comprising a key specifying a location for the data within the database, the database including a keyspace defined by attoshards, each attoshard being a segment of the keyspace having a size, in keys, proportional to a total number of nodes in the database, each attoshard comprising keys for a plurality of cluster segments at predefined positions within the attoshard, each cluster segment corresponding to one cluster of the plurality of clusters;

hashing the key to generate a token;

performing a modulo operation on the token using the total number of nodes in the database to compute a remainder value;

determining a cluster segment of an attoshard based on a position in the attoshard defined by the remainder value;

determining a cluster of the set of clusters for the instruction corresponding to the determined cluster segment; and

executing the instruction to write or read the data at the determined cluster.

10. The non-transitory computer-readable storage medium of claim 9 , wherein each cluster segment is a portion of the attoshard proportional to the overall size of the attoshard according to a ratio of nodes in the cluster corresponding to the cluster segment to the total number of nodes in the database.

11. The non-transitory computer-readable storage medium of claim 9 , wherein executing the instruction to write or read the data at the determined cluster comprises:

identifying a specific node from the set of nodes of the determined cluster by evaluating the token using a token ring of the determined cluster; and

executing the instruction at the specific node of the determined cluster.

12. The non-transitory computer-readable storage medium of claim 9 , the operations further comprising identifying the attoshard as corresponding to a current configuration of the database based on:

determining a matching database configuration of a set of database configurations based on a time of last write for the key, wherein each database configuration corresponds to a time range; and

retrieving the attoshard corresponding to the matching configuration.

13. The non-transitory computer-readable storage medium of claim 12 , the operations further comprising:

detecting a change in size of the database, the change in size of the database comprising at least one of a change in a number of nodes in a cluster and a change in a number of clusters in the cluster set;

generating a new attoshard corresponding to the change in size, wherein the new attoshard comprises at least one of a new size in keys and a new number of cluster segments;

receiving a second instruction to read or write data; and

using the attoshard to identify a cluster to which to send the second instruction.

14. The non-transitory computer-readable storage medium of claim 9 , wherein sending the instruction to the determined cluster comprises sending the instruction exclusively to the determined cluster.

15. The non-transitory computer-readable storage medium of claim 9 , wherein determining a cluster segment of an attoshard based on a position in the attoshard defined by the remainder value comprises:

advancing the remainder value number of keys into the attoshard to identify a particular key, wherein an initial key of the attoshard corresponds to a remainder value of zero; and

identifying a particular cluster segment including the particular key.

16. The non-transitory computer-readable storage medium of claim 9 , wherein the instruction is a read instruction, and executing the instruction to read the data at the determined cluster further comprises:

reading the data exclusively from the determined cluster.

17. A system, comprising:

a processor; and

a non-transitory computer-readable storage medium comprising computer program instructions executable by the processor to perform operations for querying a database distributed across a set of clusters, each cluster including a set of nodes, the operations comprising, by a node:

receiving an instruction to write or read data, the instruction comprising a key specifying a location for the data within the database, the database including a keyspace defined by attoshards, each attoshard being a segment of the keyspace having a size, in keys, proportional to a total number of nodes in the database, each attoshard comprising keys for a plurality of cluster segments at predefined positions within the attoshard, each cluster segment corresponding to one cluster of the plurality of clusters;

hashing the key to generate a token;

performing a modulo operation on the token using the total number of nodes in the database to compute a remainder value;

determining a cluster segment of an attoshard based on a position in the attoshard defined by the remainder value;

determining a cluster of the set of clusters for the instruction corresponding to the determined cluster segment; and

executing the instruction to write or read the data at the determined cluster.

18. The system of claim 17 , wherein executing the instruction to write or read the data at the determined cluster comprises:

identifying a specific node from the set of nodes of the determined cluster by evaluating the token using a token ring of the determined cluster; and

executing the instruction at the specific node of the determined cluster.

19. The system of claim 17 , the operations further comprising identifying the attoshard as corresponding to a current configuration of the database based on:

determining a matching database configuration of a set of database configurations based on a time of last write for the key, wherein each database configuration corresponds to a time range; and

retrieving the attoshard corresponding to the matching configuration.

20. The system of claim 17 , wherein determining a cluster segment of an attoshard based on a position in the attoshard defined by the remainder value comprises:

advancing the remainder value number of keys into the attoshard to identify a particular key, wherein an initial key of the attoshard corresponds to a remainder value of zero; and

identifying a particular cluster segment including the particular key.