Review on Coordination Avoidance

This paper also wants to address the tension between coordination overhead and data correctness. The key idea is to avoid coordination thus could lead to minimum synchronization and consistency executions.

The nugget of this paper is I-confluent. Basically, it is to leverage the invariants in the data. With the invariants, they formalize a necessary and sufficient condition for persevering invariants and also coordination free execution of applications.

Previous works tries coordination-free execution to reduce the coordination overhead. However, uninhibited coordination-free execution is not safe, sometimes it may reduce the execution accuracy or data consistency. Then in traditional database system, it uses serializable isolation to achieve concurrent operations. However, it may leads to more conservative serializability and coordinate more.

Different from previous works, the authors tries to avoid or to reduce the coordination into minimum.

The trade-off here is the technique proposed in the paper require user to specify his correctness criteria. If either these criteria or application operations are unavailable for inspection, users must fall back to using serializable transactions or, alternatively, perform the same ad-hoc analyses they use today.

I think it is a good way to reduce coordination overhead, but may only be influential for 3-5 years.

  

Review for Gemini (OSDI'12)

The problem that data consistency is hard to maintain in a large scale system. However, the synchronization of concurrent actions across the data center introduces large overhead.

Basically, there are two kinds of solutions. First one like Amazon's Dynamo, it sacrifices the data consistency level, but has low latency across the cluster. The second is like Yahoo's PNUTS, which can achieve strong data consistency but with high latency during data updates.

The problem that Gemini wants to tickle is to make a trade-off between the data consistency level and latency. Basically, Gemini allows multiple level of consistency to be co-existed. They propose so-called "RedBlue" strategy. More precisely, Blue operations execute locally and lazily, with low constancy level. Red operations are serialized and immediate require cross-site coordination.

The difference of Gemini from other related works are listed on the figure above.

Personally, I think Gemini will be influential within 10 years since it can reasonably balance the data consistency level and scalability. 

Review for CRDTs

The problem is data consistence is difficult to maintain. There are mainly two kinds of approaches to deal with data consistence. The first one is ensuring scalability but giving up consistency like LLW. The second kind is to serialize all updates with consistency guarantee, but cannot scale well.

CRUT stands for Commutative Replicated Data Type. It refers to that when concurrent data update happens, all the replicas updates in casual order, and then replica converge.

The author propose the CRUT (Commutative Replicated Data Type) implementation called Treedoc. Basically, they try to build up an order set with insert-at-position and delete operations.

Different from previous works, the authors are the first to address the design of CRUT.

The trade off here is that CRUT is not universal. Not all the abstractions can be converted into CRUT. For example, a queue or a stack rely on a strong invariant (a total order) that inherently requires consensus cannot be converted into CRUT.

 

I think it will be influential, since data consistency is a big problem in large scale data processing.

Review for Haven (OSDI'14)

The problem is that, current cloud computing infrastructure only to protect the privileged code from the untrusted code, and does nothing to protect user's data from being accessed by privileged code.

To tickle this problem, the authors proposed their system called "Haven" for data protection. Basically, Haven tries to provide a cloud computing security level equivalent to a user operating their own hardware in a locked cage.

The nugget of Haven is to leverage Intel SGX ( software guard extensions) and build shielded execution on top of it. By doing so, it provide privilege code and physical attacks. In addition, since SGX cannot provide enough protection by using "isolation alone" technique.

Different from previous works, Haven is the first system to achieve shielded execution of unmodified legacy applications, which includes SQL Sever andApache on a OS and hardware.

Even though Haven can provide security data processing with the adversary has full control over physical package of the processor, currently Haven cannot protect user's data processing from any side-channel attacks.

I think Haven could still have impact since the data security issue over the cloud is become more and more important for people who use cloud services.

Review for CryptDB

The theft of sensitive data from users is always a big problem. The CryptDB wants to protect user's data without trusting DBMS or DBA (Database Administrator)s. To achieve that, CryptDB let DBMS to store all the encrypted data and process the SQL queries directly without having the decryption keys.

The main idea of CryptDB consists of three parts.
1.SQL-aware encryption strategy: We can directly perform SQL-query on data encrypted with current encryption schemes without knowing the decryption key. And CryptDB only a novel cryptographic construction for privacy-preserving joins. Then CryptDB uses these encryption techniques for data encryption.

2. adjustable query-based encryption: CryptDB can dynamically adjust the data encryption level on each data item in runtime. Basically, CryptDB initially use the strongest level encryption on each piece of data and then dynamically adjust the encryption level on the server.

3.onion of encryptions: CryptDB uses this techniques to only reveal the relation between the data items but no reveal of other data information or data relation not used in this query.

The difference of CryptDB from other previous works is that CryptDB is the first private system that supports all the operators on SQL query without modifying DBMS or clients applications.

For the trade-off, based on the evaluation side, I think the overhead of encryption / decryption is very high, especially in Sum operation.

I think CryptDB will still be influential since it proposes a system to achieve data encryption without modifying the DBMS or client app.

Review for SOA (VLDB'13)

1) Is the problem real?
Currently, sampling algorithm has been incorporated into all major database systems. However, the estimate of accuracy obtained from the sample is unsolved.

This paper solve this problem by allowing GUS sampling operators to communicate with join and selection.

2) What is the solution’s main idea (nugget)?

It defines the notion of SOA equivalence.  Second Order Analytical equivalence is the key equivalence relationship between query plans that is strong enough to allow quantile analysis but weak enough to ensure commutativity of sampling and relational operators.

3) Why is solution different from previous work?
Previous works mainly have two domains. 1)using sampling to derive estimates for single relation. 2) the extension of the correlated sampling pioneered by AQUA system.

