Это чистой воды мозговой штурм. Не верьте ни единому слову. Если найдете ошибки в рассуждениях, исправляйте их.
1.
Система называется масштабируемой, если она способна увеличивать производительность пропорционально дополнительным ресурсам. [1]
Если ваш алгоритм может работать в 10 раз быстрее только на десятикратно увеличенной частоте процессора, то это немасштабируемый алгоритм. Если вы можете поставить в 10 раз больше процессоров и получить в 10 раз больше производительности, то система масштабируется.
Масштабируемыми могут быть не только алгоритмы, но и хранилища данных, процессы, и их совокупность — целые системы, состоящие из алгоритмов, хранилищ данных и процессов.
2.
Многим из нас фракталы известны в разнообразных геометрических проявлениях [2, 3]
Попробуем определить фрактал более формально, чем "фигура, обладающая самоподобием", с тем, чтобы более конкретно вести дальнейшее рассуждение. Фрактал — это 1) форма, заданная через интересующие нас статические характеристики, плюс 2) правило составления новой формы из данной с сохранением заданных характеристик.
Например, снежинка фон Коха [4] может быть определена так: это ограниченная ломаная, напоминающая шляпу с полями, плюс правило: если взять четыре такие ломаные и соединить, получится почти такая же шляпа. Тот факт, что это будет немного другая шляпа, нас не интересует. Важно, что это будет все равно шляпа с полями.
Обратите внимание, что это определение снежинки отличается от классического *обратным порядком*. В классическом определении у нас есть *аксиома* (дан отрезок) и правило трансформации (детализации): заменить отрезок на четыре отрезка. Поскольку нас интересует масштабирование *наружу*, то мы меняем определение так, чтобы снежинка *росла вширь*, а не *детализировалась*.
Ссылки
[1] //en.wikipedia.org/wiki/Scalability
[2] //local.wasp.uwa.edu.au/~pbourke/fractals/
[3] //en.wikipedia.org/wiki/Fractal
[4] //en.wikipedia.org/wiki/Koch_snowflake
11 июня 2008 в 18:02
Система, на самом деле, развязанная и очень простая. Почтовые ящики и обработчики существуют независимо друг от друга.
Фрактально это можно описать так:
1) почтовый ящик — это надежное хранилище с несколькими отверстиями (сообщение можно кидать в любое отверстие),
2) если объединить несколько почтовых ящиков получится новый почтовый ящик ("почтовое отделение нашего района").
И обработчики:
1) Адресат — это набор почтальонов, которые посещают некий набор почтовых ящиков.
2) Если взять несколько адресатов, получится новый адресат (потому что тоже состоит из группы почтальонов).
Все остальное: балансировщики, кеши, и географическое расположение — уже детали конкретной реализации.
10 июня 2008 в 23:00
Жека: ты забыл сформулировать фрактальное определение. Плюс, не очевидно, что "Труба" не станет узким местом в системе.
Hint: "труба" — это плохая метафора. Почтовые ящики — более правильная.
10 июня 2008 в 21:01
Итак, есть один большой Адресат с здоровым почтовым ящиком, куда все Отправители кидают свои сообщения. Адресат достает сообщения из ящика и обрабатывает.
Отправителям никакого ответа не дается, судя по всему – т.е. труба в одну сторону.
Адресат, конечно, состоит из нескольких машин, но будем считать, что он как-нибудь разберется, как им всем одновременно модифицировать разделяемое состояние, если оно у них есть (БД?).
Остается реализовать только, собственно, одну-единственную трубу, у которой Отправители дергают только push, отправляя запрос на единственный символический адрес Адресата, а Адресат дергает только pull.
Отправителей настолько много, что с потоком данных от них одному балансеру не справиться.
Тогда:
- push происходит так: (Я – Отправитель)
- Я отправляю запрос "Ща буду делать push!" на адрес Адресата, его принимает корневой балансер отправителей
- Мне приходит ответ "Обратись вон туда", содержащий адрес балансера второго уровня. Как он выбирается – см. ниже.
- Балансеру второго уровня я отправляю "push(<message>)", он его перекидывает наименее наполненному из подвластных ему серверов-хранилищ (он их периодически спрашивает "Чувак, а насколько ты наполнен?"). Сервер сохраняет сообщение.
Таким образом, корневому балансеру не приходится выдерживать весь поток сообщений, а нагрузка распределяется более или менее равномерно между всеми.
Каждый балансер второго уровня хранит суммарную наполненность подвластных ему серверов и периодически ее пересчитывает, опрашивая эти сервера. На этапе редиректа выбирается наименее наполненный из балансеров второго уровня.
- pull происходит так: (Я – Адресат)
- Я отправляю pull на адрес Приемного Конца Трубы
- Приемный Конец Трубы перекидывает мой обратный адрес одному из Приемных Балансеров. Какому – см. ниже.
- Приемный Балансер достает у себя из Кэша сообщение и кидает его мне
При этом Приемный Конец Трубы периодически опрашивает все Приемные Балансеры на предмет того, сколько у них сообщений в кэше. Перекидка производится на тот Приемный Балансер, у которого их больше всего.
При этом каждый Приемный Балансер соединен с несколькими серверами-хранилищами. Он периодически опрашивает их на предмет наличия сообщений и досасывает их себе в кэш.
В случае чего можно добавить еще один уровень балансеров-редиректоров с обоих сторон и продолжить фрактальность.
FIFO можно организовать, организовав FIFO на самих серверах-хранилищах нижнего уровня. Оно будет не идеально точным, но в среднем – будет, благодаря балансировке. Впрочем, доказать это я бы не взялся
10 июня 2008 в 21:01
Хм, правда тут есть предположение, что сервера не отказывают и сообщения из-за этого не теряются. Чтобы бороться с этим, можно слать сообщение не одному, а двум детям на каждом уровне, например.
10 июня 2008 в 20:03
Интерфейс неблокирующий:
Tube#push(message) #=> nil
Tube#pop() #=> "some message"
Посылка сообщения — как опускание письма в почтовый ящик.
Приём сообщения — как залезание рукой в почтовый ящик.
Все адресаты равноправны (по сути, это один толстый адресат с кучей секретарей), все отправители — тоже.
Количество отправителей может быть сколь угодно большим (это и есть источник проблемы масштабирования). Соответственно, приходится увеличивать количество обработчиков (секретарей адресата).
Потери сообщений недопустимы.
Для простоты, порядок обработки сообщений не имеет значения, но лучше всего, чтобы приблизительно соблюдался принцип FIFO (т.е. не было такого, что вчерашнее сообщение еще ждет, а сто сегодняшних уже разобраны). Т.е. тут потребуется верхняя оценка времени ожидания обработки.
10 июня 2008 в 20:00
Подписываюсь
10 июня 2008 в 17:01
Так… Интерфейс системы такой?
send(Address, Message, ReplyKey) – не блокирует
receive(ReplyKey) -> Message – блокирует
Здесь ReplyKey – секретный идентификатор отправителя.
Вообще требуется еще довольно много уточнений
- Сообщения в основном требуют ответа или в основном не требуют?
- Равноправны ли адресаты и отправители?
- Сколько адресатов, сколько отправителей?
- Допустима ли потеря запросов? А потеря ответов?
- …
10 июня 2008 в 16:05
Известную книжку Мандельброта про фракталы в природе читали?
(Это я на комментарии подписываюсь.
)
10 июня 2008 в 14:04
Для начала, нет.
10 июня 2008 в 7:04
Сохранение порядка обработки сообщений имеет значение?
10 июня 2008 в 1:01
Более интересная задача: реализация очереди сообщений. Очередь — это труба, в один конец которой помещается сообщение, а с другого конца — изымается и обрабатывается. В отличие от примера с веб-сервером, обработка — асинхронная. Тот, кто поместил сообщение, может отойти в сторонку, а не ждать перед трубой в ожидании ответа.
Интересующий параметр — пропускная способность (N сообщений в T времени). Скорость обработки одного сообщения — конечная.
Задание телезрителям: описать систему как фрактал и предложить варианты масштабирования на разных этапах (первом, втором и следующих этапах трансформации).
10 июня 2008 в 0:05
3.
А теперь представим, что мы проектируем масштабируемую систему, используя фрактальные принципы.
Для начала, простой пример — веб-сервер. Упрощенная модель веб-сервера — функция эф от икс, у которой есть две интересующие нас характеристки: скорость обработки одного запроса (быстродействие, speed) и максимальное количество запросов, обрабатываемых в единицу времени (пропускная способность, bandwidth). Скорость одного ответа не может быть сколь угодно высокой. Чаще всего требуется способность обрабатывать огромный поток запросов, т.е. требуется масштабировать систему по параметру "пропускная способность".
Реализация функции эф от икс в виде простой однопоточной программы не будет масштабируемой: её мощность упрётся в мощность одного ядра процессора.
Классическая схема масштабирования веб-сервера — использование балансирующего прокси-сервера. (Детали кооперативной и вытесняющей многозадачности внутри одного процесса опускаем, они к масштабированию отношения не имеют.)
Мы можем запустить несколько Апачей на многоядерной машине и поставить перед ними Nginx, который будет раскидывать запросы между экземплярами веб-серверов ("чётный запрос — направо, нечётный — налево"). Если каждый Апач способен отвечать на 100 запросов в секунду, то 4 апача с прокси-сервером способны отвечать на 399 запросов в секунду (считаем машину четырёхядерной).
Прокси-сервер позволяет масштабировать веб-сервер на несколько машин. Если поставить 100 машин по 4 апача на каждой, то общая пропускная способность может быть около 40 тысяч запросов в секунду. (Считаем все веб-серверы независимыми.)
На языке фракталов система выглядит так:
1) веб-сервер — это программа, выполняющая эф от икс по протоколу HTTP.
2) если взять несколько веб-серверов и поставить перед ними балансирующий прокси-сервер, то получится новый веб-сервер, выполняющий *ту же самую функцию эф от икс*. Разумеется, быстродействие и пропускная способность будут другими (быстродейтсвие чуть ниже, а пропускная способность — больше), но требования п. 1 соблюдены.
Как только система описана таким образом, становится понятен путь, по которому нужно идти при масштабировании системы под растущие нагрузки.
Далее я попробую поставить задачи для более сложных систем и сформулировать их с использованием "фрактальной нотации". Можете попробовать и вы.