More tricks up in the ArcSwap’s sleeve
This is a continuation of the Making Arc more atomic post. In short,
ArcSwap is a place where you can atomically store and load an
RwLock<Arc<T>> but without the locking. It’s a good tool if you have some
data that is very frequently read but infrequently modified, like configuration
or an in-memory database that answers millions of queries per second, but is
replaced only every 5 minutes. The canonical example for this is routing tables
‒ you want to read them with every passing packet, but you change them only when
I’ve been asked a few times how it works inside and I don’t want to repeat myself too much, so here we go. This is the high level overview of what happens under the hood, you’ll have to read the code for the fine details, proofs of correctness, etc.
I’ll be talking mostly about
Arc, but the thing is generic and can be made
to work with other things ‒ notably,
Option<Arc<T>> is supported by the
library, and if you have your own version of
Arc, you can implement a trait
on it and there you go too.
The devil is in the details
In the heart of the thing there lies an
Arc can be turned
into a raw pointer and created from one, it can be stored in there. That
conversion keeps the reference counts. The
swap method is therefore easy ‒
one pointer with its reference goes in, another gets out. Just make sure the
atomic orderings are correct.
store is just a swap that throws the result
out. That’s easy.
What does some kind of
load look like? It needs to read the pointer, and
because it returns one
Arc, while keeping another „virtual“
the storage, it needs to increment the reference count. But here lies the
problem, as by the time we get to incrementing it, some other thread might have
swapped the pointer out of the storage, dropped its copy, reached zero refcount
and deleted the data, including the reference count itself. Ouch. Not good. We
can’t increment non-existing reference count.
So, the original solution was a kind of uni-directional short-term lock which
prevented the writer (the one doing
swap) from completing before we
increment the refcount. Read the original article about the details, it is all
about that lock.
Properties of the lock
The original one (now called generation lock) had some good properties.
Specifically, the read operation was wait-free, which is great. Literally, a
reader stopped for nobody, performed its fixed sequence of operations and
continued with a copy of the
Arc in its hand.
There were just three downsides:
- While the lock is able to deal with constant stream of readers and a writer will finish even in face of that, if a reader gets stuck in the critical section, all writers wait forever.
- Even though the read operation is wait-free, all readers write into the same cache line ‒ specifically, the lock and the reference count. So if there are many concurrent reads, they get slowed down because CPUs fight over which one of them would be writing into the cache line, making it quite slow (well, here we are talking on scales where going to fetch data from RAM is considered eternity).
- The storage for that pointer was bigger than the size of a pointer, inflating any data structures built of these.
Sharding the lock
For this library, read performance is much more important than write performance. Therefore, the first changes I’ve made were to use multiple instances of the lock. Each reader would pick just one of them and lock it, while a writer would have to wait for a permission from all of them. By making sure the locks align to a multiple of cache lines size, the chance of two reader threads colliding on the same cache line is lowered (while making it slower for writers).
However, this doesn’t solve the contention on the reference count. If the only thing I want to do is to read one integer from configuration behind that pointer, incrementing and immediately afterwards decrementing the shared reference count is a big deal.
So I’ve made another method, the
peek, available. Instead of locking,
incrementing the reference count and unlocking, it returns the lock guard with
access to the data. The caller reads that
i64 from there and unlocks, never
getting the actual
Arc created (but keeping the data alive for the whole
time) ‒ and never touching the reference count.
This solves the problem for very short reads, but runs the risk of making the
writer wait in a busy loop for longer if my
peek into the data is not so
short. I could still take the
load, which creates the
Arc with its
reference, but that feels wrong.
Making the lock configurable
By default the storage uses a global set of locks. The idea is, if a thread is
busy locking one
ArcSwap, it won’t be trying to lock a different one at the
same time. That way,
ArcSwap itself has the same size as a pointer, but runs
the risk of blocking writers on unrelated instances of
It is possible to fine-tune the behaviour by a type parameter. The library contains implementation of private locks for each separate instance. This is even used inside the signal-hook crate. There, this lock is the only allowed possibility due to restrictions what can be done inside a signal handler. However, the signal handler may run for a longish time and it would not do to block unrelated processing. With a private lock instance, only adding or removing signal handlers is affected (which usually happens just on application startup).
What about hazard pointers
As you can see, the lock approach isn’t perfect.
I’m certainly not the only person to take an interest in a similar problem. I’ve
came across something called hazard pointers and one specific implementation,
AtomicArc was certainly a very interesting read. Unfortunately, as far
as I know, it’s not yet finished and released.
On a very very high level, we have a global „don’t you dare to free this, I’m using it right now“ registry. If I want to start doing something with a pointer, I read it, write it down into the registry and check by reading it once more (to avoid races). Only after this I can actually access the memory. When done, I remove it from the registry.
If I want to free a pointer, I first remove it from the storage (so nobody else can read it any more), then walk the whole registry. If I don’t see the pointer mentioned there, fine, I can safely free it. If it is there, I mark it in the registry with a note „you’re now responsible for freeing it“, passing the problem onto some other unfortunate thread. That thread in turn will try to free it (with the same check through the whole registry) when removing its entry from the registry.
This is all very nice and shiny, but I didn’t like two details about it:
- Searching for a free spot in the registry can take a long time. Additionally, a reader thread may become responsible for freeing the pointer, forcing it to walk the registry. I want my readers to be fast (and wait-free, not just lock-free). Like, always, not just most of the times. Not for some actual reason, it is simply a matter of personal pride.
- While the idea is relatively simple, code that handles all the corner cases in the registry in face of concurrent lock-free access (it wouldn’t make much sense if we put locks into the registry, would it) turns out quite tangled. Combined with the general inability to write unit tests for these corner cases (they happen as a result of thread scheduling, which CPU is faster, etc), this feels like a dangerous path to take. I do enjoy hard problems and such, but there are certain limits, especially if I want to claim some confidence about correctness of the thing. Furthermore, all the „cleverness“ of the code slows it down visibly in benchmarks.
The hybrid approach
This is the implementation of the third loading method,
lease. This one
should probably be considered the primary one for most use cases.
Eventually I’ve decided to trim the hazard pointers down to a bare minimum. If anything at all doesn’t go according to the best-case scenario, it falls back to a full load instead. That one is still formally wait-free and by making it rare to happen, the problem with contention on the reference count should be effectively gone.
Furthermore, the responsibility for freeing something is not passed through the
registry. A record in the registry means there’s an
Arc somewhere which owes
one reference (that is fine as long as we don’t reach 0). For this reason, it
is no longer called hazard pointers in the code, they are debts. So instead of
passing the responsibility to walk the registry, the writer takes the debts onto
itself (removes it from the registry) and pays them (by incrementing the
number). Actually, it pre-pays one upfront and removes it at the end, to be on
the safe side.
The read operation therefore tries this, in order:
- If this is the first access from the current thread, set up fixed number of slots in the registry. They are going to be for the exclusive use by my thread (well, the code is ready for potential sharing of the slots between threads, but no kind of slot stealing is implemented and probably not worth it). Only this part is just lock-free because the new slots need to be linked into a linked list and there may be retries doing that. Future reads from this thread will be wait-free.
- Read the pointer.
- Search for an empty slot through my fixed number of slots. If not found, fall back to full load. If found, register the debt.
- Re-read the pointer. If it’s the same, we’re done.
- If it is different, try to remove the debt from the registry. If it was
already paid by someone else, we have a full
Arcin our hands, which is great and we are done. If not, fall back to full load.
Just not to confuse people reading through the code, the
Lease guard does
not store the full
Arc as an
Arc, only as the raw pointer and that
Arc is only virtual (eg. there’s the reference count for it).
When dropping the guard, we check if we owe a reference. If we do, we actually have nothing to do (except for removing it from the registry) ‒ we simply make it even by stopping to exist. If we don’t (either because we’ve done a full load or because someone paid our debt), we decrement the reference count.
As long as the current thread doesn’t hold more leases than there are slots,
this is pretty fast ‒ comparable to lock & unlock of uncontended
(Muteces are slow only if locked, because then they have to wait in line, and go
to the OS to put the thread to sleep…), but with the ability for arbitrary
number concurrent readers ‒ no risk of being locked or slowed down.
The repository contains some benchmarks. The ones I consider the most relevant
are doing the measured operation (eg.
peek) while some other threads do
„background noise“ traffic ‒ like writing new values all the time. There are
many combinations of the measured operation and how many threads do the
background traffic and what kind of background traffic. This is done with
several alternatives to compare with [
However, benchmarks are not the real thing, for many reasons. First and foremost, real applications do other stuff than just access one shared piece of data, therefore the differences might be hidden in the costs of whatever else the application does. Apart from that, it turns out CPUs are sensitive to mostly whatever. Like, spinning up a parallel thread that doesn’t access anything near our data nevertheless may slow our core down because of the temperature gets higher or because the power subsystem is not able to feed both. So while interesting, benchmarks are not to be taken too seriously.
Areas of improvement
I’m open to ideas what and how to improve. In particular, I believe there is room for improvement in the writer performance (that one is rather slow) ‒ but I want to do that only if reader performance doesn’t get hurt. This crate is biased towards readers, if you need something „balanced“, there’s a place for some other implementation.
Also, discovering places where the documentation is not perfect (and sending a PR) would be highly appreciated. Or coming up with a nicer API.
If you feel like reading the proofs and the code and double-checking my reasoning is sound and that I didn’t overlook something would also be very valuable.
Implementation for other languages
I’ve already been asked if I would like to port this to another language
(specifically, C++). My answer to that is no, I wouldn’t. This code is
already quite challenging even with all the help and checks I get from the
Rust compiler (which is a lot even if the code is using
And I don’t have the free time for that. Besides, I don’t think C++
can be turned into a single pointer.
However, if you want to go ahead and implement it in some other language, I’ll be more than happy to answer any questions and walk you through the design or just talk about it.