SIEVE implementation that allows concurrent access with no lock contention #4
sakno
started this conversation in
Show and tell
Replies: 1 comment 1 reply
-
Awesome work! The python code is used for illustration, but rather than production-ready code. It is great to see other engineers like you solving the challenges in making SIEVE concurrent. Do you want to add the repo to the website? |
Beta Was this translation helpful? Give feedback.
1 reply
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
-
Hi @1a1a11a,
First of all, I would like to thank you for SIEVE algorithm. I found its description in this blog post. At first look, it's really simple and understandable. However, the devil is in the details. Naive implementation provided there in Python cannot be used in situation where multiple threads or co-routines trying to access the cache concurrently.
For instance, cache hit code
introduces race condition with the hand cursor adjustment:
Read of
visited
flag and then setting it toFalse
is not atomic operation. For the real world application (especially when translating to Java/C/C++/C#) the flag must be analyzed and updated by using memory barriers and/or Compare-and-Swap operations.But that's not all. The hand moves over the doubly-linked list. AFAIK, there is no lock-free implementation of update/delete operations for the linked list. Thus, concurrent insertions to the cache cannot be done in parallel due to lock contention. Moreover, the thread/co-routine which is trying to read the cached record can have race condition with the eviction triggered by concurrent thread. As a result, the reader can have stale reads or, which is more ugly, obtain the resource which is in the process of cleanup. There are ways to avoid stale reads. For instance, reference counting or epoch-based reclamation can be utilized. However, it requires some modifications of the original algorithm.
I would like to share my approach to deal with all these things:
Every thread that wants to insert a new value communicates with SIEVE algorithm asynchronously. To do that, I've organized lock-free queue. The queue has multiple producers (insertion threads) and a single consumer (a job that maintains SIEVE algorithm).
Full implementation you can find here in C#. Of course, it's much more complex than the original proposal.
Beta Was this translation helpful? Give feedback.
All reactions