Skip to content
Snippets Groups Projects
Select Git revision
  • master default protected
1 result
Blame Permalink
Code owners
Assign users and groups as approvers for specific file changes. Learn more.
README.md 7.42 KiB

Project 5: Transactional Support From a Log

v1.12

Overall Project Description

You will be implementing a fully-replicated transactional key-value store. This implies:

  • reads and writes are only valid if in a committed transaction
  • clients parse all new log entries, applying committed transactions locally.

We will be using the log as a dumb consistent ledger. To this end we need to (1) create a way to commit arbitrary strings in the log, and (2) expose the shared log to clients.

We are going to handle both of these through a new method in the Client service: Cmd. Cmd takes identity, a string command, and a seen value that specifies the prefix of the shared log seen by the client previously.

This function:

  • commits the string onto the shared log,
  • synchronously waits until it has been committed, and then
  • returns everything in the log from slot until the slot containing the new command.

The client can use this to create local copy of the log that it will use to implement and interpret gets, puts, and transactions.

Cmd and associated type definitions have already been added to client.proto.

The Software Stack

The straightforward way to integrate transactions is to build them directly into the log implementation. Primarily, this allows dependencies between commits and transactional writes.

However, a shared log is a powerful abstraction that can be used to implement all sorts of functionality even in it's cleanest, most generic form. We are therefore going to layer the transactional functionality on top of the generic string interface described above.

Our simplified system is going to implement both a key-value store and transactions by layering them over the simple string interface supported by the Cmd interface described above. The client will construct a local representation of the log by retrieving and piecing together segments of the shared log.

Once the local log is created, the client can process operations, in order, to interpret transaction commands, determine whether they commit, and update a local copy of a key-value store that reflects committed transactions.

Unfortunately, Epaxos does not support a totally ordered log, instead it has a 2-D log and only supports a partial order over those entries. We are going to fix this in order to support the strict serializability used in Tango. We are going to address this through two mechanisms:

  • Create per-replica total orderings by adding something like inst.Deps[inst.Rep] = inst.Slot - 1 (aka "Chuck's Hack") before creating edges in the execution graph. This ensures that all instances of a single replica execute in order.
  • Send all client operations to replica 0. This is essentially dumbing down Epaxos to make it execute more like MultiPaxos.

Aside from Chuck's Hack, replica.go should only be modified to deal with the new Cmd request. This means ensure that the command will be sent through the BigChan and processed like gets and puts, and ensure that it will be executed. Execution of a Cmd means only that the log segment delimited is added to ClientReply.

The Log