They mainly analyze the sampling schemes uses functions over tuple not operators and algebras which the database is used to. Whereas the approach in this paper leverages operators and algebras.

4) Does the paper (or do you) identify any fundamental/hard trade-offs?
Even though it performs well for confidence level evaluation for sampling query process, the overhead of contracting this confidence evaluation process is high.

5) Do you think the paper will be influential in 10 years? Why or why not?
I think it will last for maybe 2-3 years. The computing overhead of confidence level is too large.

Review for BlinkDB (Eurosys'13)

1) Is the problem real?
The problem of real-time data processing is a big challenge. Previous works mainly focus on using sampling technique to meet with the real-time bound. There are mainly two types of these approximate data analysis techniques. The first kind is under strong assumptions about the query workload. It can perform well if the system knows the workload and query information. The second kind is to have fewer assumptions but with the performance varied a lot.

Given this, the user must make the trade-off between accuracy and flexibility.

The BlinkDB want to achieve high accuracy approximation without good knowledge about the workload/query. The problem is real.

2) What is the solution’s main idea (nugget)?

The main idea contains two parts: sample creation and sample selection.
For the sample creation module, based on historical frequencies and past QCS, it mainly choose a set of stratified samples with total storage costs below some user configurable storage threshold.

sample selection is built to select the sample for processing the query.  It uses an Error-Latency

Profile heuristic to efficiently choose the sample that will best satisfy the user-speciffied error or time bounds.

3) Why is solution different from previous work?

The previous work either has strong assumptions about the query workload, or high flexibility but the accuracy varies a lot.

The BlinkDB is try to achieve a better balance between the efficiency and generality for  analytics workloads.

4) Does the paper (or do you) identify any fundamental/hard trade-offs?

I think the most important thing is that the data sampling is offline. It cannot perform well a data sampling when the data changes fast.

5) Do you think the paper will be influential in 10 years? Why or why not?
Maybe, I think approximate data analysis is always a way to analysis data with hard time constrain. BlinkDB provides a good sampling model to achieve high accuracy of data analysis.

Review for F1 (VLDB'13)

The problem is that MySQL cannot meet the requirement of Google's growing needs of scalability and reliability. For the requirement of scalability, availability, consistency and usability, previous publications says they are mutually exclusive. F1 want to achieve these four "impossible" goals.

F1 is based on Spanner to enable the query.

The good performance of F1 is based on following difference from other related works.
1. Hierarchical Schema.  In this schema, tables are organized into a hierarchy with child table rows, and interleaved within the rows of parent table
2. Table column contains protocol buffers.
3. Transactional fully consistent indices, which split into local indices and global indices
4. support for non-blocking schema
5 flexible lock granularity enabling.

For the shortcoming, F1 currently is not good for parallel query execution, which may needs fault recovery, isolation, etc.

I think it will still have impacts in next 10 years. Because it is the next generation of Google's NoSQL.

Review on Spanner (OSDI'12)

1) Is the problem real?
The need of schemes that want strong consistency in wide-area replications is the main problem. It is real.

2) What is the solution’s main idea (nugget)?
The nugget in Spanner is it assigns globally-meaningful commit timestamps to transactions, thus can support for strong consistency in wide-area replications.

