Introduction to Partitioning
Partitioning can be defined as dividing the data between separate nodes|partitions|computers, making it easy to scale your system horizontally.
In this article, I would like to discuss the problems we are trying to solve and a few possible solutions.
Introduction
Imagine a single server residing on the public internet, storing millions of documents, and accepting traffic from geographically distributed users.
The server would suffer due to the following problems:
- The server might have limited resources (RAM, CPU, and storage) to serve incoming requests.
- Even if you vertically scale the server, the bandwidth of the server would be a bottleneck.
- Moreover, what if the server ended up having gigantic user data? What about the performance implications of serving millions of requests?
The most intuitive solution that comes to your mind is splitting the documents evenly between N machines.
If we figured out a way to split the data evenly between N machines, the resource consumption would be divided by N!!
So let’s discuss the possible ways to split the load evenly between N nodes and compare their pros and cons.
Partitioning by userId/userName
We can imagine this type of partitioning as a library bookshelf.
If we had a total of a million users, the first node would serve users with ids ranging from 1 to 100000, while the second node would serve users from 100001 to 200000, and so on.
The above partitioning scheme theoretically spreads documents on multiple servers. However, it has the following drawbacks:
- This may spread the documents evenly between the nodes, but it does not guarantee evenly distributed traffic from users. Some users might be more active than others, creating hotspots (nodes having many users accessing them, while others remain nearly idle)
- If a document is sharable and public, the hotspot problem will become significant.
- Also, what if a node went down? What is the best way to redistribute documents among available nodes? Would this involve moving massive chunks of data if a node went down?
The problem is all bout an even distribution of traffic, not an even distribution of storage.
Partitioning by Hash of ids
Hashing users’ ids/names would provide a more random distribution of users into the available nodes. A hash function can be thought of as an encoder transforming names/ids into hash codes or numbers
Despite providing a more random distribution of users among available nodes, the above scheme would not solve the following issues:
- The uneven distribution of load by users.
- The redistribution of documents.
Partitioning using Consistent Hashing of user Ids/names
Consistent hashing could be thought of as a circular ring with all nodes placed in different locations. A user name/Id is mapped to the nearest node in a clockwise direction. We can also place multiple copies of the nodes on the ring to increase the randomness of key distribution.
With the above hashing scheme, we can solve the following issues:
- The random distribution of users among available nodes.
- Redistribution of users in case of failures (a node is down). A user would be mapped to the next clockwise node, which would distribute a failed node’s documents evenly among other nodes.
The remaining question is, What about the hot spots (skewed load) due to increased activity on certain nodes with active documents?
The problem still exists as we cannot predict the popular documents over time.
Relieving Hot Spots
So far, we have one remaining issue to solve, which is the skewed load.
There is no out-of-the-box solution to such a changing skewed load. This may depend on the application to compensate for the kind of skew on the load.
One possible solution to this problem is to shed the load on hotspots and redistribute documents among other idle nodes. However, it would complicate the mapping of user ids to their document and would require an extra layer of mapping to get a document.
