Time and Space Efficiency, an Applied Example: Part 3

Reading Time: 9 minutes
fireflies
This beautiful image painted by twitter.com/mairperkins.

This is the third post in a three-part case study. We walk through time and space efficiency considerations as we write an in-memory database.

In the previous post of this series, we implemented transaction support an in memory database. However, we did it in an extremely space-inefficient way. In case you read that post a while ago, here are a few quotes to refresh your memory:

Transactions allow us to stage a series of changes to the database that we can either commit (save) or roll back (discard) all at once. We begin the transaction by calling .begin, save the changes of the transaction by calling .commit, or discard those changes by calling .rollback.

[But, in our previous implementation], when we open our first transaction, we immediately double our database footprint. When our database only has three things in it, maybe this isn’t a big deal. If our database had 100,000 things in it, this would become a much bigger deal.

So what are we going to do about this extremely space-intensive solution?

Recursion to the rescue!

What we’ll do next: we’ll make it possible to stack multiple transactions on top of each other like this:


def test_nested_transaction
db = Database.new
db.set "Pacific", "Baza"
assert_equal(1, db.count("Baza"))
db.begin
db.set "Black", "Baza"
assert_equal(2, db.count("Baza"))
assert_equal("Baza", db.get("Black"))
db.begin
db.set "Jerdons", "Baza"
assert_equal(3, db.count("Baza"))
assert_equal("Baza", db.get("Jerdons"))
db.rollback
assert_equal(2, db.count("Baza"))
assert_equal("Baza", db.get("Black"))
assert_equal("Baza", db.get("Pacific"))
db.commit
assert_equal(2, db.count("Baza"))
assert_equal("Baza", db.get("Pacific"))
assert_equal("Baza", db.get("Black"))
assert_equal("NULL", db.get("Jerdons"))
end

Then, when we need to know the state of the database at the current transaction, recursively look back through the database versions to get the most recent value at each key. You can see how we do this in the merge_candidate and count_candidate methods in the implementation below.

Then, inside of commit, we squash down the latest transaction change set onto the previous one. In rollback, we delete the latest transaction change set.


class Database
def initialize
@count_versions = [Hash.new(0)]
@db_versions = [Hash.new()]
@tier = 0
end
# CRUD COMMANDS
def set(key, value)
@db_versions[@tier][key] = value
@count_versions[@tier][value] += 1
puts "Current state of database: #{@db_versions.inspect}"
return nil
end
def get(key)
puts "Current state of database: #{@db_versions.inspect}"
merge_candidate.fetch(key, "NULL")
end
def count(value)
puts "Current state of database: #{@db_versions.inspect}"
count_candidate.fetch(value, 0)
end
#TRANSACTION MANAGEMENT
def begin()
@db_versions.push(Hash.new())
@count_versions.push(Hash.new(0))
@tier += 1
puts "Current state of database: #{@db_versions.inspect}"
return nil
end
def rollback()
if @tier == 0
return "No transaction in progress"
end
@db_versions.pop
@count_versions.pop
@tier -= 1
puts "Current state of database: #{@db_versions.inspect}"
return nil
end
def commit()
if @tier == 0
return "No transaction in progress"
end
@db_versions[2] = merge_candidate(@tier, @tier1, @db_versions[0])
@count_versions[2] = count_candidate(@tier, @tier1, @count_versions[0])
@db_versions.pop
@count_versions.pop
@tier -= 1
puts "Current state of database: #{@db_versions.inspect}"
return nil
end
def merge_candidate(start_tier=@tier, end_tier=0, merge_item=@db_versions[end_tier])
if start_tier == end_tier
return merge_item
else
step = @db_versions[start_tier].merge(@db_versions[start_tier1]) { |key, canonical_value, transactional_value|
transactional_value || canonical_value
}
return merge_candidate start_tier1, end_tier,step
end
end
def count_candidate(start_tier=@tier, end_tier=0, merge_item=@count_versions[end_tier])
if start_tier == end_tier
return merge_item
else
step = @count_versions[start_tier].merge(@count_versions[start_tier1]) { |key, canonical_value, transactional_value|
canonical_value + transactional_value
}
return count_candidate start_tier1, step
end
end
end

