Data locality

Data locality (с англ. — «локальность данных») — это принцип организации вычислений и хранения данных, при котором обработка данных производится как можно ближе к месту их физического размещения, с целью минимизации задержек доступа и снижения объёмов сетевого трафика. В широком смысле термин относится к парадигме распределённых систем, где перемещение вычислительных задач к данным считается более эффективным, чем перемещение самих данных к вычислительным узлам.

Основные концепции

Принцип локальности

В основе Data locality лежит фундаментальное наблюдение: время, затрачиваемое на передачу данных по сети, часто на порядки превосходит время, необходимое для их обработки. В классических архитектурах «клиент-сервер» данные хранятся централизованно, а вычисления выполняются на удалённых узлах, что приводит к значительным задержкам. Data locality предлагает инвертировать эту логику: вычислительный код отправляется к узлам хранения данных, а не наоборот.

Типы локальности

В контексте распределённых систем выделяют несколько уровней Data locality:

• Локальность на уровне узла — данные и вычисления находятся на одном физическом сервере (или виртуальной машине). Это наиболее эффективный сценарий, так как доступ к данным осуществляется через локальную файловую систему или оперативную память.
• Локальность на уровне стойки — данные и вычисления находятся в разных серверах, но в пределах одной стойки (или группы стоек), соединённых высокоскоростной сетью (например, InfiniBand). Задержки доступа здесь минимальны, но всё же выше, чем при локальности на узле.
• Локальность на уровне кластера — данные и вычисления находятся в разных стойках, но в пределах одного дата-центра. Задержки возрастают, но остаются приемлемыми для большинства задач.
• Удалённая локальность — данные и вычисления находятся в разных дата-центрах или географических регионах. Этот сценарий считается наименее эффективным и применяется только в крайних случаях (например, при репликации данных для отказоустойчивости).

История

Ранние вычислительные системы

В эпоху мейнфреймов (1950–1970-е годы) проблема Data locality не стояла остро, так как все вычисления и данные находились на одном центральном компьютере. Пользователи подключались к нему через терминалы, но вся обработка выполнялась централизованно.

Появление распределённых систем

С развитием локальных сетей и персональных компьютеров в 1980-х годах возникла необходимость в распределённых вычислениях. Первые попытки реализовать Data locality были предприняты в рамках проектов по созданию параллельных файловых систем (например, IBM GPFS, позже — Lustre). Однако массовое распространение принцип получил только в начале 2000-х годов с появлением архитектуры MapReduce, предложенной Google.

Эпоха больших данных

В 2004 году Google опубликовала статью о MapReduce, где впервые была явно сформулирована идея «перемещения вычислений к данным». Apache Hadoop, открытая реализация этой парадигмы, сделала Data locality центральным принципом своей работы. В Hadoop NameNode (управляющий узел) хранит метаданные о расположении блоков данных, а JobTracker (планировщик задач) старается назначить вычислительные задачи на те узлы, где находятся обрабатываемые блоки. Если это невозможно, задача назначается на узел в той же стойке, и только в крайнем случае — на удалённый узел.

Реализация в современных системах

Apache Hadoop

В Hadoop Data locality реализуется через механизм DataNode и TaskTracker (в версиях до 2.x) или YARN (в версиях 2.x и выше). При запуске MapReduce-задачи:

1. Планировщик (ResourceManager) получает список блоков данных, необходимых для обработки.
2. Он проверяет, на каких узлах (DataNode) эти блоки находятся.
3. Если на одном из этих узлов есть свободные ресурсы (контейнеры), задача назначается именно туда.
4. Если нет — задача назначается на узел в той же стойке (сетевая локальность).
5. В последнюю очередь — на удалённый узел.

Apache Spark

Spark, в отличие от Hadoop, работает в основном в оперативной памяти, что делает Data locality ещё более критичной. В Spark используется понятие RDD (Resilient Distributed Dataset), который хранит данные в разделах (partitions). Планировщик Spark (DAGScheduler) при выполнении трансформаций старается назначить задачи на узлы, где находятся соответствующие разделы RDD. Для этого Spark поддерживает информацию о местоположении каждого раздела через метаданные из HDFS или других систем хранения.

Системы управления базами данных (СУБД)

В распределённых СУБД (например, Google Spanner, CockroachDB, Greenplum) Data locality реализуется через шардирование — разбиение таблиц на части (шарды), которые размещаются на разных узлах. Запросы, обращающиеся к данным, обрабатываются на узлах, где эти шарды находятся. В Greenplum, например, используется механизм segment-level parallelism, где каждый сегментный узел хранит часть данных и обрабатывает запросы только к своей части.

