ben-manes
commented
7 years ago This is very nicely thought out. If you don't mind, I have a few minor questions.
1. Will the "operations buffer" be used for read+write or only reads? In Caffeine the read buffer (ring buffers) are lossy, so if they fill to capacity the additions are discarded instead of waiting for a free space. This is okay because cache accesses patterns follow the 80/20 rule, so most accesses are to the same hot entries. Since we're capturing enough information to know which are hot we can prefer to minimize latency instead of being strict in our recording phase.
However writes cannot be lost but are a much rarer event. We use a dedicated buffer for writes instead of blocking on the exclusive lock. For efficiency we're using JCTools' MpscChunkedArrayQueue. When a write is recorded we prioritize draining the buffers as an eviction might be required.
2. Do you plan on revisiting the 2Q policy and considering alternatives? TinyLFU is very simple to implement and provides a superior hit rate.
3. What are the pros/cons of a custom implementation vs. using Caffeine directly? I can imagine some lifecycle differences, a desire to own the code, etc. Hopefully you can take advantage of pulling code out of Caffeine where advantageous.
Let me know if I can be of help.
andrii0lomakin
Reference:
https://github.com/orientechnologies/orientdb-labs/blob/master/OEP_8.md
Summary:
Asynchronous read cache with state machine
Goals:
Non-Goals:
Success metrics:
Motivation:
To implement thread safety guarantees inside of read cache we use implementation of group locks which are close to Google Striped. But this approach has couple of disadvantages:
An alternative approach is proposed to overcome these disadvantages. It is proposed to:
The proposed design is an adoption of the design of Caffeine framework which has excellent scalability characteristics.
Description:
Current workflow of 2Q cache looks like following:
As alternative following design is proposed:
Lock-free operations buffer.
To gather statics, we will use ring buffer which will be implemented using a plain array. But this buffer will be presented as not a single instance of the array but as an array of arrays. Each of the arrays will be used by a subset of threads to minimize contention between threads. If threshold on one of those arrays will be reached, all those arrays will be emptied by one of the threads by applying tryLock operation which prevents contention between threads. Lock mentioned above is used only during buffer flush and is not used during logging of a statistic inside of buffers. Pointers inside of buffer will be implemented without CAS operations, as a result, few of operations will be lost, but it will not cause significant changes in overall statistics. There is limit on amount of records which will be flushed at once per single thread. Eache thread flushes no more than 2 * threshold amount of elements from buffer.
State machine.
To achieve thread safety guarantees a state machine with following states will be introduced:
Eviction process
The removal process is performed during operations buffer flush (when the state of eviction policy is updated). During this process:
About ETA, we have already implemented a similar algorithm (different state machine) in the file auto-close functionality. So ETA for the worst case is 10 days , but probably smaller.
Alternatives:
There is no any other proposal for cache lock models at the moment.
Risks and assumptions:
In the case of incorrect or poorly tested implementation, there is a risk of data corruption.
Impact matrix