288 karma · joined May 4, 2011
You can mitigate the exclusive lock using a write-ahead log approach [1] [2]. Then you record events into ring buffers, replay in batches, and have an exclusive tryLock. This works really well in practice and lets you do much more complex policy work without much less worry about concurrency.
[1] http://highscalability.com/blog/2016/1/25/design-of-a-modern...
[2] http://web.cse.ohio-state.edu/hpcs/WWW/HTML/publications/pap...
I write SQL migrations for H2, an in-memory db. This is used by the build tool to code generate prior to compilation. It is also used by unit tests, when the Postgres queries can be emulated (majority of the time). The Postgres migrations are written separately, with similar code but minor dialect differences. That might be less duplicated (but trivial) work if I used LiquiBase instead of Flyway. When the application starts the migrations are run. Someday I might drop H2 for a containerized Postgres, especially if they add in-memory support for faster testing. This would avoid some codegen differences, like jsonb or (soon to be released) enum support.
The work setting things up wasn't too bad. It was more when I originally started, since I had to build part of the ecosystem. But repeating the process elsewhere has been straightforward. It definitely pays off and is a joy to use day to day.
Turn away Jewish refugees from Nazi death camps - win a peace prize. (Cordell Hull)
Repeatedly refuse peace, call for the destruction of Israel and slaughter of all Jews - win a peace prize (Yasser Arafat)
Promote a war that appeared to have served no purpose than cause anguish - win a peace prize (Henry Kissinger)
I think we need two prizes, one for those who contributed and one for those who we hope might learn basic ethics.
I'd like to use Bazel (or even Buck) these days, but no bandwidth given other projects. I always felt modules were a mistake compared to a single large tree, which Bazel does elegantly. Sadly my familiarity with Gradle is much more than Blaze these days, and I'm too exhausted to do it just for fun. I think there is also a bit of Stockholm syndrome at play, since I convinced myself it was not too bad back at Addepar.
- Cache.iterator() may return a null entry, despite null key or value is disallowed. This occurs when the cursor points to an entry that no longer exists - hasNext() was true, but the entry disappeared due to removal/eviction/expiration. This is a performance optimization to avoid underlying I/O that leaks to users and violates their assumptions.
- Cache.putAll(map) first invokes CacheWriter.writeAll(list<entry>) prior to storing them. The writer uses an in/out parameter so that if an exception is thrown, the user must remove the successfully written entries first. Then cache must store those successfully written entries before propagating the exception to the caller.
- An amusing bug was that their custom future could not be consumed by multiple threads. It used notify(), not notifyAll(), so only one waiter would wake up. The concerning part was that this existed for a few years due to lack interest in releasing a new version.
- The API violates many of Josh Bloch's guidances [1], including items in Effective Java.
- Many of its features are incompatible with itself. For example, the AOP support cannot be used with loaders, writers, or listeners.
- The AOP support does not support atomic memoization (dog piling [2]) and can crash if initializing the same cache concurrently.
- The JavaDoc dictates implementation details that matched the lead's product, rather than being open ended to allow alternative algorithmic choices.
- The JSR defines an configuration API that is not suitable for production use and promotes the silent usage of unbounded anonymous caches.
- The interfaces do not attempt to feel natural alongside the Java's Collection Framework nor the direction that the language has been heading. It redefines terms, like "access", in an incompatible way.
- Despite numerous delays in being accepted, the JSR was not modified to take advantage of significant changes in the language (java.time, lambdas, CompletableFuture, etc).
- The TCK is not robust, does not check concurrency, and bugs in it languished.
- Most importantly, writing code using JCache is not enjoyable and it is often not flexible enough to solve most needs.
There are likely many more, but that is a short list that comes to mind in a few minutes.
Counting with TinyTable: Every Bit Counts! http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2...
LIRS and TinyLFU make better use of their history to filter out low value items early. The fundamental difference in their designs is starting point: LIRS starts from LRU and infers recency, whereas TinyLFU starts from frequency and infers recency. There is work on an Adaptive TinyLFU that mimics LRU by using an admission window, sampling the hit rate, and using hill climbing to adjust the region sizes to best fit the workload.
[1] https://github.com/ben-manes/caffeine/wiki/Efficiency#glimps...
https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsU...
https://github.com/ben-manes/caffeine/wiki/Efficiency
The W-TinyLFU variant better handles recency by using an admission window so that new entries are not immediately discard. This resolves antirez's concern and improves performance in sparse burst workloads. In a way its similar to the HIR/LIR regions (window/main) using TinyLFU as a frequency filter.
Happy to work with you, antirez, and others to simulate more policies and add trace files.
http://highscalability.com/blog/2016/1/25/design-of-a-modern...
Most policies try to minimize the impact of low frequency items. For example SLRU uses a small probation space that promotes to a protected region if re-accessed. This allows quickly discarding low frequent items. ARC uses an adaptive version of this idea.
LIRS uses a very small region (HIR) that promotes to a large region (LIR) based in the inter-reference period. This allows it to discard many new arrivals by using a large number of ghosts to retain usage history.
TinyLFU is a probabilistic LFU filter that decides whether to admit by comparing the frequency of the arrival to the victim. This is often near optimal, but can suffer due to sparse bursts causing consecutive misses. An admission window (W-TinyLFU) resolves this problem, usually with a 1% window.
I have a simulator and traces that you could easily add onto to experiment. [1]
I recommend reading the TinyLFU paper as I think it is the best match to your ideas. [2]
[1] https://github.com/ben-manes/caffeine [2] http://arxiv.org/pdf/1512.00727.pdf
How will Arrow use vectorized instructions on the JVM? That seems to be only available to the JIT and JNI, which is a frustrating limitation.