линейная масштабируемость

[109]

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

Comments

[anatolix.livejournal.com]

Во-первых не любая конечно - это опять расширение изначального тезиса.

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

Под "online запросами" понимаем что-нибудь очень быстрое типа отдачу web страницы, или транзации по кредитке - типа десятые доли секунды или меньше.

Во-первых если система выдерживает 1M запросов в секунду то она обычно либо масштабируется линейно(в крайнем случае как n*ln(n) или похожие сложноси) либо не существует. Т.к. при масштабировании как O(n*n) сейчас столько машин ни у кого нет.

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

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

Что не масштабируются так это запросы на массовую обработку данных, типа создать отчет по всем записям которые юзер наплодил, но это уже кончено обычно делапется не online.

Не масштабируются многие числомолотилки - но вообщем ни у кого из нормальных людей не возникает желание создать кластер для решения задачи коммивояджера в лоб.

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

P.S. кстати можешь вспомнить какой нибудь реальный алгоритм которые регулярно отрабатывает на больше, чем на 1000 машин и имеет сложность как минимум n*n и находится в условиях экспоненциального увеличения данных в зависимости от роста интернета например?

[109.livejournal.com]

read-only queries масштабируются линейно, спору нет. и вообще с этим текстом я полностью согласен, as long as the message is "кое-что масштабируется линейно", а не "всё масштабируется линейно".

кстати можешь вспомнить какой нибудь реальный алгоритм которые регулярно отрабатывает на больше, чем на 1000 машин и имеет сложность как минимум n*n и находится в условиях экспоненциального увеличения данных в зависимости от роста интернета например?

мнэ... может не в точности что ты спрашиваешь, но вот один из моих проектов. есть у нас local entity feeds. local entity - это что угодно, имеющее координаты. магазин, ресторан, человек, мост через речку. feeds поступают как от фирм, продающих эти данные, так и от кроулинга интернета.

проблемы: 1. есть существенное перекрытие в данных и 2. данные не идеальны (где-то телефон неправильный, где-то название с ашипкой, и т.д.)

соответственно, надо дедупить, матч/мёржить и автокорректить. сложность, как очевидно, О(n*n) от размера данных. гм... может, не очевидно - поясняю. данные, которые мы получаем, уже покрывают практически каждый бизнес в штатах; большинство бизнесов - несколько раз. дальнейший рост размера данных будет происходить за счёт увеличения оверлапа.

[anatolix.livejournal.com]

Ну во первых идя которую ты описал она все-таки не про online запросы.

Во вторых не совсем понял логику, я правильно понимаю что ты исходишь из того, что тебе придется сравнить все entity со всеми? А помоему это совершенно излишне - мы такую штуку написали для кластеризации музыки(то же самое - есть иерархически организованные данные артист-альбом-трек, названия все похожи но с ошибками/добавками/бонус треками). Отлично кластеризуется по шинглам, без сравнения каждого с каждым.

[109.livejournal.com]

нет, конечно не со всеми. сравниваем с маленьким сабсетом, размер которого, тем не менее, пропорционален произведению суммарного количества данных на долю дупликатов. то есть N*N.