More precisely, the key component is a new TrueTime API and its implementation.

3) Why is solution different from previous work?

Megastore and DynamoDB also provide consistent replication across datacenters. DynamoDB can only replicates within a region, whereas Spanner can replicates globally. Megastore has writes conflicts and high communication cost, whereas Spanner do not have these shortcomings.

4) Does the paper (or do you) identify any fundamental/hard trade-offs? 

Although Spanner is scalable in the number of nodes, the node-local data structures have relatively poor performance on complex SQL queries, because they were designed for simple key-value accesses.  

5) Do you think the paper will be influential in 10 years? Why or why not?
Yes, Since bigtable is a great success, I think spanner is the next generation of Google database.

Review for Succinct (NSDI'15)

1) Is the problem real?

For secondary attributes query, the previous solution of using in-memory index has the problem of high memory footprints. The solution for this problem is to compress data, or only cache hot data. However, for either case, it introduces latency on either decompress data or disk I/O

2) What is the solution’s main idea (nugget)?

Query on compressed data. The main idea is twofold.
1 store an entropy-compressed representation of the input data, which enable random access.
2 enable query directly on the compressed data.

3) Why is solution different from previous work?

For secondary attributes query, there are basically two categories of works.
1) the previous arts use column oriented stores. the data scan introduce high latency and low network throughput.
2) the second one is to build index. However, the index memory footprint is too large. When using compression on the footprint, the corresponding response time has higher latency since they need to first decompress the index before query. When only cache hot data, the latency is introduced by the disk IO.

Succinct directly query on compressed data.

4) Does the paper (or do you) identify any fundamental/hard trade-offs? 

The first time of pre-processing data (i.e. compress function) is an overhead. In addition, Succinct currently cannot support for data updates.

5) Do you think the paper will be influential in 10 years? Why or why not?

Maybe. To me, I think it is a more compacted and sorted data representation type. Data compression is always a topic in system. Since it currently has many shortcomings (e.g. cannot support updates, etc), I think it will have several follow up works to fix it.

Review for Dash

Previous works mainly focus on query on structured format data, which has been cleansed, filtered and offline processing. However, in big data or cloud computing scenarios, the incoming data is usually huge and need real-time processing. Building indices can reduce query execution time, but introduce issues like slow data updates.

In this paper, the people build up a tool called Dash, an elastic-search engine which provides real-time search and full-text search capability. The data flow is scheme-free, which means that two docs have same type can have different type of fields. The key idea is to use elastic search, which has the good property like scalability, near real-time processing. More precisely, the good performance is due to Apache Lucne's shard,  RESTfull server's good charactoristics.

For the shortcoming, Dash lack security like authentication and access control. Furthermore, it is hard for nested query writing, and cannot support JOIN operation.

It is still useful since real-time analysis is important. I think it will still have impact in the future.

Review for Dremel

1) Is the problem real?

The problem is MapReduce's high latency (minute-level) is not acceptable in interactive data analysis at scale.  Dremel wants to have second-level latency for queries over trillion row table.

2) What is the solution’s main idea (nugget)?
It has two aspects.
1. Its novel columnar storage format. That is to use replication and definition level to translate nested record with column-striped representation. And then propose automaton for assembling records.

2. leverage serving tree for assembling query results by aggregating relies from low-levels of the tree.

3) Why is solution different from previous work?

Compared with its competitive schemes like Pig or Hive, Dremel does not execute query by translating them into MapReduce jobs.

4) Does the paper (or do you) identify any fundamental/hard trade-offs? 

Currently, for ad-hoc query using Dremel, I have not found any trade-off here. However, it could not support for data update. In addition, it does not have fault tolerance.

5) Do you think the paper will be influential in 10 years? Why or why not?

I think Dremel maybe the future. It will definitely have impacts in 10 years. It is because Dremel can really query on trillion-level data in second-level, which is amazing. Dremel maybe the next generation of Hive.

