Lockless Algorithms for Mere Mortals
lwn.net
lwn.net
The Go approach of “Do not communicate by sharing memory” holds well, because CPU and memory do not always compose as one would expect (As the author of the post notes). Passing messages simplifies a lot of things because you learn to now rely on a specific thread or order, or program defensively against that possibility.
Here's the acid test: Imagine if you got given a two-socket AMD EPYC server with 128 cores to run your software on. No virtualisation, local NVMe SSD for storage, 400 Gbps Ethernet for networking. No hardware bottlenecks of any type! Could your software utilise all 256 hardware threads of this computer? If not, why not?
Maybe you got lucky and you really haven't had issues with locks, but certainly other developers have.
The most common issue I see is with implicit locks in things like logging frameworks. E.g.: Sending output to a text file can be a bottleneck for larger servers like in the example above. Similarly, console output in multi-threaded software also requires locks, and also often has contention issues.
Even innocent-looking code that simply uses dynamic memory allocation ("new", "malloc", etc...) can be bottlenecked by cross-thread contention on the heap data structures and the associated locks. Some modern allocators have thread-local pools, but this doesn't always work. E.g.: often large allocations go to a shared pool. Code that over-allocates large buffers and rapidly frees them can hit this issue all too easily.
Web application servers will often hit the wall on something like a shared cache or the session-state store. Unless 100% of the shared data uses efficient lock-free algorithms, then given enough threads eventually some mutex somewhere will be the limit.
There was a study done recently that showed that no modern database engine can scale past 64 cores properly, let alone 128. Not Oracle, not SAP, not SQL Server.
At the rate TSMC is advancing with chip technology, they'll hit 300 million transistors per square millimeter in just a couple years. I fully expect AMD to release 128-core CPUs once they're on that process. A quad-socket server with those will have 512 cores or 1,024 threads. Completely lock-free algorithms will be the only way to scale up to just one server at that scale!
PS: I remember reading the content on http://www.1024cores.net/ a few years back and thinking to myself that this guy has the right idea, but he's thinking too far ahead. Now... not so much. Now I think the author of that site is a visionary that more people should have paid attention to.
> Web application servers will often hit the wall on something like a shared cache or the session-state store. Unless 100% of the shared data uses efficient lock-free algorithms, then given enough threads eventually some mutex somewhere will be the limit.
Without strong LL/SC (which exists nowhere for useful block sizes), it's difficult if not impossible to implement complex data structures, particularly compound data structures (lockless doesn't compose well), that can't block somewhere. Many sophisticated lock-free and even nominally wait-free data structures implicitly rely on dynamic memory and complex garbage collection strategies, which just hides the ball.
If you have shared resource contention, usually something is going to block somewhere. And the more you scale up, the more your optimization hacks to minimize real-world blocking breakdown, thus the long history of multithreaded software hitting limits at 2, 4, 8, 16, 32, 64, 128, etc CPUs.
The way around these is to architect your application at a higher-level to avoid or mitigate resource contention. And how you do that is extremely context dependent, though "share memory by communicating" is a rule of thumb intended to steer you in a less failure-prone direction, keeping your options open. If you go in planning to just add lockless implementations of basic data structures everywhere, you're going to fail hard. Often because the hit to pipelining, etc, for using atomic operations in your critical path impose huge costs upfront.
Are you familiar with any resources on this?I've noticed this when interviewing candidates and asking follow-ups related to how to make an LRU cache thread-safe. Many, many candidates usually reach for converting their HashMap into a ConcurrentHashMap, which effectively buys them nothing due to the point you raised.
Seems like a missing abstraction that makes it hard to compose these structures, and therefore construct complex structures. Another thing to the research list, irrespective. Or maybe it is naturally the case that the implementations of composition for lockless doesn't scale well?
I still need to read GP's article from 1024cores which seems to potential get into this as well.
This is one of the few areas where a subscription to the ACM Digital Archive is priceless. It's been several years since I went down the rabbit hole, and many new data structures have since been published. If there's a decent self-contained solution, there's a good chance it's been published there. Any particular paper is likely floating around on the Internet, but efficiently sifting through the literature benefits from friction-free access to all the citations.
Would transactional memory make lock-free algorithms compose better, or just race/conflict more?
I think this is the "right" level of locking for "mortals", though complex transactions can quickly become hard to understand as well.
Irrespective, thank you for the link and comment, I haven't interfaced with many of the scenarios you shared!
How often will we need that scale in a single address space?
It's certainly desirable for hypervisors/kernels, database servers, perhaps L4 load balancers and reverse HTTP proxies. Those aren't nothing but far more people work on web application servers than all of them put together.
Web application servers are often written to be stateless (with the possible exception of caches) so they can scale to multiple machines. That's important for high-reliability sites even if they aren't large enough to fully saturate a single huge machine like that. As long as you need to load-balance between machines, it's not a big problem to also run multiple instances per machine. If the application scales well to 32 cores, run 16 of them per 512-core machine. Seems a lot easier than going to extraordinary efforts to make one address space scale...
For example, a pair of threads (inside one of those 1024 processes) synchronising with each other will often go through the kernel to do so. In Linux this uses the futex syscall; Windows etc have similar. If to do that the kernel takes a lock that is shared with other processes, even if just for a moment, even if it's hashed on address and memory space, even if it's a spinlock and there's little contention, that lock causes memory traffic between multiple cores and separate processes.
Same for processes that are reading the same files as other processes, or (for example) running in the same directory when doing path lookups. There's a lot of work done in Linux to keep this scalable (RCU), but it's easy to hit scaling barriers that nobody has tested or designed for yet. Once 1024 core CPUs are common, of course the kernel will be optimised for that.
That said, in some cases I don't think it's strictly necessary for even the kernel to scale well as long as you have a hypervisor that does. It's not unusual to deploy software in VMs on a cluster. Having more, smaller VMs per machine is a way to handle poor kernel scalability, just as I suggested for the web application server. VMs are higher-overhead than multiple containers on a single kernel, so this wouldn't be my first choice, but many people use VMs anyway.
It's definitely niche, but when you need them, you really need them.
Calling it an approach is hardly true given Go programs are generally full of shared mutable memory, even more so when performance are of any concern because channels are rather slow (multiple locks are involved) but not only: any time you're sending a pointer through a channel (including sending pointer-like structures e.g. a map), you're sharing memory.
I wonder, if language is the primary barrier here, if this is a way to integrate another language for specific small pieces like this.
For example, the Pony language is written in C and guarantees no races or deadlocks without using locks or mutexes so it's faster than C with locking. The user defines intentions, similar to Rust's borrow checking, and strict compile time analysis makes it happen for you.
This claim is misleading. The reason why Pony is able to "guarantee" no races or deadlocks is because it doesn't support shared memory concurrency. If you are willing to give up shared memory concurrency in C you can achieve exactly the same performance.
In fact, you often have the opposite: shared memory concurrency (implemented in languages like C) can often offer performance advantages that actor models like Pony can't provide.
Doing this with an actor model would be tricky to the point of impossible. Sending a message to the common "dictionary" actor is much, much, much less efficient than just holding the corresponding sharded lock.
For example, in a network stack, I may want fairness. In that case, all of my packets should get through with equal probability so I want my threads to all make progress even if I lose some maximum bandwidth.
However, in an audio stack, my thread feeding the audio hardware had better NEVER block. I don't care how long the threads feeding into it have to wait, but the thread feeding the audio hardware gets priority under ALL conditions and I never want it to have to wait more than a single instruction.
Those are VERY different locking scenarios, and you can't automatically differentiate.