Difficulties in designing documents for Top-K data structures and commands

[zweix123]

Related issues: Support Top-K data structure and commands #2424

Here is a note of my interpretation of the paper, written in Chinese.

Reference paper: HeavyKeeper: An Accurate Algorithm for Finding Top-k Elephant Flows

Required data structure:

1. A matrix of $d \times n$ , where the matrix elements are a key value pair

   

2. min-heap, where node elements are a key value pair

There are several ideas on how to design metadata

For the part of the hash table list, we can follow the design of List, where metadata stores the beginning and end of d arrays, and the values of ‘sub keys values’ are the corresponding hash tables. The question is whether there is a performance issue with the entire hash table being read and written every time.

Just like the diagram below

metadata

        +----------+------------+-----------+-----------+-----------+-----------+------------+
key =>  |  flags   |  expire    |  version  |  size     |  head     |  tail     | other data |
        | (1byte)  | (Ebyte)    |  (8byte)  | (Sbyte)   | (8byte)   | (8byte)   |  (Xbyte)   | 
        +----------+------------+-----------+-----------+-----------+-----------+------------+

sub key value

                     +--------------------------------+
key|version|index => | The serialized hash table data |
                     +--------------------------------+

Another issue is the min-heap, which can reuse zset. In other words, I need to store a zset key in the other data of the metadata above. The problem is how to ensure that the key here is globally unique and does not conflict with the use of other zsets in this namespace.

The above two questions.

[mapleFU]

I've a quick glance to the original paper. Seems that the min-heap is used to storing the (idx, score). So I think maybe this can be an adhoc binary format for the specific case here

[zweix123]

I've a quick glance to the original paper. Seems that the min-heap is used to storing the (idx, score). So I think maybe this can be an adhoc binary format for the specific case here

Do you mean that the min-heap does not need to be stored in RocksDB but in memory? If that's the case, I disagree because the user may have set the value of k to a relatively large value.

And the lifecycle of this heap structure is as long as the topk itself.

The paper is missing, here are my notes, which I think are more conducive to understanding.

[mapleFU]

Do you mean that the min-heap does not need to be stored in RocksDB but in memory?

No. There're two way to storing the data:

1. Store inlined in Heap Bucket. So the heap bucket would likely to be (score, fingerprint, data). In this way, we also has two way to storing this, (1) the first is storing the key-values in separate key. This is ok for some short key scenerio, but for long key scenerio, it would causing a long value blob. And the write space amplify would be huge, if K is large (2) the second is per-slot key-value, this might be easy but poping an element might get batch of keys. (3) Maybe a z-set style storage would be a OK way here
2. Storing data in separate key-value. This would likely cause higher maintaining cost, but less searching and write amplify

Anyway, if we can assume no huge-key and K is small, I prefer storing all data in same binary. If some large key-values would be written, writing value in heap-bucket or separate value is also ok to me

[zweix123]

Do you mean that the min-heap does not need to be stored in RocksDB but in memory?

No. There're two way to storing the data:

1. Store inlined in Heap Bucket. So the heap bucket would likely to be (score, fingerprint, data). In this way, we also has two way to storing this, (1) the first is storing the key-values in separate key. This is ok for some short key scenerio, but for long key scenerio, it would causing a long value blob. And the write space amplify would be huge, if K is large (2) the second is per-slot key-value, this might be easy but poping an element might get batch of keys. (3) Maybe a z-set style storage would be a OK way here
2. Storing data in separate key-value. This would likely cause higher maintaining cost, but less searching and write amplify

Anyway, if we can assume no huge-key and K is small, I prefer storing all data in same binary. If some large key-values would be written, writing value in heap-bucket or separate value is also ok to me

Thank you, your suggestion has inspired me, which is why I have the following design proposal.

[PragmaTwice]

Several points:

• head and tail seems useless here, instead we need to store something like depth, width, decay..
• other data is very confused and you need to specify it more clearly
• I don't think we should reuse the zset data structure, you can just design a special structure inside the subkeys of TOPK.

[zweix123]

Several points:

• head and tail seems useless here, instead we need to store something like depth, width, decay..
• other data is very confused and you need to specify it more clearly
• I don't think we should reuse the zset data structure, you can just design a special structure inside the subkeys of TOPK.

Yes, I have constructed another plan below that addresses each of the three issues you mentioned.

[zweix123]

I came up with the following binary design scheme.

metadata

        +---------+---------+---------+---------+---------+---------+---------+----------------------+
