HighLoad.org – блог о высоких нагрузках
HighLoad.org > Иголка в стоге сена: эффективное хранилище миллиардов фотографий

Иголка в стоге сена: эффективное хранилище миллиардов фотографий
2010-03-08 00:10 my_fess 
Приложение Photos - это одна из самых популярных возможностей Facebook. На данный момент пользователи загрузили более 15 миллиардов фотографий, что делает Facebook крупнейшим сайтом в этом направлении. Для каждой загруженной фотографии Facebook генерирует и хранит 4 изображения различного размера, таким образом получается 60 миллиардов изображений и 1.5PB хранилище. Текущая скорость роста - 220 миллионов новых фотографий в неделю, т.е. каждую неделю потребляются дополнительные 25TB хранилища. В пиковые моменты в секунду обслуживаются 550,000 изображений. Эти числа ставят существенную задачу перед инфраструктурой хранения фотографий Facebook.

NFS инфраструктура

Старая инфраструктура обслуживания фотографий состояла из нескольких уровней:
  • Уровень загрузки получает фотографии, загружаемые пользователями, масштабирует оригинальные изображения и сохраняет их на уровне NFS хранилища.
  • Уровень обслуживания фотографий получает HTTP запросы на фотографии и обслуживает их с уровня NFS хранилища.
  • Уровень NFS хранилища построен на основе коммерческих решений для хранения данных.
Так как каждое изображение хранится в отдельном файле, на уровне хранилища находится гигантское количество метаданных, генерируемых из-за директорий пространства имен и файловых инодов. Количество метаданных намного превышает кэширующие возможности уровня NFS хранилища, что приводит к множественным операциям ввода/вывода на загрузку фотографии или запрос на чтение. Накладные расходы на метаданные на уровне NFS хранилища - узкое место всей инфраструктуры обслуживания фотографий. Это одна из причин того, что Facebook так полагается на CDN для обслуживания фотографий. Две дополнительные оптимизации были применены, чтобы в некоторой степени смягчить эту проблему:
  • Cachr: кэщирующий серверный уровень для "profile" изображений меньшего размера.
  • Кэш обработки файлов NFS, развернутый на уровне обслуживания фотографий, устраняет некоторые накладные расходы на метаданные на уровне NFS хранилища.

Haystack инфраструктура фотографий

Новая инфраструктура обслуживания фотографий сливает уровень обслуживания фотографий и уровень хранилища в один физический уровень. Он реализует основанный на HTTP сервер фотографий, который хранит фотографии в generic object хранилище Haystack. Главное требование к новому уровню было устранение любых ненужных накладных расходов на метаданные при операции чтения фотографий. Так, чтобы каждая операция чтения была только чтением данных фотографии (вместо метаданных файловой системы). Haystack может быть разделен на следующие функциональные слои:
  • HTTP сервер;
  • хранилище фотографий;
  • Haystack хранилище объектов;
  • файловая система;
  • устройство хранения данных.

Устройство хранения данных

Haystack развернут на базе блейд систем хранения. Типичная аппаратная конфигурация 2U блейд системы хранения:
  • 2 4-хядерных CPU
  • 16GB-32GB оперативной памяти
  • аппаратный RAID контроллер с 256MB-512MB NVRAM кэшем
  • 12+ 1TB SATA жестких дисков
Каждая блейд система хранения предоставляет около 10TB годного к применению дискового пространства, сконфигурированного как RAID-6 раздел, управляемый аппаратным RAID контроллером. RAID-6 обеспечивает достаточную избыточность и хорошую производительности при чтении, сохраняя невысокую стоимость хранения. Невысокая производительность при записи частично компенсируется NVRAM кэшем с обратной записью RAID контроллера. Так как операции чтения в основном случайные, NVRAM кэш полностью предназначен для операция записи. Кэши жестких дисков отключены, чтобы гарантировать согласованность данных в случае аварии или потери питания.

Файловая система

