Recitation

Recitation 001

Slides

// QUESTION: "so the layers that don't need a protocol field are transport & up." is this sentence correct? https://edstem.org/us/courses/26903/discussion/1719927

// QUESTION: "There is only one data-link protocol" is this correct?

// QUESTION: do we consider the step where the host determines whether to use TCP vs UDP as part of the transport layer or the network layer?

Recitation 002

Slides

FAQ

LSP: live sequence protocol (for udp)

// QUESTION: distinguish between server and client

// QUESTION: is that all in the slide for all checkpoint in P1? is the assignment fully established with all info, tests, specification avaliable? Only P1-PartA, and P1-Checkpoint released? What is PartB, any related?

Protocol Data

• Message Type: connect, data, ack (received previous message), cAck (received all message up until this point)

• Connection ID: uniquely identify each client-server connection

• Sequence Number (sn): increments with each data message. // QUESTION: right? only for data message

  • Initial Sequence Number (isp): randomly generated //QUESTION: Why track isn separately (make sense to not track, but just copy whatever for Ack, if not arrive in order) // TODO: understand (why random, overflow?, no nounce)

• Payload size (verification):

  • If actual payload is smaller: drop message
  • If actual payload is larger: accept and truncate it

• Checksum (verification): if doesn't match, drop message (check after truncate payload size). Check with CalculateChecksum().

• Payload: data

Protocol Behavior

• Message size: limited to single UDP (1000 bytes)

• Ack:// QUESTION: right?

  • only ack to data message
  • do not ack to any message dropped due to: corrupted payload, outside of sliding window

