Data Partitioning/Sharding
Tags: systemdesign
Published: 2023-07-26 21:18:35

Партиционирование данных это процесс разбиения большой базы данных на более маленькие части, называемые партициями или шардами. Каждая партиция независима и содержит часть данных. 

Партиционирование производится на основе некоторого критерия. Например, по диапазону данных, дате, типу данных, размеру данных и т.д.

Партиционирование и шардинг позволяют увеличить производительность и scalability приложений, которые обрабатывают большие объемы данных.

Партиционирование можно делать несколькими способами:
горизонтальным, вертикальным и гибридным способом.

## Горизонтальное партиционирование.
Горизонтальное партиционирование (или его еще называют **шардингом**) - процесс разбиения большой базы данных на шарды или партиции, в котором каждый шард содержит часть (подмножество) всех **строк (записей)**. Обычно, каждый шард рассположен на отдельном сервере. Это позволяет распараллелить обработку данных и ускорить выполнение запросов.

Например, вы разрабатываете социальную сеть и вам надо хранить информацию о большом числе пользователей. Вы можете разбить базу данных на шарды, например, на основе их географического положения. Пользователей из США в одном шарде, из Европы в другом. Это позволяет расспаралелить хранение и обработку данных. 

В таком подходе очень важно выбрать хороший критерий разбиения на шарды. Иначе могут получиться неравномерного размера шарды. Например, если мы решили разбивать данные на основе геолокации - может оказаться, что в одних регионах у нас много пользователей и много данных. В других же - мало.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sjc5eir4sqe73qewf7o8.png)



### Вертикальное партиционирование.
Вертикальное партиционирование - процесс разбиения большой базы данных на партиции, в котором каждая партиция содержит часть(подмножество) **колонок**.
Например, у нас есть некое e-commerce приложение, типа Amazon, и мы храним данные о пользователях и их покупках в одной таблице. Мы можем разбить эту таблицу на несколько партиций. В одной будем хранить персональные данные, в другой историю заказов.
Для примера про социальную сеть, мы можем исходную таблицу разбить на две. В одной хранить имя, а во второй возраст и пол. 


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r2z5c2n9fsda0lc2qdnu.png)



Такой подход также позволяет ускорить обработку данных, особенно, если одни колонки используются чаще других и мы можем сократить объем сканируемых данных.

### Гибридное партиционирование.
Гибридное партиционирование объединяет оба этих подхода. База разбивается на партиции и горизонтально и вертикально. 
Например, для примера с e-commerce приложением. Мы можем горизонтально разбить по геолокации пользователя. И вертикально по типу данных: в одной персональные данные, во второй история заказов. 

## Критерии партиционирования.
Очень важно выбрать правильный критерий для партиционирования для получения равномерного расспределения нагрузки.

### Key or Hash-based. 
Например, мы хотим разбить нашу таблицу на 100 партиций и расспределить их на разные сервера. Мы можем взять ID записи и на основе этого ID помещать запись в ту или иную партицию. Например, используя формулу: 

> номер партиции = ID % Number_of_partitions

Или же можно вычислять некую hash функцию от каких-то данных:

> номер партиции = hash(ID) % Number_of_partitions


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/hr84rrl60brwv7vyi8qd.png)

В том случае, если мы хотим добавить еще серверов, или какие-то серверы нужно удалить, или же у них случился отказ, то в таком подходе нужно все данные будет снова перераспределить между партициями. Т.к. Number_of_partitions в этой формуле изменится. Это очень долгий и сложный процесс перебалансировки. Чтобы этого не делать можно использовать подход, который называется **Consistent Hashing**, в котором используется hash-ring. Смотри мою статью про Consistent Hashing: https://telegra.ph/Consistent-Hashing-05-22. 

### List partitioning. 
Данные разбиваются на партиции на основе какого-то списка значений в какой-то колонке. Например, у нас есть колонка Country (Страна). Мы можем помещать все строки из спика Европейский стран в одну партицию, для стран Америки в другию партицию и т.д.
### Round-robin partitioning. 
Это простой подход, в котором данные распределются между N серверами по алгоритму round-robin. Первая строка попадает в первую партицию. Вторая во вторую. N в N-ю партицию. N + 1 снова в первую и т.д. Это позволяет достичь равномерного расспределения данных между партициями. Но такой подход имеет огромное число недостатков. 

### Composite Partitioning.
Этот подход объединяет несколько подходов одновременно. Например, мы можем вначале разбить данные на основе списка значений, а потом на основе hash(ID).

## Проблемы партиционирования.
В силу того, что после разбивания данных на партиции, которые зачастую рассположены на разных серверах, некоторые операции с данными становятся более проблематичными.

### Joins and Denormalization
Если мы захотим заджойнить данные, которые рассположены в разных партициях, на разных серверах, то такая операция может оказаться или невозможной или очень проблематичной. Поэтому для избегания такий джойнов можно денормализовать данные. Т.е. поместить данные в одну таблицу уже сджойненными. Тогда джойн уже не будет нужен.

### Referential integrity
Если у нас в партиционированной таблице есть foreing keys, которые указывают на записи в другой таблице, то получить Referential integrity будет сложно или невозможно. Большинство RDBMS не поддерживают такого типа констрейнты если базы рассположены на разных серверах. Допустим, если из нашей таблицы мы ссылаемся на запись в другой таблице на другом сервере. То, если в этой другой таблице на другом сервере будет удалена запись, на которую мы ссылаемся, то наша запись не будет автоматически удалена или изменена. Нам нужно будет это делать в коде нашего приложения или периодически запускать скрипты, которые будут обрабатывать такие случаи.

### Rebalancing
Например, мы выбрали не очень удачную функцию или критерий для разбиения данных на партиции. Это может привести к тому, что у нас одни партиции будут больше других и данные не будут расспределены равномерно. И/или у нас нагрузка запросов на одни партиции больше, чем на другие. В таком случае нам нужно будет перебалансировать данные. Т.е. перераспределить их между партициями используя другой критерий. Если у нас очень много данных и нам нельзя допустить существенный down-time нашего приложения, то эта операция становится очень сложной для исполнения.