Venue: JSYS 2022 Oct_Papers

Reviews:

final_score: rating: Weak accept: good paper with flaws that can be fixed in three months
review_content: This is a very well-written, easy-to-understand, and impactful paper. It describes how to implement a sequencer in systems relying on consensus to define deterministic state machines. The presented solution is named Mason, which basically consists of a highly available proxy module that is placed between clients and the server backend. The proxy module is stateful, and this assumption is leveraged to avoid holes in the sequencer's ordering deliveries.

I support acceptance of this paper but I would still point out some areas of improvement:

- Granola (ATC12) implements distributed transactions using stateful information embedded into proxy modules. To me, the approach seems similar and may be worth adding a citation.
- My understanding is that the proxy module needs a way to implement a state machine replication to tolerate failures. At the same time, Proxies are part of the protocol to implement state-machine replication. There is a circular dependency here that the authors should clarify.
- Similar to the previous point, the sequencer uses primary backup for availability but the fault tolerance guarantees are less strong than state-machine replication using consensus. It's like authors implement consensus but some of the internal parts have weaker failure models. The authors should clarify this aspect.
- I really appreciate the goal of making systems that need Sequencers easier to develop, debug, and maintain. However, it should be stated that, internally, the addition to the proxy adds a possible bottleneck that can make the performance less predictable.
- It would have been nice to measure the performance of the systems under actual failure.
- The paper does not discuss multi-leader approaches. I understand they might be seen as distantly related work but in terms of performance, they might provide insights in addition to the baseline that has been evaluated.
review_title: Nice paper, well written, strong motivation and fine solution

final_score: rating: Strong accept: excellent paper that will help the community
review_content: This paper introduced MASON, a consensus-based replicated proxy service that coordinates between clients, sharding datastore and sequencer. The proxy (or proxies) as a replicated state machine which tolerates up to f failures, provided the guarantee of any sequence number assigned to an operation will not be lost, even if sequencer and client can crash at any time. In fact, the system depends on several protocols to achieve the goal. Proxy execution protocol describes the main process. Proxy leader failover protocol ensures a new leader can identify any temporary holes and recover previous sequence or get new numbers. Sequencer recovery protocol make sure that all proxies local view of the sequence space are collected and holes filled with no-ops. Finally, a garbage collection protocol among all proxy leaders helps to reduce the cost of previous recovery protocols.

The paper is very well written, with detailed walk through of the system protocols in section 3 and 4. While I am able to follow the arguments without any issue, I do wish some of the sub-section has a diagram that shows an example of how the failure leads to potential holes in multi-sequence space.

Section 5 gives an insightful discussion about MASON service and section 6 and 7 give two types of system modification with performance evaluations. When present the results, instead of a bar graph for throughput and table with few rows for latency, plotting the throughput v.s. latency in the same graph would be a much better choice.

Overall, this paper is a good example of how consensus-based system can be used in a large scale service. Not only does it provide safety guarantees but also improves throughputs. This work would be a good contribution to the community.

review_title: An excellent example of how consensus-based system can be used in a large scale service

final_score: rating: Weak accept: good paper with flaws that can be fixed in three months
review_content: # Summary

This paper discusses a solution to a transaction or operation sequencing problem in strongly consistent distributed systems with a partitioned state. Many partitioned systems will replicate the data or operation in an order prescribed by the partition owner or leader. In transactional cases, an operation may touch data in multiple partitions, each operating in its independent sequencing space. As a result, such multi-partition operations need to order with respect to all partitions they touch. One approach for ordering such transactions is deterministic database systems, which establish a sequence of all operations ahead of commitment and execution. This preordering requires the sequencing information to be attached to each operation or transaction before it starts to replicate/execute in its partitions. 

Such transaction preordering has two limitations. Firstly, if a sequence number is issued for an operation that fails before reaching its partitions, these partitions will get stuck due to a sequencing hole from the ordered but lost operation. A complicated recovery process must either recover the operation from other partitions or replace the missing operation with a no-op in all partitions. The second limitation is the scalability of the sequencer -- the sequencing job is inherently sequential, with a single machine typically responsible for doing all the work. As such, the sequencer can be only as fast as a single machine. 

The proposed system, Mason, is a sequencer for multi-sequence partitioned systems, where each partition has its own sequencing space. The sequencer sits between clients issuing the requests/operations and the partitioned distributed service and is responsible for maintaining all the sequencing spaces for all service partitions. Mason assigns each operation a multi-sequence number that orders that operation across all relevant partitions (i.e., the partitions/shards the operation touch). Each sequence number in Mason can be viewed as a version vector across all sequencing spaces relevant to the operation. As such, the vector does not include partitions the operation does not touch, allowing the independent operations to proceed concurrently and unaware of each other. 

Mason addresses the two sequencer limitations. At the high level, Mason consists of a set of replicated client proxies and a single sequencer machine. Each client proxy receives an operation from the client, contacts the sequencer to assign a sequence number to the operation, durably replicates the ordered operations, and then passes it off to the distributed service. 

The ordered operation replication solves the sequencing hole problem. Each proxy uses Raft to replicate the operations after sequencing and before passing these ordered operations to the distributed service. By durably preserving ordered client operations, Mason ensures that client failures cannot create sequencing holes. However, it is still possible for "Mason-local" sequencing holes to emerge when the proxy leader fails after asking the sequencer for the sequence number but before replicating the ordered client's request. Mason has a mechanism to recover these local holes by making the sequencer remember sequence numbers given to each proxy, allowing the new proxy leader to fill no-ops for these sequences.

