2 of 116

План

что такое шардирование
какие есть инструменты
как на практике их применить

3 of 116

Что такое шардирование

4 of 116

Деление на части

5 of 116

Shard - осколок, фрагмент

6 of 116

Происхождение термина шард, 1997, Ultima Online

7 of 116

Шардирование в БД

8 of 116

Шардирование в RabbitMQ

9 of 116

Ключ шардирования

Признак по которому объект сопоставляется с шардом

10 of 116

Функция шардирования

f(key, shardsNumber) => shardIndex

11 of 116

Функции шардирования

12 of 116

Функции шардирования

Чистые функции

остаток от деления
consistent hash
rendevouz hash

Функции с состоянием

таблица “ключ -> шард”
hash slot в redis:�shardingKey -> node -> shard

13 of 116

Чистые функции шардирования

Остаток от деления или modular hash

shardIndex = key % shardsNumber

При смене количества шардов, меняются все значения.

14 of 116

Чистые функции шардирования

Consistent hash или стабильное хеширование

15 of 116

Чистые функции шардирования

Consistent hash или стабильное хеширование

представим область значения hash() как кольцо

16 of 116

Чистые функции шардирования

Consistent hash или стабильное хеширование

представим область значения hash() как кольцо
распределяем ноды по кольцу hash($nodeName)

17 of 116

Чистые функции шардирования

Consistent hash или стабильное хеширование

представим область значения hash() как кольцо
распределяем ноды по кольцу hash($nodeName)
рассчитываем hash($shardingKey)

18 of 116

Чистые функции шардирования

Consistent hash или стабильное хеширование

представим область значения hash() как кольцо
распределяем ноды по кольцу hash($nodeName)
рассчитываем hash($shardingKey)
выбираем ближайшую ноду по часовой стрелке

19 of 116

Чистые функции шардирования

Consistent hash или стабильное хеширование

Что будет, если добавить шрад?

20 of 116

Чистые функции шардирования

Consistent hash или стабильное хеширование

Что будет, если добавить шрад?

Значение функции шардирования меняется только для части ключей

21 of 116

Чистые функции шардирования

Consistent hash или стабильное хеширование

Расположение нод случайно, поэтому требует балансировки.

22 of 116

Чистые функции шардирования

Consistent hash или стабильное хеширование

Расположение нод случайно, поэтому требует балансировки

Равномерность достигается увеличением числа нод (алиасами)

23 of 116

Чистые функции шардирования

Rendezvous Hash�или Highest Random Weight

24 of 116

Чистые функции шардирования

Rendezvous Hash�или Highest Random Weight

HRW как алгоритм вычисления rendezvous points в мультикаст маршрутизации

25 of 116

Чистые функции шардирования