Базы данных: введение, часть шестая

Илья Тетерин
2012-10-29

(use arrow keys or PgUp/PgDown to move slides)

Хранение картинок

Строим фотохостинг

Постановка задачи

Поймал щуку - хочу показать друзьям в другом городе

Ты глянь какую машину я видел!

Вот я и пирамида!

20-25 лет назад / BBS / FIDO

Есть компьютер, телефонный кабель, модем?

Ставим программу BBS (Bulletin Board System), публикуем номер телефона и даем людям общаться.

Запускаешь программу, твой модем дозванивается до BBS, там в ANSI графике ходишь читаешь почту, скачиваешь программы. etc.

FIDO

Организуем деревянную структуру, даем узлам номера а-ля 2:5030/15 и уже программы начинают пересылать почту.

Картинки?

Форматы 320x240x256 / 640x480x16 цветов, скорости в районе 30 символов в секунду, 100к в час. Названия 8.3 символов.

Хранятся на диске, так же, как и в случае BBS. На самом деле это просто автоматизация поверх BBS.

Если надо переслать - режем на части, пакуем UUENCODE, вставляем в тело письма и отправляем. Есть файлэхо процессоры - сами собирают из N писем картинку.

20 лет, но есть tcp/ip сетки ...

Интернет / World Wide Web / 1992 ...

google:самая первая картинка в интернете
wikipedia:First_image_on_the_Web

В 1992-ом году, после шоу CERN Hardronic Festival, мой коллега Тим Бернерс Ли попросил у меня пару фоток "тех девчонок из ЦЕРНа", дабы опубликовать их в свежеизобретенной им системе под названием "Всемирная паутина".

Я не очень понял что он хотел, но отсканировал несколько фоток на моем Маке и выложил их на ныне известный ftp "info.cern.ch".

Откуда мне было знать, что так получилась первая в мире фотка, кликнутая в браузере!

Back in 1992, after their show at the CERN Hardronic Festival, my colleague Tim Berners-Lee asked me for a few scanned photos of "the CERN girls" to publish them on some sort of information system he had just invented, called the "World Wide Web".

I had only a vague idea of what that was, but I scanned some photos on my Mac and FTPed them to Tim's now famous "info.cern.ch".

How was I to know that I was passing an historical milestone, as the one above was the first picture ever to be clicked on in a web browser!

Les Horribles Cernettes ("The Horrible CERN Girls") is an all-female parody pop group, self-labelled "the one and only High Energy Rock Band", founded by employees of CERN which performs at CERN and other HEP related events. The initials of their name, LHC, are the same as those of the Large Hadron Collider which was later built at CERN.

"Просто" web developer (youtube) - wiki:Tim Berners Lee - отец World Wide Web, основатель w3.org консорциума в 1994-ом году. "Просто еще одна программа, кто же думал, что так выйдет" ...
wiki:Les Horribles Cernettes / "The Horrible CERN Girls"

Crossdressing, Compression and Colliders: The First Photo on the Web

Плюсы / минусы?

Вопрос: а если надо 100 картинок?
Ответ: сложу в .zip, заберут распакуют, посмотрят.

15 лет назад: сделаем свой http / html сервис

Плюсы:

можно сделать красиво
более простые пользователи
больше пользователей

Подробнее

Что происходит на сервере?

Что на сервере по get?

Плюсы / минусы?

Растет количество файлов и пользователей, объем данных, что делать?

Дополнительные требования

Для быстрой отрисовки html страниц на клиенте нужна мета информация

Размеры картинки для
<img src="..." height="480" width="320"/>.

Так же текстовое описание для alt="..." атрибутов.

Во времена fat16 это решалось отдельным файликом в котором к каждому файлу дописывали расширенную информацию.

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

Кстати: клиенты хотят не только оригиналы картинок, но и разные размеры для разных страниц - новинки, альбом, превью, новости етс

Надо - иконка 32х32, 128х128, 640х480 етс - 4-5 размеров.

Взрывной рост количества картинок в системе

Варианты решения

Много файлов в каталоге - сделаем дерево - поделим наши кучи картинок в одном каталоге на части.

По пользователю - /data/иванов/, /data/петров/ etc.

Плохо - у пользователей разное колво картинок, у самых активных (они же и самые полезные) - тормозит, когда сотни тысяч картинок.

Сделаем hash названия+пути и разложим в каталоги /data/0000/0001, /data/0000/0002 etc.

Проблема: Очень обидно, когда накладываются hash.
Ответ: будем назначать id картинке сами (20000001.jpg) и класть в каталоги в обратном порядке: /data/01/00/00/20.jpg

Но опять вопрос - где метаинформация, что картника 20000001.jpg принадлежит пользователю Иванову?

Хранить meta информацию

