SOSP'13 papers

Some useful links:
SOSP program page: http://sigops.org/sosp/sosp13/program.html (paper, slides, online questions and talks)
syslog: live from SOSP 2013: http://www.syslog.cl.cam.ac.uk/2013/11/04/live-blog-from-sosp-2013/




Tango: Distributed Data Structures over a Shared Log
Microsoft Research and Mircorsoft
Presented by Vijay

This is built on the same principle of log structure file system, but is distributed. It is built on SSD arrays thus random reads are fast (necessary for a log structure)

They keep a global sequence number to achieve serviceability. However, writes of different client and different sequence number will occur at different location of the log, thus could happen concurrently.
Transaction is implemented in an optimistic fashion:
A transaction starts with a transaction begin block in the shared log, followed by a read block which records the version number of all the objects this transaction is going to read (thus depend on), then followed by whatever updates this transaction made. Then every client could commit this transaction if the objects' version in the read block hasn't changed, without any coordination. If the objects in the read block has been updated, then the transaction just abort and restart again.

They claim that garbage collection is not a big problem because on flash cards you can do thousands of operations per second even with garbage collection going on.

This makes it easier to build distributed data service. They have built ZooKeeper in ~1000 lines of code on top of this. It is also likely to have higher performance because in a traditional distributed consistency protocol, communication overhead is high with many participating nodes, thus the good performance provided by SSD may  not be fully utilized.



The salable commutativaty rule: designing scalable software for multiple Processors (best paper)
Robert Morris, MIT CSAIL

Motivation:
Instead of relying on running workload to find scale bottleneck, we should look at interface design and its implementation.

Proved by simulation construction:
Whenever interface operations commute, they can be implemented in a way that scales.
      e.g., create with lowest fd doesn't commute, but create with any fd does commute
      Intuition behind: if operations commute, then the results are independent of order, thus you can implemented it in a communication-less way, thus scale well.

Commutativity are sensitive to operations, arguments, and states. (Thus more or less a dynamic thing..)

Commutor:
Take specification (e.g, POSIX, in the form of symbolic model) and implementation (e.g., Linux) as input, and output all scalability bottlenecks. It finds the bottleneck by firsty check the interface and analyze all communativity conditions (e.g, for rename, commute if both source file exist and name not the same, or neither exist, or both call self-renames, etc.) then exhaustively generate test for all possible pair of cases, see if they are conflict-free (i.e., no accessing same state), i.e., commute, and output these compute test. Finally, it will run these test cases on an implementation (say, Linux), and find for the commutative ops, is Linux generating any share states, or making them not commutative.

Results:
They use commutor on Linux and found 68% of the cases are noncommunicable. They then build sv6, removing most of the bottlenecks.

My comments:
1. How useful this thing is actually depends on the richness of the interface you provide. And here "interface" is used as a broad term, it also includes the underlying stats it might touch (say, inodes for renames), which you could argue is part of implementation...The trick is to give it enough details so that it doesn't report everything as scalable, and don't give too much details so that you give specific implementation details as interfaces.
2. The tile is "interface", yet they didn't seem to pin-point a place where POSIX interface is not scalable. (Well, maybe some small places, like create() with lowest fd instead any fd). In general, POSIX are pretty good in terms of scalability.
3. The graph the provide (figure 6 in the paper) are quite interesting. It reports conflicts, but didn't say how frequently those conflict happens in a real world though (say, I might have a global lock for a rare operation). But I guess you could argue that commutor just provides information, it is up to you to decide how important those conflict commutor finds are.
In general, this is a pretty novel paper and it certainly changed the way I think about scalability.


Toward Optimization-Safe Systems: Analyzing the Impact of Undefined Behavior
Armando Solar-Lezama, MIT CSAIL

This is actually a PL related paper done by pure system people.

High level idea:
Undefined behavior in language causes problem because programmer and compiler operate under different assumptions.

Approach:
Since compiler usually optimize away unstable code (code which invokes undefined behavior), let's run the compiler (STACK) two times, once with the assumption that undefined behavior may be invoked, once with the assumption that undefined behavior would never be invoked. Compare the delta to find where compiler discard code, and thus find unstable code.

Limitation:
I think undefined behavior doesn't manifest them just in a way that compiler optimize away code. Sometimes it is just a hidden assumption when you implement the compiler. For example, you choose a particular order to evaluate the function arguments. This couldn't be found by this framework.

My comments:
1. Undefined behavior invocation is a manifestation of a gap of semantics/agreement between programmer and compiler. And this kind of gap happens not only in language compiling, but also in file system (eg. Thanumalayan Sankaranarayana Pillai's recent work), in cpu, and in all layers of systems where we have a stable API and people expect the lower layer to just work. This paper provides a framework to identify and analyze it in compiler, can we extend it to work for all layers? What can we borrow from their insights?
2. How hard is it to implement a compiler which doesn't use undefined behavior? Maybe I shall try it next semester in 706...