Sane Concurrency with Go
blog.mozilla.org
blog.mozilla.org
Good concurrent data structures that allow multiple concurrent writers are necessary. Java has some good basic ones like ConcurrentHashMap, ConcurrentSkipListMap, and ConcurrentLinkedQueue. Clojure takes that a step further with transactional refs. For more interesting kinds of data it's better to have a good in-memory transactional database.
So for truly "sane concurrency" you need both lightweight threads with CSP and/or actors, plus a transactional, concurrent (preferably in-memory) data store[2].
[1]: https://github.com/puniverse/quasar
[2]: http://blog.paralleluniverse.co/2013/10/16/spaceships2/
Also, B-trees are a mutable data structure. "Immutable" B-trees aren't B-trees. Clojure's own persistent DS tries are quite efficient, but not nearly as scalable as a concurrent B-Tree, which easily supports lots of concurrent writes. AFAIK, there are no persistent data-structures that efficiently scale writes.
No STM of course, but RWArc allows for multiple writers, or you can just uses Arc if immutable sharing is acceptable, or just message passing via Chan (in the standard library) if sharing data concurrently is not required. Lots of options.
EDIT: Oh, I see what you mean now; sorry, I misinterpreted. Carry on.
RWArc allows multiple writers, but each blocks until the "active" writer gives up its lock. But I suppose you mean that you can't have concurrent writes, so I understand this might not be suitable for the use-cases you were talking about.
[1]: http://www.youtube.com/watch?v=sq0MX3fHkro
EDIT: The Doug Lea talk linked above is probably the best overview of what doing low-level concurrency on modern hardware entails. In particular, it demonstrates interactions among abstractions layers and dispels myths that claim that having less software layers is always better (hardware already has so many layers as it is, that some software layers can actually help, if only to hide the hardware's complexity).
EDIT: Indeed it was a great talk, very informative! I came to the opposite conclusion about layers of the system, though I'd say that it isn't the number of layers that's the problem, but the nature of them.
From the talk, having the GC insert safepoints where threads can be stopped for a collection, and having the JIT inserting counters (resulting in memory contention) are two things in Java that caused for high-performance concurrency. Running on top of a VM causes similar issues. Though, clearly there are many other layers and unanticipated layer interactions, just laying in wait to mess you up regardless.
Those things are necessary for the class of programs Java SE is meant to support (long running, high-performance server-side applications); they're not ideal for device drivers, command line programs or fast-loading GUI apps, which Rust is designed to handle. Everything is a tradeoff.
Of course you could create more advanced concurrent mutable structures as other languages have, but IORefs and STM get you a very long way when coupled with GHC's extremely light weight threading and high performance IO (which is getting even better in GHC 7.8, to be released soon).
To learn more, Simon Marlow's excellent book is available for free online [1] and in dead tree and eBook forms from O'Reilly. It's very clear, with a great balance of how to use things practically, how they work, and how to make them work their best.
[1] http://chimera.labs.oreilly.com/books/1230000000929/index.ht...
Even though the concurrent data-structures in Java's library are efficient and well built, they remain error-prone because thread-safe operations are not composable. Working with immutable data-structures in a high concurrency scenario is the best thing since sliced bread.
I do agree with your point - sane concurrency implies using the right abstractions for the job and there are cases in which you need shared memory storage. The JVM is in fact great because it does 1:1 multithreading, because the GC is so good that it allows you to be a little wasteful and because it provides the required concurrency primitives to build whatever abstraction on top that you desire.
For Scala + the JVM, just to enumerate - you've got actors by means of Akka and it's pretty capable as it's flexible and it allows you to manipulate/coordinate entire clusters of remote actors (and of course there's Quasar that does the lightweight threads thing and I'd love a comparison between the two btw), you've got the Future/Promise concept baked in and with a sane design [2], with C#'s "async" by means of a library that will be part of the standard [3], you've got great immutable data-structures that also have parallel extensions [4], you've got RxJava/RxScala for processing streams of events reactively [5], or Iteratee IO for safe processing of data streams [6], or shared transactional memory that I mentioned above [7] and of course things inherited from Java, like NIO which in spite of its flaws it's the sanest cross-platform abstraction over native APIs for async I/O, plus as I've said, the best cross-platform concurrency primitives you can get (e.g. I still get boners every time I use ReentrantReadWriteLock).
[1] http://akka.io/
[2] http://docs.scala-lang.org/overviews/core/futures.html
[3] https://github.com/scala/async
[4] http://docs.scala-lang.org/overviews/parallel-collections/ov...
[5] https://github.com/Netflix/RxJava
[6] http://www.playframework.com/documentation/2.2.x/Iteratees
Thread-safe – yes (and Clojure does this beautifully; in fact any Clojure DS is thread-safe); concurrent – not really, because you can only have one writer at a time, which simply doesn't scale for large data structures.
> I'd love a comparison between the two btw
Quasar has true lightweight threads (M:N multithreading as in Go or Erlang), and an (optional) actor system built on top. Quasar actors can and should block as much as you want, have selective receive (just like Erlang), and are especially easy to use. Also, Quasar has Java and Clojure APIs that feel natural and idiomatic in both languages.
I wonder if nowadays people can generally use it without never having to think about locks?
>One of Go’s selling points is that there are some very useful concurrency primitives baked right into the language.
Lets state this, not use any of said primitives, and then complain the language is broken...
But how does Go’s approach to concurrency fare when viewed through the lens of encouraging code that supports local reasoning? Not very well, I’m afraid. Goroutines all have access to the same shared memory space
The article is flawed because you: 1. Base it on Go failing to protect you, when in actually you fail to use any of Gos "very useful concurrency primitives baked right into the language" 2. When you choose to use these primitives you choose the the wrong primitive that results in a much more verbose and complex solution then is necessary.
It would have been much better had you: 1. Showed why the solution with no protection is unsafe (and mention its unsafe in just about any mainstream language) 2. Show a mutuex solution 3. Show a channel based solution
I would have understood snarking at my original (admittedly somewhat snarky) comment. I'm not sure why you felt the need to snark at my constructive criticism, which you actually took-
I don't think the original version was particularly flawed, and your description of why you think it was doesn't make a lot of sense to me. But I added a note anyway to make it clear that I do in fact know about the alternative approaches, and that I made the choices I made deliberately and not out of ignorance.
Regardless, I appreciate you taking the time to read it, and to give your feedback. Cheers.
When it comes to protecting a structs state, in most Go code (including the standard library) RW/Mutexes are the "go to" synchronization primitive. Channels are more commonly used for communication between longer running goroutines.
The problem with mutexes is that they are some kind of cheap way for the developer to say "stop the world while I think", but they require you to be quite aware of what happens in an object, too much I think.
In this example you'd have a mutex for the Account, so each time you want to change the amount you need to lock and unlock it. That's trivial for an object like that, but it can quickly become complex: one mutex is not enough because it blocks the whole object, so you start having multiple mutexes. But then you don't remember which mutex blocks what so you must have some good documentation about that, but the documentation is not as well maintained as the rest so it starts rotting. And then your file spreads among so many lines you can't quite grasp all the ways parallelism can kill you.
In the given example, the mindset is different: _all_ methods called from the outside are non-modifying, they only stack the change to be made. The actual data manipulation is done in a very tight loop that does a very simple thing, and nothing outside of this loop ever deals with memory. As a developer, you can fit all the code that can be "dangerous" in a mere 7 lines of code, instead of having it spread among the file.
I concure it's a different mindset, quite different at that, but it's a pretty good one (ang go makes it very pleasant)
I think this is the idiomatic way to implement this. It will lock the account every time you try to deposit to it (so other goroutines can't do it).
http://golang.org/doc/effective_go.html#concurrency
"Do not communicate by sharing memory; instead, share memory by communicating.
This approach can be taken too far. Reference counts may be best done by putting a mutex around an integer variable, for instance. But as a high-level approach, using channels to control access makes it easier to write clear, correct programs. "
E.g. An bank account is shared state (similar to a reference count) and the best approach is to put a mutex around it instead of fighting with channel synchronization.
"Reference counts MAY be best done by putting a mutex around an integer variable, for instance. BUT as a high-level approach, using channels to control access makes it easier to write clear, correct programs."
There is a difference between what someone with a background from other mainstream programming languages might think would be the best approach to locking (mutexes) and the idiomatic Go approach (unbuffered channels).
I'm the author of a Haskell library[1] for interfacing with HyperDex[2], a distributed database produced by some folks at Cornell.
The client-side library for HyperDex uses an event loop, and is "thread-safe" to call into as long as you synchronize access to the pointer. This is an awkward area to work with in Haskell-land, as the code I write has to deal with the intersection of the three uglies:
* Foreign function interfaces (and marshalling)
* Mutable resource management (allocating and freeing C-structs)
* Concurrency (synchronizing access to an object)
I've tried a variety of implementations. To speed up testing, I wrote a "fake HyperDex" client and test harness in which I can insert chaotic behaviors to test resilience.[3] While the code isn't as clean as I like right now, it lends itself to the smallest, most compact implementations of what I want. Each HyperDex connection pointer is paired with an event loop which receives requests for calls into HyperDex and processes them. When a response is demanded, the loop begins a busy-wait (will soon be replaced by an epoll/select on an fd) on results from the database. Each asynchronous request is an event loop too - a free floating closure sitting in memory that sends off a message and waits for responses.
GHC's garbage collector will determine when waiting on an MVar or Chan is deadlocked, and keeping everything in a ResourceT monad ensures that the whole system gracefully closes when portions fall out of scope and are unreachable.
The approach has a certain elegance to it. I am curious to hear what other people's thoughts are on such implementations though, because there are naturally performance implications.
[1] https://github.com/aaronfriel/hyhac
[3] http://lpaste.net/101084 - a hodgepodge of code I wrote to test implementations - ill-documented, this is just for personal exploration and testing
That is a common misconception. Or rather it is a tautalogy. No threads = thread-safe. But, it is not concurrently-modifying-data-structures safe -- which is the main painful point.
One can get just as easily tangled over a set of callbacks.
Here is a set of callbacks all started from some select/poll/epoll loop. Some call it a reactor (namely Glyph's own Twisted Python).
cb1 -> cb2 -> cb3|eb3 then cb3->cb4 and eb3->cb5
Processing starts with cb1 and ends with cb4 or cb5. Notice at some point cb2 function could result in generating an errback (eb3) which then ends up calling another callback cb5.
Understanding that the above, in a large system is just a messier, uglier concurrency structure than a thread/goroutine/task/actor is crucial.
It doesn't necessarily save you from simultaneous access to same shared data.
Imagine processing starts at cb1 and by the time it reaches cb3 (say cb2 calls some io or sleep operation), cb1 gets called again. cb1 through cb3 end up modifying some shared data (hey no need for lock, we are using callbacks remember!). Now there are two callback chains modifying shared data.
Yes you need locks and semaphores with the above just as you do with threads
For example this exists -- Twisted's own Sempahore:
http://twistedmatrix.com/documents/10.1.0/api/twisted.intern...
I had to use it, and not just for throttling concurrency, but also to protect critical data from being modified concurrently.
Asynchronous/callback/promise/future based concurrency looks really good in small examples. In large application they get messy quickly.
Threads/actors/goroutines etc are still nicer from a logical, application point of view. You can even build them on top of the same epoll/select/kqueue system calls if the language can support some kind of a coroutine structure (which for example python gevent/eventlet) is doing.
What I am doing in my implementation of a thread-safe wrapper around HyperDex is similar to what you describe at the very end of your post.
I just generalized about "thread safety" and async programming. So it was nothing specific to your particular code.
Obviously if you call a function you need to be aware of what it might do to any state you grant it access to, but even then it can only mutate state either before it returns (as in most popular programming models even without concurrency) or, if it registers a callback, at some point after you yield control.
It takes a little bit of getting used to, but this effectively makes mutual exclusion blocks the default unit of execution - and in doing so eliminates a lot of the care needed to write correct code in a preemptive model. Take a look at a well written Node.js or Twisted app - neither Javascript nor Python has concurrent datastructures in their standard library, but it just isn't an issue in most cases.
All of that being said, I think that the failure of this model is that the reason programmers tend to yield control is not because they no longer need it, but rather because you they must do so in order to avoid blocking the event loop on I/O or a timer. In other words, they need to model arithmetic, for example, fundamentally differently than they model loading a configuration file. Things get even wonkier when you start specifying interfaces without knowledge of the implementation: at some point almost any operation could require IO, even if the default implementation doesn't, so you end up registering callbacks on every line. In addition to wreaking havoc on your mental model you have to begin worrying about stack sizes, etc.
In this sense, I think well written Go has a certain elegance. The programmer knows to treat shared state as a special and dangerous case. Instead, you tend to program around a produce/consume model using channels with near zero shared state. You don't need to worry about whether a call yields to the scheduler or not, or even how many threads your goroutines map to - you just write little blocks of code that operate on easily comprehensible state.
Any buffering in the request channels would have the race you've described though.
how about sending a errChan along with the delta to the deltaChan and and error will be guaranteed to be replied to the correct sender?
Basically, everything is parallel, except that which has to be processed globally, which is just a tiny minority of everything. Then there is a non-parallelized step that knits together and coordinates the global grid. If you plotted parallelism over time, it would probably look like a saw tooth or a square wave.
Right now, there are only two tiers, but this could be generalized into a structure like an R-tree, which would probably make the algorithm cache oblivious.
It's the "knitting" step that keeps it from utilizing 100% of the cores in parallel with just one instance. I still hope to be able to support 1000's of entities with just one instance, however.
Go provides you with locks for those cases where you actually want to use a lock. And transactional balance logic absolutely screams for locks.
This just joined my favourite quote list.
sync.Once() instead of init()
unhelpful named return parameters
didn't use range over channels
For example idiomatic Java was a clusterfuck for nearly a decade, with all the EJB's and FactorySingletonProxies and XML everywhere. It would be better for Java programmers to ignore the idiomatic BS prevalent in the community, and just use the language in a saner way.
Idiomatic is often just another name for "how lots of people prefer to do it" or "cargo cult".