Method and apparatus for flexible partitioning of data in lsm-like tables
AssigneeHuawei Technologies Co., Ltd.
InventorRobin GROSMAN
Life of this patent
Estimating the term…
Abstract
There is provided a method and device for partitioning a database such that any partition is both hash-partitioned and range-partitioned. An entry may be stored on a partition which corresponds to the output of a hash function on the primary key of the entry, and which is associated to a range to which the primary key belongs. This may be implemented in LSM tables or similar systems. A global compaction process may be used to reorganize the data periodically.
Claims20
A method in a database system comprising a plurality of nodes, each of the plurality of nodes comprising different levels, the method comprising:
- specifying, for each level on each of the plurality of nodes, a hash value and a range;
- receiving a new entry, the entry comprising a primary key;
- computing a hash function on the primary key;
- selecting a level on a node for which the hash value matches the computed hash function for the primary key and for which the range comprises the primary key;
- and
- routing the new entry to the selected level.
A computing device for managing a database system comprising a plurality of nodes, each of the plurality of nodes comprising different levels, comprising:
- a processor;
- a communications subsystem;
- wherein the computing device is configured to:
- specify, for each level on each of the plurality of nodes, a hash value and a range;
- receive a new entry, the entry comprising a primary key;
- compute a hash function on the primary key;
- select a level on a node for which the hash value matches the computed hash function for the primary key and for which the range comprises the primary key;
- route the new entry to the selected level.
A computer readable medium having stored thereon executable code for execution by a processor of a computing device, the executable code comprising instructions for:
- specifying, for each level on each of the plurality of nodes, a hash value and a range;
- receiving a new entry, the entry comprising a primary key;
- computing a hash function on the primary key;
- selecting a level on a node for which the hash value matches the computed hash function for the primary key and for which the range comprises the primary key;
- routing the new entry to the selected level.
Dependencies are inferred from the claim text.