Облачные вычисления

В облачных платформах (Amazon AWS, Microsoft Azure, Google Cloud) Data locality реализуется через аффинность — привязку виртуальных машин или контейнеров к конкретным зонам доступности или регионам. Например, в AWS EMR (Elastic MapReduce) можно указать, что задачи должны выполняться в той же зоне доступности, где находятся данные в S3. В Kubernetes для этого используются pod affinity и node affinity — правила, которые заставляют планировщик размещать поды на узлах, где уже есть необходимые данные.

Преимущества и недостатки

Преимущества

• Снижение задержек — доступ к данным через локальную шину или сеть внутри стойки на порядки быстрее, чем через глобальную сеть.
• Экономия пропускной способности — сокращение объёмов сетевого трафика между узлами, что особенно важно в условиях ограниченной пропускной способности.
• Повышение отказоустойчивости — при отказе одного узла данные не теряются, так как они реплицированы на другие узлы в той же стойке или кластере.
• Упрощение масштабирования — добавление новых узлов не требует перераспределения данных по всей системе, достаточно скопировать данные на новый узел.

Недостатки

• Сложность реализации — требует точного учёта местоположения данных и динамического планирования задач.
• Неравномерность загрузки — если данные распределены неравномерно, некоторые узлы могут быть перегружены, а другие простаивать.
• Ограничения на перемещение данных — в некоторых сценариях (например, при агрегации данных из разных источников) Data locality может быть неэффективна, так как данные всё равно приходится перемещать.
• Зависимость от топологии сети — эффективность Data locality сильно зависит от физической структуры сети (стойки, коммутаторы, маршрутизаторы).

Критика и альтернативы

Критика

Критики Data locality указывают на то, что в современных системах с высокоскоростными сетями (100 Гбит/с и выше) и быстрыми SSD-накопителями разница между локальным и удалённым доступом становится менее значимой. Кроме того, в условиях динамического масштабирования облачных сред (например, при использовании serverless-функций) точное знание местоположения данных может быть недоступно.

Альтернативы

В качестве альтернативы Data locality иногда предлагается data shipping — перемещение данных к вычислительным узлам. Этот подход используется в системах реального времени (например, Apache Kafka Streams), где данные непрерывно поступают на узлы обработки, а не хранятся статически. Другой альтернативой является computation shipping — выполнение вычислений на удалённых узлах, но с кэшированием часто используемых данных локально (например, в Apache Ignite).

Применение

Научные вычисления

В суперкомпьютерах и кластерах для научных расчётов (например, в проектах LHC на ЦЕРНе) Data locality используется для обработки огромных объёмов данных, генерируемых детекторами. Данные хранятся на ленточных накопителях и HDD-массивах, а вычислительные задачи отправляются на узлы, где эти данные находятся.

Промышленная обработка данных

В системах бизнес-аналитики (BI) и ETL-процессах Data locality позволяет сократить время выполнения запросов к большим таблицам. Например, в Greenplum запросы к таблице, разбитой на шарды, выполняются параллельно на всех сегментных узлах, что даёт линейное ускорение.

Интернет вещей (IoT)

В системах IoT данные часто генерируются на периферийных устройствах (edge devices). Data locality здесь реализуется через edge computing — обработка данных непосредственно на устройстве или в ближайшем шлюзе, без передачи в облако. Это снижает задержки и уменьшает объём передаваемых данных.

Интересные факты

• В Hadoop по умолчанию используется репликация данных в три копии: две в одной стойке и одна в другой. Это позволяет достичь баланса между Data locality и отказоустойчивостью.
• В Spark существует понятие preferred locations — список узлов, на которых предпочтительно выполнять задачу. Если на этих узлах нет свободных ресурсов, задача может быть отложена на некоторое время (параметр spark.locality.wait).
• В некоторых системах (например, в Apache Flink) Data locality реализуется через stateful processing — состояние оператора хранится на том же узле, где выполняются вычисления, что позволяет избежать перемещения данных.

Источники

• Dean, J., & Ghemawat, S. (2004). MapReduce: Simplified Data Processing on Large Clusters. OSDI'04.
• Apache Hadoop Documentation. (2023). Data Locality in Hadoop.
• Zaharia, M., et al. (2010). Spark: Cluster Computing with Working Sets. HotCloud'10.
• Greenplum Database Documentation. (2022). Data Distribution and Query Processing.
• White, T. (2015). Hadoop: The Definitive Guide. O'Reilly Media.