Information Systems Group - Prof. Jens Dittrich

Hadoop++

Hadoop++: Nowadays, working over very large data sets (Petabytes of information) is a common reality for several enterprises. In this context, query processing is a big challenge and becomes crucial. The Apache Hadoop project has been adopted by many famous companies to query their Petabytes of information. Some examples of such enterprises are Yahoo! and Facebook.

Recently, some researchers from the database community indicated that Hadoop may suffer from performance issues when running analytical queries. We believe this is not an inherent problem of the MapReduce paradigm but rather some implementation choices done in Hadoop. Therefore, the overall goal of Hadoop++ project is to improve Hadoop's performance for analytical queries. Already, our preliminary results show an improvement of Hadoop++ over Hadoop by up to a factor 20. In addition, we are currently investigating the impact of a number of other optimizations techniques. paper

HAIL

HAIL (Hadoop Aggressive Indexing Library) is an enhancement of HDFS and Hadoop MapReduce that dramatically improves runtimes of several classes of MapReduce jobs. HAIL changes the upload pipeline of HDFS in order to create different clustered indexes on each data block replica. An interesting feature of HAIL is that we typically create a win-win situation: we improve both data upload to HDFS and the runtime of the actual Hadoop MapReduce job. In terms of data upload, HAIL improves over HDFS by up to 60% with the default replication factor of three. In terms of query execution, we demonstrate that HAIL runs up to 68x faster than Hadoop and even outperforms Hadoop++. initial paper follow-up paper

Publications

