You use a lock-free structure for the log.
I never liked that term.
Lock-free algorithms will usually boil down to some combination of polling, waiting (sleep(), futex-style), or use what are essentially more fine-grained, hardware-backed locks (CAS, memory barriers, LOCK instructions, hardware-specific transactional instructions, etc). The locks are very much still there.
With a lock, you acquire the lock, you perform your operation, and then you release the lock.
Lock-free is typically done differently. You don’t acquire a lock, you start performing the operation “optimistically”, and you commit the result if no other thread has stomped on your data. If another thread has stomped on your data, you start over.
One of the important differences here is that it’s a race. Whoever commits first, wins. With a lock, you have to wait for whatever thread acquired the lock first. That thread may not even be running.
So, lock-free is fundamentally different because with a lock-free system, a thread that is running will always complete work (you just don’t know which thread). In a system with locks, threads that are running may be prevented from making progress by threads that are not running.
Systems with locks can also deadlock, lock-free systems cannot deadlock. Usually, there is some sort of guarantee that lock-free systems always make progress.
> "you commit the result if no other thread has stomped on your data"
What does "committing" mean here? If it means performing an atomic write (a-la CAS), then you're using a lock (see my next point).
> "If another thread has stomped on your data, you start over."
So you let your thread sit there in a spin-loop and CAS a condition-variable. That's a lock for all intents and purposes, and your system can still "dead-lock" (read: your thread will never get to "win the race"), if your "data gets stomped on" over and over again in-between reads (which are obviously non-atomic, otherwise you'd be locking there too).
> "Usually, there is some sort of guarantee that lock-free systems always make progress."
Getting a time-slice to continue running in a tight-loop while trying to CAS is not the same as "making progress".
"Making progress" would be - you'd get a chance to commit your changes and proceed to your next bit of business logic. But with contention, that's not guaranteed to happen at-all?
- Lock-free: at least one thread will make progress
- Wait-free: all threads will make progress
The difference between locks and lock-free is very noticeable if a thread holding a lock is suspended (which can happen on a modern system just by accessing memory that is paged out). On real-time systems it’s also possible to guarantee that high-priority tasks will make progress, regardless of how a low-priority task behaves. With locks, a low-priority task can easily prevent a high-priority task from running at all.
It can live-lock.
I think you’re possibly confusing lock-free and wait-free, which is a stronger guarantee.
Practically speaking - wouldn't the exact duration be heavily influenced by the countless layers of abstraction beneath the application itself (kernel, scheduler, hardware, speculative execution, etc)? If so, can we ever truly make the claim that the "duration is strictly bounded"?
You can still use standard kernel-provided synchronization objects (mutex/events/semaphores) in your "lock-free applications", as long as you provide timeouts to blocking wait() calls, and handle abandoned objects gracefully.
For instance, if all threads except one are stopped, the single running thread should “finish” (for whatever finish means) in a finite time (lock-free is stronger than this condition, too). An algorithm using mutex-style locks fails this guarantee, if one of the stopped threads is inside the critical section.
But, a lot of people have gone through the effort to leave explanations in this case. Isn't that good enough?
For one unaddressed example:
> You can still use standard kernel-provided synchronization objects (mutex/events/semaphores) in your "lock-free applications", as long as you provide timeouts to blocking wait() calls, and handle abandoned objects gracefully.
This might be technically true, but atomics provide significant performance benefits compared to using a mutex with a timeout, and I don't think of "lock free" as relying on busy loops as you seem to think in your comments. I'm sure a busy loop makes sense in very specific algorithms, and mutexes themselves often use a limited amount of busy waiting to avoid context switches. You can simulate atomics with mutexes, but that's not the point. Lock free is hard to do correctly. Mutexes create the possibility of a deadlock, which is incompatible with being lock-free, so you have to avoid all the footguns of lock-free and the footgun of using mutexes.
So, yes, you can use standard sync objects... but that doesn't make anything better in this case. It misses the point. "Technically correct" isn't always good enough to get an upvote.
If you don't agree, that's fine... but this is completely uncalled for and against the community guidelines:
> This community has truly deteriorated over the years.
No one is obligated to upvote things they consider incorrect, and downvotes are perfectly suitable for this purpose under HN guidelines.
If you don't see how it contributes to the conversation - why not just ignore it then? Just because you think this doesn't contribute to the conversation, doesn't make it true.
> "If you don't agree, that's fine..."
Clearly it's not "fine", otherwise you wouldn't try to silence comments you disagree with by down-voting them.
This is my last comment on HN.
Because it's misleading and/or missing the point. As stated. Why would I want more people to read something that I believe is misleading?
> Clearly it's not "fine"
Once again missing the point. The prevailing opinion on HN is what will get upvoted, and a lot of other stuff will get downvoted. I have seen that prevailing opinion be hilariously wrong before.
If you want to be heard with an unpopular opinion, you have to make a compelling argument... you can't expect to be upvoted to the top just because you're sharing an opinion. It's rare for a comment to be lukewarm enough for no one to feel strongly enough to downvote it. It's going up, going down, or it's on a thread no one is reading. Downvotes don't mean people hate the person leaving the downvoted comments; it's just a tool for disagreeing with comments.
> This is my last comment on HN.
Because people disagreed with you? People even left explanations, but that wasn't enough.