key =>  |  flags  |  expire | version |  decay  |    d    |    n    |    k    | min-heap node number |
        | (1byte) | (Ebyte) | (8byte) | (8byte) | (8byte) | (8byte) | (8byte) |       (8byte)        |
        +---------+---------+---------+---------+---------+---------+---------+----------------------+

d, n and k correspond to the concepts in the paper, respectively,

-d: is the length of the "hash table" list, with $d$ arrays
-n: is the number of buckets in each hash table, and all hash tables have $n$ buckets
-k: is the "K" in the TopK command, which is also equivalent to the upper limit of the number of nodes in min-heap.

sub key value of hash table array

                                        +-------------+---------+
key|version|array_index|bucket_index => | fingerprint | number  | 
                                        |   (8byte)   | (8byte) |
                                        +-------------+---------+

Because the images provided in the paper are not so much a "hash table list" as a "matrix", and the "buckets" corresponding to each array do not have the scaling function of a "hash table". So matrix storage is used.

sub key value of min-heap

                              +----------+---------+---------+
key|version|min-heap_index => | ID_size  |   ID    | number  | 
                              |  (8byte) | (Nbyte) | (8byte) |
                              +----------+---------+---------+

Firstly, min heap can be implemented using arrays; Secondly, the min heap mentioned in the paper also needs to have the ability to be randomly modified, so each node needs to be stored separately.

And 'flow ID' requires global uniqueness, so an indefinite length storage method is used.

end

May I ask if there are any issues with this design proposal?

[PragmaTwice]

1. What we need is not a solution that just "works", but a high-performance solution. I think you need to list how many RocksDB IO operations are required for each command under the currently designed data structure. On top of that, you can consider how to optimize to reduce the number of IO operations and computational complexity.
2. You need to consider the order of fields. In my opinion, a better encoding for metadata is .. | version | k | width | depth | decay and for min-heap it's number | ID size | ID so that number is in a fixed position.
3. You need to consider whether there will be conflicts between keys. In my opinion, it is easy for key|version|min-heap_index and key|version|ID to conflict, which will cause overall mess.

[zweix123]

You're right, I'll think about it again. Thank you very much.

But will the different positions of fields in metadata have any impact?

[zweix123]

May I ask what you think of the design of the "Hash Table List" here?

[PragmaTwice]

will the different positions of fields in metadata have any impact

If we know the number is always in the zero position (begin of the string), we can replace it quickly without any parsing (e.g. while inserting).

[zweix123]

will the different positions of fields in metadata have any impact

If we know the number is always in the zero position (begin of the string), we can replace it quickly without any parsing (e.g. while inserting).

I understand what you mean, I completely agree, thank you.

[wanghenshui]

topk structure should use inside kvrocks server as a metric

store in rocksdb is bad idea

1. kvrocks need own hot key collector
2. user get hotkey, the hotkey must in the cache.memory, fetch from rocksdb really NOT HOT

[mapleFU]

I think you're right but they're totally different. Redis Top-K command is a plugin in RedisBloom and it's easy to maintain and using ( but maybe not so widely used). However, "hotkeys" ( or top-k) would be tricky and might affect get/set bottleneck.

They might use same algorithm but the server-side "hotkeys" would only use only memory, and should be cost-efficient and disabled by default, and use "--hotkeys" command to list the "hotkeys"

[zweix123]

I think you should learn about the application scenarios of the topk command, which should be suitable for streaming data. It is not meant to maintain the overall hotkey of Kvrocks, but to specifically create a space for maintaining a Topk of a series of data.

[mapleFU]

AFAIK, if "K" in topK is not so large, I prefer the structure below:

Buckets: [...][....]   <-- all fixed size buckets in same key
HeapBucket: [fp, count, itemIndex][fp, count, itemIndex][fp, count, itemIndex] <-- all fixed size heap bucket in same key, with a itemIndex point to value
ValueSlots:
* valueIndex1
* valueIndex2
* ...

Pro:

1. When adjust HeapBucket is frequent, merely value is affected, since adjust HeapBucket would not affect value
2. Small write amplify

Cons:

1. If k is huge, HeapBucket would be large
2. ValueSlot might need to maintaining a bitmap to find the next free slot

[PragmaTwice]

Sounds fine to me.

FYI:
Size of all buckets: width*depth*(sizeof FP + sizeof C)
So in the default settings, it should be ~ 8*7*16=896 bytes.

It can be in one key unless users specifying a large width or depth.