System and methods for mapping and searching objects in multidimensional space

#The invention relates generally to distributed computing environments, and particularly to a distributed key-value store that stores multi-attribute objects and enables quick and efficient lookup by any attribute.

#Storing and retrieving data is a critical operation for many software applications. For example, software applications such as web services and scientific computations often need to store data and retrieve it later. Such data is often structured to conform to a rigid schema such as the names and types of attributes common to the data. Data may also be semi-structured in that the data does not conform to a rigid schema but nonetheless contains tags or other markers to separate attribute values. Furthermore, data may be unstructured wherein the data lacks attributes entirely.

#The advent of distributed computing environments such as cloud computing systems has opened new possibilities for the rapid and scalable deployment of data storage and retrieval systems. In general, a distributed computing environment deploys a set of hosted resource servers that can be combined or strung together to perform coordinated tasks. For example, one group of resource servers can be configured to accept and service requests from web clients, known as front-end servers. A further group of resource servers can be configured to serve as a data store to provide data storage and retrieval services to the front-end servers. Other types of resource servers are also possible.

#FIG. 1 illustrates a flow chart for node coordinate assignment according to one embodiment of the present invention;

#FIG. 2 illustrates a flow chart for data object insertion according to one embodiment of the present invention;

#FIG. 3 illustrates a flow chart for searching an object of a key-value database according to one embodiment of the present invention;

#Objects are mapped to one or more data storage nodes for placement in a distributed key-value store. FIG. 1 illustrates a flow chart for node coordinate assignment 100 according to one embodiment of the present invention. As shown by step 102, data storage nodes are distributed in hyperspace. A region of the hyperspace, or hyperregion, is assigned to each data storage node according to step 104. Each data storage node is responsible for one or more data objects that fall into the assigned region. The region of n-dimensional space assigned to each of the data storage node may overlap such that the data object is mapped to multiple, redundant home nodes. In one embodiment, the multiple, redundant home nodes are organized in a linear chain. The operation instruction is then mapped to the head of the linear chain and forwarded to each of the data storage node along the linear chain in the order determined by the linear chain. The region of n-dimensional space assigned to each of the data storage node may also be performed by a coordinator algorithm, which may be centralized or de-centralized. The coordinator algorithm may also maintain a membership list of the plurality of data storage nodes. The coordinator algorithm may uniformly distribute or randomly distribute the data storage nodes within the hyperspace.

#FIG. 2 illustrates a flow chart for data object insertion 150 according to one embodiment of the present invention. As shown by step 152, a coordinate of each data object is computed from one or more attribute values of the data object. The coordinate may be computed by hashing the one or more attribute values of the data object or by calculating an order-preserving function of the one or more attribute values of the data object. For example, attribute values of an object are hashed to define an x, y, z coordinate wherein each attribute of the object corresponds to each dimension. At step 154 a home node is identified that corresponds to the coordinate of each data object. It is contemplated that more than one home node may be identified that corresponds to the coordinate of each data object. An operation instruction is then forwarded to the home node. The operation instruction may be to store the data object at the home node, delete the data object from the home node, or modify the data object at the home node. Other operation instructions are also contemplated such as comparing and swapping data objects.

#Each data storage node may store one or more data objects on persistent local storage. The persistent local storage may be divided into a plurality of partitions, each partition responsible for a subregion of the region of n-dimensional space assigned to each data storage node. The data object is stored on the partition that contains the coordinate of the data object.