[
https://issues.apache.org/jira/browse/OFBIZ-6747?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16510062#comment-16510062 ]
Ben Manes commented on OFBIZ-6747:
----------------------------------
In regards to fun algorithms, some resources to look into are...
* For general concurrency, the book [The Art of Multiprocessor Programming|
https://www.amazon.com/Art-Multiprocessor-Programming-Revised-Reprint/dp/0123973376] is excellent. It covers lock-free algorithms and is written by researchers who authored many well known papers.
* The concurrency scheme used by my caches is inspired by a database's write-ahead log. The classic approaches are to either thrash on a global lock to perform a tiny amount of work (usually pointer flipping) or avoid "movement" by using a CLOCK-based or random sampling policy. By instead recording into a ring buffer and replaying under a tryLock, the lock contention is replaced by a cheaper buffer CAS. This lets me uses non-threadsafe algorithms that are O(1) and more intelligent. The idea is simple and implementation just takes work to squeeze out performance.
* For eviction, see the ACM paper on our policy. The pre-published is on the earlier link, while the peer reviewed version can be freely downloaded from the link on the README. I wrote an [overview|
http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html] ([slides|
https://docs.google.com/presentation/d/1NlDxyXsUG1qlVHMl4vsUUBQfAJ2c2NsFPNPr2qymIBs/edit#slide=id.p]) for HighScalability. We have a followup paper under review that makes it adaptive. If interested, I can send that over private email due to submission restrictions (my email is on github).
* For expiration, see this excellent article by the Kafka folks on [Hierarchical TimerWheel|
https://www.confluent.io/blog/apache-kafka-purgatory-hierarchical-timing-wheels]. This is an amortized O(1) priority queue that leverages time to use hashing instead of tree-like comparisons. Caffeine is the only cache that I'm aware of to use this, but this data structure is fundamental in kernel subsystems. Its really elegant and fast!
And the rest is all elbow grease! :)
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
Locked
