System and method for range search over distributive storage systems

摘要

This invention pertains generally to a method for resolving and managing eventual consistency conflicts when using a Prefix Hash Tree (“PHT”) in which the underlying storage system is a Distributed Hash Table (“DHT”). An embodiment according to the within invention comprises a computer implemented method for resolving eventual consistency conflicts when using a PHT and DHT. The method includes using an algorithm to create a prefix hash tree that relates to a distributed hash table, the prefix hash tree having multiple nodes, wherein the nodes comprise leaf nodes and internal nodes, aggregating all distinct records across all conflicting nodes, wherein conflicting nodes are nodes that have identical data records, and counting records returned to obtain an aggregated record count; splitting the conflicting nodes that have the aggregated record counts that exceeding a max record count, such that the aggregated records are divided by a prefix into each new node, resulting in the consolidation of duplicate data that were in conflicting nodes into a single data record in a single node; and splitting conflicting nodes that are internal nodes regardless of the aggregated record count.

主权项

1. A computer-implemented method for resolving eventual consistency conflicts within a prefix hash tree comprising the steps of:
using an algorithm to create a prefix hash tree that relates to a distributed hash table, the prefix hash tree having multiple nodes, wherein the nodes comprise leaf nodes and internal nodes; aggregating all distinct records across all conflicting nodes, wherein conflicting nodes are nodes that have identical data records, and counting records returned to obtain an aggregated record count; splitting the conflicting nodes that have the aggregated record count exceeding a max record count, such that the aggregated records are divided by a prefix into each new node, resulting in the consolidation of duplicate data that were in conflicting nodes into a single data record in a single node; and splitting conflicting nodes that are internal nodes regardless of the aggregated record count.