view raw

database.rb

hosted with ❤ by GitHub

Now we’ll be keeping each of our change sets in separate hashes:

A Sidenote on API Design: You’ll notice that we also introduced the concept of a @tier. This keeps track of which transaction branch we are on, so we can do nested transactions.

I get that, when I add the code for @tier, it kind of feels like I did the code sample version of this:

How to draw an owl: 1. Draw two circles 2. Draw the rest of the fucking owl

In our previous implementation, we would always make our changes on whatever the last hash in the database list was, and then merge those changes with the second to last hash in the list. Technically, we could still do that, indexing our @db_versions array with -1 and -2 all over the place.

If a new developer were to show up, they’d have to figure out the significance of these unlabeled variables with values of -1 and -2. To make this easier, we assign a name to each piece of our code—preferably a name that describes what that piece of code means. I chose @tier to represent this concept, like the tiers of this cake tray:

So @tier represents the number of our latest transaction: the highest tier on the cake tray. And it allows us to manage nested transactions so we can do stuff like this:

Wait, what about deletion?

You’ll notice that we have been omitting key deletion so far in our transaction examples.

If we delete keys only from the top-tier change set, our current implementation of merge_candidate could still have values for those keys, provided that those keys are still present at a lower tier.

We could also try “overwriting” those keys at a lower tier by setting the key’s value to nil in the database. But, as we discussed in the previous post, that equates a key with a nil value to no key at all in our database.

If we were to do that, we need to make sure that every use case would treat those two things the same. And even if they did, we then end up keeping the keys for key-value pairs that we have deleted, which takes up extra space.

We need a way to delete the keys, so we get the behavior described in this test:


def test_transaction_with_deletion
db = Database.new
db.set "Homing", "Pigeon"
db.set "Fantail", "Pigeon"
assert_equal(2, db.count("Pigeon"))
db.begin
db.delete "Fantail"
assert_equal(1, db.count("Pigeon"))
assert_equal("NULL", db.get("Fantail"))
db.rollback
assert_equal(2, db.count("Pigeon"))
assert_equal("Pigeon", db.get("Fantail"))
end

Here is what we’ll do: inside the .delete method, we’ll add the key being deleted to a list of deletions. Then, in .merge_candidate, once we have our view of the database from the perspective of our current transaction, we rip out the keys in the deletion list before returning the finished hash:


class Database
def initialize
@count_versions = [Hash.new(0)]
@db_versions = [Hash.new()]
@deletion_keys = [[]]
@tier = 0
end
# CRUD COMMANDS
def set(key, value)
@db_versions[@tier][key] = value
@count_versions[@tier][value] += 1
return nil
end
def get(key)
merge_candidate.fetch(key, "NULL")
end
def count(value)
count_candidate.fetch(value, 0)
end
def delete(key)
value = merge_candidate[key]
if value
@deletion_keys[@tier].push(key)
@db_versions[@tier].delete(key)
@count_versions[@tier][value] -= 1
return nil
else
return "That key isn't in the database!"
end
end
#TRANSACTION MANAGEMENT
def begin()
@db_versions.push(Hash.new())
@count_versions.push(Hash.new(0))
@deletion_keys.push([])
@tier += 1
return nil
end
def rollback()
if @tier == 0
return "No transaction in progress"
end
@db_versions.pop
@count_versions.pop
@deletion_keys.pop
@tier -= 1
return nil
end
def commit()
if @tier == 0
return "No transaction in progress"
end
@db_versions[2] = merge_candidate(@tier, @tier1, @db_versions[0])
@deletion_keys[1].each{|key| @db_versions[2].delete(key)}
@count_versions[2] = count_candidate(@tier, @tier1, @count_versions[0])
@db_versions.pop
@count_versions.pop
@deletion_keys.pop
@tier -= 1
return nil
end
private
def merge_candidate(start_tier=@tier, end_tier=0, merge_item=@db_versions[end_tier])
if start_tier == end_tier
@deletion_keys[1].each{|key| merge_item.delete(key)} if @deletion_keys[1]
return merge_item
else
step = @db_versions[start_tier].merge(merge_item) { |key, canonical_value, transactional_value|
transactional_value || canonical_value
}
return merge_candidate start_tier1, end_tier,step
end
end
def count_candidate(start_tier=@tier, end_tier=0, merge_item=@count_versions[0])
if start_tier == end_tier
return merge_item
else
step = @count_versions[start_tier].merge(merge_item) { |key, canonical_value, transactional_value|
canonical_value + transactional_value
}
return count_candidate start_tier1, end_tier,step
end
end
end

