Revision 70c7302fb5d343fa319e05327ecf88d09fe26a2b authored by haoyuhuang on 26 July 2019, 21:36:16 UTC, committed by Facebook Github Bot on 26 July 2019, 21:41:13 UTC
Summary: This PR implements cache eviction using reinforcement learning. It includes two implementations: 1. An implementation of Thompson Sampling for the Bernoulli Bandit [1]. 2. An implementation of LinUCB with disjoint linear models [2]. The idea is that a cache uses multiple eviction policies, e.g., MRU, LRU, and LFU. The cache learns which eviction policy is the best and uses it upon a cache miss. Thompson Sampling is contextless and does not include any features. LinUCB includes features such as level, block type, caller, column family id to decide which eviction policy to use. [1] Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. 2018. A Tutorial on Thompson Sampling. Found. Trends Mach. Learn. 11, 1 (July 2018), 1-96. DOI: https://doi.org/10.1561/2200000070 [2] Lihong Li, Wei Chu, John Langford, and Robert E. Schapire. 2010. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web (WWW '10). ACM, New York, NY, USA, 661-670. DOI=http://dx.doi.org/10.1145/1772690.1772758 Pull Request resolved: https://github.com/facebook/rocksdb/pull/5610 Differential Revision: D16435067 Pulled By: HaoyuHuang fbshipit-source-id: 6549239ae14115c01cb1e70548af9e46d8dc21bb
1 parent 41df734
.gitignore
make_config.mk
*.a
*.arc
*.d
*.dylib*
*.gcda
*.gcno
*.o
*.so
*.so.*
*_test
*_bench
*_stress
*.out
*.class
*.jar
*.*jnilib*
*.d-e
*.o-*
*.swp
*~
*.vcxproj
*.vcxproj.filters
*.sln
*.cmake
.watchmanconfig
CMakeCache.txt
CMakeFiles/
build/
ldb
manifest_dump
sst_dump
blob_dump
block_cache_trace_analyzer
tools/block_cache_analyzer/*.pyc
column_aware_encoding_exp
util/build_version.cc
build_tools/VALGRIND_LOGS/
coverage/COVERAGE_REPORT
.gdbhistory
.gdb_history
package/
unity.a
tags
etags
rocksdb_dump
rocksdb_undump
db_test2
trace_analyzer
trace_analyzer_test
block_cache_trace_analyzer
.DS_Store
java/out
java/target
java/test-libs
java/*.log
java/include/org_rocksdb_*.h
.idea/
*.iml
rocksdb.cc
rocksdb.h
unity.cc
java/crossbuild/.vagrant
.vagrant/
java/**/*.asc
java/javadoc
scan_build_report/
t
LOG
db_logs/
tp2/
fbcode/
fbcode
buckifier/*.pyc
Computing file changes ...
