2.3. Глобальное сопоставление файлов на основе хэша. Структуры сопоставления файлов…
- User
2.3. Глобальное сопоставление файлов на основе хэша. Структуры сопоставления файлов сопоставляют логические смещения файла с физическими местоположениями на базовом устройстве. В большинстве традиционных файловых систем таблицы сопоставления файлов представляют собой древовидные индексы, такие как деревья экстентов и деревья оснований [28]. С увеличением количества и размера файлов размер структур сопоставления файлов также увеличивается. Операция изменения размера особенно затратна в древовидных индексах, поскольку любое обновление внутренних узлов дерева вступает в конфликт с другими параллельными операциями, которые обращаются к различным конечные узлы. Чтобы устранить эту проблему, традиционные файловые системы используют структуры сопоставления для каждого файла, чтобы изолировать одновременный доступ к разным файлам и уменьшить конфликт блокировок. В отличие от общепринятого мнения, Нил и др. [28] недавно показали, что, поскольку древовидные структуры сопоставления для каждого файла страдают от множества уровней косвенности и большего количества ссылок на память, в NVMM может быть полезна единая хэш-таблица для управления глобальными сопоставлениями файлов. Предлагаемая ими файловая система HashFS требует гораздо меньшего количества обращений к памяти, чем древовидные сопоставления, и, как таковая, производительность глобальных показано, что хэширование превосходит по эффективности деревья экстентов для каждого файла и деревья оснований [28]. Однако, все еще существует нерешенное ограничение в глобальном сопоставлении файлов на основе хэша. То есть блочное хеширование, используемое в HashFS, не подходит для последовательного ввода- вывода, поскольку блочное хеширование не управляет экстентами. Файловые системы, основанные на экстентах, позволяют размещать файлы на диске последовательно, что ускоряет последовательный ввод-вывод. Экстенты также значительно сокращают объем метаданных, сохраняя только два числа: номер первого блока и количество блоков, охватываемых экстент. Однако для хеширования блоков требуется, чтобы каждый номер блока в экстенте канонически сохранялся в соответствующем сегменте, что замедляет последовательный ввод-вывод данных. В этой работе мы разрабатываем новый алгоритм хеширования экстентов для преодоления этих ограничений, который мы описываем в разделе 4.2. Сократи текст
- Assistant
Глобальное сопоставление файлов управляет связью между логическими и физическими смещениями файлов. Традиционные файловые системы используют древовидные структуры типа деревьев экстентов для изоляции запросов, однако это приводит к большим издержкам памяти и конфликтах блокировок. Недавние исследования (Нил и др.) показали, что использование глобальной хэш-таблицы, как в HashFS, может быть эффективнее, так как она снижает количество обращений к памяти. Однако HashFS плохо справляется с последовательным вводом-выводом из-за отсутствия поддержки экстентов, которые обеспечивают ускоренную работу и уменьшение метаданных. Для решения этой проблемы разрабатывается новый алгоритм хеширования экстентов.
- User
- Структура SPFS. SPFS состоит из четырех ключевых компонентов, которые позволяют объединять PFS с устаревшими файловыми системами, как показано на рисунке 1(b) - (i) профилировщик точек синхронизации, который управляет небольшими синхронными записями в NVM с сохранением порядка, (ii) управление экстентами на основе хэша (таблица экстентов), (iii) управление свободным пространством на основе хэша (таблица растровых изображений блоков) и (iv) разрешение имен на основе хэша (таблица name2inode). В этом разделе мы сосредоточимся на профилировщике точек синхронизации, который определяет, какие блоки должны обрабатываться SPFS и помещаться в NVMM или в более низкую файловую систему для размещения в обычном хранилище. Обсуждения, основанные на хэшировании, представлены в разделе 4. Сократи текст
- Assistant
SPFS состоит из четырех компонентов: профилировщик точек синхронизации для управления записями в NVM, таблица экстентов для управления данными, таблица растровых изображений блоков для управления свободным пространством и таблица name2inode для разрешения имен. В данном разделе основное внимание уделяется профилировщику, решающему, какие блоки размещать в NVMM или в обычном хранилище. Хэширование рассматривается в разделе 4.
- User
3.1. Режим размещения файловых блоков. На рисунке 2 показаны три режима размещения файловых блоков, поддерживаемые в SPFS, - автономный, обходной и накопительный режимы. Обратите внимание, что SPFS размещает NVMM рядом с DRAM и дисками, а не в середине иерархии DRAM и блочных устройств. SPFS является верхней файловой системой, но управляет только NVM, позволяя более быстрому DRAM-кэшу VFS управляться нижней файловой системой. Автономный режим: Если выбран синхронный вариант (O_DIRECT, O_SYNC) указывается для системного вызова open(), или, если используется SPFS без файловой системы более низкого уровня, все файловые блоки размещаются в NM, как показано на рисунке 2(a). Автономный режим: Если для системного вызова open() указана опция synchronous (O_DIRECT, O_SYNC) или если используется SPFS без файловой системы более низкого уровня, все файловые блоки помещаются в NVMM, как показано на рисунке 2(a). Системные администраторы также могут принудительно использовать NVMM для каждого каталога с помощью расширенного атрибута или ioctl. То есть, например, при наличии каталога, в котором хранятся файлы журнала транзакций или файлы резервных копий с коротким сроком службы, администратор может указать каталог, который будет использоваться в автономном режиме. Режим обхода: если параметр синхронный не указан для при открытии() функция NVMM по умолчанию обходится, помещая файл в нижнюю файловую систему, как показано на рисунке 2(b). При обходе операций записи в нижнюю файловую систему рабочие нагрузки с интенсивным чтением и несинхронные операции записи могут быть выполнены за счет быстрого кэширования VFS. Накопительный режим: На рисунках 2(c), (d) и (e) показан накопительный режим, в котором и SPFS, и файловая система нижнего уровня играют определенную роль, поскольку определенные блоки файлов помещаются либо в NVMM, либо в обычное хранилище. Если профилировщик точек синхронизации, описанный в разделе 3.2, решит поместить блок в NVMM, SPFS получит получает информацию об экстенте файла с помощью fiemap ioctl и подготавливает сопоставление файлов в NVMM. При подготовке сопоставления файлов SPFS еще не выполняет физический перенос экстента, как показано на Рис. 2(c), где пунктирный прямоугольник представляет собой карту для файла, подлежащего переносу. Физическая миграция задерживается из-за того, что профилировщик точек синхронизации принимает решение о переносе при вызове функции fsync(), т.е. "грязные" блоки уже были делегированы в файловую систему более низкого уровня, и их можно было сохранить на диске путем периодической обратной записи в файловую систему более низкого уровня. файловая система. Вместо этого перенос откладывается до следующей записи, чтобы функция read() извлекла выгоду из низкой задержки кэша страниц VFS, как показано на рисунке 2(d). Поскольку нет необходимости перемещать целевой блок миграции в NVMM, если этот блок впоследствии не будет обновлен, физическая миграция запускается последующими вызовами функции write(), что позволяет избежать проблемы двойного копирования [12]. Как показано на рисунке 2(e), SPFS проверяет сопоставление файлов и записывает блоки в NVMM, если сопоставление файлов указывает на то, что файл сопоставлен в NVMM. По своей природе штабелируемый в файловых системах доступ к перенесенным блокам обеспечивается файловой системой верхнего уровня, то есть SPFS. Таким образом, блоки в нижней файловой системе становятся невидимыми для пользователя. Когда блоки действительно переносятся, блоки в нижней файловой системе удаляются с помощью функции fallocate(). Позже, если весь файл переносится в SPFS, файл удаляется из нижней файловой системы. Сократи текст
- Assistant
В SPFS поддерживаются три режима размещения файловых блоков: автономный, обходной и накопительный.
-
Автономный режим: Все блоки размещаются в NVMM, если указан синхронный режим (O_DIRECT, O_SYNC) или SPFS используется без нижестоящей файловой системы. Возможна принудительная настройка для каталогов (например, для журналов транзакций).
-
Режим обхода: Если синхронный режим не указан, записи проходят в нижнюю файловую систему, используя кэширование VFS для повышения производительности.
-
Накопительный режим: Разделение блоков между NVMM и обычным хранилищем. Профилировщик точек синхронизации решает, какие блоки переместить в NVMM. Физическая миграция откладывается для оптимизации операций записи/чтения. При переносе блоков они удаляются из нижней файловой системы, оставаясь видимыми только в SPFS.
-
- User
3.2. Механизм профилирования: Sync Point Profiler. Небольшие синхронные операции записи с сохранением порядка часто приводят к значительному снижению скорости ввода-вывода [35], поскольку это упорядочивает потенциально параллельные операции. Такие небольшие синхронные записи с сохранением порядка должны выполняться на быстрых устройствах NVMM, а не на медленных блочных устройствах. Поэтому мы разрабатываем систему синхронизации Профилировщик точек, который отслеживает вызовы функции fsync(). В частности, при вызове функции fsync(), если предыдущий вызов функции fsync() для того же файла находится в пределах определенного порогового значения и объем сброшенных данных невелик, мы считаем, что это необходимо для сохранения порядка. синхронная запись. Смысл этого заключается в том, что если интервал короткий, существует высокая вероятность того, что вызов функции fsync() выполняется с намерением сохранить порядок хранения [35]. Напротив, если интервал велик, то даже при небольшом объеме записи маловероятно, что приложения будут сбрасывать данные в непрерывной последовательности. Таким образом, они могут обслуживаться более медленной файловой системой более низкого уровня без существенного снижения производительности. Чтобы определить малый размер, мы не берем индивидуальные размеры записи в момент записи, а берем общее количество байт, записанных в более низкая файловая система в fsync(). Это объясняется тем, что для больших объемов операций записи может быть использована пропускная способность диска, а синхронные операции записи для поддержания порядка хранения обычно невелики (например, 4 КБАЙТ WAL-фреймов в СУБД). Значения по умолчанию в наших настройках - 1 секунда для интервала и 4 МБ для размера. Мы берем 4 МБ, поскольку это значение используется в политике предсказателя синхронности Ziggurat [39], в то время как была выбрана 1 секунда, поскольку мы считаем, что производительность SPFS нечувствительна к пороговому времени, если только оно не установлено слишком малым. В разделе 5 мы количественно оцениваем параметры профилировщика влияют на производительность. На рисунке 3 показаны ключевые различия между функцией определения синхронности и размера записи Zig- gurat и SPFS Профилировщик точек синхронизации. Пример на рис. 3(а), где приложение выполняет четыре небольшие операции записи размером 3 МБ (A, B, C и C’), показывает, как Ziggurat принимает решение для каждой отдельной операции записи() (таким образом, профилировщик указателя записи) и с готовностью выполняет небольшие операции записи в соответствии со своей политикой быстрого выполнения. Его предиктор размера записи определит первые две записи, A и B, как небольшие и сохранит их в NVMM. Когда вызывается функция fsync(), ее функция syn- предиктор хроничности обнаружит, что общее количество байт превышает 4 МБ, и обработает файл как асинхронный. Тем не менее, A и B уже переведены в NVMM. Предиктор размера записи также переводит C в NVMM, поскольку он маленький. Однако вторая функция fsync() рассматривает файл как синхронный, поскольку было записано всего 3 МБ (C). Следовательно, следующая запись C’ также будет записана в NVMM. В заключение мы видим, что все записи сохраняются в NVMM. Как мы покажем позже в разделе 5, метод профилирования Ziggurat не позволяет использовать более быструю DRAM и показывает производительность, аналогичную производительности файловой системы NOVA, использующей только NVMM, поскольку он агрессивно перенаправляет большинство операций записи в NVMM. SPFS, с другой стороны, принимает решения о размещении блоков при вызове функции fsync(). На том же примере, что и выше, на рисунке 3(b) показано, насколько по-разному профилировщик SPFS обрабатывает операции записи. Для A и B они изначально записываются в кэш страниц VFS, что позволяет им использовать DRAM. При первой fsync(), поскольку общий объем записи составляет 6 МБ, оба A и B записываются на блочное устройство через файловую систему нижнего уровня. Аналогично, C также записывается в кэш страниц. При вызове второй функции fsync() файловая система нижнего уровня сбрасывается C из кэша на диск, но в то же время SPFS обнаруживает small выполняет синхронную запись и переносит свое отображение блоков (не блоков данных) в NVMM. Когда запрашиваются последующие записи в некоторые из блоков C (C’), эти записи направляются в NVMM и непосредственно записываются в него. Сократи текст
- Assistant
Sync Point Profiler в SPFS оптимизирует работу с небольшими синхронными записями, которые требуют сохранения порядка. Он отслеживает вызовы
fsync()и, если интервал между вызовами короткий и объем данных небольшой, записи рассматриваются как синхронные и отправляются в NVMM для повышения производительности. Если интервал большой или данные крупные, записи могут обрабатываться через нижнюю файловую систему.В отличие от агрессивной стратегии Ziggurat, перенаправляющей большинство записей сразу в NVMM, SPFS откладывает перенос данных. Например, небольшие записи (A, B, C) сначала размещаются в кэше DRAM через VFS. Если при вызове
fsync()объем данных превышает порог (например, 4 МБ), записи отправляются на блочное устройство. Когда SPFS фиксирует небольшой объем и синхронность (например, C и C’), данные постепенно переносятся в NVMM для последующей обработки, что позволяет снизить нагрузку на NVMM и задействовать преимущества DRAM. Этот подход обеспечивает лучшее использование комбинированного хранилища. - User
3.2.1. Перенос в файловую систему более низкого уровня. По сравнению с Ziggurat, SPFS использует NVMM более экономно. Однако, когда пространство в NVMM заканчивается, SPFS выбирает нужные файлы и переносит их в файловую систему более низкого уровня. Обратите внимание, что основной целью SPFS является не кэширование часто используемых файлов, а обработка небольших синхронных записей с сохранением порядка. Таким образом, даже если в NVMM есть свободное место, SPFS переносит файл в более низкую файловую систему, если меняется схема доступа к нему, например, если схема доступа требует интенсивного чтения, то при перемещении файла в более низкую файловую систему кэш страниц VFS может принести пользу. SPFS использует показатель, называемый коэффициентом синхронизации, для определения того, какой из последних шаблонов ввода-вывода файла хорошо соответствует критериям сохранения порядка небольших синхронных записей. Формула, которая вычисляет коэффициент синхронизации (SF) в момент времени t, задается как SFt = α • вес(IO_type) + (1 − α) • SFt−1 где α - коэффициент ослабления (0 < α < 1), т.е. в формуле используется экспоненциальное скользящее среднее, чтобы ослабить влияние старых обращений к файлам. вес (IO_type) - это фиксированное положительное значение , если текущий ввод-вывод в момент времени t удовлетворяет условию профилировщика точек синхронизации . В противном случае оно равно нулю, т.е. если файл требует интенсивного чтения или обновляется большими партиями, его коэффициент синхронизации постепенно уменьшается. Коэффициент синхронизации сохраняется для каждого файла и обновляется только при Запрос ввода-вывода. Следовательно, затраты на его вычисление незначительны. Когда пространство NVMM заканчивается, SPFS переносит файлы с низким коэффициентом синхронизации обратно в файловую систему с более низким коэффициентом синхронизации в фоновом режиме. Администраторы также могут установить жесткое ограничение на Коэффициент синхронизации позволяет переносить файлы обратно в файловую систему более низкого уровня, если их коэффициент синхронизации ниже установленного предела, даже если в NVMM есть свободное место. Сократи текст
- Assistant
SPFS рационально использует NVMM, фокусируясь на обработке небольших синхронных записей с сохранением порядка. Когда NVMM заполняется или меняется характер доступа к файлам (например, интенсивное чтение), файлы переносятся в нижнюю файловую систему.
Для выбора файлов SPFS использует коэффициент синхронизации (SF), рассчитываемый через экспоненциальное скользящее среднее: SFt = α • вес(IO_type) + (1 − α) • SFt−1, где α — коэффициент ослабления, а вес(IO_type) равен положительному значению, если ввод-вывод соответствует критериям сохранения порядка. Если доступ к файлу требует больших партий записи или интенсивного чтения, SF уменьшается.
Файлы с низким SF перемещаются в фоновом режиме. Администраторы могут задавать порог SF для переноса, даже если в NVMM остается свободное место.
- User
- Управление блоками на основе хэша. Хотя SPFS является штабелируемой файловой системой, она также является автономной файловой системой NVMM на основе хэша. Как файловая система, SPFS требует постоянного управления метаданными файловой системы, и, таким образом, затраты на управление метаданными могут быть удвоены. Поскольку целевой нагрузкой SPFS является синхронный ввод-вывод с большим количеством небольших файлов, традиционные структуры сопоставления для каждого файла могут привести к потере дискового пространства [28]. Таким образом, аналогично HashFS [28], SPFS управляет информацией о сопоставлении файловых блоков, используя глобальные структуры на основе хэша. Кроме того, SPFS использует- определяет размер хэш-таблицы путем индексации экстентов, а не блоков. Однако, насколько нам известно, не существует эффективных способов хэширования экстентов, т.е. данных диапазона. Чтобы преодолеть это ограничение, мы предлагаем новый алгоритм хэширования экстента. В этом разделе мы опишем управление свободным пространством на основе хэша (таблица растровых изображений блоков), управление экстентами на основе хэша (таблица расширений) и разрешение имен путей на основе хэша (таблица name2inode) в SPFS. Немного сократи
- Assistant
SPFS, будучи штабелируемой файловой системой NVMM, требует эффективного управления метаданными, что может удваивать затраты на управление ими. Для синхронных операций с большим количеством небольших файлов традиционные структуры сопоставления данных могут быть неэффективны. Поэтому, аналогично HashFS, SPFS использует глобальные хэш-таблицы для управления блоками, индексируя экстенты вместо блоков. Однако хэширование экстентов — задача сложная, и SPFS разработала новый алгоритм для ее реализации. В этом разделе описаны таблицы для управления свободным пространством (растровые изображения блоков), экстентами и разрешением имен (name2inode) на основе хэша.
- User
4.1. Управление свободным пространством. Используя экстенты, SPFS эффективно уменьшает совокупный размер метаданных о сопоставлении файлов. Совокупный размер структур сопоставления файлов особенно важен для облегченной штабелируемой файловой системы, поскольку небольшие структуры сопоставления оставляют больше места для блоков файловых данных. SPFS использует динамическое хэширование (в частности, CCEH [27]) для динамической настройки размера нескольких хэш-таблиц и эффективного управления NVMM пространство. В частности, если коллизии хэшей нельзя избежать с помощью линейного зондирования или случайного хэширования, SPFS динамически распределяет и назначает блоки NVMM каждой хэш -таблице, а именно таблице экстентов, таблице растровых изображений блоков и таблице name2inode. SPFS управляет блоками данных с детализацией в 4 КБ, но по умолчанию размер блоков метаданных составляет 256 байт (также называемых XPLine, единицей физического доступа к DCPMM). Это делается для того, чтобы уменьшить ненужную трату пространства NVMM, а также избежать увеличения объема записи на аппаратном обеспечении, которое может быть вызвано операциями чтения- изменения-записи. Однако, если мы используем небольшие блоки, которые составляют 1/16 от традиционного размера блока, SPFS необходимо отслеживать в 16 раз большее количество блоков, что приводит к высокая нагрузка на управление метаданными. Чтобы сократить эту нагрузку, SPFS группирует 16 смежных свободных блоков в кластер размером 4 КБ и управляет расположением свободных кластеров в растровой карте кластера, как в обычных файловых системах. Для частично используемых кластеров мы управляем расположением свободных блоков, используя растровую хэш-таблицу блоков и классические изменчивые сегрегированные списки. На рисунке 4 показано расположение физического пространства NVMM для SPFS. Первые 4 Кбайт - это суперблок, который содержит различные метаданные, включая магический номер файловой системы, размер блока/кластера/ индексного узла, количество кластеров, количество индексных узлов, метаданные для трех хэш-таблиц и т.д. Затем следует кластерное растровое изображение, где каждый бит в кластерном растровом изображении указывает, все ли блоки в соответствующем кластере свободны или нет. Если какой-либо блок в кластере используется, соответствующий ему бит в кластерном растровом изображении устанавливается равным единице. Начиная с растрового изображения кластера при использовании одного бита на кластер размером 4 КБАЙТ объем используемого пространства для растровой карты кластера не больше, чем в традиционных файловых системах, которые управляют свободным пространством с точностью до блоков размером 4 Кбайт. Растровая карта кластера не указывает, какие блоки в кластере свободны или используются. Следовательно, для каждого частично используемого кластера требуются другие метаданные - битовая карта блоков, которая индексируется в таблице битовых карт блоков. Когда SPFS выделяет некоторые, но не все блоки в кластере, она создает и вставляет битовую карту блоков в таблицу битовых карт блоков. Используется таблица блочных растровых изображений только для частично выделенных кластеров. Если в кластере нет свободного блока, что является обычным случаем для файлов размером более 4 КБ, или если все блоки свободны, что также является обычным случаем при первоначальном форматировании файловой системы, растровое изображение блока в SPFS не требуется. Чтобы управлять свободными блоками частично используемых кластеров и быстро обслуживать запросы на выделение памяти, SPFS управляет изменчивыми разделенными списками, созданными на основе таблицы растровых изображений постоянных блоков. Для запроса на выделение блоков мы выбираем разделенный список в зависимости от размера запроса на выделение. Немного сократи текст
- Assistant
SPFS уменьшает размер метаданных о сопоставлении файлов, эффективно используя экстенты, что особенно важно для компактной файловой системы. Она применяет динамическое хэширование (CCEH) для управления хэш-таблицами (таблица экстентов, растровых изображений блоков и name2inode) и пространства NVMM. Для оптимизации объема и избегания излишней записи размер блоков данных установлен на 4 КБ, а блоков метаданных — 256 байт.
SPFS группирует 16 смежных блоков в кластер размером 4 КБ, управляя свободными кластерами через растровую карту. Для частично используемых кластеров используются битовые карты блоков, индексируемые через таблицу растровых изображений блоков. Такие карты создаются только для частично выделенных кластеров, экономя место. Для быстрого выделения памяти SPFS также применяет изменчивые разделенные списки, формируемые на основе таблицы растровых изображений блоков.
- User
4.2. Хэширование экстентов. SPFS индексирует экстенты в хэш-таблице, называемой таблицей экстентов. Насколько нам известно, SPFS - это первая файловая система, основанная на хэшировании, которая индексирует экстенты с помощью хэш-таблицы. HashFS [28], современная файловая система NVMM, основанная на хэшировании, которая также управляет информацией о сопоставлении файлов в глобальной хэш-таблице, требует, чтобы каждый номер блока канонически хранился в соответствующей ячейке. Таким образом, HashFS индексирует блоки, а не экстенты, как показано на рисунке 5(a). Таким образом, HashFS не только значительно увеличивает общий размер сопоставления файлов структуры, но это также замедляет запись, поскольку для записи экстента из B блоков требуется столько же инструкций, сколько и для хранения B, а также очистка кэша. В отличие от блочного хэширования, наш новый метод выбирает только несколько сегментов на основе двоичного представления номеров кластеров, как показано на рисунках 5(б) и 6. Степень Хэширование определяет количество указателей для данного экстента с помощью log2B, где B - количество блоков в экстенте. Алгоритмы вставки и поиска для хэширования экстента представлены в алгоритмах 1 и 2. Алгоритмы короткие, но они работают со сложными побитовыми операциями, такими как операции ffs и fls (поиск первого/последнего бита, установленного в ключе). Экстентное хеширование может использоваться с любой схемой хеширования, включая статические и динамические схемы хеширования с различными специальными оптимизациями, такими как линейное зондирование, цепное хеширование и "кукушкино" хеширование. Однако для простоты объяснения мы будем предполагать, что используем статическое хэширование, и объясним алгоритмы вставки и поиска на примере, показанном в Рисунок 6. В примере мы предполагаем, что хэш-ключи состоят из 4 бит, а хэш-функция hash(inode, cluster_num) возвращает cluster_num для простоты представления. Обратите внимание, что алгоритмы 1 и 2 могут быть реализованы с помощью любой хэш-функции и любой реализации хэш-таблицы. Вставка: Предположим, мы вставляем диапазон ключей [1,12] ([ 00012, 11002]) как показано на рисунке 6. Первоначально мы начинаем с первого ключа и сохраняем указатель на экстент в соответствующем ему сегменте. В приведенном примере мы храним указатель в ячейке 00012. Затем мы проверяем, сколько последовательных нулевых битов содержится в постфиксе хэш-ключа текущего сегмента, который мы называем TNZ (конечное число нулей). Т.е. TNZ - это число последовательных нулей в двоичном представлении без каких-либо изменений. ненулевые цифры справа от него. Поскольку у 00012 нет нулей справа от крайнего правого бита 1, его значение TNZ равно 0. TNZ определяет, сколько сегментов нужно пропустить, т.е. расстояние между текущим сегментом и следующим сегментом, в котором мы сохраняем тот же указатель на протяженность. Мы называем это расстояние длиной шага, значение которой равно 2T NZ . В примере, поскольку TNZ равно 0, длина шага равна 20 = 1. Следовательно, мы переходим к следующему сегменту (00102) и сохраняем другой указатель на экстент. Хэш-ключ текущего сегмента (00102) содержит один ноль после крайнего правого бита 1. Следовательно, TNZ равно 1, а длина шага равна 2, т.е. (21). Следовательно, мы пропускаем следующий сегмент и переходим к следующему следующему сегменту (01002). Затем мы сохраняем там другой указатель и проверяем следующий шаг. Поскольку текущее значение TNZ равно 2, длина шага равна 4. Итак, мы переходим к блоку 10002 ( 01002+4). В сегменте 10002 у нас есть три последовательных нулевых бита в постфиксе. Таким образом, длина шага равна 8 ( 23). Однако следующее смещение сегмента (10002 + 8) не может превышать диапазон заданного экстента. Следовательно, мы уменьшаем значение TNZ одно за другим ( 23 → 22) до тех пор, пока следующая позиция ячейки не окажется в пределах заданного диапазона клавиш. Наконец, мы сохраняем другой указатель в ячейке 11002 (10002 + 22), и вставка завершена. Хотя размер экстента равен 12, в хэш-таблице хранится только 5 указателей. Если размер данного экстента равен B, то значение Extent В худшем случае при хэшировании сохраняется максимум 2 указателя × log2B . В лучшем случае мы храним только один указатель в хэш -таблице. Таким образом, мы можем значительно сократить количество указателей (с B до 2 × log2B) по сравнению с блочным хэшированием, в частности, при большом размере экстента. Поиск: Хотя в хэш-таблице экстента нет указателя для каждого хэш-ключа, мы можем найти экстент, используя любой хэш-ключ в пределах диапазона ключей. Алгоритм поиска, показанный в Алгоритм 2 работает следующим образом. Если запрос выполняет поиск экстента с использованием хэш-ключа k, двоичный номер которого равен (b1b2b3b4)2, мы сначала ищем в корзине[(b1b2b3b4)2]. Если в сегменте нет указателя на экстент (т.е. происходит ошибка поиска), это может быть связано с тем, что текущий сегмент не является начальной точкой шага, а не с тем, что хэш-таблица не содержит этого данные. Следовательно, нам нужно вычислить начальный индекс возможного шага, переворачивая конечные ненулевые биты, начиная с крайнего правого и перемещаясь влево. Таким образом, предполагая, что значение b4 не равно нулю, следующий сегмент, который мы ищем, - это сегмент[(b1b2b30)2]. Если в этом сегменте, опять же, нет указателя на экстент, мы продолжаем указанным образом и последовательно просматриваем сегмент[(b1b200)2], сегмент[(b1000)2] и сегмент[(0000)2]. Например, предположим, что запрос выполняет поиск хэш-ключа 7 (01112) в примере, показанном на рисунке 6. Затем мы ищем в корзине [01112] (шаг 1⃝), который завершится ошибкой, поскольку не содержит есть указатель на экстент. Затем мы ищем сегмент[(0110)2] (шаг 2⃝) и, наконец, сегмент[(0100)2] (шаг 3⃝), который содержит указатель на экстент. Оптимальная сложность этого алгоритма поиска равна O(1), но его наихудшая сложность не постоянна, а равна O(log2B) где B - количество сегментов. То есть, хэширование экстента обеспечивает оптимальное соотношение производительности поиска и производительности вставки. Вероятностный быстрый поиск: Чтобы найти баланс между эффективностью вставки и поиска, мы разработали оптимизацию быстрого поиска. Эта оптимизация отслеживает, какой шаг длина является наиболее распространенным параметром, и каждый запрос сначала обращается к сегменту с наиболее распространенной длиной шага. Например, наиболее распространенная длина шага на рисунке 5(б) равна 4 из-за указателей в сегментах 0, 4, 8 и 12. Обратите внимание, что в блоке 3 есть один указатель с шагом 1, а в блоке 10 также есть один указатель с шагом 2. Если запрос выполняет поиск в кластере 7 там, где наиболее распространенная длина шага равна 4, оптимизация быстрого поиска выполняет поиск в сегменте 4 (4 = 7 - (7%4)), прежде чем перейти к сегментам 7 и 6, следуя по порядку поиска. Обоснование такой оптимизации заключается в следующем. То алгоритм поиска требует, чтобы каждый запрос обращался к ближайшим сегментам в логарифмическом масштабе, поскольку размер экстента неизвестен запросам. Однако при большом размере экстента это может привести к ненужному доступу к большому количеству сегментов. Поэтому, если сначала проверить ковш, соответствующий наиболее распространенной длине шага, есть шанс сократить количество посещений ковша. Поскольку длина шага увеличивается в степени 2, т.е. количество различных длин шага ограничено логарифмической шкалой, затраты на отслеживание общей длины шага незначительны. Сократи текст
- Assistant
SPFS использует хэш-таблицу для индексирования экстентов, что сокращает размер метаданных и улучшает производительность по сравнению с блочным хэшированием. В отличие от HashFS, где каждый блок индексируется отдельно, SPFS применяет новый метод хэширования экстентов, сокращая число указателей в хэш-таблице с B до 2 × log2B, особенно для больших экстентов.
Вставка: Указатели на экстенты сохраняются не в каждом сегменте, а в ключевых точках с расстояниями (длиной шага) между ними, определяемыми количеством нулей в хэш-ключах. Это значительно уменьшает число записей.
Поиск: Запросы находят экстенты, начиная с целевого сегмента. Если указатель не найден, алгоритм проверяет ближайшие сегменты, двигаясь к началу записи. В лучшем случае поиск имеет сложность O(1), в худшем — O(log2B).
Оптимизация: Для ускорения поиска используется вероятностный быстрый алгоритм, сначала проверяющий сегменты с наиболее часто встречаемой длиной шага, что уменьшает количество обращений к сегментам при больших экстентах.
Хэширование экстентов в SPFS сбалансировало эффективность вставки и поиска, оптимизируя работу с метаданными.