1. читаем информацию прямо из файла, но два раза - для html страницы и когда забирают картинку
Плохо - мета информацию надо парсить и она в разных местах у разных форматов.

2. кладем рядом одноименный .txt файлик с описанием
Уже лучше - файл проще и меньше, но все равно 2 раза ходить в fs

3. делаем index (index.txt) - по 1 файлу в каталоге
Заметно лучше - меньше дерганий диска, быстрее, но что с одновременной работой Н пользователей по добавлению.

Идеально - файловая система с доп. атрибутами файла, но ...

Почему не сделать один файл на весь /data?

Он постоянно меняется при добавлении, падает скорость добавления данных из-за блокировок.

Опять же растет объем файла (плавно приближается по размеру к самой FS таблице) - долго просматривать.

Много пользователей = много отдающих серверов
-> нужна репликация

Репликация файловой системы - просто копируем каталоги с одного сервера на другой

Например - rsync раз в 5 минут смотрит новые файлы и несет на другой сервер

Master-slave и так далее ...

Что хорошо - каталог (даже с индекс файлами) самодостаточен, не требует никакого запущенного рантайма, пассивно лежит на fs и легко копируется.

Добавим базу данных... 

create table images ( 
  id number primary key, 
  width number, 
  height number, 
  alt varchar(200));

create table keywords (
  id number primary key, 
  value varchar(200));

create table keyword_image (
  keyword_id number, 
  image_id number);

Плюсы - база сама разберется с блокировками, с доступом по сети с нескольких серверов etc.

За счет keywords - есть возможность сделать поиск по тэгам (животное, машинки етс).

Идеально, но ... но можно же сделать еще красивее! (сам так делал :) )

База же универсальна и мощна - сложим картинки в нее!

У нас же мощный DB сервер и проверенная временем база Oracle / MySQL...

Там есть специальные, удобные типы данных:
BLOB - бинарный объект с макс. размером 4Gb * размер блока (8kb)
BFILE - ссылка на файл, хранимый на сервере базы - макс. размер 4Gb

create table image_body (
  id number primary key, 
  body blob);

плюсы:
все в одном месте - понятнее и проще с точки зрения разработчика
один мощный сервер, а не куча файловых складов
нет вопросов consistency (что записали, то сразу всем видно) и т.д.
Backup средствами базы
Master slave средствами базы

минусы:
решение монолитно и быстро упирается в мощность сервера - ака тупик масштабируемости, да еще база всегда всем постоянно нужна.

polyglot persistence

wiki:Polyglotism is the ability to speak several languages with a high degree of proficiency.

wiki:Persistence in computer science refers to the characteristic of state that outlives the process that created it.

Комбинируйте из разных баз (хранилищ) системы, которые хороши для ваших потребностей.

Монолитность и универсальность - в прошлом на текущий момент.

О каком количестве картинок идет речь?

http://www.flickr.com/

2007-ой год, Архитектура Фликера (Flickr Architecture (перевод by Insight IT)):

Статистика

Архитектура Фликера

Всё кроме фоток - в базе данных

Статичные данные - на отдельных серверах

Клиенту выдается список серверов и клиент в случае ошибки сразу retry к следующему серверу

Активные связки master-master для MySQL, так как master-slave слишком медленно

Каждая страница - 27-35 SQL запросов, включая select count(*) для счетчиков

Шарды по 400К+ пользователей

Сервера 16Gb RAM / 120Gb данных / RedHat Linux

12Tb данных о пользователях (это без самих фоток)

etc ...

И это 2007 год

Facebook - хранилище фоток

Oct 2008 - 10 млрд фоток ...

Май 2009

Статистика
* 15+ млрд фоток
* 4 размера на каждую фотку = 60+ млрд фоток
* 1.5 Pb данных
* 220 млн новых фоток в неделю = 25Tb данных в неделю
* в пике отдаем 550 000 фоток в секунду

2010

260 млрд изображений / 20 Петабайт данных

отдаем 1 млн картинок в секунду

1 млрд новых картинок в неделю / 60 Тб данных

Needle in a haystack: efficient storage of billions of photos - Иголка в стоге сена: эффективное хранение миллиардов фоток

Finding a needle in Haystack: Facebook’s photo storage - полный pdf для OSDI'10

Архитектура до Haystack

Архитектура до Haystack

Сервера загрузки - получают фотку, ресайзят, складывают в NFS (сетевая файловая система)

Сервера отдачи - получают по http запрос, ищут в NFS файл, отдают

Сервера NFS - ( commercial storage appliance ) - покупные специализированные сервера для хранения файлов

Каждое фото - отдельный файл - очень много оверхеда и метаданных для NFS - bottleneck

Два слоя кеширования поверх NFS

Все равно море I/O операций на каждую фото - обычно 10+ операций чтения с диска для получения одного изображения.

