Someone mentioned "the saddest moment" in there in response to the back and forth comment:
https://www.usenix.org/system/files/login-logout_1305_micken...
(hope all is well!)
I enjoyed these posts between yourself and Martin. Don’t be too confident though. Data races almost always go unnoticed.
Code: https://github.com/danrl/skinny
Talks: https://youtu.be/nyNCSM4vGF4 and https://youtu.be/gAGGPaFDfwE
I am trying to implement efficient mutual exclusion without blocking and without additional mutexes besides communication mutexes (what I use to provide thread safety) in Java. (I think message passing still needs some form of thread safety to transfer data, such as a mutex or lock free algorithm, since you cannot mutually read and write to the variable without problems.)
If the solution is proven safe in the small, across threads, it should be safe across machines and in distributed systems. I might be wrong on this. But scheduling is a different solution to locks than allowing everything to run at its own behest, without external control. In other words, if we run things and wait for them to finish and never schedule two things to run at the same time that are incompatible (mutual exclusion), we can avoid race conditions where things decide to run at the same time due to two things trying to run simultaneously.
I effectively want epoll for business domain objects and infrastructure state changes. This is the space that Hashicorp consul provides, redis lock and Chubby, the Google lock service.
Imagine being able to register on arbitrary changes to business objects and chaining together complicated behaviours based on efficient epoll-style reactive rules? And have fork/join handled efficiently and mutual exclusion and retries.
I've gathered I can use scheduling, similar to an operating system scheduler to decide when to schedule mutually exclusive operations.
I am inspired by the epoll API, where you register things you're interested in changes and you react to them.
I can protect everything by a single communication lock and then implement scheduling myself. Scheduling shall detect when a task is finished all its dependencies and then schedule the next thing to be executed.
Any thoughts or ideas on distributed and multithreaded scheduling would be greatly appreciated.
This is useful because cloud storage is very cheap and serverless. It certainly beats running a Redis or PostgreSQL instance.
In my research and implementation I took care of the problems described in this article (as well as the problems I encountered in other distributed lock implementations).
Clients either freezing or outright crashing or disappearing is definitely a major problem. So timeouts are a must. But you can't just have a timeout because you don't know whether a client is arbitrarily delayed or whether it has disappeared. Furthermore, some workloads have an unknown completion time so you can't pick any sensible timeout.
I address this by encouraging clients to behave as follows:
1. Make the timeout relatively short, but regularly refresh your lease to let others know that you're still alive.
2. Your lease may at any time be taken over by another client that thinks you've disappeared. So you must regularly check whether your lease on the lock is still valid. This checking must be done way, way before your timeout expires, in order to account for the possibility that you can be arbitarily delayed at any moment (GC pauses, scheduling pauses, network delays, etc). I recommend checking in an interval at most 1/8 of the timeout. Smaller intervals are better at the expense of more overhead.
3. Attempt to split up your work into a long-running, discardable preparation phase and a short-running commit phase. Verify the validity of your lock lease right before committing (in addition to periodic verification).
This is of course still not 100% foolproof. There is still risk that two clients run at the same time, but this risk can be arbitrarily reduced by reducing the verification interval and by optimizing for doctrine 3. If your workload cannot tolerate any risk of two clients running at the same time, no matter how small the risk, then pick an infinitely timeout. But I think for most workloads, the benefits of not having to administer the lock (not having to manually break its lease because a client has crashed) outweight the risk.
My algorithm has a Ruby implementation, as well as a third-party Go implementation.
Ruby: https://github.com/FooBarWidget/distributed-lock-google-clou...
Go: https://github.com/FooBarWidget/distributed-lock-google-clou...
Let me add my own perspective: Distributed locks are a fallacy. They can be beneficial in decreasing contention, under the assumption that "most of the time, only one actor will be active". However, by themselves, they offer no solid guarantees. The blog post addresses this point by introducing the concept of fencing tokens. These tokens have the potential to provide concrete guarantees, but they require the cooperation of downstream systems for enforcement, which isn't always possible.
I was really surprised to see Antirez argue for the probability approach.
