feat(server): implement heavykeeper data structure. #257

[Super-long]

Signed-off-by: Super-long [email protected]

This commit implements a hotspot identification data structure - HeavyKeeper, and here is some description of this implemented version.

heavy_keeper.h：

1. The basic version of the original paper using min-heap is the most memory-efficient solution. However, the processing speed is limited because the time complexity of updating and searching the key in the min-heap is O(log(k)) and O(k), respectively, which is time consuming. HeavyKeeper-DF implements Optimization III in the original paper, which uses a bi-directional chain table + hash table instead of min-heap, which not only makes the time complexity of both insertion and update is O(1), but also eliminates the older hotkeys, so that the latest hotkeys are always in HeavyKeeper.

2. User can configure hk_threshold, only keys with HK[i][j].count greater than hk_threshold will be considered as hotkey, this value should be an empirical value, so it is settable.

3. hk_length is set to 3079, and there are two considerations here: (1). hk_length should be set to a prime number in order to avoid hash conflicts as much as possible, here we refer to https://planetmath.org/goodhashtableprimes. (2). In the original paper when HeavyKeeper is estimated at 80kb-100kb is very close to the theoretical probability capacity bound, and when hk_length is set to 3079 occupies about 80kb, the calculation here is like this: 12 * hk_wide * hk_length + LRUCache(topK).

4. HeavyKeeper-DF implements Optimization I/II from the original paper, and the code comments have references to both.

heavy_keeper_test.cc：

1. The basic functionality and performance of HeavyKeeper-DF was tested in Basic Test. It should be noted that HeavyKeeper is a probabilistic data structure, and the judgment condition is set to EXPECT_GE(hk_sum, hotkey_lens-1) for the stability of the unit test.
2. A simple test of HeavyKeeper-DF's hotspot elimination capability in the HotkeyEliminationTest test.

Others:

1. The current insertion rate of HeavyKeeper-DF is about 180 nanoseconds per request, which seems to satisfy the "fast insertion", and these numbers are easily reproduced in the Basic test, and gperftools is also included in the unit test by executing "pprof . /heavy_keeper_test test.prof --pdf > test.pdf" to see the performance bottleneck of HeavyKeeper-DF. My CPU model name is : Intel(R) Xeon(R) Gold 6133 CPU @ 2.50GHz. here are the results of the unit test running on my machine：

2. Currently the destructor of LRU Cache is not implemented, and the Node allocation in LRU uses new/delete (not a bottleneck), perhaps a better approach is a two-way array list

3. This PR is mainly to verify that such an implementation is feasible, and to simplify the implementation, std::string is used for the parameters of HeavyKeeper.Insert. when the feasibility is determined, I will continue to adapt dragonfly's key.

My implementation is partially referenced at: https://github.com/papergitkeeper/heavy-keeper-project .

Thanks to these clever people for creating this interesting data structure!

[Super-long]

One interesting thing, from the perf results, the performance bottleneck of HeavyKeeper-DF is focused on find operation, because ankerl::unordered_dense::map is efficient in find(string) operation, I replaced std::unordered_map in LRUCache with ankerl::unordered_dense::map, and got about 45% performance improvement, the following is the result of unit test:

Although ankerl::unordered_dense::map is an excellent open source project, we must consider stability, which is a tradeoff between performance and stability, so whether to use ankerl::unordered_dense::map I think it still needs to be discussed by the community members.

[romange]

Thanks for writing this summary. I will provide general comments here about the code style here:

1. Avoid using flags (ABSL_FLAG) for low-level data-structures. You can introduce Options struct or pass parameters directly in a c'tor instead.
2. Use cc file for the implementation and for internal data-structures. Header files should be stay as clean as possible.
3. Please comment the algo and data structures.
4. Unit tests are for correctness testing. For performance benchmarks use BENCHMARK fixtures. See https://github.com/dragonflydb/dragonfly/blob/082ac36ac195b5fd503422db7152c2d6efbd857a/src/core/dash_test.cc#L1081 for example. You also do not have to manually control profiler. You can run the test with CPUPROFILE=/tmp/foo.prof ./heavy_keeper_test and it should work.
5. I usually use absl::flat_hash_map as my default hashmap type. it's pretty efficient.

[romange]

I do not remember the paper now (need to reread it) but what if we won't have lruCache/topK at all? will this affect the correctness of Insert method?

[Super-long]

Okay, I will fix the code style issue next week.

lruCache： As far as I understand, the original paper has very little description of the heavykeeper implementation without min-heap (Optimization III: Speed Acceleration.), so there isn't a good example to guide me on how to do it.

The original paper mentions using arrays instead of min-heap to save time, but this has the problem that ：

1. in order to implement Optimization I/II we need to know quickly if a key exists in an array,
2. In the original version, min-heap records the topk of count in all keys, and its will always eliminate the element with the smallest count in min-heap. In the array version, only keys with count greater than a threshold are added to the array, and it lacks a good elimination strategy.

