December 26, 2013 at 00:46Dremel How does Google think in real-time?
Dremel is a scalable request processing system in near-real-time mode , designed to analyze immutable data [4].
The authors of the research paper [4] (among which, apparently, our compatriots are Sergey Melnik and Andrey Gubarev), which describes the basic principles and architecture of Dremel, state that the system is capable of:
UPD1: the picture below isdeja vu for attentive readers.
Dremel is a proprietary product of Google, has been in operation since 2006, was officially introduced to the community at the Very Large Data Base (VLDB) Endowment conference in 2010.
Dremel is used in the analysis of documents collected by a search robot, tracking data about installing applications in the Android Market, Google Books services and spam analysis.
In 2012, Google opened access to Dremel for developers through the Google BigQuery service [14].
Like many systems of this class, Dremel has the ability to scale to several thousand nodes , runs on commodity equipment , provides reliable data storage , fault tolerance and replication , works with immutable data and has its own SQL-like query language .
Dremel uses Google File Distributed File System for storage , and tablet is the storage unit .
But without a doubt, the key innovation of Google Dremel is the data model , which in [4] sounds like “nested columnar storage ”, or, in translation, column storage of nested data .
The basic principles of nested columnar storage are: data whose schema is explicitly defined is stored in column-striped storage, along with the data associated with it.
We will analyze the advantages and disadvantages of such a choice.
Core storageallows you to read large amounts of data and compress it efficiently (as data of the same types are stored in one place) with the highest speed, compared with storage oriented to line-by-line data storage. On the other hand, a write operation in column storages is more expensive than row-striped storages, and maintaining transactional changes is a non-trivial task.
Data storage together with related (including nested) data as well as a column storage scheme allows increasing the speed of data reading. At the same time, this storage method implies the presence of some data redundancy and, as a consequence, the need to solve the problem of consistency of different copies of this data.
Google engineers solved this problem as follows: Dremel works with immutable data, and the problem of redundancy is solved by introducing for each column two additional levels: the definition level and the repetition level .
Source of the illustration [4, Figure 2]
Source of the illustration [4, Figure 3]
A set of blocks is stored in each column. In turn, each block is compressed data and integer values of the definition level and the repetition level . Thus, Dremel, knowing everything about the structure and location of the data that are necessary to fulfill the request, can obtain the necessary information “ in place"(In terminology [4] -" in situ ").
Coding of each column block according to the schemeleads to the fact that the storage structure already contains the assembly algorithm, which is a finite state machine, where:
Source of illustration [4, Figure 4]
In order to execute queries Dremel architecture uses a multi-level tree service (multi-level serving tree): root- server receives a request from a client for execution, reads the necessary metadata and directs tablet'ov (route) requests for the following levels of the tree. And so on until the request reaches the leaves of the service tree. The leaves of the tree interact directly with GFS to obtain the necessary data.
So different requests for Dremel are executed simultaneously, Query dispatcher is responsible for scheduling requests based on their priority and the best load balancing . The Query dispatcher is also responsible for handling failures at the tablet level, which became inaccessible during the execution of the request and the "chalked" tablet.
An interesting solution is also that the query result will not return after 100% of the records have been processed, but earlier - in [4] the figure 98% is given as the most typical. On the one hand, this saves Dremel from waiting for the "slow" leaves of the query tree to finish; on the other hand, it leads to some error in the final result, which is quite acceptable for OLAP systems and hardly acceptable in OLTP systems.
As a result of experiments, the initial data of which is 3K computing nodes, 85 billion rows , Dremel executes queries orders of magnitude faster than MapReduce algorithms running both on record-oriented storages and columnar-oriented storages.
Source of the illustration [4]
In addition, it was stated in [4] that during the experiments, some table scanning speeds on some queries directly approached 100 billion records per second .
Open Source analogues of Dremel include Cloudera Impala , Apache Drill , Parquet (Twitter).
[4] Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, et al. Dremel: Interactive Analysis of Web-Scale Datasets . Proceedings of the VLDB Endowment, 2010.
[14] Google BigQuery - Google Developers.
* A complete list of sources used to prepare the cycle.
Dmitry Petukhov,
MCP,PhD Student , IT zombies, a
man with caffeine instead of red blood cells.
The authors of the research paper [4] (among which, apparently, our compatriots are Sergey Melnik and Andrey Gubarev), which describes the basic principles and architecture of Dremel, state that the system is capable of:
- Perform aggregate queries on more than a trillion rows in seconds;
- scales to thousands of CPUs ;
- Designed to work with petabytes of data ;
- has thousands of users inside Google (literally “at Google” [4]).
UPD1: the picture below is
Dremel is a proprietary product of Google, has been in operation since 2006, was officially introduced to the community at the Very Large Data Base (VLDB) Endowment conference in 2010.
Dremel is used in the analysis of documents collected by a search robot, tracking data about installing applications in the Android Market, Google Books services and spam analysis.
In 2012, Google opened access to Dremel for developers through the Google BigQuery service [14].
Data model
Like many systems of this class, Dremel has the ability to scale to several thousand nodes , runs on commodity equipment , provides reliable data storage , fault tolerance and replication , works with immutable data and has its own SQL-like query language .
Dremel uses Google File Distributed File System for storage , and tablet is the storage unit .
But without a doubt, the key innovation of Google Dremel is the data model , which in [4] sounds like “nested columnar storage ”, or, in translation, column storage of nested data .
The basic principles of nested columnar storage are: data whose schema is explicitly defined is stored in column-striped storage, along with the data associated with it.
We will analyze the advantages and disadvantages of such a choice.
Core storageallows you to read large amounts of data and compress it efficiently (as data of the same types are stored in one place) with the highest speed, compared with storage oriented to line-by-line data storage. On the other hand, a write operation in column storages is more expensive than row-striped storages, and maintaining transactional changes is a non-trivial task.
Data storage together with related (including nested) data as well as a column storage scheme allows increasing the speed of data reading. At the same time, this storage method implies the presence of some data redundancy and, as a consequence, the need to solve the problem of consistency of different copies of this data.
Google engineers solved this problem as follows: Dremel works with immutable data, and the problem of redundancy is solved by introducing for each column two additional levels: the definition level and the repetition level .
Source of the illustration [4, Figure 2]
Source of the illustration [4, Figure 3]
A set of blocks is stored in each column. In turn, each block is compressed data and integer values of the definition level and the repetition level . Thus, Dremel, knowing everything about the structure and location of the data that are necessary to fulfill the request, can obtain the necessary information “ in place"(In terminology [4] -" in situ ").
Coding of each column block according to the scheme
- many states - many columns into which the document is divided;
- transitions - values of repetition levels.
Source of illustration [4, Figure 4]
Query Execution
In order to execute queries Dremel architecture uses a multi-level tree service (multi-level serving tree): root- server receives a request from a client for execution, reads the necessary metadata and directs tablet'ov (route) requests for the following levels of the tree. And so on until the request reaches the leaves of the service tree. The leaves of the tree interact directly with GFS to obtain the necessary data.
So different requests for Dremel are executed simultaneously, Query dispatcher is responsible for scheduling requests based on their priority and the best load balancing . The Query dispatcher is also responsible for handling failures at the tablet level, which became inaccessible during the execution of the request and the "chalked" tablet.
An interesting solution is also that the query result will not return after 100% of the records have been processed, but earlier - in [4] the figure 98% is given as the most typical. On the one hand, this saves Dremel from waiting for the "slow" leaves of the query tree to finish; on the other hand, it leads to some error in the final result, which is quite acceptable for OLAP systems and hardly acceptable in OLTP systems.
Experiment Results
As a result of experiments, the initial data of which is 3K computing nodes, 85 billion rows , Dremel executes queries orders of magnitude faster than MapReduce algorithms running both on record-oriented storages and columnar-oriented storages.
Source of the illustration [4]
In addition, it was stated in [4] that during the experiments, some table scanning speeds on some queries directly approached 100 billion records per second .
Impact on Open Source
Open Source analogues of Dremel include Cloudera Impala , Apache Drill , Parquet (Twitter).
List of sources*
[4] Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, et al. Dremel: Interactive Analysis of Web-Scale Datasets . Proceedings of the VLDB Endowment, 2010.
[14] Google BigQuery - Google Developers.
* A complete list of sources used to prepare the cycle.
Dmitry Petukhov,
MCP,
man with caffeine instead of red blood cells.
