Is there a problem using A LOT of locks in a process?

Question

I'm trying to build a C# application that sends notifications from the server to its users (a mobile app). Since each user can have its notifications collection changed by any thread, I have to lock those collections whenever somebody tries to read/add/delete a notification.

The problem I think that I might face if there are a lot of users (hopefully millions ;)) logged in at the same time is that I'll have to keep a separate lock for each collection, but a process can hold only a limited number of handles and I'll need more locks than I'm allowed to have.

Is this a real problem or am I worried for nothing? Is there a better solution for this?

Answer 1

Using many locks may cause some problems:

• The number locks a process may request is often limited by the OS.
  Your system may, indeed, run out of locks.
  Note: this depends on the kind of lock. The number of interprocess locks such as Mutex and all other synchronisation primitives derived from WaitHandle is limited by the OS. The Compare-And-Swap cache line locking operations (in .net provided via the class Interlocked) are CPU instructions and can be used without limitations. Critical sections (provided by keyword lock in c# and the Monitor class in .net) are probably only limited by available memory, as may be ReaderWriterLockSlim and SemaphoreSlim (as added via comment by Greeble31).
• Requesting access to a lock costs time; and, requesting access to a lock, used by another thread, causes the OS to block the thread and switch to another one, which also costs time.
  With too many locks and threads your process might end up spending most of its time doing the bookkeeping for the locking, instead of doing computations that your users desire.
• If your process is not disciplined about what locks it tries to acquire and in what order you may end up with deadlocks.

Alternatives:

• Use an event sourcing architecture (possibly with read-only data projection (see CQRS)).
  An event broker (either custom or of the shelf) can handle the locking.
• Use lock-free algorithms and data structures, combined with lightweight compare-and-swap cache line locking instructions.
  Do most of the work outside the lock and swap pointers to new list heads/tree nodes. See for example Ctries by Aleksander Prokopec.
• Use the (row based?) locking facilities of the database to protect notification from concurrent updates (including the read/unread status of the notification) (as added via comment by Bart van Ingen Schenau).
  Each notification can be a row in a database table.

Answer 2

As mentioned in the comments, as you scale you'll run into problems trying to keep state in memory. What happens if your server crashes? Do all your users lose their notifications? As you scale up you would typically introduce a database that persists your notifications. The database handles locking in the simple case that you described, so you don't need to worry about it until you start out-growing your database.

Regarding in-process concurrency, there are some alternatives to locking:

Concurrent data structures

Concurrent data structures help implement the locking for the problem you described. You can keep your notifications in a concurrent collection and access them from different threads without deadlocking yourself. It's preferred to use these where possible instead of implementing the locking yourself, because you're much more likely to implement it incorrectly or sub-optimally.

Actor model

Your system is modeled as a set of actors that communicate via messages. There are guarantees about message order and message processing that dramatically improve the reasonability of a concurrent system vs locking. Messages are processed sequentially, so it may offer worse throughput, but when done properly you won't deadlock, and it's less likely that you'll access your state unsafely (since state is private to the actor).

Optimistic concurrency

With optimistic concurrency you don't hold a lock for a long period of time. Instead your client keeps track of the version of the state from the last time that it read the state. Then when it attempts to set the state, you verify that the versions still match. If the versions match, you set the state. If there is a version mismatch it means a different thread has already modified the state. You can then apply a retry policy to re-attempt the modification by fetching the latest state, applying the mutation and attempting to set the state. This is a good approach when you have much fewer writes than reads. This will have better throughput than locking and the actor model when most of your requests are reads.

Answer 3

In short: Yes.

Or rather, no, but your question hints to a fundamental conceptual misdesign, so... yes.

It's actually "no" because lightweight locks which take very few resources, and few handles (or none at all!) can be easily implemented. For an ultra-low congestion situation with short lock durations such as "a dozen threads at most" vs. "a million lockable things", a spinlock is perfectly suitable.
If you are afraid of spinning (shouldn't be in this situation -- spinning is bad if, and only if there is contention), locks which can block and consume a single handle for the entire process can be built around NtWaitForKeyedEvent on Windows, an locks which block and need no handle at all can be built around WaitOnAddress on Windows >= 8, or futex on Linux >= 2.6 systems. That's ultra-lightweight, and you can literally have millions of them (though you probably do not actually want to have that many).

Note that millions of concurrent users is not millions of threads running on the server. Generally, in terms of concurrent users, you might want to think of "10,000 to 50,000" rather than "million" anyway, since the former is pretty unrealistic unless you have a whole farm of servers. Which is... uh... a different beast altogether. Either way, you don't need more than a handful of concurrent threads for these.

Also, millions of users are not millions of singular, distinct, lockable collections (or things, whatever) on the server. Not normally, at least. Normally, there will be something like a database containing them all (not saying you couldn't do it differently, it's just very unusual). _{Nitpick: Yes, row-level locking is a feature that some databases do implement, so yeah, you can have millions of locks either way, without knowing}.

Depending on what the frequencies of reads versus updates are, you may consider techniques such as read-copy-update which avoid locking, too. RCU doesn't need a handle. You do it either via an extra pointer indirection and atomic reads/writes on the pointer, or by doubly incrementing a counter (atomically) and restarting the reader if a mid-way modification was found (i.e. if the counter is odd the second time you look at it). No blocking, no locks, no handles. Depending on the access pattern, this strategy can be big win.

There exist different strategies for handling large number of clients, one would be to have one multiplexer thread for the network stuff (possibly a few). For that, functions like select, poll, GetQueuedCompletionStatus, epoll, and kqueue come to mind, depending on which operating system(s) you target.
Seeing how C# often (but not necessarily) implies Windows, GetQueuedCompletionStatus looks like what you'd want to use (maybe C# even has a higher-level multiplexing functionality built on top of that available too, I wouldn't know, not using C#). For that, usually more than just one thread is used (can do half a dozen without caring much how many exactly, the function blocks/wakes them as needed), but you don't need an awful lot of them. One will probably do just fine, too. With e.g. epoll, using a single multiplexer thread is the normal thing (although you can do something different). Works perfectly well, no performance problems.

Last, a pool of workers (roughly the number of CPU cores) doing, well, whatever heavy lifting must be done in addition, and concurrent queues of some sort to communicate between them and I/O. What you use exactly (locked queue, lockfree/waitfree queue, disruptor, busy spinning or yielding, or even blocking, whatever) depends on the exact situation. Each has different strenghts and weaknesses. Note that locked concurrent structures are not in any way as abysmal as you would think. Except under hefty congestion, they're actually quite good (and dead simple to get right whereas lockfree stuff is nightmarish).

If you happen to use UDP rather than TCP (but be sure you understand the implications, notably you have to do all the reliability stuff yourself), a single dedicated thread can do all the sends in a simple blocking, one-by-one fashion. That is the simplest way, total no-brainer, 100% portable, and suffices to physically saturate the ethernet cable, and it doesn't cause needless packet loss due to threads pushing stuff to the network stack concurrently.
You also do not strictly need to wait for readiness/completion either if you use UDP. Plain, ordinary blocking reads from one or several workers will do perfectly fine, and you can hardly press more performance out of it either way (except when using special "cheat" functions like recvmmmsg that grab a dozen datagrams in one go).

If no heavy processing is needed, and latency is not paramount (so messages possibly being delayed half a second is no issue) you can probably do a server that handles a few thousand concurrent connections single-threaded, too. The above multiplexing APIs have no real trouble handling that, nor does the network stack.