These two points make me think that LRU with Insert/Find time complexity of O(1) is a good choice.

topK： topK is necessary. Because the definition of HeavyKeeper is : An Accurate Algorithm for Finding Top-k Elephant Flows

[romange]

@Super-long I totally get why topK is necessary when implementing the original article. I am saying that from product perspective, this feature is going to be used for debugging, imho, therefore we have the prerogative to do a brute force sort+topK for the whole dataset. As long as the dataset is not huge (i.e. less than millions) the cost of sort during query time is not very high. And I am not saying we should choose this option but I want to understand if this option is feasible, i.e. topK is required only for querying and not needed for updates.

[Super-long]

I actually think it's a great idea, but really it's two different directions.

1. dynamically maintaining LRU/topK allows us to know the topk information in real time, so we can do automated hotspot identification at a small cost and perform subsequent actions to optimize the hotspot or want to monitor real-time hotspot information at the second level.
2. It is perfectly feasible not to dynamically maintain LRU/topK, because when a key is a hotkey it does always reside in HeavyKeeper, and the length of HeavyKeeper is currently set to 3079, and full sorting is not a big overhead, so if we only want to call the topk interface a few times a day, obviously we don't need to maintain LRU/topK.

So I think we should think about what kind of hotkey capability we need and what kind of interface we want hotkey to have.

[Super-long]

I think I can do some research in the next few weeks to see what the current interfaces are for hotspots from the major public cloud vendors.

[romange]

I suspect we are pushing boundaries here but go ahead - would love to hear what you learn!

[Super-long]

Code style related issues were fixed in the latest commit. The next major task is to think about what kind of hotspot interface is needed in dragonfly, which is related to whether we need topk or not.

The current implementation of LRU is relatively simple and even uses bare pointers for a fast implementation, but this implementation is memory leak free.

Execute valgrind --tool=memcheck --leak-check=full --show-leak-kinds=all . /heavy_keeper_test reproduces the following result：

[Super-long]

I'll be submitting a PR soon to fix the code changes mentioned above.

I've been thinking about how to use heavykeeper in dragonfly for a while now, and here are three issues I'd like to address.

1. some drawbacks of heavykeeper as a data structure.
2. the way other public cloud vendors handle hotspots.
3. how we should use heavykeeper results.

[Super-long]

1. some drawbacks of heavykeeper as a data structure.

a. The value of hk_b in exponential-weakening decay is 1.08, which is referred to the example in the paper, but it is not necessarily suitable for drangonfly, because the decreasing probability is already very low when the count is equal to about 50, which means that when there is a conflict, often a key that is an order of magnitude larger than the previous hotspot can offset the previous key. So hk_b needs to be modified based on the qps of different machines.

b. heavykeeper is used to identify topk information over a period of time, the problem is that a period of time is not quantifiable, for example, we want to perceive hotspot information within 5s of seconds, the original heavykeeper structure is not available.

[Super-long]

2. other public cloud vendors handle hotspots.

Take the hotspots handling capability of public cloud vendors that support redis protocol as an example, full metrics detection is supported in AWS ElastiCache, Azure Cache for Redis, google memorydb, and Redis Lab, where you can see real-time hotspot information.

In Alibaba Cloud, it supports real-time hotkey statistics, offline full-volume key analysis, and hotspot optimization through Proxy Query Cache; in tencent Cloud, it supports 5/10/15 seconds hotspot analysis and historical hotkey analysis.

In larger capacity Nosql/relational database, hotspot information is usually used for split point selection.

[Super-long]

3. how we should use heavykeeper results. So, I think what we need is real-time hotspot information display and some access optimization based on hotspot information. The former can support hotspot statistics at 5s level and print the output in a separate log file; the latter can think about what optimizations we can do after getting the hotspot information, such as data replacement in the dash to reduce the number of searches, or some kind of cache, which requires a deeper understanding of the code.

[Super-long]

To summarize, a complete hotspot identification module may require at least three PRs.

1. support the basic heavykeeper structure.
2. support for hotspot identification, i.e., the logs show real-time hotspot information within 5s (configurable) (docked to ELK or Prometheus).
3. heavykeeper can sense real-time hotkey and how to optimize user access based on this information.

[Super-long]

@romange One question is do we need to use heavykeeper to support hotspot identification within 5s? The basic process is as follows.

1. heavykeeper is used for hotspot identification within 5s
2. print topk to log
3. clear heavykeeper
4. .....

There is an extreme case here, for example, the identification period of heavykeeper is [0s,5s][5s,10s], there may be a hotspot duration in [4s,7s], the general case of hotspot access is much larger than other keys, so in [0s,5s][5s,10s] this key can generally be identified as a hotspot.

[romange]

@Super-long Do you mind if i take over this PR? I will keep the high-level design as is, but will adapt the code to our style guide and do other modifications.