ТЕХНИЧЕСКОЕ ЗАДАНИЕ: Реализовать sharded cache на 10+ нод

1. Цель задачи

Разработать распределённый кэш-уровень с шардированием данных на основе consistent hashing по user_id, обеспечивающий горизонтальное масштабирование до 1 ТБ кэшируемых данных. В результате участник получит работающий прототип кэш-кластера минимум из 10 логических нод, способный корректно перераспределять данные при добавлении/удалении узлов с минимальным перемещением ключей (не более K/N ключей, где K – общее количество ключей, N – количество нод).
Ключевой результат Рабочий sharded cache на consistent hashing с виртуальными узлами (virtual nodes), клиентский API (get, set, delete), тесты масштабирования до 1 ТБ.

2. Исходные данные

Если нет реального кластера — симулируем:

1. Развернуть 10+ нод как отдельные процессы на localhost (разные порты) с помощью multiprocessing.Process.
2. Каждый процесс хранит данные в dict (in-memory).
3. Взаимодействие через TCP (сокеты или aiohttp).
4. Для теста масштабирования до 1 ТБ использовать синтетические данные: JSON-объекты среднего размера (1 КБ каждый) и симулировать 1 млрд записей (не храня все в памяти сразу, а проверять только распределение ключей и пропускную способность).

3. Технологический стек

4. Этапы выполнения

Этап 1: Проектирование архитектуры (30 минут)

Действия

1. Спроектировать consistent hashing ring:
   • Определить диапазон хэшей: [0, 2^160 - 1] (SHA-1 или MD5 128 бит, но можно взять 64-битный хэш для простоты)
   • Для каждой ноды создать VN виртуальных узлов (рекомендуется VN=160 для равномерности).
   • Каждый виртуальный узел добавляется в кольцо как точка с координатой hash(node_id + ":" + vnode_index).
   • Хранить отсортированный список всех точек.
2. Определить протокол взаимодействия между клиентом и нодами:
   • Клиент вычисляет хэш user_id и находит ближайшую точку (первый виртуальный узел по часовой стрелке).
   • Клиент подключается к физической ноде, которой принадлежит этот виртуальный узел.
   • Команды: SET <key> <value>, GET <key>, DELETE <key>.
3. Определить механизм обработки добавления/удаления нод:
   • При добавлении: новая нода со своими VN встаёт в кольцо; часть ключей, хэши которых попадают в интервал между её VN и предыдущими, переходят на неё.
   • При удалении: ключи, принадлежавшие удалённой ноде, переходят к следующей ноде.
4. Набросать схему классов: ConsistentHashRing, CacheNode, ShardedCacheClient.

Ожидаемый результат этапа Документ с описанием архитектуры (можно в виде диаграммы Mermaid) и псевдокодом.

Этап 2: Реализация consistent hashing ring (2 часа)

Действия

1. Реализовать класс ConsistentHashRing:
   • Метод __init__(self, vnodes_per_node=160)
   • Метод add_node(node_id: str) – генерирует VN и вставляет их в кольцо (sorted list).
   • Метод remove_node(node_id: str) – удаляет все VN этой ноды.
   • Метод get_node(key: str) -> str – вычисляет хэш ключа, находит в кольце ближайшую точку (бинарный поиск), возвращает node_id.
2. Хэш-функция: hash = int(hashlib.md5(key.encode()).hexdigest(), 16) >> 2 (28-битный хэш для ускорения, или полный 128-бит – по желанию).
3. Сохранять кольцо как отсортированный список кортежей (hash_value, node_id).
4. Написать юнит-тесты:
   • Проверить, что для одного ключа всегда возвращается одна и та же нода.
   • При добавлении новой ноды проверяется, что доля перемещённых ключей ≤ (1/N + 5%).
   • При удалении – аналогично.

# Пример реализации части кольца (неполный код)
class ConsistentHashRing:
    def __init__(self, vnodes=160):
        self.vnodes = vnodes
        self.ring = []  # list of (hash, node_id)
        self.node_map = {}  # node_id -> list of hashes

    def _hash(self, data: str) -> int:
        return int(hashlib.md5(data.encode()).hexdigest(), 16)

    def add_node(self, node_id: str):
        for i in range(self.vnodes):
            vnode_key = f"{node_id}:{i}"
            h = self._hash(vnode_key)
            self.ring.append((h, node_id))
        self.ring.sort(key=lambda x: x[0])
        self.node_map[node_id] = [self._hash(f"{node_id}:{i}") for i in range(self.vnodes)]

    def get_node(self, key: str) -> str:
        if not self.ring:
            return None
        h = self._hash(key)
        # binary search (bisect)
        import bisect
        idx = bisect.bisect_left(self.ring, (h, None)) % len(self.ring)
        return self.ring[idx][1]

Ожидаемый результат этапа Рабочий класс ConsistentHashRing, проходящий тесты (доля перемещённых ключей < 1/N + допуск).

Этап 3: Реализация кэш-ноды и клиента (3 часа)

Действия

1. Реализовать CacheNode как asyncio-сервер (aiohttp) на отдельном порту:
   • Хранит данные в dict (ограничение памяти можно не ставить, но для теста 1 ТБ нужно снять статистику).
   • Обрабатывает GET, SET, DELETE через REST-like эндпоинты: GET /cache/<key>, POST /cache/<key> с телом value, DELETE /cache/<key>.
   • Возвращает статус и данные.
2. Реализовать ShardedCacheClient:
   • При инициализации получает список всех нод (node_id -> host:port) и ConsistentHashRing.
   • Методы get(key), set(key, value), delete(key) – определяют нужную ноду через ring.get_node(key) и отправляют запрос через aiohttp.ClientSession.