Stefan Richter, Jorge-Arnulfo Quiané-Ruiz, Stefan Schuh, Jens Dittrich
Towards Zero-Overhead Static and Adaptive Indexing in Hadoop
The VLDB Journal. 2013. Abstract / [bib]
Towards Zero-Overhead Static and Adaptive Indexing in Hadoop
Hadoop MapReduce has evolved to an important industry standard for massive parallel data processing and has become widely adopted for a variety of use cases. Recent works have shown that indexes can improve the performance of selective MapReduce jobs dramatically. However, one major weakness of existing approaches are high index creation costs. We present HAIL (Hadoop Aggressive Indexing Library), a novel indexing approach for HDFS and Hadoop MapReduce. HAIL creates different clustered indexes over terabytes of data with minimal, often invisible costs and it dramatically improves runtimes of several classes of MapReduce jobs. HAIL features two different indexing pipelines, static indexing and adaptive indexing. HAIL static indexing efficiently indexes datasets while uploading them to HDFS. Thereby, HAIL leverages the default replication of Hadoop and enhances it with logical replication. This allows HAIL to create multiple clustered indexes for a dataset, e.g. one for each physical replica. Still, in terms of upload time, HAIL matches or even improves over the performance of standard HDFS. Additionally, HAIL adaptive indexing allows for automatic, incremental indexing at job runtime with minimal runtime overhead. For example, HAIL adaptive indexing can completely index a dataset as byproduct of only four MapReduce jobs while incurring an overhead as low as 11% for the very first of those job only. In our experiments, we show that HAIL improves job runtimes by up to 68x over Hadoop. This article is an extended version of the VLDB 2012 paper “Only Aggressive Elephants are Fast Elephants” (PVLDB, 5(11):1591-1602, 2012).
```
@article{RQS+13,
			   author    = {Stefan Richter and Jorge-Arnulfo Quian{\'e}-Ruiz  and Stefan Schuh and Jens Dittrich},
			   title     = {{Towards Zero-Overhead Static and Adaptive Indexing in Hadoop}},
			   journal   = {VLDB Journal},
			   year      = {2013},
			   }
```
Stefan Richter, Jens Dittrich, Stefan Schuh, Tobias Frey
Mosquito: Another One Bites the Data Upload STream
VLDB 2013, Riva, Italy. (Demo paper) Abstract /[bib]
Mosquito: Another One Bites the Data Upload STream
Mosquito is a lightweight and adaptive physical design framework for Hadoop. Mosquito connects to existing data pipelines in Hadoop MapReduce and/or HDFS, observes the data, and creates better physical designs, i.e. indexes, as a byproduct. Our approach is min- imally invasive, yet it allows users and developers to easily improve the runtime of Hadoop. We present three important use cases: first, how to create indexes as a byproduct of data uploads into HDFS; second, how to create indexes as a byproduct of map tasks; and third, how to execute map tasks as a byproduct of HDFS data up- loads. These use cases may even be combined.
```
@article{DRS+13,
   author    = {Stefan Richter and Jens Dittrich and Stefan Schuh and Tobias Frey},
   title     = {{Mosquito: Another One Bites the Data Upload STream}},
   journal   = {PVLDB},
   volume    = {6},
   number    = {12},
   year      = {2013},
   pages     = {unknown},
   }
```
Jens Dittrich, Stefan Richter, Stefan Schuh
Efficient OR Hadoop: Why Not Both?
Datenbank Spektrum, January 2013 Abstract /[bib]
Efficient OR Hadoop: Why Not Both?
In this article, we give an overview of research related to Big Data processing in Hadoop going on at the Information Systems Group at Saarland University. We discuss how to make Hadoop efficient. We briefly survey four of our projects in this context: Hadoop++, Trojan Layouts, HAIL, and LIAH. All projects aim to provide efficient physical layouts in Hadoop including vertically partitioned data layouts, clustered indexes, and adaptively created clustered indexes. Most of our techniques come (almost) for free: they create little to no overhead in comparison to standard Hadoop.
```
@article{DRS13,
   author    = {Jens Dittrich and Stefan Richter and Stefan Schuh},
   title     = {{Efficient OR Hadoop: Why Not Both?}},
   journal   = {Datenbank-Spektrum},
   volume    = {13},
   number    = {1},
   year      = {2013},
   pages     = {17-22},
   }
```
Stefan Richter, Jorge-Arnulfo Quiane-Ruiz, Stefan Schuh, Jens Dittrich
Towards Zero-Overhead Adaptive Indexing in Hadoop
TR, arXiv:1212.3480 [cs.DB], 2012 Abstract / [bib]
Towards Zero-Overhead Adaptive Indexing in Hadoop
Several research works have focused on supporting index access in MapReduce systems. These works have allowed users to significantly speed up selective MapReduce jobs by orders of magnitude. However, all these proposals require users to create indexes upfront, which might be a difficult task in certain applications (such as in scientific and social applications) where workloads are evolving or hard to predict. To overcome this problem, we propose LIAH (Lazy Indexing and Adaptivity in Hadoop), a parallel, adaptive approach for indexing at minimal costs for MapReduce systems. The main idea of LIAH is to automatically and incrementally adapt to users' workloads by creating clustered indexes on HDFS data blocks as a byproduct of executing MapReduce jobs. Besides distributing indexing efforts over multiple computing nodes, LIAH also parallelises indexing with both map tasks computation and disk I/O. All this without any additional data copy in main memory and with minimal synchronisation. The beauty of LIAH is that it piggybacks index creation on map tasks, which read relevant data from disk to main memory anyways. Hence, LIAH does not introduce any additional read I/O-costs and exploit free CPU cycles. As a result and in contrast to existing adaptive indexing works, LIAH has a very low (or invisible) indexing overhead, usually for the very first job. Still, LIAH can quickly converge to a complete index, i.e. all HDFS data blocks are indexed. Especially, LIAH can trade early job runtime improvements with fast complete index convergence. We compare LIAH with HAIL, a state-of-the-art indexing technique, as well as with standard Hadoop with respect to indexing overhead and workload performance.
```
@article{RQS+12,
   author    = {Stefan Richter and Jorge-Arnulfo Quian{\'e}-Ruiz and Stefan Schuh and Jens Dittrich},
   title     = {{Towards Zero-Overhead Adaptive Indexing in Hadoop}},
   journal   = {CoRR},
   volume    = {abs/1212.3480},
   year      = {2012},
   }
```
Alekh Jindal, Jorge-Arnulfo Quiane-Ruiz, Jens Dittrich
WWHow! Freeing Data Storage from Cages
CIDR 2013, Outrageous Ideas and Vision Track, Asilomar, USA. Abstract / [bib]
WWHow! Freeing Data Storage from Cages
Efficient data storage is a key component of data managing systems to achieve good performance. However, currently data storage is either heavily constrained by static decisions (e.g. ﬁxed data stores in DBMSs) or left to be tuned and conﬁgured by users (e.g. manual data backup in File Systems). In this paper, we take a holistic view of data storage and envision a virtual storage layer. Our virtual storage layer provides a uniﬁed storage framework for several use-cases including personal, enterprise, and cloud storage.
```
@inproceedings{JQD13,
   author    = {Alekh Jindal and Jorge-Arnulfo Quian{\'e}-Ruiz and Jens Dittrich},
   title     = {{WWHow! Freeing Data Storage from Cages}},
   booktitle = {CIDR},
   year      = {2013},
   }
```
Jens Dittrich, Jorge-Arnulfo Quiane-Ruiz
Efficient Big Data Processing in Hadoop MapReduce
VLDB 2012/PVLDB, Istanbul, Turkey. (Tutorial) slides Abstract / [bib]
Efficient Big Data Processing in Hadoop MapReduce
This tutorial is motivated by the clear need of many organizations, companies, and researchers to deal with big data volumes effi- ciently. Examples include web analytics applications, scientific applications, and social networks. A popular data processing en- gine for big data is Hadoop MapReduce. Early versions of Hadoop MapReduce suffered from severe performance problems. Today, this is becoming history. There are many techniques that can be used with Hadoop MapReduce jobs to boost performance by orders of magnitude. In this tutorial we teach such techniques. First, we will briefly familiarize the audience with Hadoop MapReduce and motivate its use for big data processing. Then, we will focus on dif- ferent data management techniques, going from job optimization to physical data organization like data layouts and indexes. Through- out this tutorial, we will highlight the similarities and differences between Hadoop MapReduce and Parallel DBMS. Furthermore, we will point out unresolved research problems and open issues.
```
@article{DQ12,
   author    = {Jens Dittrich and Jorge-Arnulfo Quian{\'e}-Ruiz},
   title     = {{Efficient Big Data Processing in Hadoop MapReduce}},
   journal   = {PVLDB},
   volume    = {5},
   number    = {12},
   year      = {2012},
   pages     = {2014-2015},
   }
```
Jens Dittrich, Jorge-Arnulfo Quiane-Ruiz, Stefan Richter, Stefan Schuh, Alekh Jindal, Jörg Schad
Only Aggressive Elephants are Fast Elephants
VLDB 2012/PVLDB, Istanbul, Turkey. slides Abstract / [bib]
Only Aggressive Elephants are Fast Elephants
Yellow elephants are slow. A major reason is that they consume their inputs entirely before responding to an elephant rider’s orders. Some clever riders have trained their yellow elephants to only con- sume parts of the inputs before responding. However, the teaching time to make an elephant do that is high. So high that the teaching lessons often do not pay off. We take a different approach. We make elephants aggressive; only this will make them very fast. We propose HAIL (Hadoop Aggressive Indexing Library), an enhancement of HDFS and Hadoop MapReduce that dramatically improves runtimes of several classes of MapReduce jobs. HAIL changes the upload pipeline of HDFS in order to create different clustered indexes on each data block replica. An interesting feature of HAIL is that we typically create a win-win situation: we improve both data upload to HDFS and the runtime of the actual Hadoop MapReduce job. In terms of data upload, HAIL improves over HDFS by up to 60% with the default replication factor of three. In terms of query execution, we demonstrate that HAIL runs up to 68x faster than Hadoop. In our experiments, we use six clusters including physical and EC2 clusters of up to 100 nodes. A series of scalability experiments also demonstrates the superiority of HAIL.
```
@article{DQR+12,
   author    = {Jens Dittrich and Jorge-Arnulfo Quian{\'e}-Ruiz and Stefan Richter and Stefan Schuh and Alekh Jindal and J{\"o}rg Schad},
   title     = {{Only Aggressive Elephants are Fast Elephants}},
   journal   = {PVLDB},
   volume    = {5},
   number    = {11},
   year      = {2012},
   pages     = {1591-1602},
   }
```
Alekh Jindal, Jorge-Arnulfo Quiane-Ruiz, Jens Dittrich
Trojan Data Layouts: Right Shoes for a Running Elephant
ACM SOCC 2011, Cascais, Portugal. Abstract / [bib]
Trojan Data Layouts: Right Shoes for a Running Elephant
MapReduce is becoming ubiquitous in large-scale data analysis. Several recent works have shown that the performance of Hadoop MapReduce could be improved, for instance, by creating indexes in a non-invasive manner. However, they ignore the impact of the data layout used inside data blocks of Hadoop Distributed File System (HDFS). In this paper, we analyze different data layouts in detail in the context of MapReduce and argue that Row, Column, and PAX layouts can lead to poor system performance. We propose a new data layout, coined Trojan Layout, that internally organizes data blocks into attribute groups according to the workload in order to improve data access times. A salient feature of Trojan Layout is that it fully preserves the fault-tolerance properties of MapReduce. We implement our Trojan Layout idea in HDFS 0.20.3 and call the resulting system Trojan HDFS. We exploit the fact that HDFS stores multiple replicas of each data block on different computing nodes. Trojan HDFS automatically creates a different Trojan Layout per replica to better fit the workload. As a result, we are able to schedule incoming MapReduce jobs to data block replicas with the most suitable Trojan Layout. We evaluate our approach using three real-world workloads. We compare Trojan Layouts against Hadoop using Row and PAX layouts. The results demonstrate that Trojan Layout allows MapReduce jobs to read their input data up to 4.8 times faster than Row layout and up to 3.5 times faster than PAX layout.
```
@inproceedings{JQD11,
   author    = {Alekh Jindal and Jorge-Arnulfo Quian{\'e}-Ruiz and Jens Dittrich},
   title     = {{Trojan data layouts: right shoes for a running elephant}},
   booktitle = {SoCC},
   year      = {2011},
   pages     = {21},
   }
```
Jorge-Arnulfo Quiane-Ruiz, Christoph Pinkel, Jörg Schad, Jens Dittrich
RAFT at Work: Speeding-Up MapReduce Applications under Task and Node Failures
SIGMOD 2011, Athens. (Demo paper) poster Abstract / [bib]
RAFT at Work: Speeding-Up MapReduce Applications under Task and Node Failures
The MapReduce framework is typically deployed on very large computing clusters where task and node failures are no longer an exception but the rule. Thus, fault-tolerance is an important aspect for the efficient operation of MapReduce jobs. However, currently MapReduce implementations fully recompute failed tasks (subparts of a job) from the beginning. This can significantly decrease the runtime performance of MapReduce applications. We present an alternative system that implements RAFT ideas. RAFT is a family of powerful and inexpensive Recovery Algorithms for Fast-Tracking MapReduce jobs under task and node failures. To recover from task failures, RAFT exploits the intermediate results persisted by MapReduce at several points in time. RAFT piggybacks checkpoints on the task progress computation. To recover from node failures, RAFT maintains a per-map task list of all input key-value pairs producing intermediate results and pushes intermediate results to reducers. In this demo, we demonstrate that RAFT recovers efficiently from both task and node failures. Further, the audience can compare RAFT with Hadoop via an easy-to-use web interface.
```
@inproceedings{QPS+11,
   author    = {Jorge-Arnulfo Quian{\'e}-Ruiz and Christoph Pinkel and J{\"o}rg Schad and Jens Dittrich},
   title     = {{RAFT at work: speeding-up mapreduce applications under task and node failures}},
   booktitle = {SIGMOD Conference},
   year      = {2011},
   pages     = {1225-1228},
   }
```
Jorge-Arnulfo Quiane-Ruiz, Christoph Pinkel, Jörg Schad, Jens Dittrich
RAFTing MapReduce: Fast Recovery on the Raft
ICDE 2011, Hannover. TR Abstract / [bib]
RAFTing MapReduce: Fast Recovery on the Raft
MapReduce is a computing paradigm that has gained a lot of popularity as it allows non-expert users to easily run complex analytical tasks at very large-scale. At such scale, task and node failures are no longer an exception but rather a characteristic of large-scale systems. This makes fault-tolerance a critical issue for the efficient operation of any application. MapReduce automatically reschedules failed tasks to available nodes, which in turn recompute such tasks from scratch. However, this policy can significantly decrease performance of applications. In this paper, we propose a family of Recovery Algorithms for Fast-Tracking (RAFT) MapReduce. As ease-of-use is a major feature of MapReduce, RAFT focuses on simplicity and also non-intrusiveness, in order to be implementation-independent. To efficiently recover from task failures, RAFT exploits the fact that MapReduce produces and persists intermediate results at several points in time. RAFT piggy-backs checkpoints on the task progress computation. To deal with multiple node failures, we propose query metadata checkpointing. We keep track of the mapping between input key-value pairs and intermediate data for all reduce tasks. Thereby, RAFT does not need to re-execute completed map tasks entirely. Instead RAFT only recomputes intermediate data that were processed for local reduce tasks and hence not shipped to another node for processing. We also introduce a scheduling strategy taking full advantage of these recovery algorithms. We implemented RAFT on top of Hadoop and evaluated it on a 45-node cluster using three common analytical tasks. Overall, our experimental results demonstrate that RAFT outperforms Hadoop runtimes by 23% on average under task and node failures. The results also show that RAFT has negligible runtime overhead.
```
@inproceedings{QPS+11,
   author    = {Jorge-Arnulfo Quian{\'e}-Ruiz and Christoph Pinkel and J{\"o}rg Schad and Jens Dittrich},
   title     = {{RAFTing MapReduce: Fast recovery on the RAFT}},
   booktitle = {ICDE},
   year      = {2011},
   pages     = {589-600},
   }
```
Jörg Schad
Flying Yellow Elephant: Predictable and Efficient MapReduce in the Cloud
VLDB 2010 PhD Workshop, Singapore. Abstract

