ТЕХНИЧЕСКОЕ ЗАДАНИЕ: Реализовать data locality scheduler

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

Разработать прототип планировщика (scheduler) для распределённой вычислительной системы, который размещает задачи на узлах, уже хранящих необходимые данные (data locality). Реализовать симуляцию кластера, где данные реплицированы на нескольких узлах, а scheduler выбирает узел с минимальной стоимостью передачи данных. Ключевой результат — снижение объёма сетевого трафика, связанного с перемещением данных, не менее чем на 50% по сравнению со случайным планированием.

Ключевой результат Прототип scheduler’а, который в симуляции (10 узлов, 100 задач, репликация 2–3 копий) показывает снижение сетевого трафика ≥50% относительно baseline‑алгоритма (random placement).

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

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

1. Создать класс ClusterNode с полями: id, data_shards (список имён шардов на узле), available_cpus, network_bandwidth (усл. ед./сек).
2. Создать класс Scheduler с методом schedule(task, data_shard_name), возвращающим node_id.
3. Для симуляции запуска задач использовать событийный цикл: в каждый момент времени узел обрабатывает задачу, занимая ресурсы, а по завершению освобождает.
4. Сетевой трафик засчитывать, если задача выполняется не на том узле, где находятся данные (т.е. данные пришлось передавать). Можно упрощённо: трафик = размер шарда (константа), если узел не владеет локальной копией.

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

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

Этап 1: Проектирование симулятора (2–3 часа)

Действия

1. Определить сущности

   • Узел (Node): id, доступные CPU, список локальных шардов.
   • Шард (Shard): имя, размер (усл. единица), узлы-владельцы.
   • Задача (Task): id, имя требуемого шарда, длительность CPU time, момент поступления.

2. Реализовать класс Cluster

   • Создать N узлов (например, 10).
   • Создать M шардов (например, 50), размер каждого 1 ед.
   • Распределить шарды по узлам: для каждого шарда выбрать R=2–3 узла случайно (или детерминированно). Гарантировать, что каждый шард присутствует хотя бы на одном узле.

3. Реализовать базовый генератор задач

   • Задачи поступают согласно Poisson‑процессу (например, λ=2 задачи/сек) или просто фиксированный список из 100 задач.
   • Каждая задача выбирает случайный шард (можно с неравномерным распределением, например, 20% шардов получают 80% задач — Zipf).

4. Реализовать метрику сетевого трафика

   • Если задача выполняется на узле, не содержащем требуемый шард, засчитать трафик = размер шарда (1 ед.) плюс возможная задержка.
   • По окончании симуляции вывести суммарный переданный объём и среднюю загрузку узлов.

Ожидаемый результат этапа Работающий симулятор кластера, который умеет запускать задачи наугад (random placement) и выводить метрики трафика.

Этап 2: Реализация random placement (baseline) (30–60 минут)

Действия

1. Создать класс RandomScheduler с методом schedule(task, cluster):

   • Выбрать случайный узел (из всех, не проверяя локальность данных).
   • Можно добавить проверку на занятость; если случайный узел занят — выбрать другой случайный (с ограниченным числом попыток).

2. Прогнать симуляцию с random scheduler’ом:

   • Запустить 10 симуляций с разными seed, получить средний объём трафика.
   • Построить график: номер задачи vs накопленный трафик.

3. Зафиксировать baseline:

   • Сохранить результат (например, baseline_traffic_mean = X).

Ожидаемый результат этапа Числовое значение среднего трафика для random placement (baseline).

Этап 3: Разработка data locality scheduler (3–4 часа)

Действия

1. Реализовать DataLocalityScheduler

   • При поступлении задачи определяет требуемый шард.
   • Находит все узлы, на которых есть локальная копия этого шарда.
   • Если есть хотя бы один такой узел: выбирает узел с наименьшей текущей загрузкой (например, длина очереди задач или свободные CPU).
   • Если таких узлов нет (редкая ситуация при отказе реплик) — выбирает узел, где меньше всего передаваемых данных (т.е. ближайший по сетевой топологии). Для простоты: расстояние = 1, если шард есть; 10, если нет.

