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.
Subscribe to:
Posts (Atom)