3. Написать скрипт для запуска кластера:
   • Создать 10 нод на портах 9001..9010.
   • Добавить все ноды в клиентский ring.
   • Запустить asyncio event loop с тестовыми операциями.

# Пример запуска ноды (asyncio)
async def run_node(node_id, port):
    app = web.Application()
    cache = {}
    async def get_handler(request):
        key = request.match_info['key']
        val = cache.get(key)
        if val is None:
            return web.Response(status=404)
        return web.Response(text=val)
    async def set_handler(request):
        key = request.match_info['key']
        val = await request.text()
        cache[key] = val
        return web.Response(status=200)
    app.router.add_get('/cache/{key}', get_handler)
    app.router.add_post('/cache/{key}', set_handler)
    runner = web.AppRunner(app)
    await runner.setup()
    site = web.TCPSite(runner, 'localhost', port)
    await site.start()
    print(f"Node {node_id} started on port {port}")
    # keep running
    await asyncio.Event().wait()

Ожидаемый результат этапа Запущенный кластер из 10 нод, клиент может выполнять get/set/delete, данные хранятся только на правильной ноде (проверить прямым запросом к другой ноде – должен быть 404).

Этап 4: Тестирование масштабирования и отказоустойчивости (2 часа)

Действия

1. Тест равномерности распределения:
   • Сгенерировать 1 млн случайных user_id, записать их в кэш, затем подсчитать количество ключей на каждой ноде.
   • Коэффициент дисбаланса = max/avg. Должен быть < 1.5.
2. Тест добавления ноды:
   • Запустить 11-ю ноду.
   • Добавить её в ConsistentHashRing и в клиент.
   • Проверить, что только ~1/11 часть ключей (допустимый разброс ±5%) оказалась на новой ноде, а остальные остались на старых.
   • Проверить, что все ключи доступны через клиент после добавления.
3. Тест удаления ноды:
   • Удалить одну ноду из кольца.
   • Проверить, что ключи, принадлежавшие удалённой ноде, теперь обслуживаются другой (следующей) нодой и доступны.
   • Замерить downtime (время перестройки кольца).
4. Нагрузочный тест до 1 ТБ симуляции:
   • Поскольку 1 ТБ в памяти не поместится, оценить throughput и latency при большом количестве ключей.
   • Создать 100 млн ключей (1 КБ значения) – всего ~100 ГБ (можно на нескольких машинах или с дисковым кэшем).
   • Измерить set и get latency (p50, p99). Ожидаемая p50 < 5ms при условии локальной сети.
   • Оценить, хватит ли 10 нод по 100 ГБ памяти каждая для хранения 1 ТБ (да, 10x100 = 1 ТБ).
   • Проверить, что при равномерном распределении каждая нода получает ~10% ключей.

Ожидаемый результат этапа Отчёт с метриками: дисбаланс, процент перемещённых ключей при решардинге, latencies, подтверждение масштабирования до 1 ТБ.

Этап 5: Оптимизация и документация (1.5 часа)

Действия

1. Оптимизировать бинарный поиск в кольце (можно использовать bisect).
2. Реализовать поддержку виртуальных узлов с возможностью менять количество.
3. Написать README.md с инструкцией по запуску, описанием API и примером использования.
4. Добавить тесты на отказоустойчивость (проверка, что при временном недоступе одной ноды клиент не падает, а возвращает ошибку или редиректит).
5. (Опционально) Реализовать механизм репликации – primary/secondary для надёжности.

Ожидаемый результат этапа Полный код с модульной структурой, документация, тесты, отчёт.

5. Критерии приемки (Definition of Done)

• Consistent hashing ring реализован с виртуальными узлами, количество VN настраивается.
• При добавлении одной ноды на кластер из 10 нод доля перемещённых ключей не превышает 12% (1/10 + 2%).
• При удалении ноды все её ключи становятся доступными на соседней ноде (время перестройки < 1 сек).
• Распределение ключей по 10 нодам близко к равномерному (коэффициент дисбаланса < 1.5).
• Клиентское API поддерживает get, set, delete с корректной маршрутизацией по user_id.
• Нагрузочный тест показывает среднюю задержку get < 5 мс (для операции в локальной сети) при 1 000 rps.
• В документации описана процедура запуска кластера и клиента, а также результаты тестов.
• Код покрыт юнит-тестами на consistent hashing и интеграционными тестами на решардинг.

6. Ожидаемый результат

Основной результат

• Репозиторий с кодом, содержащий модули: consistent_hash.py, cache_node.py, cache_client.py, cluster_manager.py.
• Файл demo.py, который запускает кластер из 10+ нод, выполняет серию операций и выводит статистику распределения.
• Отчёт test_report.md с результатами тестов (равномерность, решардинг, latency).

Опционально (для углубления):

• Поддержка репликации (каждому ключу соответствует primary и 1-2 реплики).
• Экспорт метрик в Prometheus.
• Реализация graceful shutdown с перераспределением данных.

7. Возможные сложности и их решение

8. Бюджет времени (оценка)

Примечание: Для первого выполнения рекомендуется заложить 10–12 часов с учётом отладки.

9. Связанные вопросы из базы знаний

10. Чек-лист самопроверки

• Я реализовал consistent hashing с виртуальными узлами и убедился, что при добавлении/удалении ноды переезжает не более 1/N + 10% ключей.
• Я написал тесты, доказывающие равномерное распределение (коэффициент дисбаланса < 1.5).
• Мой клиент корректно маршрутизирует запросы по user_id и возвращает данные только с нужной ноды.
• Я провёл нагрузочный тест и получил latency p50 < 5 мс для get на кластере из 10 нод.
• Я задокументировал процедуру запуска, описал API и приложил результаты тестирования.