линейная масштабируемость
Feb. 21st, 2008 11:53 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
109в продолжение.
откуда вообще взялся странный миф, что любая произвольная система должна линейно масштабироваться? это же всё равно что сказать, что для любой задачи должно существовать решение алгоритмической сложности O(N).
откуда вообще взялся странный миф, что любая произвольная система должна линейно масштабироваться? это же всё равно что сказать, что для любой задачи должно существовать решение алгоритмической сложности O(N).
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2008-02-21 08:33 pm (UTC)Но давай я попробую показать на пальцах, что значительная часть _уже_ _существующих_ систем _обрабатывающих_ _online_ _запросы_ обладает свойством, что количество запросов в секунду _обычно_ можно линейно масштабировать количеством машин.
Под "online запросами" понимаем что-нибудь очень быстрое типа отдачу web страницы, или транзации по кредитке - типа десятые доли секунды или меньше.
Во-первых если система выдерживает 1M запросов в секунду то она обычно либо масштабируется линейно(в крайнем случае как n*ln(n) или похожие сложноси) либо не существует. Т.к. при масштабировании как O(n*n) сейчас столько машин ни у кого нет.
Во вторых, достаточно легко показать, что системы имеющие вид read only масштабируются линейно, нужно рядом поставить второй кластер и на него перенаправить половину запросов.
Точно-так же показывается, что системы которые выполняют простую запись данных(форум, лог счетчика, база транзакций) примерно так же масштабируются. Правда для этого нужно обладать возможностью линейно порезать данные пользователей, и внутри запрос перекинуть в нужное место - ну и пусть.
Что не масштабируются так это запросы на массовую обработку данных, типа создать отчет по всем записям которые юзер наплодил, но это уже кончено обычно делапется не online.
Не масштабируются многие числомолотилки - но вообщем ни у кого из нормальных людей не возникает желание создать кластер для решения задачи коммивояджера в лоб.
Это конечно не закон никакой, но очень значительное количество находящихся сейчас в эксплуатации систем принипиально масштабируются линейно(но не факт, что это делают все реализации).
P.S. кстати можешь вспомнить какой нибудь реальный алгоритм которые регулярно отрабатывает на больше, чем на 1000 машин и имеет сложность как минимум n*n и находится в условиях экспоненциального увеличения данных в зависимости от роста интернета например?
(no subject)
Date: 2008-02-21 10:04 pm (UTC)(no subject)
Date: 2008-02-21 10:28 pm (UTC)Поддерживая дискуссию, однако, надо заметить, что любая система масштабируется с вероятностью 0.5 : либо масштабируется, либо - нет :)
(no subject)
Date: 2008-02-22 09:07 am (UTC)(no subject)
Date: 2008-02-22 10:38 pm (UTC)кстати можешь вспомнить какой нибудь реальный алгоритм которые регулярно отрабатывает на больше, чем на 1000 машин и имеет сложность как минимум n*n и находится в условиях экспоненциального увеличения данных в зависимости от роста интернета например?
мнэ... может не в точности что ты спрашиваешь, но вот один из моих проектов. есть у нас local entity feeds. local entity - это что угодно, имеющее координаты. магазин, ресторан, человек, мост через речку. feeds поступают как от фирм, продающих эти данные, так и от кроулинга интернета.
проблемы: 1. есть существенное перекрытие в данных и 2. данные не идеальны (где-то телефон неправильный, где-то название с ашипкой, и т.д.)
соответственно, надо дедупить, матч/мёржить и автокорректить. сложность, как очевидно, О(n*n) от размера данных. гм... может, не очевидно - поясняю. данные, которые мы получаем, уже покрывают практически каждый бизнес в штатах; большинство бизнесов - несколько раз. дальнейший рост размера данных будет происходить за счёт увеличения оверлапа.
(no subject)
Date: 2008-02-22 10:40 pm (UTC)(no subject)
Date: 2008-02-22 10:41 pm (UTC)(no subject)
Date: 2008-02-22 11:01 pm (UTC)---
Во-первых, допускается O(n log n), но это уже было сказано.
Во-вторых, мне как-то прям неудобно появляться среди таких зубров, но всё-таки: правильно говорить что для любой _решаемой_ задачи решение должно себя так вести. Иначе она нерешаемая, точка. Частные случаи решаемы, а сама задача -- нет. И это тоже, в общем, уже было сказано, даже не знаю, зачем я это повторяю...
(no subject)
Date: 2008-02-22 11:11 pm (UTC)Если у тебя есть n вещей, которые ты хочешь обработать, то у тебя, наверное, есть и q*n компов, которые это будут делать, где q это некий коэффициент, зависящий от того, сколько тебе платят за одну обработанную вещь. Понятно, что логарифм туда легко впихивается, потому что с n > 2^64 мы ещё очень долго не будем работать, а если этот стрёмный момент когда-нибудь и наступит, то уж до 2^128 мы не дойдём никогда. Маленькие константы. Они значат, конечно, это ведь разы в конце концов, но не такие уж и большие.
Ну так вот, в результате либо либо твоя задача линейно-логарифмически скейлиться, либо ты перестаёшь её считать как только она становится нерентабельной (впрочем, для некоторых задач ты можешь надеяться, что они никогда до этого момента не дорастут, но стоит ли ими тогда заниматься?)
(no subject)
Date: 2008-02-22 11:27 pm (UTC)(no subject)
Date: 2008-02-23 11:17 am (UTC)Во вторых не совсем понял логику, я правильно понимаю что ты исходишь из того, что тебе придется сравнить все entity со всеми? А помоему это совершенно излишне - мы такую штуку написали для кластеризации музыки(то же самое - есть иерархически организованные данные артист-альбом-трек, названия все похожи но с ошибками/добавками/бонус треками). Отлично кластеризуется по шинглам, без сравнения каждого с каждым.
(no subject)
Date: 2008-02-23 09:09 pm (UTC)(no subject)
Date: 2014-01-06 09:06 am (UTC)