288 karma · joined May 4, 2011
[1] https://dl.acm.org/doi/10.1145/3274808.3274816 [2] https://github.com/ben-manes/caffeine/wiki/Efficiency#adapti...
https://howtodoinjava.com/java/generics/java-generics-what-i...
https://github.com/ben-manes/caffeine/issues/345#issuecommen...
A variation, called scaled ttl, was nicely discussed in this video. https://www.youtube.com/watch?v=kxMKnx__uso
Guava was always made available as Google's Java core utilities. I think it was always a misunderstanding to expect external contributions, like Apache Commons, as that was not its original intent. Rather it was to reduce internal duplication and ad hoc code with a shared standard. It then became useful for open-sourced Google projects (like API clients) and recruiting (new hires would be familiar with Google's libraries). Many suggestions are best spun off into new libraries, rather than donated to Google to maintain.
Java's many flaws have been papered over by a large ecosystem of libraries. As a non-gopher, I'm not sure if that same spirit exists. Perhaps that is due to the dependency debates, whereas Maven Central was quickly adopted when managing jars (via Ant) became too burdensome. Perhaps modules will help, as the language doesn't have to be batteries included.
Has anyone considered replacing ARC? It actually has fairly poor hit rates compared to other policies, with very modest improvements over LRU. I also wonder how much ghost entries contribute to space overhead, which is actually trivial to remove (ARC is an adaptive SLRU - so replace ghosts with a sampling hill climber).
http://highscalability.com/blog/2019/2/25/design-of-a-modern...
A database will often scan many records which would flush an LRU. Postgres uses small LRU buffer caches in your per-thread model, backed by a larger LRU-like cache. The buffer caches are easily flushed by scans, but protect the shared cache from this noise. That shared cache could probably benefit from a smarter policy and this is an on going topic.
For fixed expiration (e.g. 5 min TTL), I use time-bounded LRU queues. Then if the head item has not expired, its successors have not either. If it has, it is merely a poll.
For custom expiration (varies per-entry), I use a hierarchical timer wheel. This replaces sorting with hashing, with an amortized O(1) cost.
For refresh, that's when I do it on access since its being used. I keep a refresh timestamp and an expiration timestamp, so that a refresh can occur while the data is valid but aging, but a blocking load is required when its too stale (expired).
You might enjoy this slide deck of the ideas that I use: https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsU...
https://user-images.githubusercontent.com/378614/52891655-29...
It would be much more interesting if they used the traces from ARC and LIRS, perhaps also UMass and Wikipedia. These traces are publically available and used by multiple papers from a variety of groups.
I have not seen a sampling-based policy that outperforms a policy that has tracks history outside of its working set. Since the examples specifically avoided that comparison, I suspect that it under performs in comparison. That isn't to say it isn't a useful advancement, but that a more robust analysis is needed to validate their claims.
For microbenchmarks, I try to remove any overheads during runtime by precomputing. That means fully populating the map (only hits) and generating the distribution of keys. Then the threads start at a random index and increment for the key on each operation. This is a good example in Java, https://github.com/ben-manes/caffeine/blob/master/caffeine/s...
I would expect ~15-30ns per integer key lookup on a decent hashtable, w/o concurrency, at a modest size (few collisions). Using a concurrent map that supports lock-free reads doesn't have to be significantly different. Since hashtable design make such a big difference, it sounds like you've narrowed it down to that as a reasonable bottleneck. Thanks for investigating.
https://tessil.github.io/2016/08/29/benchmark-hopscotch-map....
Java and C++ concurrent maps scale reads quite well, both in practice and in research. I was comparing only in-memory read-only map lookups, not those that persist like FASTER and MassTree. I should note though that decade or older hardware will have lower multi-threaded throughput by using many slow cores (Azul, Sparc), so those raw numbers are not comparable to today's x86 machines.
In my experience when adding atomic writes to mostly uncontended fields during this lookup, the performance degrades to 33% of the raw map. Therefore 25M/s did not make sense and I believe there is a limiting factor that could be removed to increase throughput.
[1] https://preshing.com/20160201/new-concurrent-hash-maps-for-c...
[2] http://people.csail.mit.edu/shanir/publications/LazySkipList...
[3] https://arxiv.org/pdf/1809.04339.pdf
[4] https://dl.acm.org/citation.cfm?id=3210408&dl=ACM&coll=DL
[5] https://www.usenix.org/legacy/event/atc11/tech/final_files/T...
[6] https://web.stanford.edu/class/ee380/Abstracts/070221_LockFr...
Both Zipf (skewed) and Uniform distributions have the same read throughput. That would not occur because of hardware caches and memory effects. A Zipf means that some entries are read much, much more often (80/20 rule, hot/cold cache entries). The hardware caches should benefit from this and that is how you get superlinear effects.
A uniform is the same as a random access, e.g. all eviction policies would degrade to random replacement as there is no recency/frequency/locality benefits. This means if the dataset cannot reside entirely within the CPU cache then we should see a different throughput. Yet, they are the same.
His benchmarks only have 10k elements so maybe it all fits in the cpu cache. If that's true then 25M/s is absolutely awful. Something is wrong.
His read throughput is linear to the number of cores, which means that it must have been run with the same number of cores to threads. Otherwise context switching and sharing of cores would have resulted in sublinear growth (you can get superlinear growth, but it won't look like that). Assuming his numbers are not fake, his github charts indicate a 32+ core machine.
My 2015 benchmarks were on a Azure G4, Xeon E5-2698B v3 @ 2.00GHz (16 core, hyperthreading disabled), 224 GB, Ubuntu 15.04. They show a slight superlinear growth for reads (Caffeine). https://github.com/ben-manes/caffeine/wiki/Benchmarks#server...
Both benchmarks use a Zipf distribution. I believe he said it only supports single-writer semantics, whereas mine is roughly per-entry (per hashbin). So reads should be safe to compare, and we can ignore his slow write rate. His should be faster as I do more work to maintain complex eviction policies, whereas his can reading a pseudo-immutable map with no eviction.
Since he does not perform any cache operations, as it is a concurrent map, we should be comparing against another unbounded concurrent map. That is over 1 billion reads per second on the above hardware. That is why I think something is miserably wrong or I'm misunderstanding something fundamental. Achieve 25M/s is a very disappointing result.