A little over a year ago, I wrote an essay called Callbacks are Imperative, Promises are Functional, in which I argued that promises are not a control-flow device but rather a tool to describe relationships between dependent values, such that the promise library can figure out the control flow – the correct and optimal order of operations – for you. I gave the example of a module loader, where by modelling a set of modules as a graph of lazy promises, we can write code that describes the dependencies between modules and automatically have them downloaded in the correct order and with the maximum possible parallelisation. This echoes a quote from the book Learn You a Haskell for Great Good:
In purely functional programming you don’t tell the computer what to do as such but rather you tell it what stuff is.
Writing the control flow for optimally downloading modules by hand is rather hard; better to invent a system where you can describe the shape of your domain and have the system solve the problem for you.
A few months ago, I wrote a tutorial on Make, having spent a year with it while writing JavaScript Testing Recipes. Though I didn’t realise it when writing my promises essay, there is a deep similarity between Make and my promise-based module loader: in both systems we work by defining dependencies among a set of artefacts, and then the platform figures out which things must be run and it what order when you ask for one of those artefacts. Make can even parallelise the tasks it runs when it spots that two tasks are independent and can therefore be run in any order – if it doesn’t matter which order you perform two tasks in, you can probably run them in parallel.
This week I was working on some Redis code, and I realised that this concept of solving problems by relating values and deriving the control flow from those relationships had given me an insight into solving a problem I’d been having with performing atomic changes to a Redis database. I don’t use any of the above concepts directly in the code, but I found that they gave me a new way to think about the problem and suddenly realise a solution. Let me try to explain.
Shortly before writing that promises article, I released reStore, a
remoteStorage server written in Node with both filesystem- and Redis-based
backends. remoteStorage is a protocol for storing arbitrary documents via
HTTP; each user on a server has a directory tree and they can grant applications
access to parts of that tree for the application to store user data. The
application uses GET to retrieve documents by pathname, and receives the
document’s content, plus its media type in a Content-Type header and its
version in an ETag. It can also request folder listings using GET to a
pathname ending in a trailing slash, which returns a list of the folder’s
children (documents and other folders) with their current versions.
The app can save new documents using PUT, setting their type using
Content-Type, and remove them using DELETE. Both these methods allow use of
the If-Match header; the application can pass in the current version it has
for a document, and the server will process the request only if that version is
indeed current. Otherwise, the app makes a GET to retrieve the latest version,
reapplies its changes and tries to save again; this prevents applications from
clobbering one another’s changes.
Now, these semantics lend themselves naturally to using the filesystem as a backend, and indeed reStore has such a backend. But it also has a Redis backend, and I’ve recently been doing some work to make sure that when it saves and deletes documents, all changes to the Redis database are done atomically.
Most of the complexity in doing this comes from the fact that remoteStorage is not quite as low-level as the Unix filesystem. When you save a document, all its parent folders are created implicitly, and if you delete the only remaining item from a folder then that folder is deleted. So folders exist only if they contain documents, or other folders. Clients never manipulate folders directly, they only deal with saving documents.
Furthermore, all folders have an ETag version just like documents do. A
folder’s version must change if any document within its tree is updated or
removed. This is to facilitate syncing: a client can easily tell if its copy of
a tree is up to date by comparing the version tag on the root folder, rather
than checking every document within the tree.
So when a document is saved, we need to make sure that all its containing
folders exist and update all of their versions. (We could store only the
documents and figure out the folders when a GET is made, but it’s cheaper to
generate the tree on write than on read.) For ease of implementation, the
version of a document in reStore is simply the Unix timestamp of the last time
it was changed (the remoteStorage spec previously required versions to be
timestamps and it used Last-Modified rather than ETag). The version of a
folder is the latest timestamp that exists on any of its children.
Here’s a naive version of a backend store for the requirements we’ve layed out.
Although reStore is written in Node, I’ve written these examples in Ruby since
it’s far easier to see what’s actually happening without all those callbacks
getting in the way. It has one public method: put(), that handles requests to
save documents. It takes a username, document path, content type, and optional
version string. It begins by splitting the pathname into its segments, for
example parse_path('/path/to/file.txt') returns ['/', 'path/', 'to/',
'file.txt']. It checks whether the given version is current or not – if no
version is given, the request is always allowed, but if a version is given for a
document that doesn’t exist the request is forbidden since the client has stale
data – then proceeds to update the tree. It uses SADD to make sure each item
is listed as a child of its parent folder, and HSET to set the modified time
on each parent folder to the current time. Finally, it checks if the target file
exists (we need to tell the client if the document was created or updated), then
saves its content, media type, size and modified time using HMSET.
class Store
VersionConflict = Class.new(StandardError)
def initialize(redis_client)
@redis = redis_client
end
def put(username, pathname, content, type, version = nil)
query = parse_path(pathname)
filename = query.pop
prefix = "users:#{username}:data:"
modified = (Time.now.utc.to_f * 1000).floor
is_current = get_current_state(prefix + pathname, version)
raise VersionConflict unless is_current
query.each_with_index do |dir, i|
key = prefix + query.slice(0, i + 1).join('')
@redis.hset(key, 'modified', modified.to_s)
@redis.sadd(key + ':children', query[i + 1] || filename)
end
exists = @redis.exists(prefix + pathname)
@redis.hmset(prefix + pathname, :length, content.size,
:type, type,
:modified, modified,
:content, content)
[!exists, modified]
end
private
def parse_path(pathname)
pathname.scan(/[^\/]*(?:\/|$)/)[0..-2]
end
end
Here’s what this code does when we run the call:
store.put('jcoglan', '/books/jstr/preface.txt', 'Preface to JSTR', 'text/plain')
The Redis MONITOR command prints the following:
"hget" "users:jcoglan:data:/books/jstr/preface.txt" "modified"
"hset" "users:jcoglan:data:/" "modified" "1402430750408"
"sadd" "users:jcoglan:data:/:children" "books/"
"hset" "users:jcoglan:data:/books/" "modified" "1402430750408"
"sadd" "users:jcoglan:data:/books/:children" "jstr/"
"hset" "users:jcoglan:data:/books/jstr/" "modified" "1402430750408"
"sadd" "users:jcoglan:data:/books/jstr/:children" "preface.txt"
"exists" "users:jcoglan:data:/books/jstr/preface.txt"
"hmset" "users:jcoglan:data:/books/jstr/preface.txt" "length" "15" \
"type" "text/plain" "modified" "1402430750408" "content" "Preface to JSTR"
So we can see it checking the version of the target document, updating all the parent folders and finally the document itself. However, there are two glaring holes in this implementation:
- While we’re running these commands, another client might be doing work that becomes interleaved with ours. We might both check the current version, find that we’re up to date, and then both go ahead and update the document, clobbering one another’s changes. This is precisely the ‘interceding update’ problem that the version check is supposed to fix.
- If our server process crashes part-way through this set of updates, the tree is left in an invalid state. Folders are said to have children that do not actually exist, or have modification times that don’t reflect the true state of things.
To make the system robust, we need to solve both of these problems, and this will partly involve making better use of the tools Redis gives us, and also re-framing the problem slightly to make it fit better into Redis’s constraints. The former technique is certainly useful but it’s the latter that I am particularly interested in here.
The first problem is actually quite easy to solve: since we’re making changes to the user’s entire directory tree, conditional on the state of one document, we will lock the user’s data while this is happening. To have each update have a consistent view of the world, they must be applied in sequence, and the lock will make sure only one update executes at a time.
The documentation for SETNX provides a locking algorithm for us. You
should read those docs to understand the algorithm; here’s an implementation in
Ruby:
LOCK_TIMEOUT = 10_000
def lock(name)
result = nil
while result.nil?
lock_key = "locks:#{name}"
current_time = (Time.now.utc.to_f * 1000).floor
expiry = current_time + LOCK_TIMEOUT
if @redis.setnx(lock_key, expiry)
next result = yield.tap { @redis.del(lock_key) }
end
timeout = @redis.get(lock_key)
if timeout.nil? or current_time < timeout.to_i
next sleep 0.1
end
old_value = @redis.getset(lock_key, expiry)
if old_value == timeout.to_s
result = yield.tap { @redis.del(lock_key) }
else
sleep 0.1
end
end
result
end
Wrapping this mechanism around our PUT logic lets us make sure that nothing
about the user’s tree will change between us checking the version and making our
changes.
def put(username, pathname, content, type, version = nil)
query = parse_path(pathname)
filename = query.pop
prefix = "users:#{username}:data:"
lock username do
modified = (Time.now.utc.to_f * 1000).floor
is_current = get_current_state(prefix + pathname, version)
raise VersionConflict unless is_current
query.each_with_index do |dir, i|
key = prefix + query.slice(0, i + 1).join('')
@redis.hset(key, 'modified', modified.to_s)
@redis.sadd(key + ':children', query[i + 1] || filename)
end
exists = @redis.exists(prefix + pathname)
@redis.hmset(prefix + pathname, :length, content.size,
:type, type,
:modified, modified,
:content, content)
[!exists, modified]
end
end
The second problem is more subtle. We want to make all these changes to the
database – a combination of HSET, SADD and HMSET commands – happen as
one, so Redis will execute them as a unit. Fortunately, Redis has
transactions that let us do exactly this. But, there’s one minor problem: a
Redis transaction works by sending the MULTI command, then all the commands
you want to run together, then sending EXEC. Only then will all the commands
be executed; you cannot have a command that depends on the result of another
command, because you don’t get any responses until after all the commands have
run.
In our code, there’s a pesky little EXISTS sitting between the writes to the
parent folders and the document itself. This must happen before the final
HMSET since we need to know if the document existed before that write, and
there’s a temptation to put it as close to the HMSET as possible to make sure
no other changes happen between the two.
However: notice that none of the writes depend on the result of the EXISTS
call. They do depend on the result of the HGET that checks the version,
since they are conditional on that, but everything after that depends only on
information from the original method inputs. Because of this lack of
dependencies, the writes can actually be done in any order and we will get the
same result. As long as it happens at some point before the final HMSET, and
within the lock so we know no other changes have happened, the EXISTS call
can happen as early in the process as we like. We can push it before the parent
folder updates:
def put(username, pathname, content, type, version = nil)
query = parse_path(pathname)
filename = query.pop
prefix = "users:#{username}:data:"
lock username do
modified = (Time.now.utc.to_f * 1000).floor
is_current = get_current_state(prefix + pathname, version)
raise VersionConflict unless is_current
exists = @redis.exists(prefix + pathname)
query.each_with_index do |dir, i|
key = prefix + query.slice(0, i + 1).join('')
@redis.hset(key, 'modified', modified.to_s)
@redis.sadd(key + ':children', query[i + 1] || filename)
end
@redis.hmset(prefix + pathname, :length, content.size,
:type, type,
:modified, modified,
:content, content)
[!exists, modified]
end
end
Or, we can get rid of it entirely: the initial version check can tell us whether
the document exists, since it will have no modified key if it’s absent. Let’s
modify get_current_state() to return two values: a boolean for whether the
version is current, and one for whether the document exists:
def get_current_state(key, version)
modified = @redis.hget(key, 'modified')
return [version.nil?, false] if modified.nil?
return [true, true] if version.nil?
return [version.to_i == modified.to_i, true]
end
and use this new value in our put() method:
def put(username, pathname, content, type, version = nil)
query = parse_path(pathname)
filename = query.pop
prefix = "users:#{username}:data:"
lock username do
modified = (Time.now.utc.to_f * 1000).floor
is_current, exists = get_current_state(prefix + pathname, version)
raise VersionConflict unless is_current
query.each_with_index do |dir, i|
key = prefix + query.slice(0, i + 1).join('')
@redis.hset(key, 'modified', modified.to_s)
@redis.sadd(key + ':children', query[i + 1] || filename)
end
@redis.hmset(prefix + pathname, :length, content.bytes.size,
:type, type,
:modified, modified,
:content, content)
[!exists, modified]
end
end
Now if we run our test again, we see this pattern of commands:
"setnx" "locks:jcoglan" "1402432911685"
"hget" "users:jcoglan:data:/books/jstr/preface.txt" "modified"
"hset" "users:jcoglan:data:/" "modified" "1402432901692"
"sadd" "users:jcoglan:data:/:children" "books/"
"hset" "users:jcoglan:data:/books/" "modified" "1402432901692"
"sadd" "users:jcoglan:data:/books/:children" "jstr/"
"hset" "users:jcoglan:data:/books/jstr/" "modified" "1402432901692"
"sadd" "users:jcoglan:data:/books/jstr/:children" "preface.txt"
"hmset" "users:jcoglan:data:/books/jstr/preface.txt" "length" "15" \
"type" "text/plain" "modified" "1402432901692" "content" "Preface to JSTR"
"del" "locks:jcoglan"
Two important things have happened here: first, all the commands have happened
inside a locking block bounded by the SETNX and DEL commands. Second, and
more importantly for making the writes atomic: notice that this operation is now
a read (HGET) followed by a sequence of writes (HSET, SADD, HMSET). The
fact that all the writes are uninterrupted by any reads, and do not depend on
one another, means we can wrap them in a MULTI transaction:
def put(username, pathname, content, type, version = nil)
query = parse_path(pathname)
filename = query.pop
prefix = "users:#{username}:data:"
lock username do
modified = (Time.now.utc.to_f * 1000).floor
is_current, exists = get_current_state(prefix + pathname, version)
raise VersionConflict unless is_current
@redis.multi do
query.each_with_index do |dir, i|
key = prefix + query.slice(0, i + 1).join('')
@redis.hset(key, 'modified', modified.to_s)
@redis.sadd(key + ':children', query[i + 1] || filename)
end
@redis.hmset(prefix + pathname, :length, content.bytes.size,
:type, type,
:modified, modified,
:content, content)
end
[!exists, modified]
end
end
This leaves us with out final command sequence:
"setnx" "locks:jcoglan" "1402433277043"
"hget" "users:jcoglan:data:/books/jstr/preface.txt" "modified"
"multi"
"hset" "users:jcoglan:data:/" "modified" "1402433267046"
"sadd" "users:jcoglan:data:/:children" "books/"
"hset" "users:jcoglan:data:/books/" "modified" "1402433267046"
"sadd" "users:jcoglan:data:/books/:children" "jstr/"
"hset" "users:jcoglan:data:/books/jstr/" "modified" "1402433267046"
"sadd" "users:jcoglan:data:/books/jstr/:children" "preface.txt"
"hmset" "users:jcoglan:data:/books/jstr/preface.txt" "length" "15" \
"type" "text/plain" "modified" "1402433267046" "content" "Preface to JSTR"
"exec"
"del" "locks:jcoglan"
We have made all the changes made by the put() method into a single
transaction. Redis will not run any of them until it receives EXEC, preventing
any of them from running if the process crashes while sending them. Either they
all run, or none does.
This was kind of a silly example though: technically, we could have left that
EXISTS call in the middle of the transaction. None of the writes depended on
its result, so we could have left it in before the final HMSET and received
its result at the end of the process. It turned out the EXISTS call was
redundant anyway, but this example demonstrates a key idea: analysing the
dependencies between operations, flattening that graph so that things happen as
early as possible, disinterleaving reads and writes, and noticing when the order
of commands does and does not matter, is a key strategy to atomising Redis
operations. We got lucky with PUT, but DELETE is far more tricky.
DELETE looks a little like PUT run in reverse. We delete the target
document, and remove it as a child from its parent folder. Then we go back up
the tree, removing and updating things. If a folder has no children, we delete
it. If it does have children, we set its version to the latest version of any of
its remaining children, then move up to the next level. Here’s a first stab at
an implementation, where we’ve added another return value to
get_current_state(): we need to tell the client whether the deleted document
existed and what its version was:
def delete(username, pathname, version = nil)
prefix = "users:#{username}:data:"
query = parse_path(pathname)
filename = query.pop
parents = (0...query.size).map { |i| query[0..i].join('') }.reverse
lock username do
is_current, exists, modified = get_current_state(prefix + pathname, version)
raise VersionConflict unless is_current
@redis.del(prefix + pathname)
@redis.srem(prefix + parents.first + ':children', filename)
parents.each_with_index do |parent, i|
children = @redis.smembers(prefix + parent + ':children')
if children.empty?
@redis.del(prefix + parent)
if i + 1 < parents.size
item = query[query.size - i - 1]
@redis.srem(prefix + parents[i + 1] + ':children', item)
end
else
mtimes = children.map do |child|
@redis.hget(prefix + parent + child, 'modified')
end
@redis.hset(prefix + parent, 'modified', mtimes.map(&:to_i).max)
end
end
[exists, modified]
end
end
private
def get_current_state(key, version)
modified = @redis.hget(key, 'modified')
return [version.nil?, false, nil] if modified.nil?
return [true, true, modified.to_i] if version.nil?
return [version.to_i == modified.to_i, true, modified.to_i]
end
As an example, say we run the following commands to add three documents and then delete them in reverse order:
store.put('jcoglan', '/books/jstr/preface.txt', 'Preface to JSTR', 'text/plain')
store.put('jcoglan', '/books/jstr/chapters/browser.txt', 'Browser Applications', 'text/plain')
store.put('jcoglan', '/books/jstr/chapters/cli.txt', 'Command-line Interfaces', 'text/plain')
store.delete('jcoglan', '/books/jstr/chapters/cli.txt')
store.delete('jcoglan', '/books/jstr/chapters/browser.txt')
store.delete('jcoglan', '/books/jstr/preface.txt')
Here’s the command sequence for the second delete(), which will implicitly
delete its parent folder but leave the others intact. We see it deleting the
document, then its parent, then updating the versions of the other folders above
it, by checking the children of each folder in turn.
"setnx" "locks:jcoglan" "1402435177397"
"hget" "users:jcoglan:data:/books/jstr/chapters/browser.txt" "modified"
"del" "users:jcoglan:data:/books/jstr/chapters/browser.txt"
"srem" "users:jcoglan:data:/books/jstr/chapters/:children" "browser.txt"
"smembers" "users:jcoglan:data:/books/jstr/chapters/:children"
"del" "users:jcoglan:data:/books/jstr/chapters/"
"srem" "users:jcoglan:data:/books/jstr/:children" "chapters/"
"smembers" "users:jcoglan:data:/books/jstr/:children"
"hget" "users:jcoglan:data:/books/jstr/preface.txt" "modified"
"hset" "users:jcoglan:data:/books/jstr/" "modified" "1402435167365"
"smembers" "users:jcoglan:data:/books/:children"
"hget" "users:jcoglan:data:/books/jstr/" "modified"
"hset" "users:jcoglan:data:/books/" "modified" "1402435167365"
"smembers" "users:jcoglan:data:/:children"
"hget" "users:jcoglan:data:/books/" "modified"
"hset" "users:jcoglan:data:/" "modified" "1402435167365"
"del" "locks:jcoglan"
This problem seems far harder to fix: in order to delete each folder or update its version, we need to check its children, and in order to make sure the children are up to date, we need to update the next folder down the chain, all the way back to the target document. This is, of course, how we would implement it on a real filesystem, where one cannot delete non-empty directories.
But there is a way out: think back to the PUT example: we made the writes
atomic by figuring out as many of their parameters as possible in advance,
allowing us to disinterleave the writes from anything they depended on, making
it possible to run them in a single transaction.If you think about it for a
minute, you’ll realise you can predict which folders will need to be deleted
and updated before you start deleting anything at all, and we’ll use that
trick to tease apart the reads and writes.
We can say, in advance, that if we delete a document then any folders that form a chain from its immediate parent that have only one child will need to be deleted: those folders exist entirely to contain the document we’re going to delete. So we can figure out the deletable folders in advance by walking up from the document until we find a folder with more than one child.
Similarly, we can figure out the versions of all the remaining folders after the deletion by reading all the relevant item versions in advance, that is, getting the versions of all the children of all the parents of the deleted document. Note this doesn’t involve reading the whole tree; only the immediate children of each folder need to be considered. From these lists, we can remove the version for the topmost deletable folder, then back-propagate to calculate the resulting versions of the other folders.
The code for this is significantly more verbose but I’ve tried to comment what’s going on at each point. You should be able to see how the previous approach of deleting an item, then checking how its parents need to be updated, then recursing up the tree, has been replaced with an algorithm that plans all the changes we need to make up front by doing that same process on data that we’ve already gathered into memory ahead of time.
def delete(username, pathname, version = nil)
prefix = "users:#{username}:data:"
query = parse_path(pathname)
parents = (0...(query.size - 1)).map { |i| query[0..i].join('') }.reverse
# e.g. if query = ['/', 'books/', 'jstr/', 'preface.txt']
# then parents = ['/books/jstr/', '/books/', '/']
lock username do
is_current, exists, modified = get_current_state(prefix + pathname, version)
raise VersionConflict unless is_current
# Find all the immediate child items of the list of parent folders; this
# returns an Array<Array<String>>.
children = parents.map do |parent|
@redis.smembers(prefix + parent + ':children')
end
# Determine which folders will be empty by starting with the immediate
# parent and finding folders with only one child.
empty, index = [], 0
while index < parents.size and children[index].size == 1
empty << parents[index]
index += 1
end
# The remaining folders are the non-empty ones, i.e. those after the index
# we just counted up to. Their children are the corresponding lists in the
# children array.
remaining = parents[index..-1]
children = children[index..-1]
# Construct an Array<Array<Fixnum>> of modified times corresponding to the
# children array.
mtimes = children.map.with_index do |child_list, i|
child_list.map do |child|
@redis.hget(prefix + remaining[i] + child, 'modified').to_i
end
end
# An index where we'll store the computed versions for remaining folders.
ancestors = {}
if remaining.size > 0
# Remove the uppermost empty folder as a child from its parent, and
# delete its corresponding version from the mtimes list.
item = query[query.size - empty.size - 1]
@redis.srem(prefix + remaining.first + ':children', item)
mtimes.first.delete_at(children.first.index(item))
# Back-propagate the version updates to the other remaining parent
# folders. We calculate the new version from each folder's remaining
# children, update this version in the mtimes list then repeat at the
# next level up.
remaining.each_with_index do |dir, i|
ancestors[dir] = mtimes[i].max
if i + 1 < remaining.size
item = query[query.size - empty.size - 2 - i]
mtimes[i + 1][children[i + 1].index(item)] = ancestors[dir]
end
end
# Save the updated versions to the database.
ancestors.each do |dir, mtime|
@redis.hset(prefix + dir, 'modified', mtime)
end
end
# Delete all the folders we determined were empty, and their sets of
# children.
empty.each do |dir|
@redis.del(prefix + dir)
@redis.del(prefix + dir + ':children')
end
# And finally, delete the document itself.
@redis.del(prefix + pathname)
[exists, modified]
end
end
This code produces the following command sequence for deleting the second item in our test:
"setnx" "locks:jcoglan" "1402437739275"
"hget" "users:jcoglan:data:/books/jstr/chapters/browser.txt" "modified"
"smembers" "users:jcoglan:data:/books/jstr/chapters/:children"
"smembers" "users:jcoglan:data:/books/jstr/:children"
"smembers" "users:jcoglan:data:/books/:children"
"smembers" "users:jcoglan:data:/:children"
"hget" "users:jcoglan:data:/books/jstr/preface.txt" "modified"
"hget" "users:jcoglan:data:/books/jstr/chapters/" "modified"
"hget" "users:jcoglan:data:/books/jstr/" "modified"
"hget" "users:jcoglan:data:/books/" "modified"
"srem" "users:jcoglan:data:/books/jstr/:children" "chapters/"
"hset" "users:jcoglan:data:/books/jstr/" "modified" "1402437729226"
"hset" "users:jcoglan:data:/books/" "modified" "1402437729226"
"hset" "users:jcoglan:data:/" "modified" "1402437729226"
"del" "users:jcoglan:data:/books/jstr/chapters/"
"del" "users:jcoglan:data:/books/jstr/chapters/:children"
"del" "users:jcoglan:data:/books/jstr/chapters/browser.txt"
"del" "locks:jcoglan"
Before, we had calls to SMEMBERS and HGET interleaved with SREM, HSET
and DEL. Now however, he have completely disinterleaved the reads and writes;
all the writes have been planned ahead of time and aren’t interleaved with the
reads that determine what needs to be changed. This means we can wrap all the
writes in a MULTI; I won’t reproduce the Ruby code for this (we wrap part of
the delete() method in @redis.multi do ... end) but the commands look like
this:
"setnx" "locks:jcoglan" "1402437849398"
"hget" "users:jcoglan:data:/books/jstr/chapters/browser.txt" "modified"
"smembers" "users:jcoglan:data:/books/jstr/chapters/:children"
"smembers" "users:jcoglan:data:/books/jstr/:children"
"smembers" "users:jcoglan:data:/books/:children"
"smembers" "users:jcoglan:data:/:children"
"hget" "users:jcoglan:data:/books/jstr/preface.txt" "modified"
"hget" "users:jcoglan:data:/books/jstr/chapters/" "modified"
"hget" "users:jcoglan:data:/books/jstr/" "modified"
"hget" "users:jcoglan:data:/books/" "modified"
"multi"
"srem" "users:jcoglan:data:/books/jstr/:children" "chapters/"
"hset" "users:jcoglan:data:/books/jstr/" "modified" "1402437839350"
"hset" "users:jcoglan:data:/books/" "modified" "1402437839350"
"hset" "users:jcoglan:data:/" "modified" "1402437839350"
"del" "users:jcoglan:data:/books/jstr/chapters/"
"del" "users:jcoglan:data:/books/jstr/chapters/:children"
"del" "users:jcoglan:data:/books/jstr/chapters/browser.txt"
"exec"
"del" "locks:jcoglan"
This is now a robust deletion procedure. The SETNX lock around the whole
process means that while we’re making our reads to figure out what to do, we
know the structure won’t change so we’ll get a consistent view of the data. And
putting all the writes together in one transaction means that we cannot leave
the database in an invalid state by accident. After every atomic change that
Redis makes to the data, it will be in a meaningful rather than an intermediate
state that makes sense to the application.
What we’ve done here has a deep similarity with optimising module loading or
Make task execution: they all involve flattening a dependency graph. If you look
at the first command trace for the delete() method, where reads and writes are
interleaved, almost every command depends on the one before it. The HSET that
updates a folder’s modified time depends on the HGETs that read its children’s
modified times, which in turn depend on the SMEMBERS to find the children’s
names, all of which depends on the list of children and their times being left
up-to-date by the previous iteration. The only parallelisable commands in the
whole list are the DEL/SREM pairs that delete items; the dependency graph of
this trace is thirteen steps deep, including the initial version check.
HGET current document version
|
DEL document / SREM from parent's children
|
SMEMBERS parent's children
|
DEL folder / SREM from parent's children
|
SMEMBERS parent's children
|
HGET all child versions
|
HSET parent version
|
SMEMBERS parent's children
|
HGET all child versions
|
HSET parent version
|
SMEMBERS parent's children
|
HGET all child versions
|
HSET parent version
By contrast, the final trace we ended up with is very shallow: all the writes
are mutually independent, which is why we can put them in a transaction. All the
HGETS are mutually independent, but they each depend on one of the SMEMBERS
calls, though those calls are also mutually independent. Including the initial
version check, this dependency graph is then only four steps deep compared to
the thirteen of the previous trace.
HGET current document version
|
SMEMBERS the children of all parent folders
|
HGET remaining children's versions
|
DEL / SREM / HSET items as necessary
We’ve reshaped the graph so that more of its items are order-independent. For some problems, this lets us run tasks in parallel. For this task, it means operations can be grouped into transactions and made atomic.
Now you’re probably wondering what all this has to do with promises, or Make, or functional programming. Well, the interesting thing for me is what triggered me to do this work in the first place. I was actually working on the Redis backend for Faye, where each client has a set of channels it’s subscribed to (and each channel has a reverse index of clients subscribed to it, for routing messages), and a list of messages that are queued for delivery to that client. The engine periodically sweeps the database for expired sessions and removes all their subscriptions and message queues.
For a long time after I launched the Redis engine, there were problems with race conditions that would let expired sessions leak memory over time. For example, if we delete a client’s message queue before we delete its subscriptions, then there’s a window of time where a published message can still be routed to that client and added to its queue, after that queue has been deleted.
I found this problem really hard to solve for a long time – the Redis backend
launched over 3 years ago – and it surprised me that all of the sudden the
solution became obvious to me. Just like our PUT example above, the session
expiry mechanism had a read right in the middle of it that looked up the
client’s subscriptions so it could delete them all, actually by delegating to
another function that just handled unsubscribing a client from a single channel.
Thinking about the problem as a dependency graph made me realise that the read
could be pushed to the start of the process, leaving a bunch of mutually
independent writes that could all be put in a transaction. Et voilá,
atomic client expiry, one less race condition to worry about.
I had been stuck because I was thinking about the problem from an imperative programming mindset. In imperative programming, or more precisely, in systems with strict rather than lazy evaluation, we are forced to tell the computer to perform actions in a certain order. Sometimes, the order we decide upon is important – the program would break if its statements were reordered – and sometimes it is not – a set of statements can be evaluated in any order and the program would still work. That is, in an imperative program we often see code like this:
f()
g()
But we are not sure whether it matters whether f() is called first or not.
This ambiguity arises because the program does not express the dependency
relationships between the entities it manipulates. Those relationships are in
the programmer’s head or on a whiteboard somewhere, and they have done a bunch
of computation outside of the program to determine what the program itself
should look like. The program expresses the solution the programmer invented,
rather than solving the problem itself, and crucial constraints on the design of
the solution are omitted.
In a functional language like Haskell, where functions are lazy and have no side effects, the only way to force two expressions to run in a certain order is to make one depend on the other, either by taking its output as input:
g(f())
Or by making one expression conditional on the other:
if f() {
g()
}
(These examples are generic pseudocode, not executable Haskell.)
In the above construction that simply calls f() and then g(), it’s not clear
from the code itself whether f() can be called later or removed from the
program entirely. The only reason it could be necessary to place it before g()
is that it has some side effect that affects the result of g(). The only way
to tell for sure is to run the program, possibly via a test harness, and check
what its cumulative side effects are, for example checking the state it leaves a
database in.
The latter two constructs express, via the syntax of the program, that g()
depends on f() in ways that are far stronger than simply listing them one
after the other. They make it clear that the result of the program will be very
different if f() is removed; if its output is fed directly into g(), or used
to decide whether to call g() at all, then we know it must affect g()’s
output in some way. This dependency information is encoded in the program
itself, and not enforced implicitly via a test suite or manual QA process.
Stuck in the imperative mindset, I was convinced the solution had to lie in the order I was running these Redis commands in, that if I could just find the right recipe and run commands at just the right times, the problem would be solved. But having spent the last year thinking about things like promises and Make, I suddenly saw the problem instead in terms of dependencies. Just as I have done in the examples above, I thought about the dependencies between values explicitly, then tried to see if I could rearrange that graph to bring all the writes together, and lo and behold the right answer just fell out.
The funny thing is, I’m not sure anyone would call my final code for DELETE a
‘functional’ program; it’s still very much stateful imperative code, full of
side effects and mutable data structures. But I would argue that it’s more
functional than the original DELETE code. In the original, the order of
statements is very important, and there are few places where an explicit
dependency is drawn between two operations by having values defined in terms of
other values. Frequently, getting a correct value depends on some SREM or
HSET side effect having been executed before its calculation, and that
dependency is entirely encoded by the statements executing in a certain order
rather than by relationships between values.
But in the second example, far more of the statements that are order-dependent
are forced to be so by having values defined in terms of other values. The
calculations for empty, remaining and mtimes depend explicitly on the
value of children, thus forcing children to be calculated before them. Once
we get to the write operations, those can be executed in any order and we can
tell this because there is no write operation that uses the value of another
write operation as its input. We can reorder the statements for the writes and
the program will still work. Whereas, if we reorder the statements for the
reads, we will get an ‘undefined variable’ error because a value they depend on
is not available yet. We get direct feedback from the programming language that
an operation makes no sense, rather than being able to freely reorder statements
and having to check the database to see what went wrong. If we were writing this
in a compiled language, this error could even be flagged by static analysis
without running the program at all.
In other words, the program uses functional techniques to indicate and force the correct order of operations, rather than imperative ones, and makes it clear where dependencies exist and where they do not. Instead of using the database as the working space to incrementally figure out which changes to make, we’ve moved all that work into the program’s memory where we can derive values from one another and compute a single set of changes to make at the end.
Once you start thinking in terms of dependency graphs, you start seeing them everywhere. They’re a great tool for figuring out how you can optimise programs, and make them more explicit and resistant to people accidentally introducing sequencing bugs later. They encode the problem constraints directly in the program, and get you a step closer to letting the computer solve your problems for you.
