# Dividing Infinity - Distributed Partitioning Schemes

##### 2016-08-15 16:00:00 UTC by Paul Asmuth

*
This is the second post in a series discussing the architecture and
implementation of massively parallel databases, such as Vertica [0],
BigQuery [1] or EventQL [2]. The target audience are
software and system engineers with an interest in databases and distributed systems.
*

In the last post we saw that in order to execute interactive queries on a large data set we have to split the data up into smaller partitions and put each partition on it's own server. This way we can utilize the combined processing power of all servers to answer the query rapidly.

The problem we'll discuss today is how exactly we're going to split up a given dataset into partitions and distribute them among servers.

Say we have a table containing a large number of rows, a couple billion or so. The total size of the table is around 100TB. Our task is to distribute the rows uniformly among 20 servers, i.e. put roughly 5TB of the table on each server.

Of course, solving that task is trivial: We read in our 100TB source table, write the first 5TB of rows to the first server, the next 5TB to the second server and so on.

While this simplistic scheme works well for a static dataset, we'll have to be more clever if we are to implement an entire database that supports adding and modifying rows.

Why? Consider this: If we want to modify a row in our naively partitioned table,
we first have to figure out on which server we have put the row when splitting
the table into pieces. Now, to find the row, we have to search through all rows
until we hit the correct one. In the worst case we would have to examine *all*
rows on *all* servers to find any single row - the whole 100TB of data.

In more technical terms: Locating a row has *linear complexity* [3]: Finding
the row in a table containing one thousand rows would take one thousand times
longer than finding the row in a table containing just one row. It gets slower
and slower as we add more rows.

Clearly, our simplistic solution will not scale: We need a more efficient way to figure out on which server a given row is stored.

To quickly tell the location of a specific row, we could store an index file somewhere that records the location of each row. We could then do a quick lookup into our index to find the correct server instead of searching through all the data.

Sadly, this doesn't solve the problem. The index file would still have linear complexity. Allthough this time it wouldn't be linear in time, but in space: If we were storing a bazillion rows in our table, our index file would also have a bazillion rows.

Essentially, we would just be rephrasing the problem statement from
*"How do we partition a large table?"* to *"How do we partition a large index
file?".*

We'll have to come up with a partitioning scheme that allows us to find rows with less than linear complexity. I.e. we have to find an algorithm that can correctly compute the location of any single row, but doesn't get slower and slower as we add more rows to the table.

## Modulo Hashing

One such algorithm is called *modulo hashing*. The good thing about modulo
hashing is that it's not only very efficient but also extremely simple to
implement.

If we want to partition our input table using modulo hashing, we first have to
assign an identifier `ID`

to every row in the table. This `ID`

is usually
dervied from the row itself, for example by designating one of the table's columns
as the primary key. For illustration purposes, we will use numeric identifiers,
but the same works with strings. [4]

The only piece of informationthat modulo hashing keeps is a single variable `N`

.
This variable `N`

contains the number of servers among which the table should
be partitioned.

Now, to figure out on which server a given row belongs, we simply compute the
remainder of the division of the row's `ID`

over `N`

. This use of the modulo
operation is also where the algorithm derives its name from.

```
find_row(row_id) {
server_id := row_id % N;
return server_id;
}
```

If, for example, we wanted to locate the row with `ID=123`

in a table partitioned
among 8 servers (`N=8`

), the row would be stored on server number 3
(`123 % 8 = 3`

).

Of course, this is assuming we have also used the algorithm to decide on which server to put each row while loading the input table in the first place.

Modulo hashing works out so that every possible `ID`

is consistently mapped
to a single server. The distribution of the rows among servers will be
approximately uniform, i.e. every server will get roughly the same number of
rows. [5]

The modulo hashing algorithm is a huge improvement over our naive approach as it
is constant in space and time: Locating a row takes the same amount of time
regardless of the total number of rows in the table. And the only pieces of
information we need to tell where a row goes are the row's `ID`

and the total
number of servers `N`

, which will only take a few bytes to store. Not bad.

So are we done? I'm afraid we're not.

One thing modulo hashing can't handle well is a growing dataset. If we're
continually adding more rows to the table, we will eventually have to add more
capacity and increase the number of servers `N`

. However, once we do that the
locations of almost all of the rows would change, since changing `N`

also changes
the result of all modulo operations.

This means that in order to increase the number of servers `N`

and still keep the
rows where they belong, we would have to copy every single row in the table to
it's new location every time we add or remove a server.

That's not exactly ideal: Even if we did not care about the massive overhead of copying every single row, we would eventually reach a point where our table grows faster than we can rebalance it.

