Test3 Study Guide

PDF

Test 3 study guide

NOTE: Some of these answers were produced collaboratively amongst students in the class. I do not claim authorship of every answer.

Summary

• Giant Scale Services
  • Question 1
  • Question 2
    • Part A
    • Part B
• Map Reduce
  • Question 3
  • Question 4
• CDN Coral
  • Question 5
    • Part A
    • Part B
    • Part C
• TS Linux
  • Question 1
• PTS
  • Question 2
  • Question 3
    • Part A
    • Part B
• LRVM
  • Question 1
    • Part A
    • Part B
    • Part C
    • Part D
• RioVista
  • Question 2
    • Part A
    • Part B
• Qick Silver
  • Question 3
    • Part A
    • Part B
• Security Principles
  • Question 1
  • Question 2
    • Part A
    • Part B
    • Part C
    • Part D

Giant Scale Services

Question 1

The traffic bottleneck seems to be network bound, not IO bound. Also, read-only queries tend to outnumber writes.

Question 2

Part A

For 1 query, 150TB/10TB per machine means 15 machines. To serve 1000 simultaneous queries we need 15000 machines

Part B

If all the 15 machines were holding different data, 999 queries could be handled simultaneously. If they all handled the same data, 1000-15=985 queries can be handled simultaneously.

Map Reduce

Question 3

• After a timeout has been reached, the master would find the worker A is dead, and would reschedule the task to another worker.
• Before that new worker started, the master would need to clean up the intermediate blobs left by failed worker. How that is done will be implementation specific.
• The new worker would then start, complete, and store its output in R intermediate blobs, then report back to the master
• The master would then inform worker B about the location of the files and would schedule them to start execution

Question 4

After a timeout is reached, the master will reschedule tasks. There are no risks for conflicts because the master can simply ignore redundant messages. Redundant completion messages from mapping tasks can be safely ignored because they are idempotent. Once the master receives the first completion message from a reduce task, it renames the output of the reduce task to the be the final output and any subsequent messages are ignored.

CDN Coral

Question 5

Part A

200 is the hash of the content and 10 is the node id where the content is stored. The KV pair can be stored on node 200, assuming the L value hasn’t been reached.

Part B

Alex will to store (200,1) on node 200. Noah will try to store (200,2) on node 200. The request will flow through node 100, then node 150, then node 200. Node 200 will respond saying its l value is full and it can’t store another KV pair for 200, so Noah’s request will backtrack and store (200,2) on 150.

Part C

Diana’s request will go through nodes 100 and 150 on the way to 200. Node 150 will respond early and say the content is also stored on node 2

TS Linux

Question 1

• A short overshoot provides higher timer resolution but increased overhead
• A longer overshoot reduces overhead with an increased latency

PTS

Question 2

1. Computation graph of PTS resembles a UNIX socket graph so transition from UNIX sockets to PTS is realtively easy

2. Both can be accessed from anywhere on the network

3. UNIX sockets do not support many to many connections while PTS Channels allow multiple producers and multiple consumers

4. Objects in the PTS Channel are sorted by timestamp while UNIX sequenced are not.

Question 3

Part A

This question is worded weird, but ts1 will be the minimum

Part B

yes, if the two Channels are in a group and one channel is designated as the anchor, then we only need to groupget on the anchor

LRVM

TODO: Double check this section

Question 1

Part A

Since we passed the end_transaction call, no_flush was not set, and m1 is in the range set by set_range, we know the changes will be copiedvalue of m1 will be 12.

Part B

Since we passed the end_transaction call, no_flush was not set, and m2 is not in the range set by set_range, we know the value of m2 will be 11.

Part C

m2 would equal 16. Regardless of interleaving, t1 doesn’t track m2, nothing will be persisted. t2 does track m2 and it’s change to 16 will be persisted before the crash.

Part D

t2 doesn’t involve m1 so we can ignore that. Since t1 crashed before it persisted its changes, m1 would still equal 10.

RioVista

Question 2

Part A

Inside of a transaction block, the user would need to call multiple set_ranges on the segment changes it wants to make atomic to include them in the single transaction.

Part B

Yes, RioVista needs to replay the undo logs during crash recovery

TODO: Review RioVista GC

Qick Silver

Question 3

Part A

TM (C) -> TM F --> TM D1
               \-> TM D2

Part B

The client, as the owner of the transaction, should delegate the cleanup tasks to a more stable server F

Security Principles

Question 1

1. User presents username,password to the system
2. The password is used as the handshake key and the username serves as the client id
3. By using the password to encrypt a message and sending the username in plaintext, the bind protocol is used to mutually authenticate between venus and vice.
4. Vice encrypts the secret token and clear token through the user password and sends it to venus. Venus stores these for the duration of the login session and the clear token contains the necessary handshake key to establish rpc connections.
5. Now the clear token has provided a handshake key and the secret token has provided a client id for the instance of the login session, the workstation is now prepared to use RPC for the file transfers.

Question 2

Part A

• HKC is the encryptor used by the client
• HKS is the encryptor used be the server, ideally the same as HKC
• Xr is a random number used to challenge the authenticity of the server
• Yr is a random number used to challenge the authenticity of the client

Part B

Because we already in the middle of an RPC session, we will use sk as the key.

Part C

The server will respond to Mallory with the result, but it will be encrypted with the session key. Since she does not have the sk, she won’t be able to access the data.

Part D

AFS will send the same response to Alex who will be able to read it and procede with the RPC interaction.