Use W-TinyLFU algorithm to enhance the LRU cache

[liqiangz]

Describe what this PR does / why we need it

Run testHitRateTest

Use Zipf's law(https://en.wikipedia.org/wiki/Zipf%27s_law) to test hitRate

Refer to https://blog.openacid.com/tech/zipf/

tinyLfu cache size 100, total 2000000, miss 1220740, hitRate 0.389630 lru cache size 100, total 2000000, miss 1447734, hitRate 0.276133

tinyLfu cache size 500, total 2000000, miss 971977, hitRate 0.514011 lru cache size 500, total 2000000, miss 1169400, hitRate 0.415300

tinyLfu cache size 1000, total 2000000, miss 866246, hitRate 0.566877 lru cache size 1000, total 2000000, miss 1048379, hitRate 0.475811

tinyLfu cache size 5000, total 2000000, miss 627779, hitRate 0.686110 lru cache size 5000, total 2000000, miss 765247, hitRate 0.617376

tinyLfu cache size 10000, total 2000000, miss 528916, hitRate 0.735542 lru cache size 10000, total 2000000, miss 641416, hitRate 0.679292

tinyLfu cache size 20000, total 2000000, miss 436149, hitRate 0.781926 lru cache size 20000, total 2000000, miss 517853, hitRate 0.741074

tinyLfu cache size 50000, total 2000000, miss 316985, hitRate 0.841507 lru cache size 50000, total 2000000, miss 352558, hitRate 0.823721

Does this pull request fix one issue?

Fixes #254

Describe how you did it

TinyLfu is an implementation of the TinyLfu algorithm: https://arxiv.org/pdf/1512.00727.pdf

Describe how to verify it

run tinyLFUTest run testHitRateTest

Special notes for reviews

[CLAassistant]

All committers have signed the CLA.

[codecov-io]

Codecov Report

Merging #287 (eb34490) into master (f854c93) will increase coverage by 1.07%. The diff coverage is 58.56%.

@@            Coverage Diff             @@
##           master     #287      +/-   ##
==========================================
+ Coverage   50.83%   51.90%   +1.07%     
==========================================
  Files          69       76       +7     
  Lines        3842     4321     +479     
==========================================
+ Hits         1953     2243     +290     
- Misses       1621     1795     +174     
- Partials      268      283      +15     

Impacted Files	Coverage Δ
core/hotspot/cache/wtinylfu/concurrent_tinylfu.go	0.00% <0.00%> (ø)
core/hotspot/cache/lru/lru.go	44.11% <11.76%> (ø)
core/hotspot/cache/wtinylfu/hash.go	21.42% <21.42%> (ø)
core/hotspot/cache/wtinylfu/tinylfu.go	67.02% <67.02%> (ø)
core/hotspot/cache/wtinylfu/slru.go	73.07% <73.07%> (ø)
core/hotspot/cache/wtinylfu/doorkeeper.go	82.50% <82.50%> (ø)
core/hotspot/cache/stats/cache_stats.go	83.33% <83.33%> (ø)
core/hotspot/cache/lru/concurrent_lru.go	87.50% <85.71%> (ø)
core/hotspot/cache/wtinylfu/count_min_sketch.go	93.33% <93.33%> (ø)
core/hotspot/traffic_shaping.go	62.26% <100.00%> (ø)
... and 21 more

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update f854c93...eb34490. Read the comment docs.