Solving scalability issues in Mason is a two-pronged approach. First, the proxy clients can be scaled up as needed by sharding client requests to different proxies. The real scalability bottleneck remains with the single-machine sequencer. However, the sequencer uses batching to order multiple user requests in one shot. Batching works by allocating a sequence range in each sequence space used by operations in the batch, allowing the proxy to assign final sequences to each command from the allocated sequence ranges. Batching allows Mason to trade some latency with increased sequencer throughput.  

The paper evaluates Mason in two reference implementations and shows significant throughput improvements in both. 

# Strength

1) With the popularity of deterministic databases, fast and reliable sequencers are an important problem to solve. The idea of having a reliable sequencer that can be used as a service without worrying about sequence holes and recovery is interesting. 

2) The paper shows the existence of more complicated failure scenarios and possible sources of bottlenecks due to the increased number of components and addresses most of them.

3) The evaluation shows remarkable throughput improvements in tested systems. 

4) Mason seems easy enough to use, allowing building scalable multi-shard services with relatively little overhead. 

5) The paper is well written. It is easy to read and follow. Overall, I was very engaged reading it. 

6) Good to have proofs of provided guarantees.

# Areas for Improvement. 
1\. The big one. The biggest concern I have with this work is the double replication of all client requests. First, each request replicates in a proxy before going to the actual service, which is likely to replicate the operation again. Both tested systems, Corfu and ZooKeeper, do that. This potentially makes the cost of hiding the holes to avoid complicated recoveries too much to bear. The proposed solution essentially puts (an extra) Paxos/Raft in the path of every request. The paper briefly mentions that in the Corfu evaluation, Mason used 6 proxies for each Corfu shard. 6 Raft-replicated proxies require at least 18 nodes to support one Corfu shard. Extrapolating from these numbers, to get the 2x throughout improvement in 4-shard Corfu, Mason needed 24 proxies, which is 72 additional nodes, not counting the sequencer machine. This seems like a lot of extra hardware for a 2x speedup. The numbers seem to be a bit better for ZooKeeper. 

I recommend the authors extend the evaluation to include some cost or efficiency metric while comparing systems with and without Mason. 

As a side note, if we use Mason on top of replicated services, why not push it down to the service itself? I know it defeats the purpose of having it as a separate tool to create scalable distributed services, but if the monetary and resource cost of this tool is too high, it also defeats that purpose.

The idea of separating the component roles (sequencer, client proxies that batch request, service partitions, etc.) and throwing more hardware at the problem vaguely reminds me of Compartmentalization (see "Scaling Replicated State Machines with Compartmentalization"). 

2\. Recovery. I also suggest improving the recovery discussion. It was not entirely clear to me how the system recovers from the simultaneous sequencer and proxy leader failures. In particular, it seems that the sequencer recovery process needs all proxies to participate, which can be a problem if a proxy leader fails and needs a sequencer to recover. The appendix touches on this issue briefly, but I think it needs some prime real estate in the body of the paper. 

3\. Evaluation suggestions. It may be interesting to compare sequencer batching with a no-batching setup to see if/how the latency is impacted. 

Speaking of latency, I also suggest the authors to better explain low latency in their experiments, especially ZooKeeper ones. ZooKeeper latency experiments do not correlate with assumptions made earlier in the paper: "MASON’s tradeoff for a stronger abstraction and scalable ordering throughput is higher latency relative to monolithic-sequencer designs, since the proxies and a single round of replication are on the path for each request." 

Another suggestion is to report latency-throughput curves to let readers see how latency changes as throughput increases.

4\. Related works. Several other works, including the cited ones, propose various distributed scalable sequencing schemes. I think the related works section needs to expand a bit to compare and contrast with existing approaches better. For example, Calvin uses distributed and batched sequencers that sit in front of the clients and also replicate ordered operations: "Calvin divides time into 10-millisecond epochs during which every machine’s sequencer component collects transaction requests from clients. At the end of each epoch, all requests that have arrived at a sequencer node are compiled into a batch. This is the point at which replication of transactional inputs (discussed below) occurs."  Another approach to scaling sequencers was shown in Scalog paper (also cited), and this approach avoids double-replication of Mason, so a more in-depth comparison would have been nice. 

It may also be a good idea to include a brief discussion on the benefits of multi-sequence numbers compared to mono-sequences. And finally, ideally, it would be nice to have a performance comparison with other sequencing approaches. 

5\. Reconfigurations. A minor point here, as far as paper goes. For a system like this to be usable, it needs to dynamically scale up and down in the number of proxies. This should be simple if not for the sequence GC protocol that requires all proxies to participate. I wonder whether the authors can include a few sentences about doing such reconfigurations. 

review_title: Mason is a scalable, fault-tolerant sequencer for distributed systems

Meta-review: metareview: Dear Authors, thank you for submitting to JSys. After reading the reviews, we recommend a REVISE decision. We believe the concerns of reviewers can be addressed in the next three months (potentially sooner, but we wanted to give you enough time to handle the comments). After the submission of your revised version, reviewers will evaluate your modifications and a final decision will be made.

All three reviewers appreciate the contributions and are mostly happy with the submission. In general, all reviewers are optimistic about the acceptance of the paper; however, all suggest clarifications/improvements that authors should carefully consider during the revision time. 

Most notably, reviewers pointed out some improvements in the way experiments are conducted and some needed clarification regarding the decision of making individual components in Mason highly available through (double) replication.

We look forward to receiving your revised version. Thank you one more time for submitting,
Lewis Tseng and Roberto Palmieri - Area chairs of JSys.

confidence: 5: The area chair is absolutely certain
Decision: Weak accept: good paper with flaws that can be fixed in three months