1) Is the problem real?
Currently the use of MapReduce is far beyond its original design purpose. And there are mainly two shortcomings.
1. tight coupling of programing model with source management infrastructure. It makes developers to abuse the MR model.
2. centralized job control flow, which limits the system's scalability.
2) What is the solution’s main idea (nugget)?
Separating resource management functions from the programing model.
More precisely, Yarn replaces jobtracker & tasktracker which were used in Hadoop 1.0, with new components, namely, Resource Manager, Application Master, Node Manager.
RM: it runs as a daemon machine, serves as a central authority arbitrating resources among various applications.
AM: it manages each job. It monitors all lifecycle including resources consumption, flow execution etc.
NM: they are responsible for monitor resource availability on each node.
With this new architecture, it decentralizes the workload on JobTracker (Resource Manager in Yarn) in original Hadoop. More precisely, the job of task monitoring is assigned to AM instead of RM. Further, AM can be defined by users.
Container is also another novel framework that perform well for resource isolation in Yarn.
Another advantage of Yarn over Hadoop is that, Yarn represent resource with memory, which is more reasonable compared with Hadoop's number of map/reduce slots.
3) Why is solution different from previous work?
YARN mainly have 10 unique features to make it different from previous works.
1. YARN extends Hadoop's scalability.
2. YARN meets the requirement of Multi-tenancy needs.
3. YARN has the ability of decoupling the upgrade dependencies (which may be one of Mesos's job).
4. YARN can achieve locality awareness.
5. YARN can perform high cluster utilization
6. YARN needs to enable fault tolerance among multiple tenants Hadoop cluster.
7. YARN maintains secure and auditable operations.
8. YARN must support for programming model diversity.
9. YARN has a flexible resource model.
10. Since YARN is second version of Hadoop, it must achieve backward compatibility.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
This two layer scheduling is a better way than centralized scheduling scheme. However, in the two lay scheduling architecture, each AM do not have a global view of the cluster resources, thus each AM could not achieve the best computational resources utilization.
5) Do you think the paper will be influential in 10 years? Why or why not?
Yes, since it is the second generation of Hadoop and has many novel attributes mentioned above, it definitely will be influential in 10 years.
Wednesday, September 30, 2015
Tuesday, September 29, 2015
Reviews for Mesos (NSDI'11)
1) Is the problem real?
The problem is that currently no single framework (e.g. Hadoop, Dryad ) can achieve decent performance for any applications. Once the problem is solved, the big data systems can have the potential of achieving optimal performance.
2) What is the solution’s main idea (nugget)?
1) resource offer: that is to delegate control over scheduling to the frameworks themselves.
2) fine-grained resource sharing model: consider about fairness, data locality, to achieve task-level resource sharing.
3) Why is solution different from previous work?
Previous works like HPC schedulers (e.g. Torque, LSF, Sun Grid Engine), virtual machine clouds, they achieve coarse-grained sharing for inelastic jobs. On the other hand, Mesos achieves fine-grained task-level resource sharing.
Condor cannot enable some cloud policy such as delay scheduling, whereas Mesos can achieve.
Next generation Hadoop uses a centralized scheduling based on locality reference, whereas Mesos is a decentralized resource sharing model.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
One of the key component of Mesos is its resource offer. The basic idea of resource offer is to offer available resources and let the frameworks decide which resources to use and which tasks to launch.
It keeps Mesos simple and can be used for future frameworks. However, this decentralized decisions may not be optimal.
5) Do you think the paper will be influential in 10 years? Why or why not?
Yes I think Mesos will be influential in 10 years. Since it can support future frameworks to be integrated into current data processing systems.
The problem is that currently no single framework (e.g. Hadoop, Dryad ) can achieve decent performance for any applications. Once the problem is solved, the big data systems can have the potential of achieving optimal performance.
2) What is the solution’s main idea (nugget)?
1) resource offer: that is to delegate control over scheduling to the frameworks themselves.
2) fine-grained resource sharing model: consider about fairness, data locality, to achieve task-level resource sharing.
3) Why is solution different from previous work?
Previous works like HPC schedulers (e.g. Torque, LSF, Sun Grid Engine), virtual machine clouds, they achieve coarse-grained sharing for inelastic jobs. On the other hand, Mesos achieves fine-grained task-level resource sharing.
Condor cannot enable some cloud policy such as delay scheduling, whereas Mesos can achieve.
Next generation Hadoop uses a centralized scheduling based on locality reference, whereas Mesos is a decentralized resource sharing model.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
One of the key component of Mesos is its resource offer. The basic idea of resource offer is to offer available resources and let the frameworks decide which resources to use and which tasks to launch.
It keeps Mesos simple and can be used for future frameworks. However, this decentralized decisions may not be optimal.
5) Do you think the paper will be influential in 10 years? Why or why not?
Yes I think Mesos will be influential in 10 years. Since it can support future frameworks to be integrated into current data processing systems.
Tuesday, September 22, 2015
Review for RAMCloud (SIGOPS Review'09)
1) Is the problem real?
The scalability of disk-based storage system cannot meet the needs of large-scale web services (e.g. throughput, latency, etc).
The problem is real and important.
2) What is the solution’s main idea (nugget)?
The key idea is to keep all the data in DRAM and construct the large-scale system by aggregating the main memory of thousands of servers.
3) Why is solution different from previous work?
Two main differences:
1) All information is maintained in DRAM all the time.
2) scale automatically to support thousands of servers.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
With all-in memory data storage and processing, RAMCloud achieves high throughput and low latency. However, the cost and energy consumption is high for in RAMCloud.
5) Do you think the paper will be influential in 10 years? Why or why not?
Yes, nowadays memory becomes cheaper and cheaper, it is becoming a trend that in-memory computing is more and more popular.
The scalability of disk-based storage system cannot meet the needs of large-scale web services (e.g. throughput, latency, etc).
The problem is real and important.
2) What is the solution’s main idea (nugget)?
The key idea is to keep all the data in DRAM and construct the large-scale system by aggregating the main memory of thousands of servers.
3) Why is solution different from previous work?
Two main differences:
1) All information is maintained in DRAM all the time.
2) scale automatically to support thousands of servers.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
With all-in memory data storage and processing, RAMCloud achieves high throughput and low latency. However, the cost and energy consumption is high for in RAMCloud.
5) Do you think the paper will be influential in 10 years? Why or why not?
Yes, nowadays memory becomes cheaper and cheaper, it is becoming a trend that in-memory computing is more and more popular.
Reviews for FaRM (NSDI'14)
1) Is the problem real?
Since DRAM is becoming cheaper and larger, now we can load small data set directly into Memory in order to reduce the overhead of disk/flash IO. However, by doing so, the network is still a bottleneck. The problem is real.
2) What is the solution’s main idea (nugget)?
The authors try to modify and use RDMA to improve the performance (e.g. latency, throughput) of memory systems that using TCP/IP.
Two key mechanisms to improve performance: lock-free read over RDMA, locality optimizations that enable single machine transactions
3) Why is solution different from previous work?
Previous work that also leveraging RDMA, they do not support one-sided read or efficient lock-free RDMA read, whereas FaRM can support that.
In addition, FaRM’s technique to detect inconsistent reads is more general. It provides serializability with respect to general transactions.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
While FaRM provides performance benefits of user-level networking to parallel applications, it is very hard to apply the model to a broader class of client-server applications.
In addition, RDMA is point-to-point. Each participant receives an authenticator providing it permission to remotely read/write a particular region of memory. Since clients in client-server computing are not mutually trusted, the hardware would need to keep a separate region of memory for each active connection.
5) Do you think the paper will be influential in 10 years? Why or why not?
I do not think so. It is because FaRM is just to incorporate RDMA into memory system. Even though there are some modification and refinement over RDMA, I think the whole paper's novelty and contribution is not that significant.
Since DRAM is becoming cheaper and larger, now we can load small data set directly into Memory in order to reduce the overhead of disk/flash IO. However, by doing so, the network is still a bottleneck. The problem is real.
2) What is the solution’s main idea (nugget)?
The authors try to modify and use RDMA to improve the performance (e.g. latency, throughput) of memory systems that using TCP/IP.
Two key mechanisms to improve performance: lock-free read over RDMA, locality optimizations that enable single machine transactions
3) Why is solution different from previous work?
Previous work that also leveraging RDMA, they do not support one-sided read or efficient lock-free RDMA read, whereas FaRM can support that.
In addition, FaRM’s technique to detect inconsistent reads is more general. It provides serializability with respect to general transactions.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
While FaRM provides performance benefits of user-level networking to parallel applications, it is very hard to apply the model to a broader class of client-server applications.
In addition, RDMA is point-to-point. Each participant receives an authenticator providing it permission to remotely read/write a particular region of memory. Since clients in client-server computing are not mutually trusted, the hardware would need to keep a separate region of memory for each active connection.
5) Do you think the paper will be influential in 10 years? Why or why not?
I do not think so. It is because FaRM is just to incorporate RDMA into memory system. Even though there are some modification and refinement over RDMA, I think the whole paper's novelty and contribution is not that significant.
Monday, September 21, 2015
Review on Flat Datacenter Storage (OSDI'12)
This paper tries to break the data's locality dependency during processing, which introduce high networking & I/O overhead. The problem is real and hard to be solved.
2) What is the solution’s main idea (nugget)?
They build up a shared and centralized storage system by multiplexing application's large-scale I/O across available throughput and latency budget of every disk in cluster. More precisely, they spread data over disks uniformly at a relatively fine grain.
System main components:
The system stores data in blobs and read/write to blob using tracts.
Every disk is managed by a process called tract server.
And the FDS also have a metadata server which maintains track locator table.
3) Why is solution different from previous work?
Previous work also proposes several "flat" storage models, like amazon S3, it has a large overhead from datacenter networks. FDS makes every job using cluster's I/O bandwidth instead of each node's local network bandwidth.
Different from previous research on solving specific problems brought by need for locality, FDS move datacenter back to a flat storage model so that all the "need for locality" issue are gone away.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
FDS spreads data over disks uniformly at fine grain. It makes the task/job to use all the CPU and cluster resources. However, the task/job failure becomes more frequently, since each task's data is on all the nodes, one fails, all fails. Even though the data recovery speed is fast, it still will have much overhead of job failure recovery.
5) Do you think the paper will be influential in 10 years? Why or why not?
I think it will have impacts in 10 years. I believe simple is best. To storage system, flat means simple and easy to control.
2) What is the solution’s main idea (nugget)?
They build up a shared and centralized storage system by multiplexing application's large-scale I/O across available throughput and latency budget of every disk in cluster. More precisely, they spread data over disks uniformly at a relatively fine grain.
System main components:
The system stores data in blobs and read/write to blob using tracts.
Every disk is managed by a process called tract server.
And the FDS also have a metadata server which maintains track locator table.
3) Why is solution different from previous work?
Previous work also proposes several "flat" storage models, like amazon S3, it has a large overhead from datacenter networks. FDS makes every job using cluster's I/O bandwidth instead of each node's local network bandwidth.
Different from previous research on solving specific problems brought by need for locality, FDS move datacenter back to a flat storage model so that all the "need for locality" issue are gone away.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
FDS spreads data over disks uniformly at fine grain. It makes the task/job to use all the CPU and cluster resources. However, the task/job failure becomes more frequently, since each task's data is on all the nodes, one fails, all fails. Even though the data recovery speed is fast, it still will have much overhead of job failure recovery.
I think it will have impacts in 10 years. I believe simple is best. To storage system, flat means simple and easy to control.
Review of IOFlow (SOSP'13)
1) Is the problem real?
This paper tries to deal with the complexity and overhead of I/O path to storage. The problem is critical and needed to be solved.
2) What is the solution’s main idea (nugget)?
IOFlow uses a four-tuple identifier to achieve a centralized control plane which enable high-level flow control. The key idea of IOFlow is to decouple the control of IO flows from the data plane and introduce programmable data plane queues that allow for flexible service and routing properties.
The system mainly contains 3 parts.
1. a centralized controller. It maintains data plane stages and data center topology.
2. data plane queues. It allows differentiated treatment of IO request.
3. a interface between controller and application.
3) Why is solution different from previous work?
Previously works lack a control plain which enable simple flow of I/O Stake.
IOFlow borrow some control algorithm from SDN control plain. In addition, SEDA and Click are control systems used for thread/event scheduling or router configuration. IOFlow has different focus point which is enable control for IO stack.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
Although the IOFlow can achieve useful end to end IO control policy, it introduce overhead on both data plane and control plane.
5) Do you think the paper will be influential in 10 years? Why or why not?
I think it will be useful, since I/O control is always a big problem during the system processing.
This paper tries to deal with the complexity and overhead of I/O path to storage. The problem is critical and needed to be solved.
2) What is the solution’s main idea (nugget)?
IOFlow uses a four-tuple identifier to achieve a centralized control plane which enable high-level flow control. The key idea of IOFlow is to decouple the control of IO flows from the data plane and introduce programmable data plane queues that allow for flexible service and routing properties.
The system mainly contains 3 parts.
1. a centralized controller. It maintains data plane stages and data center topology.
2. data plane queues. It allows differentiated treatment of IO request.
3. a interface between controller and application.
3) Why is solution different from previous work?
Previously works lack a control plain which enable simple flow of I/O Stake.
IOFlow borrow some control algorithm from SDN control plain. In addition, SEDA and Click are control systems used for thread/event scheduling or router configuration. IOFlow has different focus point which is enable control for IO stack.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
Although the IOFlow can achieve useful end to end IO control policy, it introduce overhead on both data plane and control plane.
I think it will be useful, since I/O control is always a big problem during the system processing.
Friday, September 18, 2015
Review for the google file system (SOSP'03)
1) Is the problem real?
The reason of designing GFS is due to the fact that nowadays data storage have some new features.
1. Component failure are normal.
2. The data files are huge.
3. Most files are used for appending more data rather than rewrite existed data.
4. Concurrently write the same file.
The four main changes are significant and need to be solved.
2) What is the solution’s main idea (nugget)?
It contains mainly 3 roles.
1. The GFS Master mainly stores all file system metadata (single).
2. The GFS Chunkserver stores the chunks(Multiple)
3. The GFS client is used as agent for requesting data on the Server.
3) Why is solution different from previous work?
The fils system has been a very old problem.
The workload is different from previous system. The main workload difference are as follows: more component failures, frequently read & append huge files, etc. These workload characteristics lead to the GFS assumptions to be different from other systems.
Based on the different workload. GFS mainly differs from previous works in following parts. These workload characteristics lead to the GFS assumptions to be different from other systems.
1. GFS do not have to cache below the file system interface.
2. GFS still keeps centralized control pattern rather than some distributed file system.
3. GFS focus on Fault tolerance rather than POSIX compliant system.
4. GFS chunk servers use lazily allocated fixed-size chunks rather than variable-length objects (e.g. NASD).
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
In order to keep the system's robust to component failures, every chunk of data has replicas (in total 3). The replicas increases the system overhead on data consistency. In addition, I think it is not efficient, since every piece of data should be write three times and take 3 times of its data size on storage.
5) Do you think the paper will be influential in 10 years? Why or why not?
Definitely. Hadoop is using HDFS which is based on GFS system design. And Hadoop is widely-deploied in real-world big data analysis systems.
The reason of designing GFS is due to the fact that nowadays data storage have some new features.
1. Component failure are normal.
2. The data files are huge.
3. Most files are used for appending more data rather than rewrite existed data.
4. Concurrently write the same file.
The four main changes are significant and need to be solved.
2) What is the solution’s main idea (nugget)?
It contains mainly 3 roles.
1. The GFS Master mainly stores all file system metadata (single).
2. The GFS Chunkserver stores the chunks(Multiple)
3. The GFS client is used as agent for requesting data on the Server.
3) Why is solution different from previous work?
The fils system has been a very old problem.
The workload is different from previous system. The main workload difference are as follows: more component failures, frequently read & append huge files, etc. These workload characteristics lead to the GFS assumptions to be different from other systems.
Based on the different workload. GFS mainly differs from previous works in following parts. These workload characteristics lead to the GFS assumptions to be different from other systems.
1. GFS do not have to cache below the file system interface.
2. GFS still keeps centralized control pattern rather than some distributed file system.
3. GFS focus on Fault tolerance rather than POSIX compliant system.
4. GFS chunk servers use lazily allocated fixed-size chunks rather than variable-length objects (e.g. NASD).
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
In order to keep the system's robust to component failures, every chunk of data has replicas (in total 3). The replicas increases the system overhead on data consistency. In addition, I think it is not efficient, since every piece of data should be write three times and take 3 times of its data size on storage.
Definitely. Hadoop is using HDFS which is based on GFS system design. And Hadoop is widely-deploied in real-world big data analysis systems.
Wednesday, September 16, 2015
Review for DataFlow on VLDB 2015
1) Is the problem real?
The problem indeed is real. Many proposed schemes, even though they have some good properties for data processing, all of them may lack of some crucial properties like exactly-once semantics, fault tolerance, etc. This DataFlow try to design a system that can balance correctness, latency, and cost in massive, unbounded, out of order data processing.
2) What is the solution’s main idea (nugget)?
Their window-based architecture is the nugget. It has two core functions ParDo and GroupbyKey.
In addition, they propose trigger & incremental processing to figure out window completeness.
3) Why is solution different from previous work?
For previous work on batch or stream processing, they either lack of fault tolerance, or lack of other important properties like exactly-once semantics, model for calculating event-time.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
While even the DataFlow can be fitted for processing all Batch, micro-batch, streaming workload. The processing efficiency is lower than other more specified schemes (e.g. spark for batch, etc).
5) Do you think the paper will be influential in 10 years? Why or why not?
Yeah, I think it will have impact. All previously systems have shortcomings. They are specifically designed for working with particular workload. On the other hand, DataFlow can be general enough to subsume the standard batch, micro-batch, and streaming model.
The problem indeed is real. Many proposed schemes, even though they have some good properties for data processing, all of them may lack of some crucial properties like exactly-once semantics, fault tolerance, etc. This DataFlow try to design a system that can balance correctness, latency, and cost in massive, unbounded, out of order data processing.
2) What is the solution’s main idea (nugget)?
Their window-based architecture is the nugget. It has two core functions ParDo and GroupbyKey.
In addition, they propose trigger & incremental processing to figure out window completeness.
3) Why is solution different from previous work?
For previous work on batch or stream processing, they either lack of fault tolerance, or lack of other important properties like exactly-once semantics, model for calculating event-time.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
While even the DataFlow can be fitted for processing all Batch, micro-batch, streaming workload. The processing efficiency is lower than other more specified schemes (e.g. spark for batch, etc).
5) Do you think the paper will be influential in 10 years? Why or why not?
Yeah, I think it will have impact. All previously systems have shortcomings. They are specifically designed for working with particular workload. On the other hand, DataFlow can be general enough to subsume the standard batch, micro-batch, and streaming model.
Tuesday, September 15, 2015
Review for Apache Flink
1) Is the problem real?
Fault tolerant is a crucial issue in stream processing. We cannot rollback and rerun the failed jobs since there is no begin/end in the failed part of stream. In addition, we need to handle state other than output.
2) What is the solution’s main idea (nugget)?
It draws snapshot of a running system topology periodically. And the checkpoint snapshot work in the background without stopping the steam process.
3) Why is solution different from previous work?
The most related work will be Apache Storm, it cannot guarantee the state consistency, whereas Flink can achieve that.
Another trend is to use micro-batching system, like spark streaming, Storm trident. It is indeed still batch-based system. This kind of system lost the good properties of continuous operator. For example, batch-based system cannot support window data, and have higher latency.
Goole Cloud Dataflow remains the good properties on stream operator, but do not fit well in batch jobs.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
The snapshot scheme needs I/O overhead. Thus for large state, the system need to make a trade-off between throughput and recovery time.
5) Do you think the paper will be influential in 10 years? Why or why not?
I do not think it will be influential in 10 years. First, the whole system is based on a model proposed in 1985. This mitigate the paper's novelty. Second, I think there is no significant advantage of Flink over Goole Cloud Dataflow. And Google Cloud Dataflow have much more users.
Fault tolerant is a crucial issue in stream processing. We cannot rollback and rerun the failed jobs since there is no begin/end in the failed part of stream. In addition, we need to handle state other than output.
2) What is the solution’s main idea (nugget)?
It draws snapshot of a running system topology periodically. And the checkpoint snapshot work in the background without stopping the steam process.
3) Why is solution different from previous work?
The most related work will be Apache Storm, it cannot guarantee the state consistency, whereas Flink can achieve that.
Another trend is to use micro-batching system, like spark streaming, Storm trident. It is indeed still batch-based system. This kind of system lost the good properties of continuous operator. For example, batch-based system cannot support window data, and have higher latency.
Goole Cloud Dataflow remains the good properties on stream operator, but do not fit well in batch jobs.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
The snapshot scheme needs I/O overhead. Thus for large state, the system need to make a trade-off between throughput and recovery time.
I do not think it will be influential in 10 years. First, the whole system is based on a model proposed in 1985. This mitigate the paper's novelty. Second, I think there is no significant advantage of Flink over Goole Cloud Dataflow. And Google Cloud Dataflow have much more users.
Monday, September 14, 2015
Paper review for D-Stream (SOSP'13)
1) Is the problem real?
This paper tries to tickle the steaming problem in big data analysis. The problem indeed happens frequently in scenarios like social network etc. Thus the problem is real and important. In addition, current record-at-a-time model cannot work well on streaming. Thus it is urgent to propose a better solution.
2) What is the solution’s main idea (nugget)?
The key idea is still using batch-based system. They run each streaming computation as a series of deterministic batch computations on small time intervals
3) Why is solution different from previous work?
This problem is not new, but previous record-at-a-time model does not work well. In other words, record-at-a-time model can only support high-cost fault tolerant and cannot tickle with stragglers. Further, this model is hard to remain global consistency.
For batch-based system, none of the existing batch systems can achieve sub-second latencies.
On the other hand, by incorporating RDD, D-stream can achieve sub-second latencies, and also support for fault tolerant, dealing with stragglers.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
The fundamental tradeoff is using Batch-based system to provide fault tolerant & straggler problem. However, using batch-based system introduces high latency, even with RDD.
In addition, with batch-based model, it lost many other properties of continuous operator model. For example, D-stream may suffer from back-pressure effect. More precisely, if the micro-batch takes longer in downstream processing than in batch operator, the micro-batch will take longer than configured. Thus it leads to batches queuing up or growing the batch size.
5) Do you think the paper will be influential in 10 years? Why or why not?
I think it will not be influential in 10 years. Indeed, D-stream is still batch-based system. Thus the latency issues is inevitable. I think we need to design system or model, which is specifically used for streaming data processing. I think system like record-at-a-time model will still be the mainstream of streaming data processing system. Or we may develop new technology to minimize latency while providing fault tolerant.
This paper tries to tickle the steaming problem in big data analysis. The problem indeed happens frequently in scenarios like social network etc. Thus the problem is real and important. In addition, current record-at-a-time model cannot work well on streaming. Thus it is urgent to propose a better solution.
2) What is the solution’s main idea (nugget)?
The key idea is still using batch-based system. They run each streaming computation as a series of deterministic batch computations on small time intervals
3) Why is solution different from previous work?
This problem is not new, but previous record-at-a-time model does not work well. In other words, record-at-a-time model can only support high-cost fault tolerant and cannot tickle with stragglers. Further, this model is hard to remain global consistency.
For batch-based system, none of the existing batch systems can achieve sub-second latencies.
On the other hand, by incorporating RDD, D-stream can achieve sub-second latencies, and also support for fault tolerant, dealing with stragglers.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
The fundamental tradeoff is using Batch-based system to provide fault tolerant & straggler problem. However, using batch-based system introduces high latency, even with RDD.
In addition, with batch-based model, it lost many other properties of continuous operator model. For example, D-stream may suffer from back-pressure effect. More precisely, if the micro-batch takes longer in downstream processing than in batch operator, the micro-batch will take longer than configured. Thus it leads to batches queuing up or growing the batch size.
5) Do you think the paper will be influential in 10 years? Why or why not?
I think it will not be influential in 10 years. Indeed, D-stream is still batch-based system. Thus the latency issues is inevitable. I think we need to design system or model, which is specifically used for streaming data processing. I think system like record-at-a-time model will still be the mainstream of streaming data processing system. Or we may develop new technology to minimize latency while providing fault tolerant.
Wednesday, September 9, 2015
Review for Naiad (SOSP'13)
The problem this paper tries to tackle is triple-fold: application performs iterative processing on real-time data stream, and supports interactive queries on a fresh consistent view of results. And the authors say that no system can achieve all these requirements. The problem itself is real, and more-specified.
The main idea of this paper is timely dataflow. Timely dataflow is a computational model based on directed graph where vertices send/receive timestamped messages along directed edges. It can have cycles.
The unique character of Naiad is that, it can fulfill the triple-fold requirement in one system. In addition, Naiad introduce less overhead than Spark, etc. Since Spark and other systems requires centralized modification to dataflow graph. Compared with previous asynchronous systems, Naiad provides completeness notification in a global synchronization, whereas the previous asynchronous systems are lack of.
For the trade-off, I think without inheriting batch-computationa model, Naiad is not as robust as Spark on fault-tolerance. In addition, Naiad has a lot of checkpoints. These periodically checkpoints needs worker to pause and deliver message, which may slow down the performance. Thus the user needs to balance the checkpoints overhead and the system correctness.
I do think Naiad gives more freedom for the user to balance processing speed and system correctness. Thus Naiad can be adaptive in both streaming and batch processing. However, the Naiad system do not provide good fault tolerance. Therefore, I think this system is not influential in 10 years. It is because fault tolerance is a key issue in data processing.
The main idea of this paper is timely dataflow. Timely dataflow is a computational model based on directed graph where vertices send/receive timestamped messages along directed edges. It can have cycles.
The unique character of Naiad is that, it can fulfill the triple-fold requirement in one system. In addition, Naiad introduce less overhead than Spark, etc. Since Spark and other systems requires centralized modification to dataflow graph. Compared with previous asynchronous systems, Naiad provides completeness notification in a global synchronization, whereas the previous asynchronous systems are lack of.
For the trade-off, I think without inheriting batch-computationa model, Naiad is not as robust as Spark on fault-tolerance. In addition, Naiad has a lot of checkpoints. These periodically checkpoints needs worker to pause and deliver message, which may slow down the performance. Thus the user needs to balance the checkpoints overhead and the system correctness.
I do think Naiad gives more freedom for the user to balance processing speed and system correctness. Thus Naiad can be adaptive in both streaming and batch processing. However, the Naiad system do not provide good fault tolerance. Therefore, I think this system is not influential in 10 years. It is because fault tolerance is a key issue in data processing.
Review on Spark (hotcloud'10)
This paper point out the fact that MapReduce is not good at conducting iterative jobs and interactive analysis. The system Spark (aka, the implementation of RDD) try to achieve more efficiency in these two scenarios (e.g. iterative jobs, interactive analysis). The problem is real and urgent to be solved.
The nugget of this paper is Resilient Distributed Dataset. RDD enable user to cache RDD in memory and reuse it in multiple MapReduce rounds. And it can be fault tolerant.
RDD is related to DSM (Distributed Shared Memory). The difference is that RDD provides more restricted programming model and better fault tolerance. RDD achieves in memory MapReduce, rather than letting nodes access a global address space.
Compared with MapReduce, RDD can persist across operations. Different from Twister, RDD enable fault tolerance and more general.
For the tradeoff, even though RDD is more suitable for iterative jobs and interactive analysis, MapReduce performs better with common transaction workloads.
Another tradeoff is, RDD enable fault tolerance with parallel recovery, in exchange, RDD introduce overhead for centralized modifications to dataflow.
I think Spark will be influential in next 10 years. even though RDD is based on MapReduce, they developed in different ways. For RDD, it mainly focus on iterative jobs and interactive analysis. For MapReduce, it performs better in common transaction workloads.
The nugget of this paper is Resilient Distributed Dataset. RDD enable user to cache RDD in memory and reuse it in multiple MapReduce rounds. And it can be fault tolerant.
RDD is related to DSM (Distributed Shared Memory). The difference is that RDD provides more restricted programming model and better fault tolerance. RDD achieves in memory MapReduce, rather than letting nodes access a global address space.
Compared with MapReduce, RDD can persist across operations. Different from Twister, RDD enable fault tolerance and more general.
For the tradeoff, even though RDD is more suitable for iterative jobs and interactive analysis, MapReduce performs better with common transaction workloads.
Another tradeoff is, RDD enable fault tolerance with parallel recovery, in exchange, RDD introduce overhead for centralized modifications to dataflow.
I think Spark will be influential in next 10 years. even though RDD is based on MapReduce, they developed in different ways. For RDD, it mainly focus on iterative jobs and interactive analysis. For MapReduce, it performs better in common transaction workloads.
Review for Dryad (EuroSys'07)
The authors of this paper try to design efficient scheme that can make developer to write distributed and parallel applications. At first sight, the problem seems too big to be real. After viewing the whole Dryad system, it indeed provide a more efficient way for developer to process big data.
2) What is the solution’s main idea (nugget)?
Dryad represent the computation workflow as a directed acyclic graph. Each vertex is a program whereas each edge represents data channel.
3) Why is solution different from previous work?
First, the problem itself is not new. However, the method is novel. Previous works are more restricted to the workflow, which gives developer less space to personalize the system. Dryad enable the developer to have fine-grained control over the whole communication graph including subroutines.
Second, Dryad can use arbitrary number of inputs and outputs. Other systems like MapReduce can only enable one input one output, whereas SQL and shader achieve multiple input but only single output.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
Even though Dryad proved higher-level programming model, it is indeed more complicated than other competitive scheme, such as MapReduce. The trade off here is, the developer has more freedom in using Dryad, but need to learn more about how to use it.
I do not think this paper still has impact in 10 years. Even Dryad provide higher-level programming model, it is still not as simple as MapReduce. In my perspective, simple is the key issue in system design. And that is the reason why MapReduce has 10 times more citation than Dryad.
Tuesday, September 8, 2015
review for MapReduce (osdi'04) paper
1) Is the problem real?
Based on the authors' experience on processing data at Google, they found out an interesting phenomenon that is twofold:
1) Nowadays the computation are quite straightforward.
2) However, the quantity of data is huge.
Therefore, how to process huge amount of data (aka, "big data") with simple computation is the key issue. More precisely, how to achieve parallel processing "big data" on distributed system, and also keep resistance to failure is the key challenge.
From my perspective, it is a fundamental issue needed to be solved in "big data" processing.
First, currently the only efficient way we can process "big data" is to use distributed system and process the data in parallel. This paper is proposing an abstraction for efficient "big data" processing on distributed system (including data distribution, load balancing, etc.).
Second, this paper also tries to tickle a key issue in running distributed system, that is the node failures.
2) What is the solution’s main idea (nugget)?
Two steps: Map & Reduce.
Map: shuffle and distribute data into parallel processing.
Reduce: merge data with specified characteristic.
Another key component: Intermediate Key--link between Map & Reduce.
3) Why is solution different from previous work?
MapReduce is simpler and easier than many other restricted parallel programming models. In addition, MapReduce provide fault-tolerant on larger scale to thousands of processors.
4) Does the paper (or do you) identify any fundamental/hard trade-offs?
1. Since MapReduce rely on atomic commits of map and reduce tasks, it can provide non-faulting execution when Map/Reduce operators are deterministic. However, MapReduce provides weak semantics when the Map/Reduce operators are non-deterministic.
2. By introducing Combiner function, it can mitigate the non-uniformly distributed workload on each reduce function. Thus, there are some nodes need to do both map and reduce functions. This one node play two role thing is not good for pipelining the whole process.
3. Since MapReduce need to replicate data during processing, the whole replication process is limited by the network bandwidth.
5) Do you think the paper will be influential in 10 years? Why or why not?
I think it will still have impacts in next 5-10 years. Even though Spark project works better in some specific scenarios (e.g. iterative algorithm, interactive data mining tools, etc.), MapReduce works well in common transaction workloads.
Subscribe to:
Posts (Atom)