Фрагментация данных¶

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

¶Причины возникновения

¶Фрагментация в файловых системах

В файловых системах фрагментация возникает при многократных операциях записи, удаления и изменения размера файлов. Когда файл удаляется, освобождаемое пространство становится разрозненным. При создании нового файла или расширении существующего операционная система вынуждена размещать его данные в нескольких несмежных областях диска, если непрерывного блока нужного размера нет. Этот процесс называется внешней фрагментацией. Внутренняя фрагментация возникает, когда файловая система выделяет под файл блоки фиксированного размера (кластеры), и последний блок используется не полностью.

¶Фрагментация в оперативной памяти

В операционных системах, использующих сегментную или страничную организацию памяти, фрагментация возникает при динамическом выделении и освобождении памяти процессами. Внешняя фрагментация в памяти — это появление множества небольших свободных участков, которые в сумме достаточны для размещения нового процесса, но не могут быть использованы из-за своей разрозненности. Внутренняя фрагментация в страничной памяти — это неиспользуемая часть последней страницы, выделенной процессу.

¶Фрагментация в базах данных

В системах управления базами данных (СУБД) фрагментация может быть как нежелательным явлением (например, фрагментация индексов или таблиц при частых операциях вставки и удаления записей), так и целенаправленной стратегией (см. раздел «Преднамеренная фрагментация»).

¶Виды фрагментации

¶По природе возникновения

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

¶По объекту фрагментации

• Фрагментация файлов — части одного файла располагаются в разных, не смежных областях носителя.
• Фрагментация свободного пространства — разрозненность свободных областей на диске.
• Фрагментация индексов — в базах данных индексы теряют упорядоченность страниц, что замедляет поиск.
• Фрагментация таблиц — строки таблицы физически располагаются не в порядке первичного ключа или кластеризованного индекса.

¶Последствия фрагментации

¶Отрицательные последствия

• Снижение производительности ввода-вывода. Для чтения фрагментированного файла головке жёсткого диска (HDD) приходится совершать множество перемещений, что увеличивает время доступа. В системах с твердотельными накопителями (SSD) влияние фрагментации на скорость чтения менее выражено, но может снижать эффективность записи и сборки мусора.
• Увеличение накладных расходов. Файловая система тратит больше ресурсов на управление метаданными, отслеживающими расположение фрагментов.
• Усложнение резервного копирования и восстановления. Фрагментированные данные могут требовать больше времени для чтения и обработки.
• Риск потери данных. В случае сбоя системы восстановить фрагментированный файл сложнее, чем непрерывный.

¶Положительные последствия (при преднамеренном использовании)

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

¶Преднамеренная фрагментация (шардирование и партиционирование)

В современных системах управления базами данных и распределённых хранилищах фрагментация применяется как архитектурное решение.

¶Вертикальная фрагментация

Разделение таблицы на несколько таблиц с меньшим количеством столбцов. Каждая новая таблица содержит подмножество атрибутов исходной, связанных через первичный ключ. Применяется для разделения часто и редко запрашиваемых данных, а также для повышения безопасности.

¶Горизонтальная фрагментация (шардирование)

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

¶Гибридная фрагментация

Комбинация вертикального и горизонтального разделения, когда сначала таблица делится по столбцам, а затем полученные части — по строкам.

¶Методы борьбы с фрагментацией

¶Дефрагментация

Процесс обратный фрагментации — перераспределение данных на носителе таким образом, чтобы файлы и свободное пространство стали непрерывными. В файловых системах Windows (NTFS) и Linux (ext4, XFS) существуют встроенные утилиты дефрагментации (например, defrag в Windows, e4defrag в Linux). Для SSD-накопителей дефрагментация традиционно не рекомендуется из-за ограниченного числа циклов перезаписи и особенностей работы контроллера, однако современные операционные системы могут выполнять оптимизацию, не приводящую к износу.

¶Компактификация (сборка мусора)

В системах управления памятью (например, в среде CLR .NET или JVM Java) компактификация — это процесс перемещения живых объектов в непрерывную область памяти, устраняющий фрагментацию кучи. В SSD-накопителях сборка мусора (garbage collection) выполняется контроллером для освобождения и объединения блоков, помеченных как удалённые.

¶Оптимизация запросов и структуры данных

В СУБД для предотвращения фрагментации индексов и таблиц применяются:

• Регулярное перестроение (rebuild) и реорганизация (reorganize) индексов.
• Использование кластеризованных индексов с монотонно возрастающими ключами.
• Настройка коэффициента заполнения (fill factor) для страниц индекса.

¶Фрагментация в распределённых системах

В распределённых файловых системах (например, HDFS, Ceph) и объектных хранилищах (Amazon S3, Яндекс Объектное хранилище) фрагментация является основой архитектуры. Файл разбивается на блоки фиксированного размера (обычно 64–128 МБ), которые реплицируются на разные узлы кластера. Это позволяет:

• Обрабатывать файлы, размер которых превышает ёмкость одного диска.
• Распараллеливать чтение и запись между узлами.
• Обеспечивать отказоустойчивость за счёт хранения нескольких копий каждого блока.

¶Примеры и применение

• Файловые системы: FAT32, NTFS, ext4, APFS — все они подвержены фрагментации при интенсивной работе.
• Базы данных: Microsoft SQL Server, PostgreSQL, Oracle, MySQL — поддерживают как автоматическое, так и ручное управление фрагментацией индексов и таблиц.
• Распределённые хранилища: Google File System (GFS), Hadoop Distributed File System (HDFS), Amazon DynamoDB — используют шардирование и фрагментацию для масштабирования.
• Операционные системы: Windows, Linux, macOS — управляют фрагментацией оперативной памяти через подсистему виртуальной памяти.

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

• Первые алгоритмы дефрагментации для жёстких дисков появились в 1980-х годах и были реализованы в утилитах типа Norton Speed Disk.
• В современных файловых системах (например, ZFS, Btrfs) фрагментация может быть менее выражена благодаря механизмам copy-on-write и динамическому выделению экстентов.
• В системах реального времени фрагментация памяти может приводить к критическим задержкам, поэтому для таких систем разрабатываются специальные алгоритмы управления памятью, исключающие фрагментацию (например, пулы фиксированных блоков).

¶Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е изд. — СПб.: Питер, 2015.
• Гарсиа-Молина Г., Ульман Дж., Уидом Дж. «Системы баз данных. Полный курс». — М.: Вильямс, 2003.
• Документация Microsoft по дефрагментации дисков (Windows).
• Документация Linux по файловым системам (man-страницы ext4, XFS).
• Статья «Sharding» в документации MongoDB.
• Клейнберг Дж., Тардос Э. «Алгоритмы: разработка и применение». — М.: ДМК Пресс, 2016.