Выпустили свои патчи к ядру - кеширование открытых file-handle - малые выигрыши, обычно данные не в cache.

Memcache слой - тоже не сработал - нет нужных изображений в памяти

Особенности данных - после загрузки фотка интересна 2 дня, а потом она "остывает", но может потребоваться в любой момент. (wiki:long tail)

Решение? Используем CDN + HayStack

URL

URL: http://[CDN]/[CACHE]/[MACHINE ID]/[LOGICAL VOLUME,PHOTO ID]

Store

сервер на 10Tb = 100 физических дисков по 100Gb

из физических дисков собираем "логические" ... и пишем на логический, который пишет во все свои физические

Directory

Маппинг logical volume - физический volume

Load balance запись на логические и чтение на физические диски

Определяет идти в CDN, в Cache или в Store

Контролирует логические и переводит их автоматом в r/o в случае проблем

Проблемы фиксятся руками

Cache

Распределенная hash table photo-id -> data.

Получает запросы от браузеров пользователя и от CDN.

Складывает в cache только если запрос пришел от пользователя, а не от CDN - потому что основной кеш всё-таки CDN, не надо дублировать.

Складывает только если photo находится на доступном для записи логическом диске - дабы облегчить процессы записи.

Store

API - get key/value

Состоит из многих физических дисков.

На каждом диске миллионы фоток

Физический диск (physical volume) - это файл размером в 100Gb по пути /hay/haystack_[logical_volume_id]

Запрос = logical_volume_id + offset в файле

Все файлы всё время открыты и в памяти есть map file -> Needle (содержащей в том числе и file_offset)

Haystack Object Store

файл данных - 8kb супер блок и только добавляемые данные

Чтение

Cache машину дергают с полным URL, она идет в Store с
[logical_volume_id],[photo_id],[alt_id],[cookie]

Cookie - random набор данных, дабы бороться с перебором фоток по photo_id++

Обращаемся в маппинг в памяти, проверяем флаг удаления, получаем offset

Позиционируемся в file по смещению, читаем весь Needle в память

Проверяем контрольную сумму и cookie

Отдаем cache серверу

Запись

Пользователь отправляет данные на web server

Directory назначает куда писать - logical_volume_id, photo_id, alt_id, cookie

Web server напрямую, синхронно пишет во все физические диски новый Needle в конец файла (append only)

Если needle записана дважды, то Store использует с бОльшим offset

файл индекса

Просто меньше по размеру ( < 1% ), в том же порядке, может быть восстановлен по файлу данных

Сортировка и скорость - на стороне клиента, сами сортируйте индекс у себя

Пишется асинхронно, поэтому при рестарте - пробегает по основному файлу с max(offset), что есть в индексе

Удаление

Проставляем флажок в файле, не обновляем index. Индекс обновляем только при последующем чтении фотки

Удаляется в среднем 25% фоток в течение года

Compaction

Создаем рядом новый файл, копируем туда данные из исходного, можно даже во время записи в него

По окончании копирования блокируем запись, "атомарно" переименовываем

Оптимизации памяти

Флаг удаления вырожденный - просто ставим offset = 0 и экономим на отдельном поле.

Cookie не храним в памяти, а проверяем только с начитанным с диска.

Таким образом экономим 20% от памяти на запись и получаем 10 байт на одно фото.

Для сравнения - один inode в XFS занимает 536 байт ...

Фото (web) сервер - обрабатывает http запросы

На старте берет в память индексы - нужны минимальные записи:
* 64 bit назначенный ключ
* сдвиг 1-ой уменьшенной копии + размер
* сдвиг 2-ой уменьшенной копии + размер
* сдвиг 3-ей уменьшенной копии + размер
* сдвиг 4-ой уменьшенной копии + размер

Добавление
назначаем ключ, отправляем в стог
обновляем индекс в памяти, оставляя с большим offset

Чтение
По урлу ( https://fbcdn-sphotos-a-a.akamaihd.net/hphotos-ak-ash4/395828_336894629660406_587498094_n.jpg ) получаем:
* id стога
* ключ фото
* размер
* cookie (нужен, дабы нельзя было _перебрать_ все существующие фотки)

Идем в стог, получаем данные. Если получаем "удалено", обновляем индекс у себя (проставляем offset = 0)

Основная нагрузка на сеть, так что мало загружен по CPU

Haystack

Storage

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

Haystack: summary

Получилась масштабируемая система хранения бинарных объектов.

Используется не только для фото, но и для хранения email attach-ей в Facebook Message System

Уменьшен на порядки overhead работы с файлами - пара файлов на 100 000+ фоток

Маленькие индексы - влезают в память - не нужно I/O на метаданные

Получение данных - минимальное количество I/O (стремится к 1 disk i/o на фотку)

Итого:

Вопросы?