Flying Yellow Elephant: Predictable and Efficient MapReduce in the Cloud
Today, growing datasets require new technologies as standard technologies — such as parallel DBMSs — do not easily scale to such level. On the one side, there is the MapReduce paradigm allowing non-expert users to easily deﬁne large distributed jobs. On the other side, there is Cloud Computing providing a pay-as-you-go infrastructure for such computations. This PhD project aims at improving the combination of both technologies, especially for the following issues: (i) predictability of performance, (ii) runtime optimization and (iii) Cloud-aware scheduling. These issues can result in signiﬁcant runtime overhead or non-optimal use of computing resources, which in a Cloud setting directly correlates to high monetary cost. We present preliminary results that conﬁrm a significant improvement on performance when addressing some of these issues. Further, we discuss research challenges and initial ideas for above mentioned issues.
Jens Dittrich, Jorge-Arnulfo Quiane-Ruiz, Alekh Jindal, Yagiz Kargin, Vinay Setty, and Jörg Schad
Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing)
VLDB 2010/PVLDB, Singapore. correction slides Abstract / [bib]
Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing)
MapReduce is a computing paradigm that has gained a lot of attention in recent years from industry and research. Unlike parallel DBMSs, MapReduce allows non-expert users to run complex analytical tasks over very large data sets on very large clusters and clouds. However, this comes at a price: MapReduce processes tasks in a scan-oriented fashion. Hence, the performance of Hadoop — an open-source implementation of MapReduce — often does not match the one of a well-configured parallel DBMS. In this paper we propose a new type of system named Hadoop ++ : it boosts task performance without changing the Hadoop framework at all (Hadoop does not even ‘notice it’). To reach this goal, rather than changing a working system (Hadoop), we inject our technology at the right places through UDFs only and a ff ect Hadoop from inside . This has three important consequences: First, Hadoop ++ signifi- cantly outperforms Hadoop. Second, any future changes of Hadoop may directly be used with Hadoop ++ without rewriting any glue code. Third, Hadoop ++ does not need to change the Hadoop in- terface. Our experiments show the superiority of Hadoop ++ over both Hadoop and HadoopDB for tasks related to indexing and join processing.
```
@article{DQJ+10,
   author    = {Jens Dittrich and Jorge-Arnulfo Quian{\'e}-Ruiz and Alekh Jindal and Yagiz Kargin and Vinay Setty and J{\"o}rg Schad},
   title     = {{Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing)}},
   journal   = {PVLDB},
   volume    = {3},
   number    = {1},
   year      = {2010},
   pages     = {518-529},
   }
```
Jörg Schad, Jens Dittrich, and Jorge-Arnulfo Quiane-Ruiz
Runtime Measurements in the Cloud: Observing, Analyzing, and Reducing Variance
VLDB 2010/PVLDB, Singapore. slides Abstract / [bib]
Runtime Measurements in the Cloud: Observing, Analyzing, and Reducing Variance
One of the main reasons why cloud computing has gained so much popularity is due to its ease of use and its ability to scale computing resources on demand. As a result, users can now rent computing nodes on large commercial clusters through several vendors, such as Amazon and rackspace. However, despite the attention paid by Cloud providers, performance unpredictability is a major issue in Cloud computing for (1) database researchers performing wall clock experiments, and (2) database applications providing servicelevel agreements. In this paper, we carry out a study of the performance variance of the most widely used Cloud infrastructure (Amazon EC2) from different perspectives. We use established microbenchmarks to measure performance variance in CPU, I/O, and network. And, we use a multi-node MapReduce application to quantify the impact on real data- intensive applications. We collected data for an entire month and compare it with the results obtained on a local cluster. Our results show that EC2 performance varies a lot and often falls into two bands having a large performance gap in-between — which is somewhat surprising. We observe in our experiments that these two bands correspond to the different virtual system types provided by Amazon. Moreover, we analyze results considering different availability zones, points in time, and locations. This analysis indicates that, among others, the choice of availability zone also influences the performance variability. A major conclusion of our work is that the variance on EC2 is currently so high that wall clock experiments may only be performed with considerable care. To this end, we provide some hints to users.
```
@article{SDQ10,
   author    = {J{\"o}rg Schad and Jens Dittrich and Jorge-Arnulfo Quian{\'e}-Ruiz},
   title     = {{Runtime Measurements in the Cloud: Observing, Analyzing, and Reducing Variance}},
   journal   = {PVLDB},
   volume    = {3},
   number    = {1},
   year      = {2010},
   pages     = {460-471},
   }
```

Hadoop++ and HAIL

Hadoop++

HAIL

People

Publications