Comments 65
Где-то я уже писал, что есть определенное не понимание, когда нормальный инженерный подход начинают называть преждевременной оптимизацией. Подумать над кодом и его маштабированием заранее не является примером преждевременной оптимизации. Особенно если код после этого не усложняется ибо нет ничего хуже "неоптимизированного" написанного за пять минут кода, который на самом деле является просто примером применения парадигмы "фигаг фигаг и в продакшен".
Короче говоря уж очень часто запретом на оптимизацию прикрывают собственную некомпетентность.
нет ничего хуже "неоптимизированного" написанного за пять минут кода
Если этот код приносит или экономит деньги, то с точки зрения бизнеса лучше сначала в продакшен, а потом думать над оптимизациями. Вот сейчас сижу и думаю, насколько повысится производительность от смены Rest-like на GraphQL, сколько времени это займёт, а деньги бизнесу от Rest уже идут.
Если этот код приносит деньги, то его действительно выгодно быстро вкинуть в продакшен, но потом, немедленно начать разбираться с тем техническим долгом, который с ним связан. Иначе, спустя годы, будет очень дорого его пытаться оптимизировать.
Пример с GraphQL не вполне отражает тот случай о котором я говорю. Сменить один API на другой может быть очень сложным и дорогим удовольствием.
Я скорее о очевидных, мешающих производительности и маштабируемости мелочах: например хранить картинки в SQL базе, а не на файловой системе или S3, или его подобии, использовать базу данных, но хранить настройки в конфиг файле (а потом применять pupet, для обновления этого конфига :D), хранить одну и ту же информацию (настройку) в трех четырех разных конфигах, использовать JQuery ради одной мелкой фичи, раздражая пользователя долгой загрузкой, не делать индексы на таблице "ведь она никогда не вырастет!" и т.д. Такие мелкие "оптимизации", если их не провести перерастают в огромную проблему, поэтому их надо решать как можно быстрее. Как только макет доказал свою работоспособность от этих проблем надо избавляться, а не ждать когда это станет заметно.
Как мне кажется точный список этих инженерных особенностей приходит только с опытом. А умение заранее увидеть в коде узкие места является очень ценным скилом, который позволяет экономить огромные суммы денег.
Кстати, а что не так с хранением картинок в SQL базе?
Очень плохо масштабируется: большой объем, зачастую низкий рейт использования, рост времени бэкапа и восстановления из него. Дело в том, что базу зачастую нельзя восстановить куском, она либо целая и работает, либо не работает вся. А главное в этом нет смысла, ибо задачи выборки картинки по её содержимому обычно не стоит (в отличии от метаинформации, которую стоит хранить в базе). Если картинка потом отдается на веб, то её лучше сразу хранить в неком пригодном для запроса из браузера виде, например в CDN сети.
Но с другой стороны, храня картинку в базе, мы сразу же получаем:
Транзакционность и согласованность с другими данными! Убирается сразу же целый пласт проблем.
Бэкапы. Софт для инкрементальных бэкапов файлов надо еще отдельно найти, (купить), поставить и настроить. Для СУБД бэкапы настраиваются более очевидным способом.
Разграничение доступа. К конфиденциальному файлу на CDN не так-то и просто ограничить доступ, самое простое решение — генерировать криптостойкое имя файла и закрывать его от индексирования поисковиками, и все равно специалисты по безопасности будут над таким решением смеяться. Более сложные решения завязаны на конкретные CDN...
Картинка, лежащая в БД, отдается сервером приложений — и там-то авторизацию прикрутить не проблема.
Да, такие проблемы есть, но тут надо решать: сложнее писать или сложнее эксплуатировать. Я, как админ, даже термин специальный придумал: "написано программистами", т.е. невозможно экслуатировать легко, без проблем и за недорого.
3. Как связаны CDN, конфеденциальные файлы, и хранение файлов в базе? Три разных вещи в одном странном предложении.
По последнему, вот вам куда более разумное решение:
Картинка лежащая в файловой системе отдаётся веб сервером, с помощью x-accel-redirect какого-нибудь, после авторизации, или ещё чего-либо обрабатываемого приложением.
Быстро, и масштабируется куда проще чем БД для хранения картинок.
3. Я же писал. Из базы файл достается сервером приложений и доступ к нему проверяется не сложнее чем к любой другой странице.
Файлы отдаются веб-сервером, который более ограничен в вопросах авторизации.
Про CDN я писал потому что выше мне его для файлов советовали. И так с авторизацией еще сложнее.
Не спорю, все эти проблемы — решаемые. Но на их решение требуется время, которого всегда не хватает.
Файл так же может доставаться сервером приложений с диска и доступ к нему проверяется не сложнее чем к любой другой странице. Кстати ещё один плюс для хранения картинок в памяти — файл может легко отдаваться потоком прямо клиенту, без предварительного чтения всего в память, про СУБД же про такие механизмы не слышал, чтобы конкретное поле запроса отдавалось потоком. А это могут быть гигабайты от одного показа странички с десятком-другим картинок по 100 метров. Их сначала надо выбрать в память СУБД, потом передать в память апп-сервера. И даже если СУБД как-то оптимизирует процесс отдачи блобов, то вряд ли легко получится стримить их на веб-сервер через апп-сервер.
про СУБД же про такие механизмы не слышал, чтобы конкретное поле запроса отдавалось потоком
MS SQL — FILESTREAM.
Не очень хорошо знаю современную продукцию этой фирмы, но разве это не о способе хранения блобов? Разве обычным селектом не блоб будет отдаваться, всё равно?
Обычный SELECT отдаст блоб. Но если в запросе использовать функцию PathName — она вернет сетевой путь к файлу.
Обычным селектом отдастся блоб, но есть несколько вариантов получить напрямую поток.
Я настолько часто встречал совет "да храни ты все в файлах и раздавай напрямую веб-сервером" — что и забыл что файлы можно считывать сервером приложений :) Да, признаю, такой "переходный" вариант имеет право на жизнь.
Тем не менее, вы согласны с тем, что хранение картинок в файлах — это именно оптимизация, и она может оказаться преждевременной (если, к примеру, аудитория веб-приложения — 10 однопальцевых операторов)?
Очевидное — база раздувается, усложняется её обслуживание (те же бэкапы). Особенно заметно, если под базу ради быстродействия выделяются дорогие быстрые диски — разница по цене между, например, сотней гигов и терабайтов сильно заметной может быть. А к хранению картинок обычно требования не такие жёсткие, как к, например, финансовому балансу пользователя.
Картинкой может быть и скан квитанции. С тем самым финансовым балансом пользователя...
Если есть жёсткие требования к согласованности картинок и остальных данных, то вариант с хранением их в базе приходится рассматривать, увы. Но в целом, обычно, по моему опыту, складывание их в базу по умолчанию приводит к бОльшим проблемам со временем, чем в ФС. Вернее не конкретно в ФС, а в отдельное от более важных данных хранилище. Одна база с основными данными и другая с картинками, возможно на разных серверах — нормальный вариант, если накладные расходы устраивают.
Никакой проблемы со сканом нет. Важен факт его наличия, который можно отметить в базе, а на картинку можно сказать, что временная проблема, щас все будет, админу уже прописали люлей.
Как раз сила здесь в отсутствии согласованности. Сила базы (не говоря даже о sql) в том, что она хранит все согласовано, поэтому она так хороша для финансовой информации (приход, расход, движения денег по счетам). Я понимаю, что можно вообразить ситуацию, когда нужны согласованные действия с картинкой, но я такого не видел, а вот запихивания не очень важных, вспомогательных вещей (типа квитанций) в базу, это сколько угодно.
Мне пришлось эксплуатировать базу данных размером 10T, в которой на картинки проходилось 99%. Это был ад. И очень, просто ну очень дорогой ад. Чтобы уложится в норматив по бэкапу и восстановлени туда надо был подпихивать очень дорогой сторадж (одной почкой разработчика тут бы не обошлось).
Пожалуйста, прочитайте мой комментарий еще раз. Проблема скана квитанции — вовсе не в согласованности...
Ну значит я это совершенно не понял.
Я отвечал на вот это:
А к хранению картинок обычно требования не такие жёсткие, как к, например, финансовому балансу пользователя.
Скан квитанции — это картинка, которая содержит конфиденциальные данные пользователя. В частности, баланс его лицевого счета на определенную дату.
Соответственно, и требования к защите тут "финансовые", а не "картиночные". В частности, заливка скана квитанции на CDN почти наверняка нарушит уйму требований регулирующих органов.
Ну CDN, конечно не для скана квитанции. Я даже не вижу смысла это обсуждать. Да acl поддерживающая прослойка нужна, куда же без неё, но это очень простой к реализации вопрос.
Я не конфиденциальность данных имел в виду, а именно транзакционную целостность. Скажем, что если оплата на 1000 рублей есть в базе, то обязательно должен быть скан квитанции на оплату. Конфиденциальность хранения картинок в базе не требует, даже если требуется сильная авторизация. Причём сама авторизация будет одной и той же в обоих случаях, что в базе, что ещё где хранить.
Некомпетентность компенсируются мощью поисковых машин при наличии сомнений и желания, чаще этим запретом манипулируют менеджеры, а не инженеры.
Как быть тогда?
Странные какие-то исследования...
https://blog.kissmetrics.com/speed-is-a-killer/
Тем не менее, порог "работает достаточно быстро" — есть.
Так, мировой рекорд скорости печати — 750 знаков в минуту — означает что задержка отклика в 80 миллисекунд даже при самом быстром наборе текста будет означать запаздывание всего в 1 символ. Половина от этого значения, 40 миллисекунд, заметна не будет уже совсем. Другие же виды деятельности налагают на время отклика еще меньше ограничений.
Несколько штрихов:
У внешнего пользователя, т.е. у человека есть границы восприятия, быстрее которых нет смысла оптимизировать (например https://www.nngroup.com/articles/response-times-3-important-limits/). Границы меняются с адаптацией человека к технологиями и эволюцией человека, но всё же они есть — т.е. не каждое увеличение быстродействия будет замечено.
У бизнеса ориентированного на пользователя тоже нет смысла улучшать бесконечно, потому что у продукта который он предоставляет пользователю есть 3 состояния качества — лучше чем у конкурента, хуже чем у конкурента и так же как у конкурента. Если уже лучше — то зачем тратить деньги кроме пиара, если хуже — то вопросов нет, если так же, но есть другие преимущества — то тоже особо нет смысла.
И конечно же у каждого бизнеса разные возможности, поскольку улучшение от 15 до 10 секунд стоит одних денег, от 10 до 3 секунд других денег и от 3 до 1 секунд — третьих денег.
Есть ещё одно, и очень важное — настолько хорош, что им начинают пользоваться даже те, кто раньше не пользовались.
Но поскольку необходимы результаты, а не бесконечное стремление к идеалу — даже в таких условиях будут какие-то необходимые и достаточные для внедрения на прод требования по производительности, на которые надо ориентироваться.
Оценить стоимость оптимизации (или хотя бы оценить оценку стоимости оптимизации :) и планируемое "хорошо для бизнеса". Не забыть про то, что может текущие задачи на новую функциональность и багфиксы принесут больше денег чем трата ресурсов на оптимизацию.
Вообще, с точки зрения обычного (с ограниченными ресурсами) бизнеса есть три метрики необходимости каких-то движений, будь то открытие нового завода или замены одной сортировки на другую:
- ресурсы, которые надо на это движение потратить
- прибыль, которую это движение принесет (частая подметрика — срок окупаемости)
- прибыль, которую принесут другие движения, на которые можно потратить эти ресурсы (от направления разработчиков на багфиксинг до разгона разработчиков и покупки коробки, а то и вообще закрытия бизнеса и покупки акций Теслы)
любое увеличение быстродействия делает пользователя более довольным, а значит хорошо для бизнеса.— Очень уж светлый и радужный вариант, который на самом деле под вопросом, потому как «довольный пользователь» — совсем не значит «прибыльный пользователь».
В качестве контрпримера могу назвать случай, при котором снижение быстродействия может улучшить дела бизнеса: увеличение времени отклика страниц пополнения счёта на сайте увеличило сумму разового пополнения баланса — то есть средства раньше переходили от клиента к бизнесу — получателю.
Пример читал скорее всего на хабре, но ссылку на статью найти не могу, общая суть статьи — пытаемся увеличить скорость загрузки страниц на сайте и посмотреть — что же будет.
Что проще и менее затратно:
1. Выделить небольшой диск под БД.
2. При росте БД докупить диск побольше, смигрировать БД на неё.
или
1. Сразу выделить диск с запасом.
Или более жёсткий пример, но тут не про ПО:
1. Построить сеть на 100 мегабит
2. Когда станет не хватать, переделать под гигабит.
Там хорошо поделены все они на
- зелёную зону — упрощаем код, делая его лучше как с точки зрения читаемости, так и с точки зрения перформанса за счёт использования хороших алгоритмов из стандартных библиотек и т.п.
- жёлтую зону — когда пишется понятный, но многословный код для повышения производительности
- красную зону — грязные хаки, использование непубличного API и обход багов платформы.
Если оптимизация из зелёной зоны- она хороша всегда. И никогда не будет преждевременной. Убрать лишние абстракции, странные наследования, использовать оптимизированную библиотеку вместо самописного костыля (или просто заменить библиотеку от apache на аналог от google) и т.д. и т.п.
Жёлтой- только если иначе нельзя, когда «зелёная» не помогла, а проблемы остались. Это может быть преждевременно.
Красная- «если Вы это читаете, значит Вам этого делать нельзя». Это всегда плохо. Но редко нужно (чем чаще- тем хуже платформа).
Допустим, что нам нужно написать программу, которая должна обработать 100 записей и уложиться в 2 секунды. В ходе разработки мы придумали некий алгоритм, временная сложность которого O(n^2).
У вас дальше неправильно, правильно примерно так:
У вас есть 2 сек\100 записей = 2000/100 = 20 мсек в среднем на обработку одной записи.
Но если количество записей для обработки увеличится в 2 раза, то время на обработку увеличится в 4 раза.
Количество записей увеличится в 10 — время в 100 раз.
Сложность говорит о росте времени работы алгоритмов при росте количества элементов, но ничего не говорит про время обработки.
Если один элемент обрабатывается за 10 секунд — это ничего не значит.
Но:
Если один элемент обрабатывается за 10 секунд, и 20 элементов за 10 секунд, то это O(1)
Если один элемент обрабатывается за 10 секунд, а 20 элементов за 200 секунд, то это O(n)
Если один элемент обрабатывается за 10 секунд, а 20 элементов за 4000 секунд, то это O(n^2)
Вы подтверждаете, что сложность описывает связь между количеством элементов, временем обработки одного элемента и временем обработки всех элементов. Задача, которую я рассмотриваю в этой статье — обратная. Т.е. исходя из ограничений на время обработки всех элементов, и зная количество элементов определить ограничение на время обработки одного элемента. Вы же не будете отрицать, что 4000/20^2=10?
Сложность говорит не только о росте, поскольку время обработки алгоритма O(n) и O(n^2) всё-таки сильно отличается при одном и том же значении n — как раз по той причине, что нужно сделать выполнить больше операций над одним и тем же количеством элементов.
Сложность n^2, 2 секунды и 100 элементов дает нам только время на обработку «20 мсек». Причем тут 0,2 мсек.
Даже если сложность n!, все равно при «2 секунды и 100 элементов» у вас «20 мсек» на запись.
Сколько будет выполнений внутреннего тела цикла в примере ниже? 100 или 10000?
int count = 0;
int n = 100;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
count++;
}
}
Вы к сложности алгоритма притягиваете еще какие-то дополнительные обходы.
Лучше перестану отвечать, у меня будет «бомбить и пригорать».
А вы останетесь при своем мнении.
Действительно, стоит прекратить дискуссию, раз вы не готовы аргументировать свою позицию и искать точки соприкосновения.
Внутренний цикл имеет отношение к сложности, а не к количеству элементов.
Почитайте про сложность, и не додумывайте в стиле «я так думаю\мне кажется».
В моём примере выше выполнений цикла 10000, и если нам нужно чтобы весь цикл выполнился за 2 секунды на одно выполнение цикла в среднем сколько получится?
Например, википедия:
Временная сложность алгоритма (в худшем случае) — это функция от размера входных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.
Т.е. если мы подставим в функцию временной сложности размер входных данных (в рассмотренном мной случае он известен из требований), то получим максимальное количество операций (в худшем случае). Тут сложность заканчивается. Далее, зная требуемое время выполения и кол-во операций можно посчитать требуемое время выполнения одной операции в среднем.
Допустим, что нам нужно написать программу, которая должна обработать 100 записей и уложиться в 2 секунды. В ходе разработки мы придумали некий алгоритм, временная сложность которого O(n^2).
В таком случае у нас есть 2/100^2=2*10^-4 секунд (0,2 миллисекунд или 200 микросекунд) в среднем для обработки каждой записи
а должно быть так
В таком случае у вас есть 2/100=20 миллисекунд в среднем для обработки каждой записи
Если у вас массив в 100 элементов и у вас O(n^2), то это не значит что вы должны обработать и учитывать время на 10.000 элементов. Это значит при изменении количества элементов (которых изначально было *100*) время будет ограничиваться сверху как квадрат отношения количества изначальных элементов.
Станет не 100, а 300 элементов. Алгоритм может начать укладываться в 18 секунд (2*(300\100)^2)
Все просто же )
Сложность нужна для того что могли оценить «так, вот на таком количестве скорость ок, но в определенный момент» скорость резко упадет.
Для примера напишите программу на c# которая будет к строке добавлять тысяч 50.000 слов.
что-то вроде
string s = "init string";
for (int i = 0; i < 50000; i++)
{
s = s + i.ToString();
}
Этот пример «плохой». Но показывает сложность конкатенации иммутабельных строк и необходимость StringBuilder-а
Т.е. при количестве добавляемых чисел, например, до 100 все будет ок. Но в определенный момент скорочть резко упадет. Из-за аллокации памяти под новую строку и копирование данных туда-сюда.
посмотрите
https://habrahabr.ru/post/195996/
https://habrahabr.ru/post/104219/
https://habrahabr.ru/post/188010/
Я согласен и не спорил с вами по поводу
Если у вас массив в 100 элементов и у вас O(n^2), то это не значит что вы должны обработать и учитывать время на 10.000 элементов
Я согласен, что
Сложность нужна для того что могли оценить «так, вот на таком количестве скорость ок, но в определенный момент» скорость резко упадет.
На нём в общем-то всё и завязано в статье — т.е. на выяснении того, что на требуемом нам количестве скорость ок, или не ок.
Я пытался донести, что подразумеваю под «обработкой записи» наиболее практический аспект обработки записи — «элементарную операцию» (тут можно отдельно закопаться), количество которых можно рассчитать с помощью функции сложности.
Я намеренно упростил этот момент, и я не вижу смысла усложнять его обратно введением «элементарной операции» вместо «обработки записи».
Думаю стоит добавить отдельную оговорку про среднее время на обработку записи в рассматриваемом мной контексте.
В таком случае вопрос будет исчерпан?
Практическая рекомендация: на соревнованиях алгоритмы часто реализуются на С++. Как только вы проанализировали сложность вашего алгоритма, так сразу можете получить и грубую оценку того, как быстро он будет работать, приняв, что в секунду выполняется 1 000 000 команд. Их количество считается из полученной вами функции асимптотической оценки, описывающей алгоритм. Например, вычисление по алгоритму с Θ( n ) займёт около секунды при n = 1 000 000.
Но в определенный момент скорость резко упадет. Из-за аллокации памяти под новую строку и копирование данных туда-сюда.
Я вот не очень разбираюсь в сложностях, но мне почему-то кажется, что пространственная аллокация памяти с временной сложностью самого алгоритма никак не связана. А скорость не "резко упадет", а по вполне определенному закону. Который и написан в скобочках. И который показывает количество элементарных операций, которые, собственно, и занимают время.
Своевременная оптимизация