view raw

database.rb

hosted with ❤ by GitHub

This is starting to shape up pretty well.

A Sidenote on API Design: The recursive methods merge_candidate and count_candidate have a lot of code in common. Why didn’t I factor out a method that takes a hash and a block, and have each of these methods call that one rather than possessing their own logic?

Before I do that refactor, I want to be certain that the operations I am performing are, in fact, the same. If it turns out later that I was wrong, I have put either myself or my team in a bind, because factoring down (separating things) is often significantly harder than factoring up (combining things). I explain my cost evaluation for refactors in this keynote talk on the technology and psychology of refactoring.

Full disclosure: I stand by this refactoring choice, but not everyone agrees with it. I implemented the in-memory database you see here in four hours as a code challenge in an interview process, and I think this choice not to refactor might have been one of the reasons the company did not move forward with me after this code challenge 🙃.

Nevertheless I thought the exercise valuable to share as a demonstration of the way I consider space and time constraints while writing software.

That brings me to a time efficiency constraint of this implementation:

Both merge_candidate and count_candidate do an iterative lookback through each individual transaction currently open for the database. Iteration is frequently a culprit for speed leaks in code that needs to be super fast. Numpy gets around this by dropping into C. Dask gets around this by parallelizing iterative processes across cores. Even if we don’t mess with threads or shell out to a faster language, are there things we could do to speed up our code?

We could try a few things.

For one, we could stop comparing keys for which we already have a value from a more current transaction. I chose not to do this for a few reasons:

  1. The list of keys not to consider could itself significantly increase the database memory footprint
  2. We’d still have to iteratively remove those keys from each less recent version
  3. When we remove those keys, we’d have to store them rather than delete them because they’d still be in effect if more recent transactions were all rolled back.

So I’m not convinced it would save any time, and it would definitely cost space.

How about caching? We could cache the output of merge_candidate and count_candidate, then invalidate the cache anytime a write (.set or .delete) is called. That would slow down the writes to speed up the reads (like .get and .count) since we currently call those candidate methods inside the read methods.

Before I start down any of these routes, though, it’s wise to determine the benefit I would derive from doing it.

So I’m making a risk calculation: “How likely is it that a user has 100,000 transactions nested inside each other in this database, and what are the consequences if they do?”

Consequences: reads will be slow. Maybe prohibitively slow.

Likelihood: please let me know if you think of something here, because I’m coming up blank on a scenario where it would be wise to open 100,000 transactions nested inside one another.

Maybe we would ship this to users, I’d be wrong about that being an unlikely thing, and then we’d need to consider some of our proposed solutions. But before I introduce the complexity of cache invalidation to a code base, I need solid evidence that it’s solving a problem. If the database is slow in a scenario that no one gets into, that’s not a problem.

Again, not everyone will agree with this choice. A comment from an interviewer during my code review tipped me off that my decision here was probably another reason that the company did not move forward with me from this code challenge 🙃.

Conclusion

Since this is an implementation walkthrough, I don’t know how much it makes sense to write a conclusion. That said, I hope the decisions we’ve discussed in the time and space efficiency posts has reinforced a few ideas:

  1. We sometimes face a tradeoff between a time-efficient implementation and a space-efficient one.
  2. Even as we try to build a small, fast program, it makes sense to optimize for a clear API, which will save ourselves and other developers valuable time when maintaining this program in the future.
  3. When a program can be made smaller or faster, we want to consider how beneficial those changes will be. They may not be worth the risk.

If you enjoyed this series, you might also like:

This three-part series on API Design

This post on diagramming data

This close (uh, VERY close) look at part of the Scipy CSR Matrix

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.