_____________

  SECTION7

  Raymond Cheng & Irene Zhang
_____________


Table of Contents
_________________

1.) Lab Architecture
2.) Shardmaster
.. 2.1 Interface
.. 2.2 Replication
.. 2.3 Balance
3.) Lab 4b architecture
.. 3.1 Client-side
.. 3.2 Server-side
.. 3.3 Moving configs



1 Lab Architecture
==================

  - Shards that each hold a subset of the keys
  - replica groups of storage servers
  - Each replica group gets assigned a few shards
  - Centralized shardmaster that holds the assignment between shards and
    groups (Part A)
  - Replica groups serves keys for their assigned shards (Part B)


2 Shardmaster
=============

  - system moves through sequence of configurations of mapping between
    shards and groups. first config is 0, all shards = gid 0
  - shardmaster dictates what configuration the system is in


2.1 Interface
~~~~~~~~~~~~~

  - JOIN(gid, []servers)
  - LEAVE(gid)
  - MOVE(shard id, gid)
  - QUERY(number) if -1 or bigger than known config, return biggest


2.2 Replication
~~~~~~~~~~~~~~~

  - use your kv store from last lab
  - one instance per config or one instance per change will work
  - so either replace your put/get calls with shardmaster calls
  - or use instances to agree to next config (but remember if you lose,
    you might have to change your next config membership)


2.3 Balance
~~~~~~~~~~~

  - Want to ensure that group sizes are balanced. tests will check!
  - And ensure you move as few shards as possible with each change
  - I just took one shard from the largest group each time, but there
    are other ways to do it
  - small number of shards (~10), so no need to do anything fancy like
    consistent hashing


3 Lab 4b architecture
=====================

3.1 Client-side
~~~~~~~~~~~~~~~

  - key2shard maps Get and Put keys to a shard
  - shardmaster maps shards to replica groups
  - client side is already pretty much set up, but you have to implement
    at most once RPC yourself


3.2 Server-side
~~~~~~~~~~~~~~~

  - implement key-value store just like last lab with the Paxos log
  - tick() should check config from shardmaster occasionally
  - on new config, stop accepting requests for shards you lost and go
    get latest version of shards you gained (diff the new config with
    the old one)


3.3 Moving configs
~~~~~~~~~~~~~~~~~~

  - Be sure the move from one config to the next biggest one! What
    happens if you dont?
  - You don't have a leader, so all replicas may try to do a config
    change at once, You will probably want to coordinate this among the
    replicas in a group
  - You probably want to stop taking client requests during a config
    change. It depends on your design.
  - You need to make sure that when you move a shard from another group:
    (1) the group stops accepting requests for the shard at the same
    time and (2) the group is in the same config as you. So you either
    want to retry or start a thread to bring the group up to date
  - Think about what happens if the group is ahead of you in configs by
    a lot (what if the shard moved to you then back again?)
  - Locks are tricky. When one group calls another to move, if the
    second group has to move some shards from the first group, what
    happens? Make sure there are no deadlocks
  - Think about what happens if the move message fails. What should the
    RPC semantics for moving shards be?