Review of "One Size Fits All"

Today, this paper seems to address something that is a nonissue - throughout the duration of my career in computer science I've been of the mindset that "one size fits all" has no place. It's strange to me to think how ubiquitous the DBMS was in times past - amazing that we were at a point when all of the systems I think of today as distinct - OLAP, OLTP, analytics, warehousing, etc. - were run through the same platform. I don't know if this paper in particular was influential in causing the shift to today's mindset, but in any case, the shift certainly occurred. 

One interesting question that I think arises from this is - will there ever be a time when we have systems that are so efficient we can again return to a one size fits all paradigm? It currently doesn't seem likely, but that would seem to be the "holy grail" of sorts. The Hadoop ecosystem today does provide at least a unified platform that many such systems can interact upon, with a unified data later (e.g. HDFS, Tachyon) and unified schedulers (Mesos, YARN). 

Review of "Jellyfish: Networking Data Centers Randomly"

The main idea of Jellyfish is to connect servers / switches completely randomly, rather than trying to conform to a regular structure such as the traditional tree / fat-tree structure. The primary motivation was the ease of incrementally adding new servers, but they found that the random layout actually increased bandwidth capacity when using the same hardware due to the paths between servers being shorter on average.

The VL2 paper also involved an element of randomness, though at the routing level rather than the physical connection level, which makes me wonder if there may be anything fundamental about the use of randomness in networking to avoid congestion and increase connectivity.

