SkyAPM / aiops-engine-for-skywalking

This is an incubating repository of the Apache SkyWalking AIOps Engine
https://github.com/apache/skywalking/discussions/8883
Apache License 2.0
37 stars 7 forks source link

[Algorithm] Drain cache look up optimization, evaluate accuracy impacts #12

Open Superskyyy opened 2 years ago

Superskyyy commented 2 years ago

Now, @Liangshumin has a prototype to use cache look-up to speed up Drain significantly. I changed the lookup to after masking since

The algorithm sped up at least 40%, by reducing tree traversal almost to neglectable time. (then it's the divide and conquer the problem of masking task).

We should keep this optimization in mind and conduct further testing. If it's stable, we should probably contribute back upstream as it's a general purpose optimization.

This thread tracks our case by testing and theoretical evaluation in case unwanted side-effects emerge.

We also need to evaluate the choice of cache size to limit memory usage, it most likely should be near max_cluster limit.

Superskyyy commented 2 years ago

Caching technique has been proven to be effective. Implementation is on going.

Superskyyy commented 2 years ago

Addressed in #23

Superskyyy commented 2 years ago

Maybe LFU cache works better in some cases? It should be provided as an option depending on the data.