Как определять какие данные в какой шард идут?

Как определять распределение данных по шардам

Шардирование (Sharding) — это горизонтальное партиционирование данных, при котором разные подмножества данных хранятся в разных базах данных или кластерах. Ключевая задача — правильно выбрать алгоритм, который определяет, какие данные идут в какой шард.

Основные методы шардирования

1. Range-Based Sharding (Диапазонное распределение)

Идея: разделить данные по диапазонам значения ключа.

# Пример: шардирование пользователей по ID
SHARD_MAPPING = {
    "shard_1": (0, 1_000_000),           # user_id: 0-999,999
    "shard_2": (1_000_000, 2_000_000),  # user_id: 1M-1.999M
    "shard_3": (2_000_000, 3_000_000),  # user_id: 2M-2.999M
}

def get_shard_for_user(user_id: int) -> str:
    """Определяет шард по user_id"""
    for shard_name, (min_id, max_id) in SHARD_MAPPING.items():
        if min_id <= user_id < max_id:
            return shard_name
    raise ValueError(f"User ID {user_id} out of range")

# Использование
user_id = 1_500_000
shard = get_shard_for_user(user_id)  # "shard_2"
db_connection = connect_to_shard(shard)
db_connection.query(f"INSERT INTO users (id, name) VALUES ({user_id}, 'Alice')")

Плюсы:

• Простая реализация
• Легко добавить новый диапазон

Минусы:

• Неравномерное распределение (если IDs неравномерны)
• Пример: если user_id в основном 0-100,000, весь трафик идёт в shard_1
• Сложно переконфигурировать (требует перезагрузки данных)

2. Hash-Based Sharding (Хеш-распределение)

Идея: применить хеш-функцию к ключу, результат определяет шард.

import hashlib

NUM_SHARDS = 10  # Количество шардов

def get_shard_hash(key: str) -> int:
    """Определяет шард по хеш-функции"""
    # Хешируем ключ в число
    hash_value = int(hashlib.md5(key.encode()).hexdigest(), 16)
    # Берём остаток от деления на количество шардов
    shard_id = hash_value % NUM_SHARDS
    return shard_id

# Использование
user_id = "user_12345"
shard_id = get_shard_hash(user_id)  # 7 (например)
db_connection = connect_to_shard(f"shard_{shard_id}")
db_connection.query(f"INSERT INTO users (email) VALUES ('{user_id}@example.com')")

# Распределение по шардам: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
# Примерно 1/10 пользователей в каждом шарде (равномерно)

Плюсы:

• Равномерное распределение (если хеш-функция хорошая)
• Детерминировано: one key → always same shard

Минусы:

• При добавлении шардов требуется перехеширование
• Если было 10 шардов, а стало 11, нужно перемешать ~10% всех данных

# Problem: если добавим шард
NUM_SHARDS_OLD = 10
NUM_SHARDS_NEW = 11

user_id = "user_12345"
old_shard = get_shard_hash_with_count(user_id, NUM_SHARDS_OLD)  # 7
new_shard = get_shard_hash_with_count(user_id, NUM_SHARDS_NEW)  # 3

# user_12345 нужно переместить из shard_7 в shard_3!
# Это может быть дорого при большом количестве данных

3. Consistent Hashing (Согласованное хеширование)

Идея: разместить шарды на кольце, данные распределяются по часовой стрелке.

import hashlib
from sortedcontainers import SortedDict

class ConsistentHashRing:
    def __init__(self, nodes: list, num_replicas: int = 3):
        """
        nodes: ['shard_1', 'shard_2', 'shard_3', ...]
        num_replicas: количество виртуальных копий каждого узла
        """
        self.nodes = set(nodes)
        self.num_replicas = num_replicas
        self.ring = SortedDict()
        self._build_ring()
    
    def _build_ring(self):
        """Строит hash ring"""
        for node in self.nodes:
            for i in range(self.num_replicas):
                virtual_key = f"{node}_{i}"
                hash_value = int(hashlib.md5(virtual_key.encode()).hexdigest(), 16)
                self.ring[hash_value] = node
    
    def get_node(self, key: str) -> str:
        """Находит узел для ключа"""
        hash_value = int(hashlib.md5(key.encode()).hexdigest(), 16)
        
        # Находим первый узел с хешем >= hash_value
        for ring_hash, node in self.ring.items():
            if ring_hash >= hash_value:
                return node
        
        # Если не найдено, берём первый узел (wrap around)
        return self.ring.peekitem(0)[1]
    
    def get_replicas(self, key: str, num_replicas: int = 3) -> list:
        """Находит несколько узлов для репликации"""
        replicas = []
        hash_value = int(hashlib.md5(key.encode()).hexdigest(), 16)
        
        for ring_hash in self.ring.irange(hash_value, float('inf')):
            node = self.ring[ring_hash]
            if node not in replicas:
                replicas.append(node)
            if len(replicas) == num_replicas:
                break
        
        # Если не хватает, оборачиваемся в начало
        for ring_hash in self.ring.keys():
            if self.ring[ring_hash] not in replicas:
                replicas.append(self.ring[ring_hash])
            if len(replicas) == num_replicas:
                break
        
        return replicas