## Consistent Hashing

Consistent hashing is a more involved version of modulo hashing. The main improvement of consistent hashing is that it allows to add and remove servers without affecting the locations of all rows.

At the heart of the consistent hashing algorithm is a so called *circular
keyspace*. Before we discuss what exactly that means let's define the term
*keyspace*:

As with modular hashing we need to assign an identifier `ID`

to each row. Now,
the keyspace is the range of all valid `ID`

values. If the `ID`

is numeric, the
keyspace is the range from negative infinity to positive infinity.

Within the keyspace, identifiers are well-ordered [6]. That means each `ID`

has a
*successor* and a *predecessor*. The successor of an `ID`

is the `ID`

that goes
immediately after it and the predecessor is the one that goes immediately before it.

In the illustration above, the successor of green (`ID=123`

) is red (`ID=856`

), the
successor of red (`ID=856`

) is yellow (`ID=923`

) and so on.

But what is the successor of yellow (`ID=923`

)? Does it have one? The answer is
not entirely clear. However, we will later have to come up with a successor for each
possible position in the keyspace, so we will have to define what the successor
of the last position in our keyspace is.

Imagine, we glued one end of our keyspace to the other end:

Now we can clearly say that, in clockwise order, yellow's (`ID=923`

) successor
is green (`ID+123`

). Also, it finally looks like a circular keyspace!

Back to consistent hashing. Like we did with modulo hashing, we will choose
an initial number of servers `N`

. For each of the `N`

servers, we will put a marker
at a random position in the circular keyspace.

To decide on which server a given row `ID`

belongs, we first locate the position
of the `ID`

in the circular keyspace and then search clockwise for the next
server marker. In other words: each row goes onto the server whose marker
immediately succeeds the row-id's position in the keyspace.

The illustration below shows a circular keyspace with eight server markers. In
the illustration, the succeeding server marker for row `123`

is `server 1`

,
while the suceeding server marker for rows `856`

and `923`

is `server 3`

.

So row `123`

gets stored on `server 1`

while rows `856`

and `923`

get stored on
`server 3`

.

Alike the modulo hashing scheme, we still end up with a uniform distribution of rows among servers [7] and can quickly locate each row. The only information we have to store are the positions of each server's marker in the keyspace.

Additionally, any server marker that we add or remove will only affect the rows immediately between it and the previous marker: The location of all other rows remain consistent, hence the name consistent hashing.

This means we can add or remove servers and only have to move a small subset of the
rows into their new locations. The ratio of rows that needs to be moved is `1/N`

where `N`

is the number of servers. So as we add more servers, the percentage of
rows that need to be moved actually gets smaller.

Can we still do better? It depends on your usecase. Consistent hashing is successfully employed in a number of popular key/value databases [8] such as DynamoDB [9], Cassandra [10] or memcache [11]. Nevertheless, here are two things that we could improve about consistent hashing:

Firstly, consistent hashing only supports an exact lookup operation. That is, we
can only find a row quickly if we already know it's `ID`

. If we want to find the
locations of all rows in a range of `IDs`

, for example all rows with an `ID`

between `100`

and `200`

, we're back to scanning the full table.

Because of this, consistent hashing is particularly well suited for key/value databases where range scans are not required but less so for OLAP [12] systems like EventQL.

The other possible improvement is that we still have to copy roughly `1/N`

of the
table's rows after changing the number of servers. If we had 100TB on 20 servers,
that would mean we're - realistically - still copying at least 15TB for every
server addition [13]. Not too bad, but still a lot of overhead network traffic.

## The BigTable Algorithm

The last algorithm we will look at today is best known for it's publication in Google's BigTable paper [14].

The bigtable algorithm takes a completely different approach to the problem, but it also starts by defining a keyspace. Except this time it's not a circular keyspace, but a linear one.

The illustration below shows a bigtable keyspace and the position of three rows
with the identifiers `123`

, `856`

and `923`

within the keyspace.

The next thing bigtable does is to split up the keyspace into a number of
*partitions* that are defined by their start and end positions, i.e. by the
lowest and highest row identifiers that will still be contained in the partition.

The illustration below shows a keyspace that is split into five parititions
A-E. In the illustration, the row with `ID=123`

goes into partition `B`

and
the rows with `ID=856`

and `ID=923`

both go into partition `D`

.

Now, the clever bit about the bigtable algorithm is how it comes up with the partition boundaries. To see why it's clever we have to understand why we can't simply divide the keyspace into equal parts without knowing the exact distribution of the input data:

One reason for that is that if you split up the range from negative to positive infinity into a list of discrete partitions, you end up with an infinite number of partitions.