Review for Spark SQL(SIGMOD'15)

1) Is the problem real?
MapReduce is powerful, but the low-level programming for declarative query is complicated for programmer. This is true. Furthermore, users may want to query on both relational and complex procedural algorithms. And this is partially true. However, this is the key motivation of this paper.

2) What is the solution’s main idea (nugget)?
Spark SQL contains two parts: DataFrame API and Catalyst.

DataFrame SQL enables users intermix procedural and relational code.  DataFrame API is based on DataFrame, which is like a table in relational database. DataFrame SQL is the main part of SparkSQL.

Catalyst is a extensible optimizer. Catalyst is a tree of node objects. For rule-based optimization, Catalyst leverages pattern matching functions. And Catalyst conduct optimization in 4 aspects. 1) analyzing the logical plan to resolve references 2) logical plan optimization 3) physical planning (only in selecting join algorithm) 4) code generation using quasiquotes in scala to compile parts of queries to Java byte code

3) Why is solution different from previous work?
Spark SQL is based on Shark. Compared with Shark, Spark SQL has more AIP, DataFrames.

Another similar one is DryadLINQ. Compared with DryadLINQ, Spark SQL provides DataFrame interface, and support for iterative algorithm on Spark.

Compared with other system like Hive, Pig, etc, Spark SQL integrate more closely to Spark applications. In addition, Spark SQL enable mix procedural and relational API in the same language.

4) Does the paper (or do you) identify any fundamental/hard trade-offs? 


Spark SQL is still not good at processing low latency guaranteed queries (e.g. BI query, ETL SQL, etc.)

5) Do you think the paper will be influential in 10 years? Why or why not?

Compared with HiveQL, the performance gain is significant. However, as mentioned in the paper's evaluation part, when comparing with Impala, the latency is always higher than Imapla. At least, I think with incorporating with DataFrame, Spark SQL is at least good for more general query, with low latency. I think it will be still influential, since it is an more general one. 

Reviews for Impala (CIDR'15)

The problem of conducting SQL query on Hive is its high latency. This is because Hive is based on MapReduce. The Impala is trying to reduce this latency.

Impala is consisted of 3 main services: Impala daemon (impalad), statestore daemon, Catalog daemon.

Impala daemon: run on each machine in the cluster. It is used for accepting queries and manage executing across the cluster.

Statestore daemon: metadata publish-subscribe service. It transmits cluster-wide metadata to all impala processes.

Catalog daemon: serve as Impala's catalog repository and metadata gateway.

I think the most important contribution of Impala is to translate SQL into query plans, without leveraging. In addition, since the intermediate results are stored in memory instead of writing back to disk. I think it is a good way to do so.

Compared with Hive, Impala do not need to use MapReduce, which has long latency for processing SQL query. In addition, in memory processing is also a difference compared with other related works.

For the tradeoff, Impala do not have fault tolerance. However, since the time overhead is low. Impala can re-do the failed query.

For the influence, I think Impala is kind of a Hadoop version of Dremel. So for the novelty, I do not give it much credits.

Review for Cassandra (SIGOPS review)

1) Is the problem real?

Yes. For very large-scale cluster system, the server and networking components are failing frequently rather than rare. It is a need to build a software system that treat failure as normal rather than rare.

2) What is the solution’s main idea (nugget)?

For the data model, Cassandra is based on google's bigtable, but Cassandra introduces super column family, which can be regarded as column family within a column family.

The system mainly has following contributions.
1. Achieve dynamically partition over nodes by using an order preserving hash function.
2. Cassandra incorporates Zookeeper to let the leader arrange data replica among nodes.
3. Using Scuttlebutt to enable cluster membership and disseminate other system control state.
4. Cassandra can dynamically adding more nodes into the system.

3) Why is solution different from previous work?

Previous systems like Bayou, Coda, etc. cannot achieve scalability and availability, whereas Cassandra does. In order to provide strong consistency guarantee, these systems cannot handle network partitions.

Compared with Cassandra, Dynamo cannot enable high write throughput.


4) Does the paper (or do you) identify any fundamental/hard trade-offs? 


Cassandra's partition is based on preserving hash function, which is a probability partition algorithm. It is simple to be implemented. However, compared with other system like HBase which has a master node for global dynamic data partition, Cassandra's partition mechanism may not achieve optimal performance.

