HNHacker News
TopNewBestAskShowJobs

NovaX

288 karma · joined May 4, 2011

https://github.com/ben-manes
submissionscomments
NovaX··on Apache Traffic Server
TinyLFU+FIFO is in the simulator (https://github.com/ben-manes/caffeine/wiki/Simulator). However, you'd probably also want the window cache to correct the deficiency outlined in the updated paper (http://arxiv.org/pdf/1512.00727.pdf). A FIFO version with that isn't in the simulator, but would be easy to add.

mutli1 trace - W-TinyLFU: 55.6% - TinyLFU+Random: 53.8% - TinyLFU+FIFO: 48.6% - TinyLFU+LRU: 54.8% - FIFO: 41.0% - LRU: 46.7%

FIFO's poor choice of a victim has a big impact, so it doesn't seem promising. A random policy looks like an attractive fit, though.

NovaX··on Beyond the LRU cache policy
Any chance you have pointers for public trace files? Its interesting to see the behaviors under different workload patterns.

Adding a cost model (GDSF, et al) is too specialized that I haven't spent time looking in that domain. From your hints that sounds like the unexplored area that your work successfully optimized.

NovaX··on Beyond the LRU cache policy
Are you allowed to describe the eviction policy? It would be interesting to know the differences. You can contact me privately (ben.manes at gmail). I'd be interested in knowing,

- Did it use a sketch in a similar manner? - Was it an LRU window to a classic LFU? Did it retain history? - Was it robust in all workload patterns or optimized for VDN workloads?

I would expect a 4-Segment LRU (S4LRU) policy to work well in VDN, while being a simple O(1) policy. That's used by Facebook photos, among others, so probably good for CDN content.

NovaX··on File system replacement algorithms (2006)
I recently did an analysis of caching algorithms and the difference can be quite large. Approaches that only use the current working set are very similar, but those that take advantage of historic data can make more intelligent choices.

https://github.com/ben-manes/caffeine/wiki/Efficiency

NovaX··on Clarifications about Redis and Memcached
As you said elsewhere, the network I/O is the primary bottleneck. There are a lot of different hashtable designs (so per-key locks not required), but fine grained locking of the table/LRU is probably enough. Since an in-app cache has a different perf profile, the latter two links summarize my work.
NovaX··on Clarifications about Redis and Memcached
The locks are becoming more fine-grained in memcached [1], so that should be less of a problem now.

It is possible to remove lock contention on the read path [2] if a concurrent hash table is used. This can be done while using an O(1) eviction policy that outperforms LRU [3].

[1] https://github.com/memcached/memcached/pull/97 [2] https://github.com/ben-manes/caffeine/wiki/Design [3] https://github.com/ben-manes/caffeine/wiki/Efficiency

NovaX··on A high performance caching library for Java 8
I've been doing a lot of work on a new optimal eviction policy. It out performs or matches the current gold standard, without requiring the cache holds evicted keys as those policies do (doubles or triples the physical size). Instead it uses a 4-bit CountMinSketch to record the historic frequency and two LRU queues to balance temporal workloads (high/low frequency + high time locality). This approach is simpler, fast, and much more memory efficient.

By moving to a policy that knows which entries are hot, a fast path read could be added to skip policy maintenance for the hottest entries. This could improve performance by 2-3x on a Zipf workload (typical) and has minimal impact on the hit rate.

We're hoping to publish a paper on this new policy. I'm currently integrating it into the cache (but already implemented in the simulator).

NovaX··on Einstein as a Jew and a Philosopher
"As a child I received instruction both in the Bible and in the Talmud. I am a Jew"
NovaX··on Caffeine – Java 8 caching
* Benchmarks: https://github.com/ben-manes/caffeine/wiki/Benchmarks

* Design: https://github.com/ben-manes/caffeine/wiki/Design

This is an evolution of two previously successful caching libraries:

* ConcurrentLinkedHashMap: https://code.google.com/p/concurrentlinkedhashmap/

* Google Guava's Cache: https://github.com/google/guava

NovaX··on OpenZFS: Reducing ARC Lock Contention
That would require a write rate very atypical for a cache and easily mitigated, though largely an almost impossible scenario.
NovaX··on Lock-Free Data Structures. The Evolution of a Stack
Elimination can be enhanced by using a combination strategy, such as DECS [1]. Using a combiner approach should also work on a queue structure, though interestingly enough there is a paper on elimination-based fifo queues. I wrote an elimination stack in Java [2], but I haven't gotten around to adding combining to the arena yet. The performance is pretty good compared to other shared concurrent structures.

[1] http://www.cs.bgu.ac.il/~hendlerd/papers/DECS.pdf [2] https://github.com/ben-manes/caffeine

NovaX··on The Opposite of a Bloom Filter
Its called a direct mapped cache: http://en.wikipedia.org/wiki/CPU_cache#Direct-mapped_cache
← PreviousPage 6 of 6