This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
- # aleph (1)
- # beginners (152)
- # cider (26)
- # clara (2)
- # cljs-dev (13)
- # cljsrn (5)
- # clojure (198)
- # clojure-greece (15)
- # clojure-italy (39)
- # clojure-sanfrancisco (3)
- # clojure-spec (28)
- # clojure-uk (16)
- # clojurescript (52)
- # community-development (15)
- # core-async (26)
- # cursive (42)
- # data-science (28)
- # datomic (19)
- # devops (7)
- # duct (11)
- # emacs (24)
- # fulcro (22)
- # garden (4)
- # leiningen (12)
- # luminus (1)
- # mount (5)
- # off-topic (106)
- # om (5)
- # onyx (10)
- # parinfer (37)
- # re-frame (17)
- # reagent (47)
- # shadow-cljs (36)
- # yada (2)
When Rich Hickey uses "CAS" in his talks, I am assuming that means "Compare And Swap", but not necessarily just the processor instruction version of that idea?
And if that is correct, what is the more general form of it that is not a processor instruction? The moral equivalent in any concurrent system you are talking about?
Here is link to several uses of CAS in his talks across the years, from matthiasn's Github repo of talk transcripts: https://github.com/matthiasn/talk-transcripts/search?utf8=%E2%9C%93&q=CAS&type=
In particular the reference to "CAS timelines" in the "Are We There Yet" talk is not familiar to me. That might mean "a causal timeline constructed between threads based upon an order that they succeeded updating a compare-and-swap word of state"?
@andy.fingerhut: I do not know for certain what Rich is saying by STM vs CAS, but I can give a plausible theory. Do you want to hear it?
STM incorporates multiple values changing atomically, whereas CAS involves single values, if I'm not mistaken. Basically refs vs. atoms?
Do you have a pointer to some place where he is saying "STM vs CAS", or a few sentences in one of his talk transcripts that you are describing that way?
Say we have some map M, thread 1: read (:a M) read (:b M) do some computation write to (:c M) thread 2: write (:a M) write (:b M) //in the STM model, both of these are executing optimistically, but there is a potential "oh shit", if it happens taht: thread 2 writes :a thread 1 rreads :a thread 1 reads : b thread 2 writes : b thread 1 writes : c so the STM somehow needs to detect thes interleaved read/writes, and rolls stuff back in the CAS model, we have: thread 1: I read M_bar, I now want to write it with M_bar' thread 2: I read M_foo, I want to write M_foo' so basically both threads are saying: "if current state of M is the state I read it as, then use this new value for M" ^-- this is all theory / my understanding / no idea if this s what Rich meant in the talk
with regards to your other uestion, here we are "CAS" on a entire MAP, not just a single value
So I understand that CAS the instruction can be used to implement a pointer-flip atomically, so "if this pointer to a map is the one I have been calculating an updated version of, then here is the pointer to the new version to replace it with, otherwise return failure, and I will start all over again with the current latest map".
With which you can do atomic updates of arbitrarily complex data structures, but only single ones.
The 'start over and retry' is what makes it a CAS as opposed to what is traditionally called just 'atomic swap'
STM is coordinated updates across an arbitrary subset of your refs, which I haven't dug into all the details of, other than if I wanted to do that, I would want to do nothing else brain intensive while studying it for a month.
You do some work, tracking all the refs you need to read/write from, when you're done you lock all the refs and and make the changes. If the contents of the refs have changed between the reading and the final lock, roll everything back
There's a lot more in the implementation though since you have to lock the refs in the right order (to avoid deadlock), and Clojure STM has the ability to barge a lock. One thread can say "you're taking too long, stop it!" and take control of the refs from another thread.
So in his "Language of the System" talk, he says this: "There's nothing about what I just said that is about Clojure, that is about memory, that is about locking. There is a little bit that's probably about CAS, but not CAS on the chip. It's a very, very general notion, and Datomic implements that notion at large, but you can also implement it yourself. And you're going to need to combine a couple things. You're going to need to combine naming values with some sort of reference and some sort of a la carte coordination."
I am curious what the "very general notion" of CAS is meant here -- is it basically "any way of doing the equivalent of a Clojure atom swap! operation", whether it involves a compare-and-swap instruction in a chip, or some other method?
Right, so in the case of Datomic it's all a bit different. Values + single writer + some queue = Datomic's model
So in the case of Datomic on Cassandra, most of the data storage used is immutable but it uses Cassandra's conditional put to store the roots of the DB tree.
That doesn't require lockcmpxcg (x86 CAS or whatever it's called), Cassandra just has a way of doing an atomic conditional put on a CRDT store
I mean, I can implement a little web service that has no parallelism at all within its implementation, and it implements a 'compare and swap' service that many clients could use, and it wouldn't need a CAS instruction on a chip, but it would implement that feature for its clients.
And if your clients used an immutable store, they could store the GUID for the root node in your service
In his "Are We There Yet" talk, he uses the term "CAS timeline", e.g. here: "You can use CAS, which is essentially saying there’s one timeline per identity. Right? And it’s uncoordinated. It’s impossible to coordinate two things that are using CAS timelines, but CAS timelines are still useful."
My guess is that means something like "the causal sequential ordering you can see, after an execution occurs, that is the order that multiple threads CAS operations (or something like it, e.g. atom swap! operations) successfully complete.
I took it to mean that you can't do two
swap! calls and guarantee consistency between two atoms.
That makes sense, but it is the "CAS timeline" part that I haven't seen described elsewhere, and was trying to clarify what he means by that term.
so I'd assume it's what you say, the succession of values seen by a location being updated via cas.
But I guess that makes sense, CAS has a form of time. Update 1, Update 2, Update 3. That timeline is unique to that "cell" of memory.
On the STM note, Intel Processors used to have HTM, that worked a lot like Clojure's STM. And it'd roll back any changes if someone touched the data you were working on. Sadly it had so many bugs it was disabled for future work. AFAIK it's still disabled.
him, maybe they fixed it: https://en.wikipedia.org/wiki/Transactional_Synchronization_Extensions
That definitely sounds like the kind of thing that is a few steps beyond what I would recommend putting in specialized hardware.
I'm recalling a paper that basically described that synchronizing multiple individual values, each on their own timeline, was irreducible; I think that was back when reading up on vector clocks?
Programming Erlang: Software for a concurrent world Is on the clojure reading list. Does reading that book give perspective that's useful for clojure developers?
I understand the erlang VM still has pretty efficient CSP to this day. Anything to gleam there?
Yes, that book I mentioned is written by also reliable/knowledgeable authors, and it's certainly more up to date
Erlang is great at what it does, but most of the criticisms here are well founded: https://clojure.org/about/state#actors
rh said it himself indirectly recently in one of his talks, you prolly wouldn't use clojure to write "phone switches"
even tho it's arguable, the memory model is so different, both have strength/weaknesses
If I'm undestanding correctly, an important disadvantage to consider is that you lose the ability to throw something on a channel and stop caring about what happens to it, which is a form of complexity
@radomski That's true. Also, actors require a message to be sent in order to deref the actor. That's another cause of complexity
But on the other end, your messaging is complected with locality with CSP from what I'm gleaming
As I've heard Rich say several times: "The first thing people do with Erlang is build a distributed queue".
There's a lot of truth in that ^. I've never reached for Erlang simply because stuff like Tibco, Rabbit and Kafka exist.
elixir has a few "behaviors" to fix that, or in erlang you have to use credit flow control and such
Elixir is cool for what it does, back when I did Erlang all we had was the prolog syntax. Now I love me some prolog, but dang Erlang code is ugly.
@radomski that's correct. Pulsar is about the closest Iv'e seen. Although I think Akka works just fine with Clojure as well.
There's also a lot of confusion about what actors are. Erlang takes a rather loose view of actors
Notice that Erlang does a ton of stuff not mentioned here: https://en.wikipedia.org/wiki/Actor_model#Fundamental_concepts
I am understanding in terms of channels. Sort of a two way chennel with required locking
@mpenet correct, that's a big reason why Erlang is better at these sort of things.
@radomski eh...CSP channels are a many-to-many queue with an optional buffer. Each message is delivered exactly once. If the channel doesn't have a buffer the channel works as a handoff between two threads.
Guaranteed delivery as well, so if you don't have a buffer, and a put succeeds, you know another thread has the message.
An actor is a computational entity that, in response to a message it receives, can concurrently: send a finite number of messages to other actors; create a finite number of new actors; designate the behavior to be used for the next message it receives. There is no assumed sequence to the above actions and they could be carried out in parallel.
@radomski they need a name, to send to, in many situations this is nothing more than a id
Excellent discussion here, by one of the inventors of Actors systems, and the inventors of a few other languages: https://channel9.msdn.com/Shows/Going+Deep/Hewitt-Meijer-and-Szyperski-The-Actor-Model-everything-you-wanted-to-know-but-were-afraid-to-ask
When I send a message, I will always expect one back or there will be a failure?
The low level send primitive has no hard guarantees. You have to build ACK in your protocols. OTP gives you some of those though.
The thing is, you don’t know if the process you’re sending the message to is local or remote or across the network. Hence the uniformity of no guarantees.
In practice, most people model with “generic servers” which OTP provide which have to acknowledge messages within a time out (default is 5s).
Of course, this means that calling code effectively blocks waiting for the response to come back. This works well if you had to block anyway, e.g. reading from a database in order to proceed.
The way failures work is by declaring dependency trees between processes. If a process that you depend on dies (or becomes inaccessible), you get notified and most often propagate the crash upwards until someone restarts the whole tree.
Fault tolerance + decomplecting with locality seems like 2 big pluses. I think I'm starting to understand why the model doesn't have core support though
https://github.com/onyx-platform/onyx and then I see this and want to play around with it