Хранилища объектов Haystack реализованы поверх файлов, хранящихся в единой файловой системе, созданной на 10TB томе. Запросы на чтение фотографий приводят к системному вызову read() по известным смещениям в этих файлах, но для того, чтобы выполнить эти операции чтения, файловая система должна сначала определить местонахождение данных на физическом томе. Каждый файл в файловой системе представляется структурой, которая называется inode. Она включает в себя блок отображений, который отображает смещение логического файла в физический блок смещений на физическом томе. Для больших файлов, блок отображений может быть довольно большим в зависимости от типа используемой файловой системы. Блочные файловые системы поддерживают отображения для каждого логического блока, и для больших файлов эта информация обычно не помещается в закэшированном иноде и вместо этого хранится в блоках косвенных адресов. Эти блоки должны быть пройдены для того, чтобы прочитать данные файла. Может быть несколько уровней косвенности, таким образом единственная операция чтения может привести к нескольким операциям ввода/вывода, в зависимости от того закэшированы или нет блоки косвенных адресов. Файловые системы с поддержкой экстентов поддерживают отображения для смежных диапазонов блоков (экстентов).  Отображение блоков для большого файла может состоять из указателя на один экстент, который помещается в иноде. Однако, если файл сильно фрагментирован и блоки разбросаны по физическому тому, его блок отображений соответственно увеличится. В файловых системах, поддерживающих экстенты, фрагментация может быть компенсирована агрессивным выделением большего блока данных  при росте физического файла. На данный момент, мы выбрали XFS файловую систему, которая поддерживает экстенты и обеспечивает эффективное выделение места под файлы.

Хранилище объектов Haystack

Haystack - это простое log-structured хранилище объектов, содержащее иголки, представляющие хранимые объекты. Haystack состоит из двух файлов - файл, хранящий сами иголки и индексный файл. Следующее изображение показывает схему файла хранения данных: Первые 8KB хранилища Haystack занимает суперблок. Сразу за ним идут иголки, каждая из которых состоит из заголовка, данных и футера: Иголка уникально идентифицируется кортежем <Offset, Key, Alternate Key, Cookie>, где Offset - смещение иголки в haystack хранилише. Haystack не накладывает ограничений на значение ключей, и могут быть иголки с повторяющимися ключами. Следующее изображение показывает схему индексного файла: Каждая иголке в файле Haystack хранилища соответствует запись в индексе, и порядок индексных записей должен соответствовать порядку связанных иголок в файле Haystack хранилища. Индексный файл предоставляет минимальное количество метаданных для нахождения конкретной иголки в файле Haystack хранилища. Загрузка и организация индексных записей в структуру данных для эффективного поиска - это ответственность приложения, использующего Haystack (в нашем случае Photo Store). Индексный файл не является критическим, он может быть построен заново из файла Haystack хранилища при необходимости. Главная цель использования индекса - это быстрая загрузка метаданных иголки в память без прохода по всему большому файлу Haystack хранилища, т.к. размер индекса обычно менее 1% от размера файла Haystack хранилища.

Операция записи Haystack

Операция записи Haystack последовательно добавляет новые иголки в файл Haystack хранилища. После того, как все иголки внесены в файл, соответствующие индексные записи записываются в индексный файл. Так как  индексный файл не критичный, индексные записи записываются асинхронно для лучшей производительности. Индексный файл периодически сбрасывается на низлежащее хранилище данных, чтобы ограничить продолжительность операций восстановления, вызванных аппаратными сбоями. В случае аварии или неожиданной потери питания процесс восстановления отменяет все частичные иголки в хранилище и обрезает файл хранилища по последней действительной иголке. Затем записываются отсутствующие индексные записи для иголок в конце файла хранилища. Haystack не позволяет перезаписывать существующее смещение иголки. Поэтому если требуется изменить данные иголки, новая ее версия с тем же кортежем <Key, Alternate Key, Cookie>. Таким образом приложения могут считать, что среди нескольких иголок с одинаковыми ключами, самая последняя - с самым большим смещением.

Операция чтения Haystack

Операции чтения передаются смещение иголки, ключ, альтернативный ключ, cookie и длину данных. Haystack добавляет длину заголовка и футера к длине данных и читает целую иголку из файла. Операция чтения завершается успешно: если ключ, альтернативный ключ и cookie соответствуют переданным в качестве аргументов; если данные проходят проверку контрольной суммы; и если иголка не была до этого удалена (см. ниже).

Операция удаления Haystack