There are two main tradeoffs I see here: complexity of routing, and length/complexity of cabling. Since servers are no longer connected to nearby neighbors in a tree fashion, and may be connected to servers anywhere else in the data center, the average cable length may increase significantly, and the cabling follows a less regular structure so it may result in a "dread spaghetti monster" (authors' words). They discuss ways to solve this issue including clustering switches (which there will be many more as compared to servers for large clusters) in the middle of the data center, constraining most of the cabling to that area. They discuss a number of ways to deal with the routing complexity issue.

This idea is very interesting, and I am curious to see if in the 3 years since publication anyone has tried this.

Review of "PortLand: A Scalable Fault-Tolerant Layer 2 Data Center Network Fabric"

PortLand tries to solve extremely similar problems as VL2: making the network appear flat and allowing VMs to migrate gracefully, reducing amount of configuration necessary, efficient communication between any pair of nodes. Again, this is definitely a real issue.

PortLand uses a "PMAC" (pseudo-MAC) address to abstract away physical location details; this is similar to the directory lookups used in VL2. It seems that these two systems are taking very similar approaches; add another layer of abstraction to make physical location transparent to the application developer. PortLand seems to place less emphasis on providing high bandwidth between any pair of servers, instead not requiring a change in network topology and focusing on fault tolerance (whereas VL2 adds a more dense linking structure to provide high bandwidth).

Since both of these papers are 7 years old, I am curious to know if either of these systems (or something similar) is in use anywhere. I'm sure some of the ideas have appeared by now, and it would be interesting to find which approach was more successful. It is my intuition that PortLand's approach with fewer network links required probably appears more often, though I don't think I have ever heard of any PMAC approach to a physical-layer-hiding abstraction.

Review of "VL2: A Flexible and Scalable Data Center Network"

The issue of getting good network bandwidth across arbitrary machines within a data center is very important; task placement is often based on data locality rather than placing machines near each other, and having to juggle both of these concerns simultaneously is very difficult. Making the network more flat in terms of performance eases this issue.

They have a few central ideas: use Valiant Load Balancing to route flows (rather than packets, as in typical VLB) randomly across the network, use a lookup table to map IP addresses to physical locations such that machines can easily be relocated, and push work to the end nodes to reduce state and complexity of switches.

There are a number of tradeoffs; for example, using the directory lookup structure for IP addresses helps create the flat network illusion they work to achieve, but provides some overhead. Their networks require a fair amount more connections than standard topologies, e.g. having a full bipartite graph between the intermediate and aggregate nodes. This cost comes at the benefit of much improved performance and ease of programming/task scheduling layout.

I can see this being influential in the future; as data center computing becomes completely ubiquitous, we expect it to become easier, with more of its complexities hidden, and the flat network abstraction is very helpful in achieving this. The performance gains as opposed to a standard tree hierarchy are also substantial. I don't necessarily think this system in particular will take off, but the ideas seem important.

Review of Tao

As more data becomes represented in graph formats to capture the intrinsic connectivity of the data, the ability to store information in a way that is aware of this structure becomes more important. 

The main idea of Tao is to provide a caching layer on top of a MySQL database which is graph-aware, intelligently fetching data based on its structure. It is essentially a replacement to memcache which is tuned specifically to graph-structured data - nothing too revolutionary. 

One trade-off they made which I am surprised about is the use of MySQL as the backing storage engine. It seems to me that this translation layer from graph-structured to relational must impose unnecessary overheads, but it also means that transitioning was likely easier and they get the reliability guarantees of MySQL automatically. 

I don't see this being influential in 10 years - there's uncertainty over whether we will want to continue to use graphs as the primary representation of data moving forward, and even if we do, it doesn't seem that this work is particularly novel. 

Review of Neo

Neo provides a data storage solution built from the ground up to store graph-structured data, unlike Tao which simply acts as a layer on top of an inherently relational storage model. 

While this seems like a good thing, the details provided in the paper about how performant the system is and how they achieved this are very sparse (essentially nonexistent). I would be very curious to know more about how this performs as opposed to traditional databases and NoSQL stores, and if it does perform well, how they managed to achieve this. It read almost like a marketing document more so than an academic document. 

The traverser / navigational model is interesting, and I would be curious to see how more complex queries are written in this manner. If the data really is naturally graph-structured, it seems that it would probably be intuitive to write queries in this way, but without any examples I am unsure if that intuition is correct. 

Review of "GraphX: Graph Processing in a Distributed Dataflow Framework"

I am not sure how frequent it is to need to be able to join graphs against other data when doing graph computations, but it does seem that it could be a common situation and GraphX can certainly help to solve this while still being extremely performant.

The main nugget is essentially to be able to run graph algorithms on top of Spark, which gives you fault tolerance for free, as well as allowing you to seamlessly intermingle graph data and other data that you may want to join against the graph data. One important thing done to make this successful was to optimize the common join-map-group pattern.

One trade-off is programming model; the vertex-program model of GraphLab and Pregel may be more intuitive for graph processing than fitting an extension of Spark's RDD API to the problem; I certainly had a little harder time reasoning about the program's behavior. Performance may also be an issue in some cases, but it seems that in general GraphX performs very well.

Review of "PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs"

I thought this paper was pretty interesting - intuitively the power law distribution of natural graphs makes sense, but I would not have originally thought about it when working with something like GraphLab. I'm not sure exactly how general the power law distribution is, but it's definitely true for social networks, which are extremely important for graph processing in today's world, so this is definitely a worthwhile problem to solve.

There are two main ideas: first, separate the program explicitly into Gather / Apply / Scatter phases, allowing PowerGraph to optimize your program by having a better understanding of what needs to occur where. Second, partition the graph based on edges, not vertices, since this is more representative of the work that needs to be done.

The first trade-off I see is simply usability / programmability; it seems that it is a bit easier to reason about the programs which are written in GraphLab and Pregel than in PowerGraph due to the developer having to be more aware of the different phases in PowerGraph. However, this increase in complexity is relatively minor, and certainly seems worth the performance benefits in applicable situations.

I can definitely see this being impactful in 10 years - graph processing is a very hot subject right now, and this paper seems to introduce some ideas that seem very promising.

Review of "Materialization Optimizations for Feature Selection Workloads"

In the current state of machine learning, using a machine learning algorithm on your data often essentially comes down to deciding on what features to use, which can sometimes be extremely nonintuitive, and requires a great deal of testing. With machine learning becoming more ubiquitous all the time, being able to do this quickly is important.

The main ideas of this paper to speed up this process are: intelligent subsampling (since this is just to determine good features and not to actually make business decisions, exact results aren't necessary), materializing partial results to be able to reuse them on similar computations, and maintaining a cache of computed values (since much of the computation will be the same on each iteration of trying new features, with only a few things changed).

Subsampling comes with a fundamental trade-off in terms of speed vs accuracy, but this is easily tunable, and due to the intelligent nature of their subsampling they show that in some cases they can achieve an 89x speedup with only a 1% error, which is pretty impressive.

I am pretty surprise that no one has already done work on this, since besides the transformation materialization, these optimizations seem to be pretty intuitive, and I am somewhat skeptical that they are the first to apply this... I think that these techniques will be influential in 10 years, but whether or not this paper specifically will be, I am not sure.

Review of "Towards a Unified Architecture for in-RDBMS Analytics"

While I am not sure that running your data analytics in your RDBMS (which generally isn't designed for such a thing) is the best way to go about the problem, people are certainly doing it, so making this faster is definitely a valuable problem to tackle.

The main idea of this paper is to note that many of these analytics algorithms can be solved using IGD (incremental gradient descent). By leveraging this common solution mechanism, they can implement a framework which requires only small extensions to be able to run a wide variety of algorithms, making the development of new algorithms and applying them to new RDBMSes much easier. They also make clever use of data layout and parallelism.

Intuitively, it would seem that there should be a trade-off between performance and generality, with more specific implementations being more performant. This doesn't end up to be the case in their analysis, with their more general solution outperforming specific implementations. This may be more of a result of their other techniques; perhaps if they leveraged the techniques used to implement the general framework to fine-tune the individual algorithms, they could achieve even better performance at a loss of generality and ease of development.

Review of "Scaling Distributed Machine Learning with the Parameter Server"

Machine learning is becoming increasingly ubiquitous and complex, running over increasingly large datasets. Being able to run these algorithms (some of which don't lend themselves well to large-scale parallelism) in a distributed fashion quickly is increasingly important, so this is definitely a real problem.

The main idea is to use a centralized set of parameter servers which maintain the shared state of the system, coupled with a large number of worker nodes which actually perform computation. Worker nodes push state updates and pull down state. The system highly leverages the fact that machine learning algorithms are generally convergent and are not significantly disrupted by having stale state, so they don't require synchronous state updates.

One trade-off they discuss is convergence rate vs per-iteration performance. As state becomes more stale, things converge less slowly, but having more stale state allows you to do more computation asynchronously.

Review of "Making Geo-Replicated Systems Fast as Possible, Consistent when Necessary"

This paper aims to present a solution to the issue of maintaining consistency across multiple datacenters. As services become increasingly global, this becomes important to decrease latency to users across the globe, which also ensuring consistency.

The main idea is to separate operations into two categories: Blue (commutative, eventual consistency) and Red (strong consistency). They provide guidelines for how to determine what operations fall into each category, plus a system for forcing more operations to fit into the blue category: decomposing operations into generator and shadow operations, which can turn some non-commuting operators into commuting ones.

This work comes about most likely because the scale of geo-replication that exists now is significantly larger than in the past, and being able to maintain low latency (small consistency overheads) is very important - higher latency has a significant correlation to decreased per-user profits.

There are a number of trade-offs here. Using blue operations only guarantees eventual consistency, which still may come with issues ("eventual consistency is no consistency"), though it provides much higher speed. Breaking down operations into generator/shadow operations may grant much lower latency, but also makes things more difficult to reason about.

I can see this being influential in the future - services are becoming increasingly more global and people expect increasingly lower latencies, but application programmers also want consistency. This seems to provide a good framework for maintaining both of these things simultaneously.

Review of "CRDTs: Consistency without Concurrency Control"

Attempting to balance strong consistency models with low concurrency control overhead is a very important line of research because as systems grow larger our current concurrency control schemes have overheads which are often prohibitively high, but some reduced-consistency schemes make things difficult to reason about for application programmers and result in complex handling logic. Any work to bridge this gap is certainly solving a meaningful problem.

The main idea is to use CRDTs, commutative replicated data types, on which all operations commute, to allow for the construction of data structures without communication: if all operations can be applied in any order, just apply it locally and them disseminate the operation, since eventually it will reach all replicas and we don't mind if it was applied out-of-order. Note that this is still eventual consistency and makes no guarantees about how soon things will be consistent, just that they will eventually reach such a state.

I think this work was different from previous work partly because of the size of systems in today's world; concurrency control schemes which previously worked fine are reaching the limits of their scalability and it is important that we investigate new ways to achieve the same consistency guarantees in more scalable ways.

One trade-off is generality vs. speed; not everything can easily be represented as a CRDT. There is also the trade-off of ease of use; CRDTs are only eventually consistent, and this must be planned for as an application programmer.

I can definitely see this paper being influential moving forward--though I don't see CRDTs in this form being widely used, the ideas are important.

Review of "Coordination Avoidance in Database Systems"

Scalability is hugely important in today's world, and communication/coordination is the bane of scaling. This paper works towards reducing the amount of coordination necessary for maintaining correctness, a very important problem.

The main idea is to analyze transaction sets against application invariants to determine when exactly coordination is necessary, in contrast to traditional database systems which serialize all transactions. By only coordinating when absolutely necessary, many transactions can run independently in parallel.

A trade-off here is complexity vs. speed. It is much easier to reason about transactions as completely serializable, and you don't need to write down all of your invariants, but this will often be worth it in a high performance setting.

This work seems very interesting - I feel that most literature I have seen uses the same concurrency scheme for all transactions, and the idea of predetermining which transactions actually need coordination seems like it will have a lot of practical benefits as systems scale larger and larger. I can definitely see this being influential in 10 years.

Review of "Shielding Applications from an Untrusted Cloud with Haven"

They are solving a very interesting problem: shielding application-level code from the OS that is executing it. I am not convinced that this is a real problem in today's world...

The main idea of their solution is to use hardware-provided instructions (Intel SGX) to be able to allocate protected memory regions (enclaves) within which the application's execution code is protected, even from the OS which is running that code. Haven takes a viewpoint that neither the OS nor the application trust each other, and provide interesting ways for them to provide services to each other despite this limitation.

This work is emerging because it is becoming increasingly more common to run your application on hardware that is managed by others, e.g. Microsoft Azure, Amazon EC2, etc. Previously, you managed the hardware, but were concerned about application-level possibly doing some harmful. Now, the hardware providers still need to be concerned with that same problem, but application-level code is also dealing with an outside entity and may want to be protected.

A big trade-off here is speed; the extra protection comes at a cost of higher latency because of things like system calls being more expensive, and generally using SGX extensions has a bit higher cost.

I don't really see this being overly influential in 10 years - like I said earlier, I am not convinced this is a real issue.

Review of "CryptDB: Protecting Confidentiality with Encrypted Query Processing"

This paper addresses an issue that has become increasingly more important as of late, viewable as an issue even to those not involved in the software community. Data breaches are becoming increasingly more common, and increasingly more devastating, so encryption of sensitive data is very important. Having a DB that makes this directly in to its storage seems very promising.

The main nugget is to store the data in an encrypted format inside of the DB, but store it such that SQL queries are still able to execute over the data. This is made possible because SQL has a specific subset of operations that it will run, and thus the encryption scheme can be aware of these operations. Though sometimes data will need to be decrypted for certain operations, CryptDB attempts to minimize the amount of data that is decrypted.

I cannot say exactly why this is new work - perhaps partially because security has become an increasingly larger concern as more data is stored online and data hacking has become increasingly widespread and damaging.

The primary trade-off here is resource cost vs security. A fully homomorphic cryptography scheme would provide even better security, since it could execute all of the necessary operations without decrypting data, but would be very prohibitively CPU intensive. CryptDB attempts to provide security while still providing reasonable real-world performance, and seems to do a good job at this.

I can see this being influential in 10 years -- companies are being slammed harder and harder by data breaches and anything that can remedy this must pique the interest of many large companies.

Review of "A Sampling Algebra for Aggregate Estimation"

While there is a great deal of work going into making databases fast so that you can process the wealth of data you collect in today's world, it still remains useful to do sampling to obtain a quick estimate of a result. But in today's world, you often have no idea (except perhaps an intuition) how accurate that data is. People have figured it out in some cases, but not in a way that is at all general. This paper serves to solve that, with a main contribution of the idea of a GUS (generalized uniform sampling) operator which can describe any sampling method, as well as the idea of Second Order Analytic (SOA) equivalence to denote the equivalence of two query plans in terms of expected value and variance. Combining these with supported relational operators provides a way to reason about and calculate error bounds for nearly any type of sampling.

It seems to be that this is new because as data volumes grow, it becomes ever more important to be able to sample and sample confidently. 

There is a trade-off here in that the generality of the GUS also makes it harder to reason about - I certainly had trouble really understanding what things meant. 

I can see this being influential in 10 years; they provide a general use tool for others to use in a space that can only become increasingly more important as we move forward. 

Review of "Succinct: Enabling Queries on Compressed Data"

Everyone needs to store enormous amounts of data these days, and everyone wants to be able to access it quickly. Succinct presents the problem that storing large quantities of data means you want to be as space-efficient as possible, but to access it quickly you (generally) build indices, which are not at all space-efficient. I am unsure how frequent of a problem this is in practice, but I imagine that there are many use cases for Succinct where it would greatly advance the current state of the art.

The main idea of Succinct is to essentially build an indexing system into the compression. This eliminates the need for space-costly secondary indexes, while also providing fast search capabilities.

I think this is probably different from previous work because the quantities of data that are now being stored in e.g. NoSQL systems are blooming hugely, and in the past typical systems did not need to rely as heavily on compression and space awareness, but the increase in data volume has made it a very necessary feature. Yet, at the same time, the data still needs to be accessed quickly, leading to Succinct.

The trade-off here is, of course, speed vs. space. Succinct falls into a pretty happy middle ground between the two, though it still falls short in some areas, e.g. large sequential reads.

I can see this being influential in the future - this seems to be a very new way of thinking about compressed storage that should be very useful.

Review of "Mining Modern Repositories with Elasticsearch"

As companies gain increasingly larger amounts of data, they need scalable solutions to deal with that data. Most of what we have looked at in this class has been somewhat complex - how to process large amounts of data, etc. - but we can't forget about one of the simplest applications: simply finding things within this wealth of data, aka search.

This is different from previous offerings simply because of the volume of data - local searching and indexing is by no means a new concept, so the main contribution of Elasticsearch was intelligently distributing and sharding this data to be able to access it quickly in a scalable manner.

The trade-off is primarily complexity vs speed. Elasticsearch is pretty simple: you get textual searches on certain fields, even letting you define a range for e.g. numeric types, but that's about it. There's no joining, aggregation, etc. On the other hand, this enables it to run extremely quickly on very large datasets.

This paper in particular I don't see being influential in 10 years, but I do see Elasticsearch in general (or at least, some derivative) continuing to be very important moving forward.

Review of "Spark SQL: Relational Data Processing in Spark"

Spark SQL solves two interesting problems simultaneously: better support for declarative / SQL programming on nested / semistructured / big data, and better integration of procedural with declarative programming.

The main idea is to provide a DataFrames API which abstracts a data source (RDD, Hive table, CSV file, etc) and provides relational-style operations which can be optimized. This allows developers to seamlessly operate on many different data storages, including Java/Python objects. They also introduce the Catalyst optimizer, a highly extensible query optimizer. One important thing to notice, in my opinion, is how flexibly the entire system was built: it is easy to define new data sources, optimizations, UDTs, and UDFs, all of which play nicely together.

One thing about this paper that I think will continue to be influential is the idea of mixing declarative / SQL programming with procedural programming. While it has always been possible to some extent using UDFs, Spark SQL provides a much more integrated intermingling that seems both easier to work with and more flexible.