5) Do you think the paper will be influential in 10 years? Why or why not?

Yes. I think so. It is because Cassandra is simple and can achieve high throughput especially in writing, which is always a bottleneck for other competitive schemes.

Review for BigTable (osdi'06)

1) Is the problem real?

The problem is that existed distributed store system cannot achieve good scalability to petabytes of data and thousands of machines. It is real.

2) What is the solution’s main idea (nugget)?

BigTable's three components: Rows, Column Families, Timestamps.

Rows: row keys are arbitrary strings, which may also be regarded as the first level of bigtable index. row range for a table is dynamically partitioned. Each row range is called a tablet, which is the basic unit of distribution and load balancing.

Column Families: column can be regarded as the second level of bigtable index (Row-Column two level ). Each row can have limited columns. And columns are separated by its type. Each type of the data in a column will be collected as a column family.

Timestamps: It is used for store the same data of different versions, which may also be regarded as the third level index in bigtable. Basically, the default return value will be the latest version of data in the specified row&column space.

3) Why is solution different from previous work?

Boxwood from Microsoft has some overlapping with BigTable. However, Boxwood is targeted at a lower level (i.e. provide infrastructure for building filesystem/database). Whereas BigTable is to support client app that wish to store data.

Other projects like DB2 from IBM, Real Application Cluster Database from Oracle, they can achieve similar goal as BigTable does. However, their system architecture are totally different.

4) Does the paper (or do you) identify any fundamental/hard trade-offs? 


One key concern is that when the B+ tree architecture. It is good for storing and manage data in the system. However, if the root tablet position is missing, or Chubby cannot work, the whole system will break down.

5) Do you think the paper will be influential in 10 years? Why or why not?

Yeah. It is one of Google's 3 masterpieces of art (i.e. BigTable, MapReduce, GFS).

Review for Sparrow

1) Is the problem real?

Now data analytics framework turns to process shorter tasks with high parallelism in order to achieve low latency. Current scheduler cannot achieve millisecond latency guarantee. This is a real problem. It is because the centralized scheduler have too much workload on single node or a few nodes. The paper wants to build up a new scheme that fits for millisecond latency guarantee scheduling.

2) What is the solution’s main idea (nugget)?

The basic idea is to use a distributed and random algorithm called "the power of two choices". That is to randomly probe on two severs and place the task on the sever with fewer tasks.

Sparrow made some modifications to original the power of two choices technique.
Batch sampling: instead of per task sampling, Sparrow place m task sampling together.
Late binding: delay tasks assigning to the workers until workers are ready to run the tasks. Thus it reduces job response time.
policies and constrains: Sparrow uses queues on workers for global polices. And it supports for per-job/task constrains.

3) Why is solution different from previous work?

Previous schedulers are mainly centralized ones. Either with single node or two-level scheduling, there are too much scheduling workloads on the scheduler node/nodes. Therefore, they cannot achieve scheduling with millisecond latency guarantee.

However, different from these centralized schemes, Sparrow is a distributed and randomized scheduling scheme, which could achieve low latency.

4) Does the paper (or do you) identify any fundamental/hard trade-offs? 


Even though distributed and randomized scheduling algorithm can achieve low latency, the scheduling could not achieve optimal performance. Although the authors claims the nearly-optimal results, which is a case-by-case evaluation.

5) Do you think the paper will be influential in 10 years? Why or why not?

I do not think so. I think centralized scheduling may still be the main stream. And some centralized scheduler (such as scheduler in spark streaming) has already achieve scheduling latency guarantee within a second. 

Review for Omega (Eurosys'13)

1) Is the problem real?
Running a mix of data processing workloads on large scale cluster introduces a high workload on scheduler. And in the future, the scheduler may be the bottleneck. Therefore, it is a must to design a new framework for scheduler on cluster.

2) What is the solution’s main idea (nugget)?

Omega grants each scheduler full access to the entire cluster, and offers the resources allocation decision by the framework schedulers themselves.

When there is conflict between framework schedulers. Omega scheduler will conduct an all-or-nothing gang scheduling to solve that.

3) Why is solution different from previous work?

