company_banner

Как инкрементальные обновления влияют на скорость загрузки. Опыт Яндекс.Почты

    Яндекс.Почта — большое и сложное веб-приложение. Для первоначальной загрузки ей необходимо более 1 МБ статических ресурсов (JS/CSS/Шаблонов). При этом Яндекс.Почта обновляется два раза в неделю, а иногда и чаще.

    Но при обновлениях от версии к версии меняется не так много кода — особенно в случае хотфиксов. Это показывают и фризы. Чтобы снизить время загрузки почты при выходе новых версий, мы уже делаем следующее:


    Но этого нам недостаточно. Даже при фризе, если в релизе меняется всего один файл, в котором несколько строк, хэш от контента этого файла меняется и кэш инвалидируется, следовательно файл перезакачивается целиком. Чтобы избежать этой проблемы и еще более эффективно грузить новые ресурсы, мы придумали механизм инкрементальных обновлений.

    Мы подумали: «А что если хранить где-то старую версию файлов (например, в localStorage), а при выходе новой передавать только diff между ней и той, которая сохранена у пользователя?» В браузере же останется просто наложить патч на клиенте. О том, что из этого получилось и каким выводам мы с Panya пришли, читайте под катом.

    На самое деле эта идея не нова. Уже существуют стандарты для HTTP — например, RFC 3229 “Delta encoding in HTTP” и Google SDHC, — но по разным причинам они не получили должного распространения в браузерах и на серверах.

    Мы же решили сделать свой аналог на JS. Чтобы реализовать этот метод обновления, начали искать реализации diff на JS. На популярных хостингах кода нашли библиотеки: VCDiff, google-diff-patch-match, jsdiff, Pretty Diff и jsdifflib.

    Последние две библиотеки (jsdifflib и Pretty Diff) нам сразу не подошли, потому что не умеют накладывать патч, а показывают только изменения между строками. А jsdiff генерирует патч в формате, похожем на google diff patch match, но накладывает его в пять раз медленнее. В итоге у нас осталось два кандидата.

    Для окончательного выбора библиотеки нам нужно сравнить их по двум ключевым для нас метрикам. Первая — размер генерируемого патча. Мы нагенерировали патчей для разных ресурсов разных версий и сравнили google diff patch match и vcdiff с разным размером блока.

    Vcdiff (размер блока 3) Vcdiff (размер блока 10) Vcdiff (размер блока 20) google diff patch match
    13957 3586 3431 9297
    865 367 309 910
    4615 1854 1736 6740


    Как видно по таблице результатов, vcdiff с размером блока 20 байт имеет наименьший размер патча. Вторая ключевая метрика для нас — время наложения патча на клиенте.

    Библиотека IE 9 Opera 12 Firefox 19 Chrome
    vcdiff (размер блока 10) 8 5 5 3
    google diff patch match 1363 76 43 35


    Тут тоже vcdiff выигрывает c большим отрывом. В IE 9 и ниже google-diff-patch-match накладывает патч больше, чем за секунду.

    У нас определился победитель — vcdiff. Этот алгоритм был предложен в 2002 году (RFC3284). Он достаточно популярен и имеет множество реализаций на разных языках, в том числе на C++, Java и JS.

    После того как мы определились с библиотекой для диффа, нужно определиться с тем, где и как хранить статику на клиенте. Яндекс.Почта — современное веб-приложение, у нас нет старых браузеров, поэтому почти все поддерживают localStorage. Он является удобным местом для хранения статики. Никаких личных данных пользователя там нет, поэтому нет проблем с безопасностью. Каждый файл хранится в отдельном ключе. В этот ключ вшито не только название ресурса, но и его версия. Это позволяет избежать проблем, когда версия смогла записаться в localStorage, а сам файл — нет (или наоборот), в варианте, когда файл и его метаданные хранятся в разных ключах.

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

    Формат файла с патчами для проекта выглядит так:
    [ { "k": "jane.css", "p": [patch], "s": 4554 }, { “k”: “jane.js”, “p”: [patch], “s”: 4423 }, ...]

    То есть это обычный массив из объектов. Каждый объект — отдельный ресурс. У каждого объекта есть три свойства. «k» — названия ключа в localStorage для этого ресурса. «p» — патч для ресурса, который сгенерировал vcdiff. «s» — чексумма для ресурса актуальной версии, чтобы потом можно было проверить правильность наложения патча на клиенте. Чексумма вычисляется по алгоритму Флетчера.

    Почему именно алгоритм Флетчера, а не другие популярные алгоритмы вроде CRC16/32 или md5? Потому что он быстрый, компактный и легок в реализации.

    Процесс обновления


    В самом начале загрузчик смотрит в localStorage. Если у пользователя в нем ничего нет или версии настолько старые, что у нас для них нет патчей, то загружаются все файлы целиком.

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

    На этом процесс обновления закончен. Дальше все необходимые ресурсы мы берем из localStorage. Код JS-модулей и скомпилированных шаблонов мы выполняем через new Function(), а CSS подключаем через динамическую вставку тега .

    Что получили


    Фактически мы экономим 80-90% трафика. Размер загружаемой статитки в байтах:
    Релиз С патчем Без патча
    7.7.20 — 7.7.21 397 174 549
    7.7.21 — 7.7.22 383 53 995
    7.7.22 — 7.8 18 077 611 378
    7.8 — 7.8.50 2 817 137 820
    7.8.50 — 7.8.8000 14 868 443 159


    Что же мы получили в реальности?


    В реальности скорость загрузки выросла совсем немного. Почему так?

    У нас сразу появилась проблема с проверкой чексуммы. Считать его для всего файла оказалось очень дорого. Даже в современных браузерах на мощных компьютерах на один файл уходит примерно 20мс, а в Opera 12 и IE9 — более 100мс. Для загрузки Почты надо минимум шесть файлов. С учетом того, что JavaScript в браузере — однопоточный, то получаем последовательный расчет хеша для каждого файла, то есть в лучшем случае это будет минимум 120мс, а в реальности — еще больше.

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

    Проблема усугубляется еще и тем, что, скажем, валидность JS мы можем проверить просто исполнив его. Если полученный JS не запускается, то патч не прошел — надо все стирать и перезагружать. А вот с CSS проблема остается открытой. Невалидный CSS просто исполнится, не вызовет никаких ошибок, но пользователь увидит не то (у нас даже были такие случаи). Да, можно дописать валидатор CSS после его исполнения, но это опять же повлияет на скорость загрузки — по аналогии с хешсуммой.

    Еще есть проблема со слишком большими патчами. Мы ограничили размер патча 30% от исходного файла. Если патч получается слишком большим, то браузер загружает весь файл целиком. И в итоге с этой схемой мы получили блокирующий HTTP-запрос. Рассказать заранее, с каких версий можно обновляться, а с каких — нет, мы не можем, потому что информация о кеше в браузере. Соответственно, наш загрузчик понимает, что есть кеш и идет за патчами. В этот момент ничего больше не грузится. Если в патчах сказано «грузи все полностью», то загрузчик начинает обычный процесс загрузки, как будто нет кешей, но время уже потеряно.

    По сути патч VS. скачивание файла — это соревнование между скоростью браузера и скоростью подключения к интернету. Если смотреть на мировые тенденции в этом размере, то компьютеры не становятся быстрее. Наоборот, мощные стационарные компьютеры заменяются планшетами и ноутбуками, которые не обладают той же производительностью. В то же время интернет становится быстрее, причем обычно бесплатно. Обновляются тарифы провайдеров, которые строят сети нового поколения.

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

    Итог


    Мы поняли, что ни на какие 146% загрузку почты таким способом не ускорить. А лишнюю головную боль как разработчикам, так и тестировщикам получить легко — появляется еще один способ загрузки страницы, который надо проверять для каждого релиза. В то же время фризы и грамотное деление кода на модули дает понятный и абсолютно безопасный, с точки зрения тестирования и поддержки, способ ускорения.

    Кстати, в HTTP/2 хотели включить механизм, похожий на RFC3229, но в последних версиях спецификации его убрали. В итоге эксперимент с инкрементальным обновлением мы признали неудачным и решили от него отказаться. Теперь ждем встроенной поддержки такого механизма в браузеры.
    Яндекс
    Как мы делаем Яндекс

    Comments 73

      +38
      Отличный пример ситуации «быстрее снова скачать, чем найти куда сохранил».
        –1
        Я вижу, что вы тестируете в старой Opera 12. Не думаете отказаться от поддержки устаревающего браузера? У вас есть статистика о том, сколько людей всё ещё им пользуются?
          +17
          Конечно у нас есть такая статистика :)
          Opera 12.x у нас самая популярная из всех Опер, где-то 7%
            +10
            Спасибо, что не забили на мой любимый браузер, как некоторые :)
              0
              7% от всех браузеров или 7% среди разных версий Opera?
            0
            В проекте DynoSRC, в рамках Node Knockout 2013 была реализована часть описанного функционала, посмотреть можно здесь и здесь.
              0
              Интересно, почему google diff patch match на IE 9 так медленно работает?
                +2
                В IE не очень быстрая работа со строками
                  0
                  +1

                  Желательно массивом строки сначала отмапредьюсить, а уж потом с ними общаться. Так точно быстрей. Но уж очень мозгоёмко. Оптимальные размеры 1-8 Кб.
                –5
                Кстати о мобильной версии Яндекс.Почта: после последнего обновления Яндекс.Почты на Андройд (4.4.3) телефон HTC One телефон постоянно находится в режиме «синхронизации», аккумулятор разряжается в ноль за 2-3 часа. Спасает только удаление приложения из телефона. Это я к тому, что перед выпуском обновлений надо их сперва тщательно тестировать.
                  0
                  Интересно, как выглядит diff для однострочного css файла? Или вы не минифицируете их?
                    0
                    Минифицируем конечно, но там же не построчный дифф :)
                      0
                      Что-то я даже не допустил такого варианта :)
                    +6
                    Очень радует что вы проводите подобные эксперименты.
                      +3
                      Да, и самое хорошее, что любые идеи мы можем проверить в реальной жизни на многомиллионной аудитории.
                        0
                        Совмещение научно-теоретической деятельности с практической.

                        Кстати, это в Питерском офисе?
                          0
                          В том числе и в Питерском :)
                      +1
                      С учетом того, что JavaScript в браузере — однопоточный

                      Web workers не пробовали?
                        +5
                        Для этой задачи пока не пробовали. Но у нас уже появляются идеи для второго подхода к снаряду )
                          0
                            +2
                            В порядке бреда… Вроде бы последние версии браузеров умеют криптографию. И, получается, умеют её нативно, а значит очень быстро. Вы чек-суммы вычисляли js-способом?
                              +1
                              Это совсем недавно появилось и почти нигде еще не поддерживается. Нужно тестить, но да, это бы нам сильно помогло.
                                +2
                                сrypto.subtle, где есть метод digest появился недавно, кажется этим летом. В Fx он до сих «This is an experimental API that should not be used in production code.»
                                Ну и главная проблема с чексуммами была в старых браузерах, а не в новых. Поэтому и реализовали это на JS быстрым Флетчером.
                          –3
                          Зачем вы сменили адреса для почты для домена?
                          Было mail.yandex.ru/for/мой домен/neo2/ теперь mail.yandex.ua/neo2/

                          У меня есть почта для двух адресов, и теперь при переключении между ними надо каждый раз логиниться…
                            +1
                            Теперь можно делать мультиавторизацию, попробуйте. Не придется логиниться.
                              +1
                              Хмм… неплохо
                                0
                                кстати, не в курсе,
                                это
                                image
                                нормально, или ко мне adware прокралось? :)
                                  +1
                                  Нормально, вы попали в эксперимент.
                                    0
                                    Ну вот тогда вам сразу фидбек, показывайте как-то что это ваше, а не от вируса рекламного или еще откуда-то, ну переход какой-то визуальный сделайте, например. В текущем виде немного нервирует :) (был разок adware, выглядел один-в-один так же(внезапно появляющийся с какой-то стороны рекламный блок))
                                    0
                                    Уже давно: blog.yandex.ru/post/83889/
                                  • UFO just landed and posted this here
                                      0
                                      «Приватные» вкладки, не?
                                      • UFO just landed and posted this here
                                          +1
                                          В каком браузере приватные вкладки изолированы друг от друга (т.е. каждая имеет свой набор кук/local storage/etc)?
                                          Хотя, если одна приватная, а вторая — обычная, то должно работать.
                                    0
                                    Как часто (и по каким причинам) были ошибки чексуммы? Ведь версия файла известна, патч получен (если он пришёл битый, то всё очень плохо и даже чексумма не поможет), процесс наложения патча не такой сложный (ну то есть если работает, то работает)… Или проблема в не отловленных багах?
                                      +1
                                      Да, проблема именно в багах. Кто-то ошибся, под видом одной версии загрузили другую, например, и все такое. В итоге, это становится сильной головной болью тестировщиков.
                                        0
                                        А что если перед заливкой автоматически проводить эту проверку один раз, вместо того, чтобы на каждом клиенте её проводить? От такого рода ошибок должно помочь.
                                          0
                                          Нет, от такого рода ошибок как раз не поможет.
                                          Я говорю про такие случаи:
                                          по ошибке разработчика под видом version=1 записалась статика от version=2. Выходит version=3 и мы накладываем патч 2 -> 3, он, естественно, накладывается неправильно
                                            0
                                            То есть клиенту под видом версии 1 попала версия 2 и он накатывает патч 2->3?
                                            То есть как если бы кто-то залил новую версию, не обновив номер версии? Этого можно избежать, используя автоматическое назначение версии вместо задания вручную.
                                              0
                                              Все ошибки, конечно, можно избежать. :)
                                              Главный вопрос ведь в другом — «стоит ли игра свечь». У нас оказалось, что не стоит. Держать сложную логику ради небольшой оптимизации просто неэффективно.
                                                0
                                                У нас оказалось, что не стоит.

                                                Если я правильно понял, то основным bottleneck была проверка хэша, от которой можно было избавиться, изменив подход и сократив человеческий фактор.
                                                  0
                                                  Нет, блокирующий запрос за диффами — тоже bottleneck.

                                                  Если честно, то я склоняюсь к идее, что накладывать патчи должен браузер, так что идея с SDHC или чем-то подобным мне нравится больше.
                                      0
                                      Почему, всё-таки, не SDCH? Есть нативная поддержка в Хроме и форках, включая Яндекс.Браузер, скоро будет поддержка в Safari, активно поддерживается гуглом в своих сервисах; т.е. вам не придётся сражаться с производительностью cliend-side, целостностью, хешами и прочим — всё это уже встроено и тщательно протестировано, и от вас нужно просто сделать словарь и разложить по http сервисам. И, да, кодирование/декодирование в 400мкс — заметно меньше метрик vcdiff.
                                        0
                                        Мы, на самом деле, собираемся поэкспериментировать с SDCH. Но пока веры в его успех немного. Ведь у нас выдача очень персонализированная, т.е. у разных пользователей ответы сервера будут разными. Не очень понятно, как формировать словари. Но подробно мы этот вопрос еще не изучали.
                                          0
                                          SDCH хорошо работает на стабильных словарях. А у нас сервис с персональной выдачей. Еще есть проблема, что словарь генерируется очень долго в тех реализациях, что мы смотрели. Это нельзя делать на лету.
                                            0
                                            Технические куски html (шаблоны итп) и статики меняются не очень сильно, т.ч. словарь можно делать редко, например раз в месяц.
                                              0
                                              Мы делали прототип, у нас было все плохо
                                                0
                                                Расскажите, это интересно. У LinkedIn, например, со статикой всё получилось.
                                                  +1
                                                  Все как я описал выше, словари долго генерились и диффы были большими. Но я не отрицаю, что мы просто могли его неправильно готовить :)

                                                  А можете про LinkedIn ссылку дать почитать?
                                                    +1
                                                    Словарь генерируется действительно долго (10 часов на 1200 файлов LinkedIn), но если его менять раз в месяц, это не проблема.

                                                    Исходно это доклад на Highload 2014, видео и презентация когда-нибудь будут.
                                        • UFO just landed and posted this here
                                            0
                                            Все просто, если нет localstorage, то работает обычная загрузка
                                            • UFO just landed and posted this here
                                                0
                                                Что значит глючит?
                                                • UFO just landed and posted this here
                                              +1
                                              Ведь в LocalStorage теперь хранятся js-файлы. И если их кто-то подменит, будет фигово.

                                              LocalStorage заявляется как domain-based, то есть подменить может только тот, кто с того же домена. Но тогда с таким же успехом могут подменить и без LocalStorage, или есть какая-то магия для cross-domain доступа к LocalStorage?
                                                +3
                                                Да, все так. localstorage не шарится между доменами, а вариант его замены 3-им лицом — это уже история про вирусы.
                                                • UFO just landed and posted this here
                                                0
                                                1. почему не кэшировать хэши?
                                                2. почему не использовать для расчетов вебворкеры?
                                                3. почему бы не использовать канвас? Сунули строку как imageData, сделали какую-то трансформацию, проверили. Я бы вообще на шейдерах попробовал это сделать для ie10+, если честно.
                                                4. почему бы просто не использовать ленивую помодульную загрузку+async/defer? Условно, если открываем какое-то письмо — загружаем сначала код, связанный с письмом, остальное потом. Открываем общий интерфейс — загружаем сначала код, связанный с отображением общего списка писем
                                                  0
                                                  На 1 и 2 я ответил выше
                                                  3. А какую проблему решит canvas?
                                                  4. У нас есть модули и ленивая загрузка
                                                    +1
                                                    работа с графикой делается на уровне видеокарты -> парралельные и просто очень быстрые вычисления. Хэши очень быстро можно считать.
                                                      0
                                                      Хорошая идея, спасибо )
                                                        0
                                                        а вообще если есть желание поизвращаться — можно посмотреть на то, как на js4k оптимизируют загрузку скриптов, загружая их как png-картинку. Я не применял на практике, но с виду эффективно, но гемморойно (+определенная задержка на клиенте)
                                                      0
                                                      Работа с canvas (преобразование в нее и из нее) работает медленно. Будут большие издержки на трансформацию кода.
                                                    +1
                                                    Еще пять копеек: судя по размеру диффов, вы вполне можете их докидывать в конец HTML для клиента (зная, например, последнее время захода).
                                                    Значительные проблемы при выявлении целостности применения изменений, тут вы молодцы, что отказались. CSS селектор может посередине «порваться», а вы этого не узнаете…
                                                    Я бы делал так: накидывал бы патчи для клиентов по времени последнего захода (подразумевая, если в localStorage что-то лежит). И быструю проверку можно просто по длине делать (или по значению какого-то селектора или JS-переменной). А потом бы по onload потихоньку сверял бы checksum от всего файла с заданным. Чтобы наверняка. Или даже прогрузить полную версию в localStorage, чтобы бы без патча.
                                                    Задача очень похожа на оптимизацию изображений: «на лету» файлик в 100 Кб png оптимизировать очень тяжело. Будет проигрыш по времени: быстрее загрузить обычно неоптимизированный файл, чем его оптимизировать «на лету» и только потом отдавать.
                                                    Но в отложенном режиме в несколько потоков все отлично оптимизируется. Для последующих использований.

                                                    Соответственно, вопрос: что мешает полностью обновленную версию файлов загружать по onload (если там минорные изменения)? Канал у всех достаточно быстрый, экономия получится на спичках, а целостность данных — на порядок выше.
                                                      0
                                                      Докидывать патчи в HTML — хорошая идея )

                                                      А вот перезагружать полную версию еще раз, не уверен. Если патч наложился и почта отрисовалась, то можно считать, что версия актуальная и валидна.
                                                        0
                                                        Вы можете никогда (никак) не узнать, наложился ли патч корректно или нет. «Лобовая» загрузка ресурсов позволит гарантировать целостность данных.
                                                      0
                                                      А вы выбрали бы библиотеку от Гугла если бы она оказалась быстрее? =)
                                                        0
                                                        Да
                                                        0
                                                        Linux 3.17.2-1-ARCH
                                                        Chromium 38.0.2125.111
                                                        image
                                                        С месяц наблюдаю картину. Куда писать, чтоб поправилось?
                                                        Недавно поставил Я.Браузер. Там лучше ситуация, но иногда просто виснет на этапе загрузки ленты :(
                                                          0
                                                          А «классические» инструменты и форматы, вроде unified diff, тут никак заюзать нельзя?
                                                          Этакий маленький git у пользователя в docstorage, который делает fetch и merge при загрузке? Или даже не, комплект патчей gilt.
                                                          Ведь тот же патч можно накатить локально, чтобы стопудово удостовериться, что получается правильный файл в итоге. А если не так — что-нибудь подшаманить (например, увеличить контекст на единичку), и попробовать снова. И уже «правильный» патч слать клиентам.

                                                          Only users with full accounts can post comments. Log in, please.