Google Dremel: 1 TRILLION FILE READS in 10 seconds

Oh, hello everyone. We are going to be talking about Google Dremel today, a paper from 2008. Dremel has been an extremely influential system. In fact, even now, more than 15 years later, you will see that Dremel is being used at Google by a system called BigQuery.

It's been so influential, and 15 years later, you will see that Dremel is being used at Google by a system called BigQuery. It has been so influential that VLDB awarded it the Test of Time Award in 2020, 12 years after it was published. As a software engineer, it makes a lot of sense to be familiar with this paper. Now, the first question is, what is Dremel? In 2008, Google had a significant amount of data—petabytes worth—that it wanted to analyze.

They wanted to mine the data, and product managers, engineers, and CXOs wanted to write queries on this data to see what patterns they could use. The problem was that scanning petabytes of data takes a lot of time to process and output. Usually, product managers and CXOs want to run one-off queries. For example, a product manager at Google may want to see how many people taking long rides, let’s say from Mumbai to Goa, stop over at restaurants for food. Based on this information, they might want to serve contextual ads. If we know you are on a long drive, perhaps we can give you an ad for a restaurant that is on the way. This is just an idea; it’s a brainstorm at this point. First, you need to analyze the data to help inform your decision, but how do you query this data? In 2008, the standard way of doing things was MapReduce, which essentially meant that jobs were running, defined using code. Engineers would write this code and these scripts based on what they heard from product managers.

And once these scripts are executed, you will receive an output. In our example, the percentage of people who go to restaurants nearby during a long drive is 56%. The product manager looks at this and says, "This is great. I want to know the percentage for the last three months and what it was before that. Is this number increasing?"

Are people more prone to choosing a restaurant nearby during a long drive? What do you need to do now? You need to write another job. You need to write code again. Essentially, this product manager has to go to a software engineer, explain the task, wait for them to write the code, and then wait for them to execute the code.

After the execution, based on what you see and the insights gained, you might ask a new question. The iteration time for this was very large; it used to take days. Even with dedicated engineers working solely on MapReduce jobs, it would still take hours—usually one to three days—before you could make any sensible decisions.

That's a long time. CXOs had the same problem. Now, put yourself in the principal engineer's shoes. In 2008, at Google, you have a lot of product managers complaining about engineers being slow or about the systems being slow. Sometimes, this MapReduce job fails.

You have to restart it. It's a nightmare. Engineers are complaining about their time being wasted by product managers because half the day is spent just mining data, and the rest is spent talking to PMs and understanding their requirements. Google decided that they need some sort of interactive analytics system. "Interactive" means that you want to get results for any query within a minute.

The second thing you want to do is free up the software engineers who are currently just writing MapReduce jobs. You can utilize them by placing them in different teams and providing an interface for the product managers so they can query the data themselves. This will eliminate one layer of dependency. The software engineers will no longer need to be consulted before any kind of query is executed, allowing you to remove that dependency.

How do you do this? One way would be to provide an extremely detailed interactive analytics tool where a product manager without any coding experience can easily run queries. What kind of tool would that be? Most product managers know SQL at least at a high level. And if they don't, they can hire a data analyst.

They can use a team of data analysts who are great at writing SQL queries. This approach is much cheaper. You don't need to have software engineers writing MapReduce jobs; you can have data analysts.

Let's do this, or you can have the product managers themselves writing SQL queries. This was one major decision that has significantly contributed to Dremel's popularity in the analytics space, particularly for interactive analytics, allowing for the rapid answering of queries in under one minute. You can't achieve this without analyzing the access patterns of the system. How is this system being used? Typically, the system is utilized for generating count queries and statistical queries.

This is a great insight. CXOs normally don’t want to get the details; they are not interested in the individuals who actually visited a restaurant. What matters to them is the aggregated data—counts, percentages, and similar statistics—that help them make decisions. So, you are mainly looking for statistical data when it comes to queries.

And usually, this data is distributed across systems. Therefore, you need to filter through these systems and then aggregate the data. Both of these processes, filtration and aggregation, have to be extremely fast. You want answers within one minute.

Filtration and aggregation have to happen blazingly fast. Let's understand how this works. This is the query architecture of Dremel. You can see that clients, who are product managers, use a dashboard or some sort of interactive user interface. They issue a query that goes to the query manager.

Sure! Here's your text with corrected capitalization and spelling: "Okay, the query manager is part rate limiter, part load balancer. It determines which shards should be targeted based on the load on each shard. If you are not familiar with sharding, please check out the video. It has a dual role, right? So you have a query manager that is sending queries to the root."

And the root node, as you can expect, is the root of a tree. It aggregates all the results and returns a response once the query has finished processing. What the root does is look at the query and identify the shards that need to be accessed for this query. Each shard manages a specific key range, let's say from k1 to k1000, while another shard manages keys greater than k1000. If you want to query for keys 100 and 1100, then the query has to flow to both nodes, both shards.

What are these shards? Are they logical entities? No, they are physical servers. A shard then recursively queries its sub-shards, so if you have a query for 100, maybe the first 500 exist in one location and the next 500 exist in another. Since 100 is less than 500, you don't need to query this shard, which saves some resources. Eventually, k100 will reach the leaf node where it belongs, and the leaf can retrieve it from its local disk if it is available. If not, it will retrieve it from a distributed file store.

In 2008, there was the Google File System (GFS). You might have heard of this. We'll pick this paper sometime. Currently, the newer version is called Colossus.

Interestingly, most systems at Google require some sort of storage managed by Colossus. They need network capabilities powered by Jupiter. They also need compute and memory, which is provided by Borg, inspired by Kubernetes. Additionally, they need some configuration setup, which is handled by Spanner.

