Federated indexing from hashed primary key slices
A method and system stores and retrieves data items associated with a primary key, using search indices at multiple storage locations. A server receives a primary key, identifies one or more segments of the primary key, and hashes each segment with one or more hash functions to obtain a sequence of hash values. The hash values are used as keys to index a chain of search indices that are stored in multiple storage locations. One or more of the hash values in the sequence are used to form a host name, and the host name is mapped to an address of a server that stores a first search index in the chain. The last search index in the chain contains the data items associated with the primary key, or provides a reference to one or more locations at which the data items can be found.
1. A computer-implemented method, comprising:
receiving, by a computer system, a primary key associated with a plurality of data items, the primary key including a plurality of segments;
hashing, by the computer system, each segment with one or more hash functions to obtain a sequence of hash values; and
determining, by the computer system, one or more storage locations of the data items using a chain of search indices that uses the sequence of hash values as keys.
2. The method of claim 1 , further comprising:
forming, with a predetermined number of the hash values in the sequence, a name of a host that stores a first search index in the chain; and
obtaining an address of the host from a domain name server (DNS) using the name of the host.
3. The method of claim 1 , further comprising:
forming a name of a host that stores a first search index in the chain, the name including a predetermined number of the hash values in an order that a first hash value in the sequence being farthest right in the name; and
performing a recursive DNS query that uses the hash values from right to left in the name to obtain an address of the host.
4. The method of claim 1 , further comprising:
mapping a predetermined number of the hash values in the sequence to an Internet Protocol (IP) address of a host that stores a first search index in the chain.
5. The method of claim 1 , further comprising:
querying a server referenced by a last search index in the chain using the primary key to obtain the data items.
6. The method of claim 1 , further comprising:
obtaining the data items from a last search index in the chain.
7. The method of claim 1 , wherein receiving a primary key further comprises:
identifying the segments as separated by a delimiter or as fix-length data segments.
8. The method of claim 1 , further comprising:
using each hash value in the sequence as a key to index one of the chain of search indices that are stored across multiple locations.
9. A computer readable storage medium including instructions that, when executed by a processing system, cause the processing system to perform a method comprising:
receiving a primary key associated with a plurality of data items, the primary key including a plurality of segments;
hashing each segment with one or more hash functions to obtain a sequence of hash values; and
determining one or more storage locations of the data items using a chain of search indices that uses the sequence of hash values as keys.
10. The computer readable storage medium of claim 9 , further comprising:
forming, with a predetermined number of the hash values in the sequence, a name of a host that stores a first search index in the chain; and
obtaining an address of the host from a domain name server (DNS) using the name of the host.
11. The computer readable storage medium of claim 9 , further comprising:
forming a name of a host that stores a first search index in the chain, the name including a predetermined number of the hash values in an order that a first hash value in the sequence being farthest right in the name; and
performing a recursive DNS query that uses the hash values from right to left in the name to obtain an address of the host.
12. The computer readable storage medium of claim 9 , further comprising:
mapping a predetermined number of the hash values in the sequence to an Internet Protocol (IP) address of a host that stores a first search index in the chain.
13. The computer readable storage medium of claim 9 , further comprising:
querying a server referenced by a last search index in the chain using the primary key to obtain the data items.
14. The computer readable storage medium of claim 9 , further comprising:
obtaining the data items from a last search index in the chain.
15. The computer readable storage medium of claim 9 , wherein receiving a primary key further comprises:
identifying the segments as separated by a delimiter or as fix-length data segments.
16. The computer readable storage medium of claim 9 , further comprising:
using each hash value in the sequence as a key to index one of the chain of search indices that are stored across multiple locations.
17. A system comprising:
a network;
data storage coupled to the network to store a search index; and
an indexing server coupled to the data storage to receive at least one hash value in a sequence of hash values that are obtained from hashing one or more segments of a primary key with one or more hash functions, and to use the at least one hash value as a key to the search index to cause a location of one or more data items associated with the primary key to be determined.
18. The system of claim 17 , further comprising:
a main server coupled to the network to hash the segments of a primary key with one or more hash functions to obtain the sequence of hash values; and
a routing module coupled to the main server to use a predetermined number of the hash values in the sequence to identify a name of one of a plurality of indexing servers that holds a first search index in a chain of search indices stored across multiple locations.
19. The system of claim 17 , further comprising:
a main server coupled to the network to hash the segments of a primary key with one or more hash functions to obtain the sequence of hash values; and
a routing module coupled to the main server to use a predetermined number of the hash values in the sequence to identify an Internet Protocol (IP) address of one of a plurality of indexing servers that holds a first search index in a chain of search indices stored across multiple locations.
20. The system of claim 17 , further comprising:
one or more domain name servers coupled to the network to receive a name of a host and to return an address of the host, the host being one of a plurality of indexing servers that holds a first search index in a chain of search indices stored across multiple locations.