-
Notifications
You must be signed in to change notification settings - Fork 11
Actors and immutability
Querki is going to operate mainly in-memory for the first release -- we're going to have what amounts to a distributed in-memory object-oriented database for everything that is currently in-use. The way we're going to make that work without melting down in race-condition chaos is through a very principled use of Actors and Immutability.
Querki is going to be built on the Scala stack, including a number of free and open-source packages. The most important of these is Akka, which looks to be the most advanced Actors library available for Scala.
If you aren't familiar with the Actor style of architecture, it's worth reading into it (here's the Wikipedia article on the subject). But the high concept is that an Actor is sort of like an object in a typical object-oriented system, except:
-
Actors communicate solely through message-passing -- they are not permitted to call each other's methods directly.
-
Each Actor operates in its own single-threaded bubble. The Actors collectively share a big thread pool, but any given Actor at any given time has at most one active thread. In its thread, an Actor takes messages from its incoming queue, processes them, and sends out responses. It never does anything aside from this message-processing loop.
Combine these, and you get a tried-and-true model for building very large scale, extremely high-reliability systems. It is a way of thinking about concurrency that avoids many of the common problems in multi-threaded programming. It is relatively easy to reason about -- vastly easier than traditional, lock-based threading.
The Actor Model is the main reason why the Erlang language (which drives me a little batty in most respects) has become popular in recent years: for decades, Erlang and the Actor Model have been used to build some of the most reliable computer systems in the world.
One of the early decisions in the Scala community was to adapt the Actor Model to Scala. This was carried further by Jonas Bonér and associates with the Akka project, which did a very principled job of adapting all of the lessons from Erlang's experience to the Scala world -- not just Actors, but all the infrastructure required to make a truly high-availability system. The result is an increasingly popular mechanism for handling large scale programming in Scala, and on the JVM in general.
Actors are only half the story, though. The other trick is how you use them. Actors make the system genuinely safe for multi-threaded programming if you truly confine all mutable state to them. This is a hard rule for Querki: all mutable state must be locked inside a single Actor.
That is, Actors communicate via message-passing. The important rule is that these messages are all immutable objects. You don't send a message in and have it edited by the receiver; the message is simply information to be sent along. Any actual variables are contained within a single Actor. If another Actor needs access to that information, it has to send a request for it. Moreover, the "client" that receives that information is not permitted to reason about it excessively -- if it is potentially mutable information, then all that the client knows is that the state was this particular value. It doesn't necessarily knows what the value is now, and shouldn't make assumptions.
This model actually works very well for Querki, but you have to keep in mind some key constraints. The most important is that we are trying for "eventual consistency" -- any given outside view of the information may be slightly out of date. This really isn't controversial any more -- it's downright common in the social-media world -- but it isn't the way most engineers think of data.
Remember that a user is always working in a "Space" -- essentially a small, usually personal, database for a particular application. There is precisely one copy of that Space loaded into memory, somewhere in the Querki Cluster. That is contained in an Actor, and absolutely all changes to that Space go through the Actor as requests. These requests are lined up in a queue. Each one in its turn gets validated (check to make sure that the change isn't out of date due to edit contentions); processed (changing the state of the Space); and stored (sending a request off to the Storage Actor for this Space to make this change to the on-disk database).
When another Actor (such as a user session) wants to display something from the Space, it sends a request to the Space's Actor, asking for a copy of the Space. That request generally returns a complete copy of the Space. (This is one of the reasons why we are currently limiting Spaces to be fairly small -- most are expected to be well under 1Meg in size, and the majority will probably only be tens of K.) The requesting client runs its queries and displays over that. This lets us perform extremely sophisticated queries with ease, since the query processor has a complete copy of the Space right in memory to examine; performance in most cases is expected to be extremely high.
The client session should generally drop its copy of the Space as soon as it is done running the request. To avoid excessive message-passing traffic, though, each Space will be proxied as needed. That is, if a client on node A is interacting with a Space on node B, we will construct a thin proxy on A. That will work with the actual Space Actor on B, and maintain a cached copy of the Space's State on A, updating it as seems best.
In practice, we don't expect these proxies to be the norm: most Spaces, most of the time, will only be in use by one user session, and the Space Actor will tend to wind up on the same node as the session itself. In those cases, having the Session ask for the current state of the Space each time will be so cheap that there is no reason not to do it. But we will use proxies as necessary, so that a Session can avoid keeping its own cache while still having quick and cheap access to a reasonably current state of the Space.
This approach has many advantages. Besides the speed with which we can process interesting queries, it also takes a healthy attitude towards the Space's state. Since we are always operating on a coherent copy of the Space, but not assuming that it is the on-disk copy, it will be extremely easy down the line to provide access to older snapshots of the Space. If the user wants to see what his Space looked like three months ago, the Space's Actor just loads up the change list, constructs a version that represents the state at that time, and hands that off to the client to process. In principle, this will provide an extremely easy variety of version control for end users to play with, given them a clear view of the evolution of their state with no manual work involved.
It also provides a clear approach to dealing with contention. By the nature of Querki and its use cases, edit contention is not expected to be common -- I am usually only editing a single Thing at a time, so contention is mainly an issue if two people are trying to edit the same thing at the same time. To deal with this case, we will always remember which timestamp of the Space we are editing against. When I submit a change request, I will say what timestamp this change is being submitted against. If the Thing has changed since that timestamp, the Space's Actor will bounce the request, asking for a fresh edit against the current state of the Space.
This approach to contention is a bit crude, but terribly easy and common, and should do well enough for the time being. Later, we might get fancier about it if there is user demand -- if we get terribly ambitious, we could even implement a Google Wave style of operational transformations, to get co-editing on the same field at the same time.
The Akka architecture promotes extremely high reliability when used correctly, but that doesn't come automatically. So there are some rules we should follow as we build the system:
-
All Actors should be in properly-designed Supervisor Hierarchies. That is, each Actor has a higher-level Actor in charge of it, responsible for addressing faults and restarting children as necessary. It will take us a while to learn exactly what those hierarchies should look like, but that should be an explicit goal.
-
All round-trip communication between Actors should include exception handling. That is, if you are using a Promise or a Try or a Future, you must handle the error cases if something goes wrong.
-
All round-trip communication between Actors (especially between nodes) must handle timeouts. You must declare an appropriate timeout, and deal with it if that happens. Cloud environments are especially unreliable, and it is always possible that the Actor at the other end of your communications might go away abruptly.
-
Messages to Actors should, by and large, go through the supervisory chains, rather than being directly addressed. We're not going to be hard-assed about this -- masters should usually work directly with their workers, for example -- but User Sessions should not, as a rule, assume anything about the lifecycle of the Spaces they are working with. They should send messages via Space Supervisors, which will route them appropriately.
More guidelines and best practices may be added to this list as we go. Following these rules should help keep the system properly robust.