Операция удаления проста - она помечает иголку удаленной в хранилище, устанавливая бит "deleted" в поле флагов иголки. Однако, связанная индексная запись не изменяется в любом случае, так что приложение может завершить ссылаться на удаленную иголку. Операция чтения такой иголки увидит флаг "deleted"  и завершится с соответствующей ошибкой. Место удаленной иголки не может быть освобождено в любом случае. Единственный способ освободить место из под удаленных иголок - сжать haystack (см. ниже).

Сервер хранения фотографий

Сервер хранения фотографий отвечает за принятие HTTP запросов и преобразование их в соответствующие операции Haystack хранилища. Для того, чтобы минимизировать количество операций ввода/вывода необходимых для получения фотографий, сервер хранит в памяти индекс смещений всех фотографий в файле хранилища. При запуске сервер считывает индексный файл haystack и заполняет in-memory индекс. С сотнями миллионов фотографий на узел (и число только растет с большей вместительностью жестких дисков), нам необходимо убедиться, что индекс помещается в доступную память. Это достигается засчет хранения в памяти минимального количества метаданных, только информация необходимая для нахождения изображений. Когда пользователь загружает фотографию, ей присваивается уникальный 64-битный id. Потом фотография масштабируется до 4-х разных размеров.  У каждого масштабированного изображения одниковые cookie и 64-битный ключ, а логический размер изображения (большой, средний, маленький, миниатюра) хранится в альтернативном ключе. Сервер загрузки затем вызывает сервер хранения фотографий для сохранения всех четырех изображений в Haystack. In-memory индекс хранит  следующую информацию для каждой фотографии: Haystack использует open source Google SparseHash структуру данных для сохранения небольшого размера  in-memory индекса, т.к. у нее всего 2 бита накладных расходов на запись.

Операция записи/изменения хранилища фотографий

Операция записи записывает фотографии в Haystack и обновляет in-memory индекс информацией о новых записях. Если индекс уже содержит записи c теми же ключами, тогда это модификация существующих фотографий и изменяются только смещения, чтобы отразить размещение новых фотографий в файле Haystack хранилища. Хранилище фотографий всегда считает, что если есть повторяющиеся изображения (изображения с одинаковыми ключами), изображение с наибольшим смещением действительно.

Операция чтения хранилища фотографий

Операции чтения передаются Haystack id, ключ фотографии, размер и cookie. Сервер производит поиск в in-memory индексе, основываясь на ключе фотографии, и получет смещение иголки, содержащей запрашиваемое изображение. Если находит, то вызывает операцию чтения Haystack для получения изображения. Как уже упоминалось выше операция удаления Haystack не обновляет индексный файл Haystack. Следовательно только что заполненный in-memory индекс может содержать просроченные записи для ранее удаленных фотографий. Чтение ранее удаленной фотографии провалится и in-memory индекс обновится, чтобы отразить это установкой смещения изображения в 0.

Операция удаления хранилища фотографий

После вызова операции удаления Haystack in-memory индекс обновляется установкой смещения изображения в 0, помечая изображение удаленным.

Сжатие

Это онлайн операция, которая освобождает место, используемое удаленными и повторяющимися иголками (иголками с одинаковыми ключами). Она создает новый Haystack копированием иголок, пропуская повторяющие и удаленные. По завершению она меняет местами файлы и in-memory структуры.

HTTP сервер

HTTP фреймворк, который мы используем - это простой evhttp сервер, предоставляемый open source библиотекой libevent. Мы используем множественные потоки, каждый поток может обслуживать отдельный HTTP запрос за раз. Так как нагрузка у нас в основном приходится на ввод/вывод, производительность HTTP сервера не критична.

Резюме

Haystack представляет основанное на HTTP generic object хранилище, содержащее иголки, которые отображаются на хранимые непрозрачные объекты. Хранение фотографии как иголок в Haystack устраняет накладные расходы на метаданные, объединяя сотни тысяч изображений в единый файл хранилища Haystack. Это поддерживает накладные расходы на метаданные невысокими и позволяет хранить местоположение каждой иголки в in-memory индексе. Это позволяет получить данные изображения за минимальное количество операций ввода/вывода, устраняя все ненужные накладные расходы на метаданные.

Автор: Peter Vajgel Дата: 1 мая 2009 Оригинал статьи


комментарии [0]  | комментировать

  © 2010-2018 HIGHLOAD