• Sliding Window Protocol: the window size determines the queue size for receiving message in order (by counting sequence number // QUESTION: right) // QUESTION: will older message be in window?

• Max Un-ACKed Messages: 2 (must be smaller than window size). Track using sequence number // QUESTION: both max un-acked and sliding window is for sequence number, don't count duplicate?

• Epoch Event: to deal with dropped packet, and check if connection is live (Server and client tracks and fires their epoch events independently.)

  • Resend: for every unAcked message, we will resend message using exponential backoff (only for data and connect message) // QUESTION: only for data connect right?
  • Exponential Backoff: the first resend will wait 1 epoch, second resend will wait 2, then 4, then 8, ... (separate for each message)
  • Time interval: time between two epoch is fixed // QUESTION: logical time stamp or physical? // QUESTION: do epoch sync?

// TODO: last slide

Transmission Establishment

• Connect: send until epochLimit.

  • Only establish one connection when duplicate
  • No exponential backoff (no backoff at all, just resent in every epoch)
  • Repeat until we receive an Ack from the server, or reach epochLimit

• Disconnect: if no data message is sent in the past epochLimit epoch.

• Heartbeat Message: a Ack message with sequence number 0

  • send if: no data message is sent in the last epoch

Useful Tools:

• Marshal: a library to convert go datastructure to byte array for transmission

• time: go's package to keep track of time for epoch

• Read(), Write(), Close(), CloseConn(): library functions // QUESTION: is this API or something we need to write

  • Handout version: You can assume nothing will be called after Close() (so undefined behavior is OK).
  • API version: If Read(), Write, Close(), or CloseConn() is called after Close() is called, they must either return an error, or never return anything

Recitation 003

Proof of work: given $M$, and unsigned integer $\max$, find $0 \leq n \leq N$ such that $hash(M, n)$ is minimum. Goal: build your own server cluster for mining pool.

Details:

• When server lost contact to minor: re-assign assigned job to other minor

• When the server loses contact with a request client: drop the client's job (wait for minor to complete and ignore result)

• load balance: design by yourself (should clearly document it)

  • small request goes first
  • but larger request don't starve for

• there is hiddent tests

• you should: 360 lines of code, 700 lines of test

Recitation 004

In this project you will implement Raft

Checkpoint: election, heartbeat

• leader election: raft state machine for election

• RequestVote RPC: requesting leadership votes

• Heatbeats: AppendEntries RPC, timeout for detect leader failure to trigger re-election

Final: log replication

Raft:

• Server State:
  • All Servers
    • const numberOfNodes int (must be odd// QUESTION)
    • track me ID
    • track log [](index int, term int, payload []byte) (on disk)
    • track maxTerm int (sync with disk)
    • track maxIndex int (sync with disk)
    • track votedFor int (persist on disk)
  • Invariants
    • There is only one leader for one term globally
    • Logs does not have holes
    • Logs are sorted by the terms
    • Same index and terms must store the same command, and everything before is the same
  • MessageTypes
    • Request(payload []byte)
    • AppendLog(id ID, term int, prevTerm int, prevIndex int, payload []byte)
    • AppendAccept(id ID)
    • AppendReject(id ID, needIndex int)
    • RequestVote(id ID, term int, index int)
    • AcceptVote(id ID)
  • Leader:
    • BecomeLeader:
      • track numberOfAccept int
      • track requestQueue payload[]byte
    • ReadRequest(payload []byte):
      • log.append(payload)
      • notifyHeartbeatCh(1)
      • try append message to notifyHeartbeatCh
      • Wait:
        • track numberOfAccept
        • On AppendAccept(_ ID)
          • increse numberOfAccept
          • if numberOfAccept > numberOfNodes / 2: finish Wait
        • On AppendReject(_ ID, needIndex int)
          • if needIndex >= log.size()-1: panic("index out of bound")
          • respond AppendLog(id=me ID, term=maxTerm int, prevTerm=log[needIndex-1].term int, prevIndex=needIndex-1 int, payload=log[needIndex].payload []byte)
    • On Request(payload []byte):
      • requestQueue.append(payload)
    • On AppendLog(id ID, term int, _ int, _ int):
      • if term == maxTerm && id != me: panic("two leader in one term")
      • if term > maxTerm, set term, set votedFor=-1, BecomeFollower, re-process AppendLog(_ ID, term int, _ int, _ int)
      • Send commit, Respond request // TODO: how to send commit in subsequent AppendEntries RPCs
    • On AppendAccept(_ ID)// TODO
    • On AppendReject(_ ID, _ int)// TODO
    • On RequestVote(id ID, term int, _ int):
      • if term > maxTerm: update maxTerm to term, set votedFor=-1, BecomeFollower, respond AcceptVote(id=me ID)
      • else: don't respond
    • On AcceptVote(id ID)// TODO
    • On HeartbeatTimeout:
      • if <- notifyHeartbeatCh has message, send AppendLog(id=me ID, term=maxTerm int, prevTerm=log[log.size()-1-1].term int, prevIndex=log.size()-1-1 int, payload=log[log.size()-1].payload []byte)
      • if none, send anyway...
  • Follower: default
    • BecomeFollower
    • StartElectionTimeout:
      • Random count down 150ms~300ms
      • If countdown succeed, then BecomeCandidate
    • On RequestVote(id ID, term int, index int):
      • if term > maxTerm: update maxTerm to term, set votedFor=-1
      • if votedFor == -1 || votedFor == id and maxTerm > term || (maxTerm == term && log.size()-1 > index): set votedFor=id, respond with AcceptVote(id=me ID) and reset StartElectionTimeout, else no respond
    • On AppendLog(_ ID, _ int, prevTerm, prevIndex int):
      • if term > maxTerm: update maxTerm to term, set votedFor=-1, BecomeFollower // QUESTION
      • track appendStack
      • reset StartElectionTimeout
      • if non-empty, and index <= <index, _, _>+1, write to log, respond AppendAccept(id=me ID). If log already written://TODO: choose the newer term? do a running checksum?
      • if index does not match last index+1, respond AppendReject(id=me ID,
  • Candidate:
    • On BecomeCandidate
      • maxTerm++, votedFor=-1
      • send RequestVote(id=me ID, term=maxTerm int, index=log.size()-1 int) to all nodes (including itself)
      • listen for majority of AcceptVote or NewElectionTimeout (// QUESTION: assuming odd?)
      • if majority AcceptVote, BecomeLeader
    • On RequestVote(_ ID, _ int, _ int):
      • reject vote // QUESTION
    • On NewElectionTimeout
      • BecomeCandidate
    • On AppendLog(id ID, term int, _ int):
      • if term >= maxTerm: update maxTerm to term, set votedFor=-1, BecomeFollower, re-process AppendLog(id ID, term int, _ int)
      • else: respond AppendReject(id=me ID, needIndex=-1 int)