The other reason is that it's highly likely that the row identifiers will all be piled up in a small area of the keyspace. After all, the identifiers might be user-supplied so we can't nessecarily guarantee anything about their distribution.

So it could be, that even though we have split up the keyspace into a large number of partitions, all rows actually end up in the same partition. And we can't solve the problem by making the partitions infinitesimally small either - that would be like going to back to keeping track of every row's location individually, just a bit worse.

Here's how bigtable solves the problem: Initially the table starts out with a single partition that covers the whole keyspace - from negative infinity to positive infiity.

As soon as this first partition has become too large, it will be split in two. The split point will be chosen so that it roughly halves the data in the partition into equal parts. This continues recursively as partitions become too large. At a basic level, it's an application of the classic divide and conquer principle [15].

This way, you always end up with a number of partitions that are roughly equal in size. Even though the distribution of row identifiers in the keyspace is initially unknown.

And since each partition is defined in terms of it's lowest and highest contained row identifier, we can easily implement efficient range scans: To find all rows in a given range of identifiers, we only have to scan the partitions with overlapping ranges.

Lastly, the bigtable scheme does require a second allocation layer to assign partitions to servers that we didn't discuss here. Suffice to say that this second allocation layer allows us to add new servers to a cluster without physically moving a single row. Of course, we still need to move around some rows every time we split a partition.

## Conclusion

So is the bigtable algorithm really "better" than consistent hashing? Again, it depends on the usecase.

The upsides of the bigtable scheme are that it supports range scans and that we can add capacity to a cluster without copying rows. The major downside is that implementing the algorithm in a masterless system requires a fair amount of code and synchronization.

For EventQL, we still chose the bigtable algorithm as the clear winner. After
reading this post, go have a look at the debug interface of EventQL where you
can see the *partition map* for a given table. Hopefully it will make a lot more
sense now:

That's all for today. In the next post we will discuss how to handle streaming updates on columnar files. You can subscribe to email updates for upcoming posts or the RSS feed in the sidebar.

[0] Andrew Lamb et al. (2012) The Vertica Analytic Database: C-Store 7 Years Later (The 38th International Conference on Very Large Data Bases) — http://vldb.org/pvldb/vol5/p1790_andrewlamb_vldb2012.pdf

[1] Sergey Melnik et al. (2010) Dremel: Interactive Analysis of Web-Scale Datasets (The 36th International Conference on Very Large Data Bases) — http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36632.pdf

[2] EventQL (2016) An open-source SQL database for large-scale event analytics &mdash http://eventql.io

[3] Complexity Theory on Wikipedia — https://en.wikipedia.org/wiki/Big_O_notation

[4] The usual way to do this is to first run the string through a hash function and then use (a subset of) the output of the hash function as a numeric identifier.

[5] To ensure uniform distribution, pre-process the identifiers with a suitable hash function (i.e. a hash function that guarantees uniform distribution of its outputs such as MurmurHash)

[6] Well-order on Wikipedia — https://en.wikipedia.org/wiki/Well-order

[7] Practical systems will apply a hash function to the row ID and assign more than one marker per server. Marker values are chosen randomly in usually a 160 bit keyspace. This works out so that the data is almost guaranteed to be uniformly distributed among servers.

[8] Key-value database on Wikipedia — https://en.wikipedia.org/wiki/Key-value_database

[9] Giuseppe DeCandia et al. (2007) Dynamo: Amazonâ€™s Highly Available Key-value Store (21st ACM Symposium on Operating Systems Principles) — http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

[10] Avinash Lakshman, Prashant Malik (2009) Cassandra - A Decentralized Structured Storage System (ACM SIGOPS Operating Systems Review archive Volume 44 Issue 2) — https://www.cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf

[11] memcached - a distributed memory object caching system — https://memcached.org/

[12] OLAP on Wikipedia — https://en.wikipedia.org/wiki/Online_analytical_processing

[13] Assuming a replication factor of 3. In practice, replication facotr and overhead combined may result in the data being copied 6-9 times.

[14] Fay Chang et al. (2006) Bigtable: A Distributed Storage System for Structured Data (7th USENIX Symposium on Operating Systems Design and Implementation) — http://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf

[15] Divide and conquer on Wikipedia — https://en.wikipedia.org/wiki/Divide_and_conquer

#### Next up in the series:

- Part 1: Parallel I/O and Columnar Storage
- Part 2: Dividing Infinity - Distributed Partitioning Schemes

Tagged with massively parallel databases, internals, eventql, bigquery, vertica, sql, columnar storage