The last 25 years DBMS is trying to design a one size fits all system. Basically, traditional database has been used for varied application types. And the authors argue that the "one size fits all" DBMS would be a failure. In fact the one size fits all illusion is because of the same user interface. Indeed, they run multiple system on the background.
Nowadays domain specific engine can beat RDBMS by 10x (e.g. Data warehouse, text search, stream processing, scientific data). For example, for the performance discussion, the in-bound data processing is increasingly take place of out-bound data storage. Therefore , the stream processing engines extend the SQL data processing system, which is used for conventional DBMS.
The main idea of this paper is to illustrate several domain specific engine that can outperform than the "one size fits all" DBMS.
The trade-off here is whether you should use a general system which supply more data type while sacrificing the performance, or using domain specific engine which has faster performance but the application type is narrowing down.
I think it will be influential in the future, since the debate between whether using domain specific engine or general engine is always a topic in database area.
Monday, November 23, 2015
Sunday, November 22, 2015
Review for "Managing Data Transfers in Computer Clusters with Orchestra"
Previous solutions for maximizing cluster utilization efficiency has been focusing on computing and storage usage. However, the network resources have been ignored.
In the paper, the author argue that in order to achieve good job performance, we should focus on transfer instead of each flow. A transfer is defined as all data flow transmitted between two stages of a job. They mainly focus on two transfer types, shuffle and broadcast. In intra-transfer activities, they design a Transfer Controller. For broadcast, they propose a transfer controller scheme called Cornet. For shuffle, they present weight shuffle scheduling. For inter-transfer, they design a simple ITC (inter-transfer controler), which can support FIFO, priority scheduling, etc. The basic idea of ITC is to achieve a weighted fair sharing.
Previous works have been analyzing and optimizing the network performance. They propose flow-level scheduling to improve the performance. However, it lacks of job-level semantics, thus cannot schedule collective behaviors.
The trade-off here is between utility and deployability. Orchestra can be implemented at the application level. Therefore it can be directly implemented into existing clusters without any modifications on hardware or management mechanism. However, this application-level transfer control cannot achieve perfect control over the network.
As a networking guy, I like the idea of Orchestra. And since it has been used in Apache Spark for shuffle process, I believe it will still be influential in 10 years.
In the paper, the author argue that in order to achieve good job performance, we should focus on transfer instead of each flow. A transfer is defined as all data flow transmitted between two stages of a job. They mainly focus on two transfer types, shuffle and broadcast. In intra-transfer activities, they design a Transfer Controller. For broadcast, they propose a transfer controller scheme called Cornet. For shuffle, they present weight shuffle scheduling. For inter-transfer, they design a simple ITC (inter-transfer controler), which can support FIFO, priority scheduling, etc. The basic idea of ITC is to achieve a weighted fair sharing.
Previous works have been analyzing and optimizing the network performance. They propose flow-level scheduling to improve the performance. However, it lacks of job-level semantics, thus cannot schedule collective behaviors.
The trade-off here is between utility and deployability. Orchestra can be implemented at the application level. Therefore it can be directly implemented into existing clusters without any modifications on hardware or management mechanism. However, this application-level transfer control cannot achieve perfect control over the network.
As a networking guy, I like the idea of Orchestra. And since it has been used in Apache Spark for shuffle process, I believe it will still be influential in 10 years.
Saturday, November 21, 2015
Review for "FairCloud: Sharing The Network In Cloud Computing"
The key problem here is that, networking performance of a VM x not only depend on the VMs running on the same machine, but also on the VMs that x communicated with and the multiplexing data transfer on the links used by x.
The authors want to design a new approach which fulfill the following 3 requirements. 1 network share should be promotional to the payment. 2 users should receive some guarantee about the minimum network bandwidth they can use. 3 maximize the network utilization
There are mainly two key concept in FaireCloud. First, they allocate the congested links in proportional to the number of VM instead of number of links/flows. Second, they use the VM proxy to link to a tenant's share on the link.
The trade-off here is between the ability to share congested links in proportional to the payment and providing the minimum bandwidth guarantee.
I think it will be influential in 10 years. It is because that the networking performance is a key issue on cloud computing area.
Review for "Towards Predictable Datacenter Networks"
The cloud provider and tenants relationship is common in today's on-demand usage of computing resources. However, the interface between provider and tenants do not consider about the networks. The provider do not guarantee the network resources for the tenants, and let the tenants share the whole network. This high variably networking performance will cause several problems: unpredictable application performance and tenant cost, limited cloud applicability, inefficiency in production and revenue loss.
The authors propose the "virtual networks" as a network abstraction or interface between cloud provider and tenants. The corresponding implemented system is called "Oktopus". Basically, besides the computing instances, they now offer a new network connecting the computing instances. And they provides two abstraction for the virtual network topology. First, "virtual cluster" provides illusion of all VM connecting to a single switch. Second, "virtual oversubscribed cluster" provides an oversubscribed two-layer cluster.
Compared with previous works like Seawall or NetShare which also focus on network sharing in data center, Oktopus can balance the trade-off between the tenant demand and provider flexibility. Other allocation schemes try to allocate arbitrary network thus hamper the system scalability.
The trade off here in Oktopus is the balance between tenants' demand and provider's flexibility.
I think this work will be influential in 10 years, since it is a key issue in current cloud computing environment.
The authors propose the "virtual networks" as a network abstraction or interface between cloud provider and tenants. The corresponding implemented system is called "Oktopus". Basically, besides the computing instances, they now offer a new network connecting the computing instances. And they provides two abstraction for the virtual network topology. First, "virtual cluster" provides illusion of all VM connecting to a single switch. Second, "virtual oversubscribed cluster" provides an oversubscribed two-layer cluster.
Compared with previous works like Seawall or NetShare which also focus on network sharing in data center, Oktopus can balance the trade-off between the tenant demand and provider flexibility. Other allocation schemes try to allocate arbitrary network thus hamper the system scalability.
The trade off here in Oktopus is the balance between tenants' demand and provider's flexibility.
I think this work will be influential in 10 years, since it is a key issue in current cloud computing environment.
Thursday, November 19, 2015
Review for "Fastpass: A Centralized “Zero-Queue” Datacenter Network"
Current networks mainly make packets transmission decisions by congestion control and packet routing. By doing so, it can achieve high scalability and good fault tolerance. However, this kind of method cannot achieve low latency. Basically, the high latency is because of the queue, which is used for absorbing packet bursts. The mean delay maybe low, but the tail delay is high.
The authors try to design a centralized arbiter to control all packets's timing and routing path. They try to build a system that can allow endpoints burst at the full-bandwidth capacity, at the mean time, eliminating congestions at switches.
There are three main components:
1 time slot allocation algorithm. It is used for determine when should each packet being sent at endpoints.
2 path assignment algorithm. It enable the arbiter to decide which routing path should a packet being sent.
3 a replication strategy for the central arbiter. It is used for failure recovery.
Previous works also focus on using centralized controller, in order to get better load balancing and network sharing. However, they work at the control plane for the coarse granularity. Therefore, it cannot provide packet-level latency control and allocation over small time scale.
For the trade-off, the centralized arbiter is not good for the scalability of data center networks. Since it only contain one arbiter, when the system scales, the arbiter may be the bottleneck.
I think this paper could not be influential in 10 years. Since it is not suitable for scalability.
The authors try to design a centralized arbiter to control all packets's timing and routing path. They try to build a system that can allow endpoints burst at the full-bandwidth capacity, at the mean time, eliminating congestions at switches.
There are three main components:
1 time slot allocation algorithm. It is used for determine when should each packet being sent at endpoints.
2 path assignment algorithm. It enable the arbiter to decide which routing path should a packet being sent.
3 a replication strategy for the central arbiter. It is used for failure recovery.
Previous works also focus on using centralized controller, in order to get better load balancing and network sharing. However, they work at the control plane for the coarse granularity. Therefore, it cannot provide packet-level latency control and allocation over small time scale.
For the trade-off, the centralized arbiter is not good for the scalability of data center networks. Since it only contain one arbiter, when the system scales, the arbiter may be the bottleneck.
I think this paper could not be influential in 10 years. Since it is not suitable for scalability.
Review for "Less is More: Trading a little Bandwidth for Ultra-Low Latency in the Data Center"
The data flow in the network can be categorized into 2 parts, throughput originated applications, and latency sensitive applications. However, the latency sensitive applications need a man in the loop and the completion time is slow. Therefore, the network is not optimized with for latency or predictable packet delivery.
The author proposes HULL (High bandwidth Ultra Low Latency), a system that can ensure deliver ultra-low latency packet and high bandwidth utilization in a shared data center fabric. The observation here is it is possible to reduce or eliminate network buffering. Given this, the author cap the bandwidth and trade for low latency.
The nugget of HULL is to trade bandwidth with latency in the network. They leverage pacer module to place space between the packets of large flow. And it also implement a dynamic pacing rate estimation function to adjust pacing dynamically.
The previous works mainly focus on bandwidth provisioning for achieving low latency. On the contrary, HULL is try to sacrifice some bandwidth in order to achieve low latency.
The trade off here is of course the lower bandwidth utility in HULL.
I think the idea is interesting. And it maybe influential in 10 years.
The author proposes HULL (High bandwidth Ultra Low Latency), a system that can ensure deliver ultra-low latency packet and high bandwidth utilization in a shared data center fabric. The observation here is it is possible to reduce or eliminate network buffering. Given this, the author cap the bandwidth and trade for low latency.
The nugget of HULL is to trade bandwidth with latency in the network. They leverage pacer module to place space between the packets of large flow. And it also implement a dynamic pacing rate estimation function to adjust pacing dynamically.
The previous works mainly focus on bandwidth provisioning for achieving low latency. On the contrary, HULL is try to sacrifice some bandwidth in order to achieve low latency.
The trade off here is of course the lower bandwidth utility in HULL.
I think the idea is interesting. And it maybe influential in 10 years.
Review for "pFabric: Minimal Near-Optimal Datacenter Transport"
In existing TCP-based fabrics, it introduce high latency in short flow processing. The key reason for this is that the short flows are often get queued behind the large amount of packets from large flow of the co-existing network workload. Therefore, this queue latency significantly introduce more latency on the short flows.
The most important concept here is that, rate control is a poor and ineffective scheme for flow control. The key design of pFabric is a priority-based packet scheduling. More precisely, each host put a priority number in the header of each packet. And the switch can determine which packet should in the queue and which should be scheduled strictly by its priority. When the switch buffer is full, the switch can compare the priority level to decide which packed should be dropped. For the flow control, all the flows start with line-speed and being limited only when there is high loss rate.
Previous works that try to solve this short flow's high latency problem by using rate control. The first kind of works is to reduce the queue length (i.e. keep it nearly empty). Therefore, with less queue, there is less latency, which improves FCT (flow completion times). The second kind of approach is to repeatedly calculate and assign rate to each flow in the network. However, it is complicated and impractical in real-world deployment.
The trade off here is since pFabric guarantee the short flow to have short FCT, it may leads to starvation on the large flows.
pFabric is essentially useful for interactive short flow transmission in the real-world scenarios. I think it will be influential with 10 years.
The most important concept here is that, rate control is a poor and ineffective scheme for flow control. The key design of pFabric is a priority-based packet scheduling. More precisely, each host put a priority number in the header of each packet. And the switch can determine which packet should in the queue and which should be scheduled strictly by its priority. When the switch buffer is full, the switch can compare the priority level to decide which packed should be dropped. For the flow control, all the flows start with line-speed and being limited only when there is high loss rate.
Previous works that try to solve this short flow's high latency problem by using rate control. The first kind of works is to reduce the queue length (i.e. keep it nearly empty). Therefore, with less queue, there is less latency, which improves FCT (flow completion times). The second kind of approach is to repeatedly calculate and assign rate to each flow in the network. However, it is complicated and impractical in real-world deployment.
The trade off here is since pFabric guarantee the short flow to have short FCT, it may leads to starvation on the large flows.
pFabric is essentially useful for interactive short flow transmission in the real-world scenarios. I think it will be influential with 10 years.
Review for "Jellyfish: Networking Data Centers Randomly"
One key problem that current data centers encounter is the incremental network expansion. More precisely, the entire structure of increase the network bandwidth is determined by the port-count on the switch. Thus the incremental delta can only be coarse. Even one can replace a switch with larger port size, this makes the whole network's capacity distribution unbalanced.
Therefore, the authors try the opposite way: to build the network in random interconnection, called "Jellyfish". Jellyfish is to construct a random graph at the Top-of-Rack switch layer. The key insight is that, compared with structured graph, random graph has lower path length on average. Therefore, when the network is at its full capacity, low path length enable us to support more flow at high throughput in the network.
A large amount of previous works are focusing on building high capacity network interconnects. However, they cannot solve the problem of incremental networking expansion. The most related works are build on certain port-count fact, which hinder the system linage incremental performance.
For the trade off, the cabling issue of JellyFish may be more complicated than the structured ones.
I think it will not be accepted in industry within a few years. It changes to much on existing structured networks. Therefore, I do not think it will still have impacts in 10 years.
Therefore, the authors try the opposite way: to build the network in random interconnection, called "Jellyfish". Jellyfish is to construct a random graph at the Top-of-Rack switch layer. The key insight is that, compared with structured graph, random graph has lower path length on average. Therefore, when the network is at its full capacity, low path length enable us to support more flow at high throughput in the network.
A large amount of previous works are focusing on building high capacity network interconnects. However, they cannot solve the problem of incremental networking expansion. The most related works are build on certain port-count fact, which hinder the system linage incremental performance.
For the trade off, the cabling issue of JellyFish may be more complicated than the structured ones.
I think it will not be accepted in industry within a few years. It changes to much on existing structured networks. Therefore, I do not think it will still have impacts in 10 years.
Review for “PortLand: A Scalable Fault-Tolerant Layer 2 Data Center Network Fabric”
Basically the problem of data center network may be the scalability. More precisely, the future data center networks may need following 5 requirements. 1 any VM can be migrated to any physical machine without changing IP address. 2 administrators should have "plug and play" deployment on switches. 3 end host can efficiently communicate with other end hosts within the data center 4 no forwarding loop 5 failure detection and recover should be efficient and fast. And of course, it is not easy to fulfill all these requirement based on existing techniques. Therefore, the authors proposes PortLand scheme.
The fundamental observation of PortLand is that data center networks are often physically inter-connected as a multi-rooted tree (e.g. fat tree). So the nugget of Portland is to employ a lightweight protocol for switches to discover their own position in the network topology. Basically, the location discovery is to let the switches send messages indicating the port directions. The key insight here is the edge switches only receive message from aggregation routers, whereas the aggregation routers receive messages from edges routers downwards facing the port.
Previous works mainly suffer from the scalability or cannot fulfill the 5 requirements mentioned above. Whereas PortLand can achieve all the requirements and easy to be scaled.
PortLand is designed for a unknown network topology. However, when you have a known topology, there is no need to build up such a system.
I think PortLand may be influential in ten years. Currently I think existing protocols works well in data center networks, there is no need to build up such a system. However, in the future, when the data center is huge, it may need to use PortLand protocol.
The fundamental observation of PortLand is that data center networks are often physically inter-connected as a multi-rooted tree (e.g. fat tree). So the nugget of Portland is to employ a lightweight protocol for switches to discover their own position in the network topology. Basically, the location discovery is to let the switches send messages indicating the port directions. The key insight here is the edge switches only receive message from aggregation routers, whereas the aggregation routers receive messages from edges routers downwards facing the port.
Previous works mainly suffer from the scalability or cannot fulfill the 5 requirements mentioned above. Whereas PortLand can achieve all the requirements and easy to be scaled.
PortLand is designed for a unknown network topology. However, when you have a known topology, there is no need to build up such a system.
I think PortLand may be influential in ten years. Currently I think existing protocols works well in data center networks, there is no need to build up such a system. However, in the future, when the data center is huge, it may need to use PortLand protocol.
Tuesday, November 17, 2015
Review for "VL2: A Scalable and Flexible Data Center Network"
Agility is an important character for the data
center networks. However, the structure of today's data center networks prevent
agility. More precisely, there are 3 main issues. First, conventional data
center networks are hierarchal, which do not provide enough capacity between
servers. Second, when hosting multiple services, the data center network is
fragile with traffic flood. Once a service has traffic flood, it will have
collateral effects on other services.
The VL2 is trying to deal with the limitations
of existing data center networks and also provide agility. There are three main
goals of VL2: uniform high capacity, performance isolation, layer-2 semantics.
Basically, VL2 is trying to build up a layer 2.5
for the servers’ network. VL2 incorporates with Clos topology and valiant load balancing, which provide extensive path among the servers. By implementing
Equal Cost Multipath and OSPF, VL2 can also achieve high scalability.
Previous works like fat-tree and Monsoon, they
cannot provide the communication-intensive operations such as data shuffle,
whereas VL2 can support these communication spikes. Dcell and BCube cannot be
scaled well, whereas VL2 can achieve good scalability.
I think VL2 can be influential in 10 years. It
is because VL2 actually solves some vital problem that existing data center
networks cannot deal with.
Review for "The Neo Database"
The traditional relational database has several problems needs to be solved:
1 The object-relational impedance mismatch
2 It is uneasy to evolve schemas in the RDBMS.
3 The relational model is not suitable for capturing semi-structured data.
4 it performs poorly when traversing the network in order to extract information.
The NEO model is trying to deal with the problems mentioned above. In NEO, everything is translated into nodes, relationship and properties. A relationship connects two nodes. The property are key-value paris which attached into both relationship and nodes. Indeed, NEO's data model is a network.
NEO is good for data that is naturally ordered in network. It makes the user easier to write complex and high-performance traversals on data. In addition the semi-structured data can be easily stored in NEO.
The trade-off here is, NEO may have a learning curve compared with other relational tools like SQL, etc. In addition, the relational databases are much better in processing arbitrary queries on structured data.
I think NEO may not be influential in 10 years. Even though the model is novel and insightful, there is no that significant gain compared with relational database.
1 The object-relational impedance mismatch
2 It is uneasy to evolve schemas in the RDBMS.
3 The relational model is not suitable for capturing semi-structured data.
4 it performs poorly when traversing the network in order to extract information.
The NEO model is trying to deal with the problems mentioned above. In NEO, everything is translated into nodes, relationship and properties. A relationship connects two nodes. The property are key-value paris which attached into both relationship and nodes. Indeed, NEO's data model is a network.
NEO is good for data that is naturally ordered in network. It makes the user easier to write complex and high-performance traversals on data. In addition the semi-structured data can be easily stored in NEO.
The trade-off here is, NEO may have a learning curve compared with other relational tools like SQL, etc. In addition, the relational databases are much better in processing arbitrary queries on structured data.
I think NEO may not be influential in 10 years. Even though the model is novel and insightful, there is no that significant gain compared with relational database.
Review for "TAO: Facebook's Distributed Data Store for the Social Graphs"
Since Facebook needs to check the privacy and data dependency everytime when the content is viewed. This kind of implementation place high pressure on reading from the graph data store.
The previous lookaside cache (e.g. Memcache) has some problems. 1 Inefficient edge lists (single edge change requires entire list to be reloaded) 2 Distributed control logic (control logic do not communicate with each other, which leads to thundering herds) 3 Expensive read-after-write consistency. TAO can solve all of these questions. And this maybe the main difference of TAO compared with other related works.
TAO's goal is to achieve low read latency, high read availability, write consistency. The key architecture of TAO is three parts, web server, cache, database. Basically, they use separate cache and database, graph-specific caching and subdivide data centers to achieve efficiency at scale read latency. In order to avoid thundering herds, it propose a leader cache layer, which is used for coordinating the follower caches. The write-through cache is used for enable read-after-write consistency.
In order to improve the availability, the read failover of a follower cache will have not cost. It is because if we cannot request from the corresponding follower cache, we can instead query on a different follower cache. If we cannot talk to the leader cache, we can bypass it and directly go to the databases for the results. And if we cannot query on the data base of replica data center, we can directly forward the query to the leader cache of the master data center.
I think TAO will be influential for 10 years. It is because that the TAO system is used as a new generation of data store for Facebook.
The previous lookaside cache (e.g. Memcache) has some problems. 1 Inefficient edge lists (single edge change requires entire list to be reloaded) 2 Distributed control logic (control logic do not communicate with each other, which leads to thundering herds) 3 Expensive read-after-write consistency. TAO can solve all of these questions. And this maybe the main difference of TAO compared with other related works.
TAO's goal is to achieve low read latency, high read availability, write consistency. The key architecture of TAO is three parts, web server, cache, database. Basically, they use separate cache and database, graph-specific caching and subdivide data centers to achieve efficiency at scale read latency. In order to avoid thundering herds, it propose a leader cache layer, which is used for coordinating the follower caches. The write-through cache is used for enable read-after-write consistency.
In order to improve the availability, the read failover of a follower cache will have not cost. It is because if we cannot request from the corresponding follower cache, we can instead query on a different follower cache. If we cannot talk to the leader cache, we can bypass it and directly go to the databases for the results. And if we cannot query on the data base of replica data center, we can directly forward the query to the leader cache of the master data center.
I think TAO will be influential for 10 years. It is because that the TAO system is used as a new generation of data store for Facebook.
Saturday, November 14, 2015
Review for "GraphX: Graph Processing in a Distributed Dataflow Framework"
The problem of graph processing is that it may not scale well and also it do not support for the fault tolerance. In addition, most of graph processing system are specially designed which is not well suited for general purpose graph processing. Furthermore, the graphs are often part of the data workflow which also contains unstructured and tabular data.
On the other side, general purpose distributed data flow frameworks are well suited for deal with the problems mentioned above. Thus, the author tries to convert previous specialized graph processing frameworks into a general purpose distributed dataflow framework. Therefore, the author build up a general purpose graph processing system on top of Apache Spark, called GraphX. By incorporating with spark, GraphX can enable users to easily and efficiently express the graph analytics pipeline.
The basic idea of GraphX is illustrated as follows. Basically, it first leverages flexible vertex-cut to split the graph into small pieces, and then encoding the split graphs as collections in Spark. In addition, since GraphX is based on Spark, it is naturally inherited of fault tolerant by leveraging the lineage and logical partitioning.
The difference of GraphX and other existing schemes is that, GraphX can achieve the composition of graphs with unstructured and tabular data. In addition, by leveraging logical partitioning and lineage in Spark, GraphX can achieve fault tolerance.
The trade off here is, since GraphX is a more general system designed for graph processing, compared with specialized graph processing system, GraphX may need more time for running the same job. It is because that specialized system are optimized for only a group of graph problem, thus it can achieve better optimization.
I think to design and implement a graph processing system which can serve as a general purpose architecture is very useful. And Spark is now on fire. Therefore, I think GraphX can also be influential within 10 years.
On the other side, general purpose distributed data flow frameworks are well suited for deal with the problems mentioned above. Thus, the author tries to convert previous specialized graph processing frameworks into a general purpose distributed dataflow framework. Therefore, the author build up a general purpose graph processing system on top of Apache Spark, called GraphX. By incorporating with spark, GraphX can enable users to easily and efficiently express the graph analytics pipeline.
The basic idea of GraphX is illustrated as follows. Basically, it first leverages flexible vertex-cut to split the graph into small pieces, and then encoding the split graphs as collections in Spark. In addition, since GraphX is based on Spark, it is naturally inherited of fault tolerant by leveraging the lineage and logical partitioning.
The difference of GraphX and other existing schemes is that, GraphX can achieve the composition of graphs with unstructured and tabular data. In addition, by leveraging logical partitioning and lineage in Spark, GraphX can achieve fault tolerance.
The trade off here is, since GraphX is a more general system designed for graph processing, compared with specialized graph processing system, GraphX may need more time for running the same job. It is because that specialized system are optimized for only a group of graph problem, thus it can achieve better optimization.
I think to design and implement a graph processing system which can serve as a general purpose architecture is very useful. And Spark is now on fire. Therefore, I think GraphX can also be influential within 10 years.
Review for "PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs" (OSDI‘12)
Graph-structure computation is very popular and important in data processing. However, the real-world graph have highly skewed power-law degree. More precisely, a small amount of vertex have connections with a large fraction of nodes within the graph.
Therefore, Power graph tries to provide great parallelism and reduce the network connections in the graph processing. The key concept of PowerGraph is to exploring the factor computation over edges instead of vertices.
Different from previous works like Pregel or GraphLab, these kind of system cannot deal with the high-skewed power-law degree problem. Whereas PowerGraph is designed for deal with this problem.
The nugget of PowerGraph is to "Think like a vertex". Basically, it tries to split the high-degree vertex and design a new abstraction for the spliced vertices. Therefore, PowerGraph can run multiple vertex programs in parallel in a cluster instead of a single node.
The high parallelization is based on increasing the storage overhead. I think it maybe a trade-off here for the power graph.
Graph problem is a main challenge in nowadays data processing. In addition, the increasing using of large-scale cluster computing is a big trend. To processing graph problem based on these big data processing system is a important way to achieve high performance. I think it will be influential within 10 years.
Therefore, Power graph tries to provide great parallelism and reduce the network connections in the graph processing. The key concept of PowerGraph is to exploring the factor computation over edges instead of vertices.
Different from previous works like Pregel or GraphLab, these kind of system cannot deal with the high-skewed power-law degree problem. Whereas PowerGraph is designed for deal with this problem.
The nugget of PowerGraph is to "Think like a vertex". Basically, it tries to split the high-degree vertex and design a new abstraction for the spliced vertices. Therefore, PowerGraph can run multiple vertex programs in parallel in a cluster instead of a single node.
The high parallelization is based on increasing the storage overhead. I think it maybe a trade-off here for the power graph.
Graph problem is a main challenge in nowadays data processing. In addition, the increasing using of large-scale cluster computing is a big trend. To processing graph problem based on these big data processing system is a important way to achieve high performance. I think it will be influential within 10 years.
Friday, November 13, 2015
Review for "Materialization Optimizations for Feature Selection Workloads" (SIGMOD'14)
In machine learning, feature selection is the most critical step in data analysis. And based on the survey conducted with industrial analysis, the feature selection is an interactive process. Given this, the authors design a feature-selection language, and also implement it into a R-integaration-based system.
Basically, the user write a standard R program, and directly using the library that provided by the system called "Columbus". After that, the Columbus will use these high-level constructs to optimize the data and computation reuse.
More precisely, Columbus optimize several aspects of feature selections: 1 subsampling, 2 transformation materialization, 3 model caching. This new system also incorporates decomposition (QR decomposition), multiblock logical optimizations and also warmstart methods to optimize the performance.
Trade off: Since user needs to use the high-level columbus libraries, it can be optimized by columbus's optimizer for data and computation reuse. However, it may not enable users to modify or specify some detailed functions within the columbus libraries.
It is a very efficient way for data analysis optimization. I think it will be influential in 10 years.
Basically, the user write a standard R program, and directly using the library that provided by the system called "Columbus". After that, the Columbus will use these high-level constructs to optimize the data and computation reuse.
More precisely, Columbus optimize several aspects of feature selections: 1 subsampling, 2 transformation materialization, 3 model caching. This new system also incorporates decomposition (QR decomposition), multiblock logical optimizations and also warmstart methods to optimize the performance.
Trade off: Since user needs to use the high-level columbus libraries, it can be optimized by columbus's optimizer for data and computation reuse. However, it may not enable users to modify or specify some detailed functions within the columbus libraries.
It is a very efficient way for data analysis optimization. I think it will be influential in 10 years.
Review for Bismarck (SIGMOD'12)
The problem is that, the implementation of new statistical technique into RDBMS is a huge and complicated development process. The authors want to propose a unified architecture for in-database analytics. Basically, they want to leverage existing code path as much as possible when developing the new platforms.
The main difference of this paper compared with other related works is that, Bismarck is a general statistical technique that can be span to many different models. In short, it is a more general one.
The authors find out that many common data analytics problem can be formalized as convex programming problem. They propose a unified architecture "Bismarck". The key idea of BISMARCK is to formulate many data analytics as incremental gradient descent (IDG) into RDBMS. The main component of BISMARCK is the IDG with a data access pattern similar to SQL aggregate query.
In addition, the authors also made several optimization in BISMARCK. For example, it changes the per epoch shuffle into a one-time shuffle, etc.
The trade-off is that, even the one-time shuffle reduce the computational complexity, it may lead to bad performance if the rendering order is not good for the IDG.
From my perspective, the general model/system is much more suited than specified ones. Therefore, I think it will still be useful in the future.
The main difference of this paper compared with other related works is that, Bismarck is a general statistical technique that can be span to many different models. In short, it is a more general one.
The authors find out that many common data analytics problem can be formalized as convex programming problem. They propose a unified architecture "Bismarck". The key idea of BISMARCK is to formulate many data analytics as incremental gradient descent (IDG) into RDBMS. The main component of BISMARCK is the IDG with a data access pattern similar to SQL aggregate query.
In addition, the authors also made several optimization in BISMARCK. For example, it changes the per epoch shuffle into a one-time shuffle, etc.
The trade-off is that, even the one-time shuffle reduce the computational complexity, it may lead to bad performance if the rendering order is not good for the IDG.
From my perspective, the general model/system is much more suited than specified ones. Therefore, I think it will still be useful in the future.
Wednesday, November 11, 2015
Review for Scaling Distributed Machine Learning with the Parameter Server (OSDI'14)
Current powerful and complex machine learning model can have 10^9 to 10^12 parameters. The parameter sharing among work nodes in the cluster is challenging. There are mainly 3 challenges:
1 parameter access require high network bandwidth.
2 synchronization and machine latency may hurt the system performance.
3 fault tolerant cannot be guaranteed in the cloud computing environment.
The Parameter server (PS) is trying to manage the parameters among the nodes within the cluster. Briefly, there are mainly five unique characters: 1 Efficient communication, 2 Flexible consistency models, 3 Elastic Scalability, 4 Fault Tolerance and Durability, 5 Ease of Use. And this is the main difference between this scaling ML parameter server and other related works.
The parameter server that the authors proposed is the 3rd generation PS system. It mainly contains two parts: the server group and the work group. For each work group it only report updates to its own corresponding server node, instead of to all the node in the server group. All server nodes partition parameters keys with consistent hashing.
The tread-off here is that there is no feature balance within the cluster. More precisely, if a working node contains 90% or more features of the machine learning model. This is not a good load balance among all the workers.
In addition, there is another trade-off of asynchronous calls. Even it main use less time for data processing compared with synchronized system. However, it may need more iteration during data processing.
Since machine learning is vital to nowadays cluster computing, I think this parameter server can be influential within 10 years. Maybe there is some more features added in the Distributed parameter server.
1 parameter access require high network bandwidth.
2 synchronization and machine latency may hurt the system performance.
3 fault tolerant cannot be guaranteed in the cloud computing environment.
The Parameter server (PS) is trying to manage the parameters among the nodes within the cluster. Briefly, there are mainly five unique characters: 1 Efficient communication, 2 Flexible consistency models, 3 Elastic Scalability, 4 Fault Tolerance and Durability, 5 Ease of Use. And this is the main difference between this scaling ML parameter server and other related works.
The parameter server that the authors proposed is the 3rd generation PS system. It mainly contains two parts: the server group and the work group. For each work group it only report updates to its own corresponding server node, instead of to all the node in the server group. All server nodes partition parameters keys with consistent hashing.
The tread-off here is that there is no feature balance within the cluster. More precisely, if a working node contains 90% or more features of the machine learning model. This is not a good load balance among all the workers.
In addition, there is another trade-off of asynchronous calls. Even it main use less time for data processing compared with synchronized system. However, it may need more iteration during data processing.
Since machine learning is vital to nowadays cluster computing, I think this parameter server can be influential within 10 years. Maybe there is some more features added in the Distributed parameter server.
Review for ZooKeeper
The problem of coordination process in the distributed system is always a big challenge. The ZooKeeper is trying to solve this problem in a more general way.
The key components of ZooKeeper are illustrated as follows:
Wait-Free: ZooKeeper do not use locks for coordinations. Lock-free can achieve faster processing time, since the slow process cannot block other normal processes.
Order guarantee: Writes are linearizable (strongest guarantee), FIFO client ordering of all operations.
Watch mechanism: enable clients to see the updates on objects.
Different from previous work, ZooKeeper is a more general approach, which enable users implement their own primitives by exposing ZooKeeper's API. It is more like a coordination kernel.
In order to guarantee the operations satisfy linearzability, ZooKeeper incorporates with a leader-based atomic broadcast protocol called Zab. However, this atomic broadcast protocol also has shortcomings. Specifically, the atomic broadcast limits the throughput performance of ZooKeeper, when the size of ensemble increases.
ZooKeeper is a general coordination mechanism, and works well in many kinds of applications in or outside Yahoo!. I think it will still has impacts in next 5-10 years.
The key components of ZooKeeper are illustrated as follows:
Wait-Free: ZooKeeper do not use locks for coordinations. Lock-free can achieve faster processing time, since the slow process cannot block other normal processes.
Order guarantee: Writes are linearizable (strongest guarantee), FIFO client ordering of all operations.
Watch mechanism: enable clients to see the updates on objects.
Different from previous work, ZooKeeper is a more general approach, which enable users implement their own primitives by exposing ZooKeeper's API. It is more like a coordination kernel.
In order to guarantee the operations satisfy linearzability, ZooKeeper incorporates with a leader-based atomic broadcast protocol called Zab. However, this atomic broadcast protocol also has shortcomings. Specifically, the atomic broadcast limits the throughput performance of ZooKeeper, when the size of ensemble increases.
ZooKeeper is a general coordination mechanism, and works well in many kinds of applications in or outside Yahoo!. I think it will still has impacts in next 5-10 years.
Tuesday, November 10, 2015
Review for Raft
Previous implementations of consensus are mainly based on Paxos algorithm. However, Paxos is not easy to understand. In addition, its architecture needs to make many changes on existing practical systems. Therefore, it is needed to propose a new algorithm which may achieve the same duty as Paxos, but can be more suitable to practical system, and easier to understand. That is the reason why the authors propose Raft algorithm.
The consensus algorithms are with in the area of replicated state machines(SM). In the SM, keep the log consistent among servers is the main job of consensus algorithm.
Just like Paxos, Raft also has 3 roles: follower, candidate and leader. And during the runtime, it mainly contains two phrase: leader election and log replication.
Leader election: the followers transit into candidate state. And they vote and issues RequestVote RPCs within the cluster. Then finally one candidate will win when it receives votes from a majority of the servers.
Log replication: The elected Leader will make sure that AppendEntries RPCs in parallel to each of other servers to replicate the entry. And then the leader ensures the committed entries are executed by all the available state machines eventually.
Even though the authors claims that, compared with Paxos, their approach is easier to understand, I would argue about that. I do not think Raft is easier. And the "experimental result" of user study in two university(in total 43 students) is also untenable.
Yes, I think it will be influential in next few years. It is because, compared with Paxos, Raft is more like a system work instead of only theoretical statement.
The consensus algorithms are with in the area of replicated state machines(SM). In the SM, keep the log consistent among servers is the main job of consensus algorithm.
Just like Paxos, Raft also has 3 roles: follower, candidate and leader. And during the runtime, it mainly contains two phrase: leader election and log replication.
Leader election: the followers transit into candidate state. And they vote and issues RequestVote RPCs within the cluster. Then finally one candidate will win when it receives votes from a majority of the servers.
Log replication: The elected Leader will make sure that AppendEntries RPCs in parallel to each of other servers to replicate the entry. And then the leader ensures the committed entries are executed by all the available state machines eventually.
Even though the authors claims that, compared with Paxos, their approach is easier to understand, I would argue about that. I do not think Raft is easier. And the "experimental result" of user study in two university(in total 43 students) is also untenable.
Yes, I think it will be influential in next few years. It is because, compared with Paxos, Raft is more like a system work instead of only theoretical statement.
Review for Paxos
The consensus and fault tolerant in data processing is a vital problem, especially in large-scale distributed system. The Paxos is a consensus algorithm which ensures only one value proposed has been chosen, after which the processes can learn from the chosen value.
The key idea is three classes of agents: proposers, accepters and learner.
The assumptions of Paxos is that the message takes arbitrary time for delivery, and can be duplicated, can be lost. However, the message cannot be corrupted. Given this, it is not appropriate to implement Paxos algorithm when it is likely to have message corruptions.
I think it maybe a classical consensus algorithm. I am not sure, but I think it is simple and practical. Thus it maybe influential in the following years.
The key idea is three classes of agents: proposers, accepters and learner.
Proposers: propose (m, v)
Acceptors: accept proposals and choose values
Learners: learn the chosen values
Proposer proposes (n, v) such that v = value of highest number proposal among phase 1 responses, or any if no reported proposal
Acceptors: accept proposals and choose values
Learners: learn the chosen values
Phase 1: Prepare
Proposer proposes proposal number n
Acceptor responds if n > any prepare request to which it has responded
Phase 2: Accept
Phase 2: Accept
Proposer proposes (n, v) such that v = value of highest number proposal among phase 1 responses, or any if no reported proposal
Acceptor can accept request for a proposal unless
it has already responded to a prepare request
having a number greater than n.
I think it maybe a classical consensus algorithm. I am not sure, but I think it is simple and practical. Thus it maybe influential in the following years.
Tuesday, October 27, 2015
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.
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.
Monday, October 26, 2015
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.
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.
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.
Sunday, October 25, 2015
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.
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.
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.
Saturday, October 24, 2015
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)?
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.
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.
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
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.
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.
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.
Monday, October 12, 2015
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.
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?
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.
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.
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.
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.
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.
Wednesday, October 7, 2015
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.
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.
Tuesday, October 6, 2015
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?
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.
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.
Sunday, October 4, 2015
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.
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).
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.
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.
Subscribe to:
Posts (Atom)