US 10,769,126 B1 · Data entropy reduction across stream shard

Abstract

Systems and methods are disclosed to implement a re-sharding technique that redistributes data in a first set of shards of a first stream into a second set of shards of a second stream to reduce the entropy of the data. In embodiments, individual ones of a number of re-sharding nodes determine statistics on an individual shard. The statistics include, for individual data keys in the shard, a frequency of the key and the cardinality of the key. The re-sharding node then selects a list of high-frequency, low-cardinality keys to be used generate a re-sharding scheme that is used to redistribute data items in the first set of shards to the second set. The re-sharding scheme assigns data items having the same key value combinations to the same range of shards in the second set. Accordingly, upon redistribution, data entropy in the second set of shards is reduced.

Claims20

Dependent claims

A system, comprising:

one or more hardware processors with associated memory that implement:
a data stream service configured to:
receive semi-structured data items to be added to a first stream, the data items having a plurality of different key-value pairs;
distribute the data items into a plurality of shards of the first stream based on a randomized sharding scheme;
and
a plurality of re-sharding nodes, each configured to:
obtain data items of a respective different shard of the plurality of shards from the data stream service, and:
determine statistics for a set of the data items of the respective shard, including frequency and cardinality statistics for the set of data items;
select an ordered subset of the keys in set of data items based at least in part on the statistics;
determine a re-sharding scheme based at least in part on the ordered subset of keys and the statistics;
and
wherein the data stream service is configured to:
redistribute the set of data items to a plurality of shards of a second stream based at least in part on the re-sharding scheme.

10 more elements

A non-transitory computer-accessible storage medium storing program instructions that when executed on one or more processors of a re-sharding node, cause the re-sharding node to:

determine statistics from a set of data items in a shard of a plurality of shards of a stream, wherein the statistics include frequency and cardinality statistics for the set of data items;
select an ordered subset of keys in the set of data items based at least in part on the statistics;
and
determine a re-sharding scheme based at least in part on the ordered subset of keys and the statistics, wherein the re-sharding scheme specifies how the set of data items are to be redistributed to a plurality of other shards.

1 more element

Dependencies are inferred from the claim text.

Data entropy reduction across stream shard

Life of this patent

Data entropy reduction across stream shard

Life of this patent

Abstract

Claims20