# Использование
ring = ConsistentHashRing(['shard_1', 'shard_2', 'shard_3', 'shard_4'])

user_id = "user_12345"
primary_shard = ring.get_node(user_id)  # "shard_2"
replica_shards = ring.get_replicas(user_id, num_replicas=3)  # ["shard_2", "shard_3", "shard_4"]

# Добавляем новый шард
ring.nodes.add('shard_5')
ring._build_ring()

new_primary_shard = ring.get_node(user_id)  # может быть "shard_2" или "shard_5"
# При добавлении только ~1/5 ключей переместятся, не все!

Плюсы:

• При добавлении шарда переместяется только ~1/n часть данных (n = кол-во шардов)
• Хорошо работает с масштабированием

Минусы:

• Более сложная реализация
• Нужна синхронизация кольца между сервисами

Реальный пример: YouTube (Google)

YouTube использует Directory (таблица маршрутизации) + Hash:

# Simplified YouTube approach

class YoutubeShardRouter:
    def __init__(self):
        self.directory = {
            # video_id -> shard_id
            'dQw4w9WgXcQ': 'shard_uswest_1',
            'jNQXAC9IVRw': 'shard_useast_2',
            '9bZkp7q19f0': 'shard_europe_3',
            # ... миллионы записей
        }
        self.shard_count = 5  # Всего 5 больших шардов
    
    def get_shard(self, video_id: str) -> str:
        # Вариант 1: Прямая таблица (для горячих видео)
        if video_id in self.directory:
            return self.directory[video_id]
        
        # Вариант 2: Хеш для остальных
        hash_value = hash(video_id) % self.shard_count
        return f'shard_{hash_value}'

# Использование
router = YoutubeShardRouter()
video_id = 'abcdef123456'
shard = router.get_shard(video_id)  # Determines which database
db = connect_to_shard(shard)
db.query(f"INSERT INTO videos (id, title) VALUES ('{video_id}', 'My Video')")

Проблемы при шардировании

1. Hotspot (Горячая точка)

# Проблема: один шард получает больше трафика
# Пример: распределяем по country_id
# shard_1: US (millions of users) → перегружен
# shard_2: Luxembourg (thousands) → недогружен

# Решение: вложенное шардирование
SHARD_MAPPING = {
    'US': ['us_shard_1', 'us_shard_2', 'us_shard_3', ...],  # 10 шардов
    'DE': ['de_shard_1', 'de_shard_2'],  # 2 шарда
    'LU': ['lu_shard_1'],  # 1 шард
}

def get_shard(country: str, user_id: int) -> str:
    country_shards = SHARD_MAPPING[country]
    shard_index = user_id % len(country_shards)
    return country_shards[shard_index]

2. Joins между шардами

# Проблема: JOIN между данными в разных шардах

# Запрос (неэффективно):
# SELECT * FROM users
# JOIN orders ON users.id = orders.user_id
# WHERE users.country = 'US' AND orders.amount > 100

# users.country=US может быть в us_shard_1, us_shard_2, ..., us_shard_10
# orders для user X может быть в другом шарде!

# Решение: Шардировать оба по одному ключу (user_id)
def get_shard(entity_type: str, user_id: int) -> str:
    """
    Оба users и orders используют одинаковое шардирование по user_id
    """
    shard_id = user_id % NUM_SHARDS
    return f'{entity_type}_shard_{shard_id}'

# Теперь JOIN работает в одном шарде:
# - User 12345 → shard_5
# - Orders для user 12345 → тоже shard_5

Best Practices

1. Выбирайте immutable шардинг ключ

# Плохо: шардирование по user_location
# Пользователь переехал из US в DE
# Нужно перемещать все его данные!

# Хорошо: шардирование по user_id
# user_id никогда не меняется

2. Используйте consistent hashing для масштабирования

# При добавлении нового сервера нужно переместить
# только часть данных, не все

3. Документируйте схему шардирования

# Пример конфигурации
SHARDING_CONFIG = {
    "shard_key": "user_id",
    "algorithm": "hash",
    "num_shards": 10,
    "hash_function": "md5",
    "modulo": 10,
    "mapping": {
        "0": "db1.example.com:5432",
        "1": "db2.example.com:5432",
        # ...
    }
}

Вывод

Шардирование определяется выбором алгоритма:

• Range: простой, но требует внимания к распределению
• Hash: равномерно, но дорого масштабировать
• Consistent Hash: лучший баланс для масштабирования
• Directory: для сложных случаев (YouTube, Uber)

Основной принцип: выберите immutable shard key (user_id, account_id, etc), примените алгоритм, и все операции пойдут в нужный шард.