donavanm
a year ago
If anyone is interested in space & time efficient caching and working set tracking check out some of my favorites, gil einziger https://scholar.google.co.il/citations?user=kWivlnsAAAAJ and the ex coho data guys https://www.usenix.net/system/files/conference/osdi14/osdi14....
Ben Manes[1] worked with Gil Einziger on an implementation of TinyLFU and actually contributed to an updated version of the TinyLFU paper, IIRC. Gil has a ton of very relevant work[2][3] around cache admission, control, and information density.
Coho data was working very large storage arrays, specifically optimizing data placement across different media/hosts/etc. lots of similar problems where even the metadata of the working set was prohibitively large. So they had space & time efficient functions to track access patterns in realtime. Their business didnt work out (unfortunately) and most of them ended up at AWS, working on storage like S3 and Glacier.
[1] https://github.com/ben-manes/caffeine/wiki/Efficiency#window... [2] https://scholar.google.com/citations?user=kWivlnsAAAAJ&hl=en [3] https://github.com/gilga1983