DistOS 2023W 2023-03-27

Notes

Zookeeper & Delos
-----------------

Consensus
 - why is this such an important problem in distributed OS?

Notice that consensus isn't a concern in single-system operating systems
 - we get "consensus" simply by having one copy of data

But in a distributed system we have copies of data & distributed state
 - so if we want all of the system to be in the "same" state, we need consensus
 - consensus has to be constructed, it isn't the natural state of the system

Consensus in natural systems can take interesting forms, not really like how we currently do things in computers
 - consider flocking behavior

Artificial systems typically need greater precision in their consensus, and so they need different solutions than natural systems

In the papers, don't focus on the algorithms
 - instead focus on the APIs, abstractions
 - how do they compare?
 - compare "file-like" abstractions to "log-like" abstractions

What is the real difference between a log and a file?

Groups go until 12:20

AFTER GROUPS

What do the APIs look for the different systems?

Chubby: whole-file API with exclusive access (locking)
Zookeeper: whole-file API without locking
Delos: shared log API

Why does Zookeeper avoid locking?
 - slow clients can block everyone else

Wait-free access vs blocking

With chubby, a client can try to do something and will be blocked if the resource is taken

With zookeeper, operations can always work, so if you want locking mechanisms you have to build on top.  Only guarantee is there is a fixed, universal order to writes, and when you read you get the same data.

Key addition: watching nodes

With blocking, you are "notified" when the resource is available, you just can't do anything in the meantime

With "watching", you get a callback when state has changed, and you can work in the meantime on other things

Which do you think is easier to use, Zookeeper or Chubby?
 - chubby is easier, because blocking semantics are normally easier to reason about, that's why we traditionally use locks for so many concurrency problems
 - zookeeper is lower level in a sense, you have to build the abstraction you want on top of it (and potentially can get it wrong)
    - locks are built on top of zookeeper, are not a fundamental part of it
    - but zookeeper gets more flexibility, allows for greater optimization based on application needs

So what is Delos?
 - going lower level than zookeeper, to the fundamentals of what is needed for consensus
 - abstraction is appending to, sealing, and checking the end of a log file
   (Loglet)

Why is a log more fundamental than a file for consensus?
 - keeps track of time
 - keeps track of *state changes*

With a file, you only get the most recent state, you can't see the history.

You can implement files on top of logs
 - that's a log-structured filesystem

Fundamental nature of consensus is an agreement over the the time of events
 - and that's what hard in a distributed system, every view of events is relative
 - if you make a local change to state and hear about a remote change of state, did your local change happen "before" or "after" the remote change?
   - really matters if you both modified the same thing or related things

If you have a globally consistent view of events, this never happens
 - you always know who did what when relative to the other
 - so if there is a conflict, you know who was first or last and can resolve it

A file is just the result of a sequence of state updates
 - so if you know the sequence of updates, you know the contents of the file

So why bother with focusing on logs?
 - because we can build various consensus algorithms on top of it, clients just see a log, and different ways of building the log will have different performance characteristics