Previous works are mainly separated in two categories. First, Monolithic scheduler uses a centralized scheduling algorithm for all jobs. It is not scalable  The second kind is called two-level scheduler, which has a single resource manager offers resource among different frameworks in parallel. This kind of scheme cannot support preemption or policies requiring access to the whole cluster state. It is because each framework scheduler cannot have a view of overall cluster.

Omega offers each scheduler full access to the entire cluster. Therefore, it can be scalable. In addition, compared with 2-level scheduling, this idea also reduce the scheduler workload, since there is no need for the Omega scheduler to make the resource allocation decision.

4) Does the paper (or do you) identify any fundamental/hard trade-offs? 


Omega gives each framework scheduler full access to the entire cluster, it may improve cluster utilization efficiency. However, this full-access offer also gives scheduler opportunity to devour all the computing resources or even preempt other framework's resources. Thus there is no fairness at all.

5) Do you think the paper will be influential in 10 years? Why or why not?

Yeah, I think it is good way to reduce workloads on scheduler. Simple and efficient scheduler is the need for running mixed workload on large scale cluster scheduling. However, it is a prototype, without considering the issue of fair-sharing, etc. Hope a more sophisticated version may be proposed instead of this one.

Reivew for DRF (NSDI'11)

1) Is the problem real?

To achieve fair sharing using Max-Min fair sharing on one resource is simple and efficient. However, when it comes to about heterogeneous resources demands, the max-min fair sharing cannot achieve good performance. The paper wants to achieve fairness among multiple resources when users have heterogeneous demands. The problem is real and needs to be solved.

2) What is the solution’s main idea (nugget)?

The DRF (Dominant Resource Faireness) introduces dominant sharing concept as the metric and using max-min fair sharing on this dominant sharing value. Dominant sharing is the amount of dominant resource one user needs.

The DRF tries to equalize the dominant share of users.

For online scheduler, DRF will schedule a task that has the smallest dominant share.

3) Why is solution different from previous work?

Previous works focusing on multi-resouces sharing only considering about the multiple instance of  interchangeable resources, whereas DRF focus on allocation of resources of different types.

And many other framework using Max-Min fair sharing may only considering about one resources allocation. On the contrary, DRF considers about multiple resources fair sharing.

4) Does the paper (or do you) identify any fundamental/hard trade-offs? 


The paper is based on the assumption that users want to achieve overall fairness. However, as shown in the evaluation part, by achieving this dominant fair sharing, a large amount of CPU/memory recourses are wasted. Some portions of CPU/Mem are idle during the tasks processing by each user. I think balancing both fairness sharing and computing resource utilization will be a better solution.

5) Do you think the paper will be influential in 10 years? Why or why not?

I do not think so. Since by achieving fairness, many resources are idle and wasted. DRF might be good for some specific scenarios that fairness sharing is necessary. I think balancing both fairness sharing and computing resource utilization will be a better solution.

Review for Kubernetes

The fault handling and resource management has always been a big problem in large-scale cluster computing. although the problem has been solve by many other works like Mesos, Yarn, etc. , the project Kubernetes want to solve this problem at massive scale.

The key idea of Cabernets is to place applications into Docker containers on multiple host nodes. And the whole project is based on Google's Borg project. It has several key concepts.

1. Pods: it is the unit of scheduling in Kubernetes. It has the resources that enable one or several containers to run.
2. Services: it enable naming and load balancing on Kubernetes.
3. Lables: It is arbitrary key/value pairs that user attached on Pods. Compared with Borg, it enables more flexible collections by organizing Pods.

The work flow of Cabernets is illustrated as the figure above. The Kubernetes consists of Kubecfg, Master API Server, Kubelet, Minion(Host) and Proxy.

The master defines Master/API sever's main statements, including Pod Registry, controller Registry, Service Registry, endpoint registry, minion registry, binding registry, etc. It is the center for client (Kubecfg) calling Kubernetes's API, container control. Master has API Server, Scheduler and Registry components.

Kubelet is the connecting point of Minion and Master API server.

Proxy is designed for using Kubernets's containers from outside internet.

The difference of Kubernetes from other previous works is main in 3 aspects.

1. Kubernetes enables lightwight, simple access.

2. it can build multiple-cloud.

3. it is highly extensible.

For the project's influence, I am quite sure container is a trend for cloud computing, since it provides a simple interface for programmer to use the clusters.