Designing Data-intensive Applications – Partitioning (6)

1. Write it first

“This article has participated in the call for good writing activities, click to view: the back end, the big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!”

When I read this chapter before, I did not seriously think about the sentence of preface. When I wrote the chapter notes this time, I was suddenly shocked. If anyone has written code for many years, no one has really thought about the difference between the “object oriented” and “process oriented” primitively that they first learned. (Ps is another learn to earn day

Note: We must move beyond the computer’s sequence of instructions. The narrative defines, describes metadata, and sorts out relationships, not the writing process

— Grace Murray Hope

One of the first programmers in the world, and one of the first female programmers. She created what is now the first compiler, the A-0 system, and the commercial computer programming language, COBOL

Q: Start with purpose 🤔?

A: The main reason for partitioning is scalability. Different partitions can be placed on different nodes in a non-shared cluster. As a result, large data sets can be spread across multiple disks, and the query load can be spread across multiple processors.

2. Partition and replication

Partitioning is often used in conjunction with replication, which means that even if each record belongs to a partition, it can still be stored on multiple different nodes to gain fault tolerance.

An example of using replication and partitioning in combination: each node acts as a leader for some partitions, while others act as followers.

3. Partition of key-value data

Suppose you have a lot of data and need to partition, how do you decide which records to store on which nodes?

• Random allocation, the advantage is that there is no skewness problem in equilibrium, the disadvantage is that the query of the specified record must traverse all partitions ❎
• Partition ✅ based on the range of key values

Note: Partitions are not fair, some partitions have more data or queries than others, which we call skew. Unevenly loaded partitions are called hot spots.

3.1 Partitioning by key range

One way to partition is to specify a contiguous key range (maximum and minimum) for each partition, such as the volume of a paper encyclopedia. If you know the boundaries between ranges, you can easily determine which partition contains a certain value. For example, encyclopedias are grouped by keyword

Note: The range of keys is not necessarily evenly distributed, so the data is likely to be uneven. For example, the first volume contains fewer words while the second volume contains more words. Because simply specifying that each volume contains two letters will result in some volumes being larger than others. To distribute data evenly, partition boundaries need to be adjusted based on the data.

Partition boundaries can be selected manually by the administrator or automatically by the database.

3.1.1 Partitioning by key hash

Due to the risk of skew and hot spots, many distributed data stores use hash functions to determine partitioning for a given key.

A good hash function distributes the skewed data evenly, and by choosing the right key hash function, you can assign a hash range (not the key range) to each partition, as shown in the following figure:

Note: Partitioning with a Key hash removes a nice property of Key range partitioning: the ability to perform range queries efficiently. Keys that were once adjacent are now scattered across all partitions, so the order between them is lost.

3.1.2 Load Tilting and Hotspot elimination

“Current data systems cannot automatically detect and compensate for tilted workloads and need to be automatically adjusted.”

An easy way to do this is to add a random number at the beginning or end of the primary key. Just a random two-digit decimal number can split the primary key into 100 different primary keys, which can be stored in different partitions.

Note: After splitting the primary key, any read must do additional work, so it must also read from the 100 primary key distribution and merge it.

4. Partitioning and secondary indexes

Secondary indexes are the foundation of relational databases and are common in document databases. Many key-value stores (such as HBase and Volde-Mort) have abandoned secondary indexes to reduce implementation complexity, but some (such as Riak) have started adding them because they are so useful to the data model.

The problem with sub-indexes is that they do not map neatly to partitions. There are two ways to partition a database with secondary indexes: document-based partitioning and keyword based partitioning.

4.1 Partitioning based on the secondary index of the document

Each list has a unique ID — called a document ID — and the database is partitioned with the document ID. Partition based on secondary index of document:

• In this indexing approach, each partition is completely independent
• Each partition maintains its own secondary index, covering only the documents in that partition. It doesn’t care about data stored in other partitions
• Writing to the database (adding, deleting, or updating documents) requires only the partition containing the ID of the document being written
• Queries need to be sent to all partitions and all returned results consolidated

4.2 Partitioning based on keyword (Term) secondary index

Instead of creating its own sub-index (local index) for each partition, you can build a global index that covers all partition data.

Note: You cannot store this index on just one node, as it can become a bottleneck and defeat the purpose of partitioning. Global indexes must also be partitioned, but they can be partitioned differently than primary keys.

Advantages: It is more efficient to read, there is no need to scatter/collect all partitions, and the client only contains the keyword partition to make requests

Disadvantages: Writing is slow because writing a single document may affect multiple partitions of the index

5. Partition rebalancing

Databases change over time

• Query throughput increases, so more cpus need to be added to handle the load
• The data set size increases, so more disks and RAM need to be added to store it
• When the machine fails, other machines need to take over the responsibility of the faulty machine

All of these changes require data and requests to move from one node to another. The process of moving load from one node in a cluster to another is called rebalancing.

No matter which partitioning scheme is used, rebalancing usually meets some minimum requirements:

• After rebalancing, the load should be fairly shared among the nodes in the cluster
• When rebalancing occurs, the database should continue to receive reads and writes
• Only necessary data is moved between nodes for quick rebalancing and to reduce network and disk I/O load

5.1 Balance Policy

** Hash mod N ** : Advantages are simple to implement; The downside is that this approach makes rebalancing too expensive

Fixed number of partitions:

• Create more partitions than nodes and assign multiple partitions to each node. For example, a database running on a 10-node cluster might be split into 1000 partitions from the start, so about 100 partitions are assigned to each node.
• If a node is added to the cluster, the new node can steal some partitions from each of the current nodes until the partitions are equally divided again.

Dynamic partitioning:

• For databases that use key range partitioning, a fixed number of partitions with fixed boundaries can be inconvenient. “If a boundary error occurs, it can cause all data in one partition or all data in the other partition to be empty.” Manually reconfiguring partition boundaries can be tedious.
• Partitions are created dynamically for databases that are partitioned within the range of keys. When a partition grows beyond its configured size, it is split into two partitions, each containing about half of the data. In contrast, if a large amount of data is deleted and the partition shrinks below a certain threshold, it can be merged with adjacent partitions.

Partition by node proportion:

• Make the number of partitions proportional to the number of nodes — each node has a fixed number of partitions. In this case, the size of each partition grows proportionately to the size of the dataset while the number of nodes remains the same, but as the number of nodes increases, the partition becomes smaller again.

5.2 OPERATION and maintenance: Manual or automatic balancing

• Fully automated rebalancing: The system automatically decides when to move partitions from one node to another
• Fully manual: A partition is assigned to a node administrator for explicit configuration and will only change if the administrator explicitly reconfigures it

“Having someone involved in the rebalancing process is a good thing. It’s slower than a fully automated process, but it helps prevent operational contingencies.”

6. Ask for directions

Now split the data set across multiple nodes running on multiple machines. But there is still an unresolved problem: how do you know which node to connect to when a customer wants to make a request?

There are three mature solutions:

• Allow clients to request any node. If the node happens to own the partition of the request, it can process the request directly; Otherwise, it forwards the request to the appropriate node, receives the reply and passes it on to the client
• All requests from the client are first sent to the routing layer, which determines which node should process the request and forwards it accordingly. The routing layer itself does not process any requests; It is only responsible for the load balancing of partitions
• Clients are required to know partition and node allocations. In this case, the client can connect directly to the appropriate node without any mediation

7.

Probably the most procrastination-free month ever

• There is no denying that life has sapped some of our courage and gentleness. But I also believe that because we are so young, what we have lost will grow back, and the new will surely shine.

• Look at all the girls in the world

  Some are working hard for the offer of a prestigious university

  Some are working into the early hours of the morning on their own career development

  Some are preparing three meals a day for their spouses and children

  I also worked hard to improve my body by exercising, sweating and limiting myself to eating healthy food

  But either way, they’re beautiful girls

Writing while thinking should be a good progress, don’t hurry to walk slowly, but also walk steadily.