So, among these four, Jupyter is used by Dremel for network capabilities, and storage is also utilized. The shards you see are definitely coming from Borg. When you make a query, the query manager estimates how much compute you need. The compute is measured as the number of machines multiplied by the number of threads they have; therefore, the total number of threads defines the compute power for this query. If you need more compute power, you can increase it. Conversely, if you want to reduce the compute power for this query, you can do that as well. Based on this, the time taken by the query will increase or decrease. Now, when the result is fetched from disk or a distributed file store, it is propagated upward to the parent shard. You see, I've added dots here very sneakily.

That means there can be any number of levels, and the query manager is what suggests how many shards will be needed to effectively aggregate this kind of query. At a high level, if you have worked with segment trees or interval trees, what we are doing is taking results, aggregating them, placing them on the higher shard, and moving up the tree until we reach the root. This architecture is repeated at Google many times; tree architectures are favored, and they also utilize them in Google Monarch. It's highly efficient because queries are usually answered in just a few seconds, allowing clients and users to make decisions quickly. They don’t have to wait for every query to complete before going to lunch.

Instead, users can sit at a desktop, wait for a minute for loading to complete, and then receive a result. Following that, they can fire a new query based on the insights gained. The system is also intelligent in that it includes a prefetch cache that retrieves data relevant to the query just made. For example, when you ask, "Tell me the number of people who have visited a restaurant while going on a long drive," it will gather data related to long drives and data concerning restaurants that have been pre-fetched into the cache. Consequently, the subsequent queries are likely to fetch the same kind of data, resulting in a 95% hit rate. This means you don't have to go all the way down to the leaf for information.

You don't have to fetch from the local disk. In the worst case, you don't have to fetch from a distributed file store. You can get it from a cache with a 95% hit rate, which really improves latency. Another optimization that is very useful is when clients, specifically product managers, are okay with not having perfect answers; they are fine with getting 99% accuracy or even 90% accuracy. For example, you might want to know the percentage of people who, during a long trip, have gone to a restaurant.

You don't have to achieve 56 percent; you can be off by plus or minus two percent. It's not mandatory, but why is that important? If you have this luxury and can make an approximate result, then the query manager informs the route that when you have 98 percent or 90 percent of the results, you should give a response. Don't keep the client waiting. It’s possible that L3 is down or L4 is taking a long time. We don't need to wait for all the leaf nodes.

We can provide a response as soon as we are ready. Alternatively, if it takes a long time for L4 to respond, we don’t need to wait for all the leaf nodes. We can generate a response as soon as we are confident enough. This opens up a lot of possibilities; for example, if you want to see the top K results—such as the top 10 most popular YouTube videos—you don't need to go through the entire YouTube video set. You can examine about 95 to 98 percent of the data, as the tail latency for the last two percent is very high. By ignoring them, you can significantly save on latency. The final optimization that Dremel offers is columnar storage.

All data processed by Dremel is stored as columns. The benefit of this is that columnar compression is much better, especially when you are looking at aggregate statistics. For example, if I have tuples like this, where the name, country, and age of a person are noted, this would be Row 1. The way I would store this would be to attach Row 2 with the name, country, and age, and then Row 3 would come next with the same information. If I wanted to know the average age of my users, I would need to scan all of this data.

I would need to sequentially read all the data. Instead, if I could keep all the columns together—Age One, Age Two, Age Three, Name One, Name Two, Name Three, and Country One, Country Two, Country Three—then the average age would just require a scan of three data points instead of nine data points. This would allow for faster scans due to columnar storage. The other thing that is really important is compression. If you have the same kind of data being stored together, you can use compression algorithms like non-zero run-length encoding to reduce the space consumed by your data. This means you need less storage and less bandwidth, leading to usually faster processing. However, non-zero run-length encoding does have some issues. One of the challenges is that whenever you have a block of zeros and want to query between that block, it's difficult to find a header when all the records are zeros. To actually hydrate this data, you have to go up to the top header.

To avoid this, Google developed its own compression algorithm, which has inspired many other systems. Apache Parquet, for example, has adopted ideas from it. The engineers at Twitter also developed an algorithm that has influenced various other systems, including Apache Parquet.

The engineers at Twitter developed this format. Now it's open source and features even better algorithms than this. The basic idea here, if you know about Huffman coding, is that you take your data and spread it out like a tree. A trip has an ID, multiple locations, and multiple users, ranging from zero to star.

Each of those users may have multiple interests. They either have a country defined or they do not. The interest may have a type. For example, I am interested in burgers and I am interested in pizza. The location may actually be a polygon.

So, that enclosed space may also refer to a specific type of location. It could be a restaurant, a playground, or something else. What Google did was take each of these data fields and compress them in a way that makes it easy to decompress later. When you're querying that data, it will be easy to find the range you're looking for and obtain the aggregate statistics.

The algorithm for converting these objects into a format suitable for columnar storage is very complex. I spent hours researching this topic and decided not to include it here. If you're interested, I have the links in the description. You may wonder if this will be useful to me as an engineer. Well, no, but if you want to experiment with the math, feel free to do so. The Huffman coding algorithm, which involves choosing a path in a tree, shares some similarities with the Dremel algorithm.

So that's it for Google Dremel. It's a short, concise paper, just eight pages long. That's why the main core ideas were explained so quickly. If you have any doubts or suggestions, you can let me know in the comments below.

I'm trying to create a system design judge on my site called "Interview Ready." Check it out, and I'll see you next time. Bye-bye!