2. Учесть репликацию и балансировку:

   • Дополнительно можно ввести кэширование: после выполнения задачи на узле, если там не было шарда, можно (опционально) оставить копию на время (LRU). Это выходит за рамки ТЗ, но можно как усложнение.

3. Реализовать класс SimulationRunner:

   • Принимает scheduler, список задач, кластер.
   • Запускает симуляцию событий (по времени) с использованием asyncio.sleep или simpy.
   • Собирает метрики: по каждой задаче — узел выполнения, локальность (True/False), переданный трафик.

4. Провести эксперимент:

   • Сравнить трафик DataLocalityScheduler с baseline на тех же сценариях и seed.
   • Построить график и посчитать процент снижения.

Ожидаемый результат этапа Функция run_simulation(scheduler, tasks, cluster), возвращающая словарь метрик, и значение % снижения трафика.

Этап 4: Анализ и визуализация (1–2 часа)

Действия

1. Собрать статистику по 20 запускам с разными seed:

   • Средний трафик, медиана, min/max.
   • Процент задач, выполненных локально (data‑local hit ratio).

2. Построить графики:

   • Boxplot сравнения трафика для random vs data locality.
   • Cumulative traffic over tasks.
   • Распределение загрузки узлов (чтобы показать, что не возникло дисбаланса).

3. Составить краткий отчёт:

   • Таблица с основными метриками.
   • Вывод: достигнуто ли снижение ≥50%?

Ожидаемый результат этапа Jupyter Notebook (или скрипт, генерирующий png) с графиками и выводами.

Этап 5: Покрытие тестами и фиксация (1 час)

Действия

1. Написать unit‑тесты:

   • test_data_locality_chooses_local_node_if_available().
   • test_random_scheduler_does_not_guarantee_locality().
   • test_traffic_counting_correct().
   • test_simulation_runs_with_given_tasks().

2. Проверить корректность метрик:

   • Вручную рассчитать трафик для двух задач и убедиться, что симулятор считает правильно.

3. Зафиксировать код в репозитории (README с инструкцией по запуску).

Ожидаемый результат этапа Набор тестов (pytest) и документация.

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

• Симулятор поддерживает произвольное число узлов, шардов и реплик (задаётся в конфиге).
• Random scheduler — полностью работоспособен и даёт baseline трафика.
• Data locality scheduler выбирает узел с локальными данными, если это возможно, иначе минимизирует перенос.
• В симуляции (10 узлов, 50 шардов, репликация 3, 100 задач) data locality scheduler снижает общий трафик на ≥50% относительно random.
• Написаны минимум 3 unit‑теста.
• Результаты визуализированы (графики).
• README содержит описание алгоритмов, запуск и пример вывода.

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

Основной артефакт Python‑пакет (один модуль или несколько) с классами Cluster, Task, RandomScheduler, DataLocalityScheduler, SimulationRunner.

Содержание

• cluster.py — модели узлов и шардов.
• schedulers.py — реализации планировщиков.
• simulation.py — симулятор, сбор метрик.
• analysis.ipynb или analyze.py — анализ и графики.
• tests/ — тесты.

Дополнительно

• Скриншот графика, подтверждающий снижение трафика.
• Краткий отчет (PDF/Markdown) с метриками.

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

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

Примечание: время дано для первого выполнения. При наличии опыта с simpy или asyncio — сокращается до 6–8 ч.

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

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

• Я реализовал симулятор, который можно запустить одной командой (python simulate.py).
• Random scheduler и data locality scheduler используют одинаковые сценарии (seed) для честного сравнения.
• Я проверил, что data‑local scheduler не выбирает узел без данных, если есть доступный узел с данными.
• Я построил хотя бы один график, наглядно показывающий снижение трафика.
• Я написал 3 unit‑теста, и они проходят.