Яндекс.
Диск — один из немногих сервисов Яндекса, в состав которого входит десктопное программное обеспечение.
И одна из важнейших его составляющих — алгоритм синхронизации локальных файлов с их копией в облаке.
Недавно нам пришлось его полностью изменить.
Если старая версия с трудом переваривала даже несколько десятков тысяч файлов и к тому же недостаточно быстро реагировала на некоторые «сложные» действия пользователя, то новая, используя те же ресурсы, справляется с сотнями тысяч файлов.
В этом посте я расскажу, почему так произошло: чего мы не могли предусмотреть, когда придумали первую версию программы Яндекс.
Диск, и как мы создали новую.
Прежде всего о самой задаче синхронизации.
Технически говоря, он заключается в наличии одинакового набора файлов в папке Яндекс.
Диск на компьютере пользователя и в облаке.
То есть такие действия пользователя, как переименование, удаление, копирование, добавление и изменение файлов, должны синхронизироваться с облаком автоматически.
Почему это не так просто, как кажется на первый взгляд?
Теоретически задача может показаться довольно простой, но на деле мы сталкиваемся с различными сложными ситуациями.Например, человек переименовал папку на своем компьютере, мы это определили и отправили команду на бэкенд. Однако никто из пользователей не ждет, пока бэкенд подтвердит успешность переименования.
Человек сразу открывает свою локально переименованную папку, создает в ней подпапку и, например, переносит в нее какие-то файлы.
Мы попадаем в ситуацию, когда невозможно сразу выполнить все необходимые операции синхронизации в облаке.
Сначала вам нужно дождаться завершения первой операции и только после этого можно продолжать.
Ситуация может усложниться, если несколько пользователей одновременно работают с одной учетной записью или у них есть общая папка.
И такое случается довольно часто в организациях, использующих Яндекс.
Диск.
Представьте, что в предыдущем примере, в тот момент, когда мы получили от бэкенда подтверждение первого переименования, другой пользователь берет и снова переименовывает эту папку.
В этом случае снова невозможно сразу выполнить действия, которые уже совершил на своем компьютере первый пользователь.
Папка, в которой он работал локально, в это время на бэкенде уже называется по-другому.
Бывают случаи, когда файл на компьютере пользователя не может называться так же, как он называется в облаке.
Это может произойти, если имя содержит символ, который не может использоваться локальной файловой системой, или если пользователь приглашен в общую папку и у него есть собственная папка с таким же именем.
В таких случаях нам приходится использовать локальные псевдонимы и отслеживать их связь с объектами в облаке.
Предыдущая версия алгоритма
В предыдущей версии десктопной программы Яндекс.Диск для поиска изменений использовался древовидный алгоритм сравнения.
Любое другое решение на тот момент не позволяло искать перемещения и переименования, поскольку бэкенд не имел уникальных идентификаторов объектов.
В этой версии алгоритма мы использовали три основных дерева: локальное (Local Index), облачное (Remote Index) и последнее синхронизированное (Stable Index).
Кроме того, чтобы предотвратить повторную генерацию уже поставленных в очередь операций синхронизации, использовались еще два вспомогательных дерева: локальное ожидаемое и облачное ожидаемое (Expected Remote Index и Expected Local Index).
Эти вспомогательные деревья хранили ожидаемое состояние локальной файловой системы и облака после завершения всех операций синхронизации, которые уже были поставлены в очередь.
Процедура сравнения деревьев в старом алгоритме выглядела так:
- Если локальное дерево ожидания и облачное дерево ожидания пусты, инициализируйте их, скопировав последнее синхронизированное дерево;
- Сравниваем локальное дерево с ожидаемым облачным деревом и по результатам сравнения отдельных узлов добавляем в очередь операции синхронизации в облаке (создание коллекций, перенос файлов в облако, перемещение и удаление в облаке);
- Для всех операций, поставленных в очередь на предыдущем шаге, мы записываем их будущий эффект в ожидаемом облачном дереве;
- Сравниваем облачное дерево с локальным ожидаемым и по результатам сравнения отдельных узлов добавляем в очередь операции синхронизации с локальной файловой системой (создание каталогов, скачивание файлов из облака, перемещение и удаление локальных файлов и каталогов).
;
- Для всех операций, поставленных в очередь на предыдущем шаге, мы записываем их будущий эффект в ожидаемом локальном дереве;
- Если в очередь попадают одновременные операции с одним и тем же файлом или каталогом (например, передача файла в облако и загрузка того же файла из облака), то фиксируем конфликт — файл изменился в двух местах;
- После завершения операции синхронизации в облаке или с локальной файловой системой вносим ее результат в последнее синхронизированное дерево;
- Когда очередь синхронизации становится пустой, мы удаляем локальное и облачное деревья ожидания.
Синхронизация завершена и они нам больше не понадобятся.
Почему нам пришлось придумать новый алгоритм
Основными проблемами алгоритма сравнения деревьев были большое потребление памяти и необходимость сравнивать целые деревья даже с небольшими изменениями, что приводило к большой нагрузке на процессор.При обработке изменений даже одного файла использование оперативной памяти увеличивается примерно на 35%.
Допустим, у пользователя было 20 000 файлов.
Потом при простом переименовании одного файла размером 10 КБ резко выросло потребление памяти - со 116 МБ до 167 МБ.
Также нам хотелось увеличить максимальное количество файлов, с которыми пользователь может без проблем работать.
Например, у фотографа, хранящего результаты фотосессий на Яндекс.
Диске, может оказаться несколько десятков, а то и сотен тысяч файлов.
Эта задача стала особенно актуальной, когда у людей появилась возможность покупать дополнительное место на Яндекс.
Диске.
Еще мне хотелось кое-что изменить в разработке.
Отладка старой версии вызывала трудности, так как данные о состояниях одного элемента располагались в разных деревьях.
К этому времени на бэкенде появились id объектов, с помощью которых можно было эффективнее решать задачу обнаружения движений — раньше мы использовали пути.
Новый алгоритм
Мы решили изменить структуру хранения данных и заменить три дерева (Локальный индекс, Удаленный индекс, Стабильный индекс) на одно, что должно было привести к уменьшению избыточности в основной структуре данных.За счет того, что ключом в дереве является путь к элементу файловой системы, в результате слияния объем используемой оперативной памяти значительно сократился.
Также мы перестали использовать вспомогательные деревья при синхронизации, поскольку каждый элемент дерева в новой версии хранит все необходимые данные.
Это изменение структуры значительно облегчило отладку кода.
Поскольку мы поняли, что это серьезное изменение, мы создали прототип, подтвердивший эффективность нового решения.
Давайте рассмотрим на примере, как изменяются данные в дереве при синхронизации нового файла.
- После того как пользователь добавил новый файл в папку «Диск», программа обнаружила его и добавила в дерево новый элемент. У этого элемента есть только одно известное состояние — локальное.
Поскольку стабильных и удаленных состояний нет, память для них не выделяется;
- Программа загружает файл.
Из облака приходит пуш, подтверждающий появление нового файла, и удаленное состояние добавляется в дерево;
- Сравниваются локальное и удаленное состояния.
Поскольку они совпадают, добавляется стабильное состояние;
- Локальное и удаленное состояния удалены.
Они больше не нужны, так как вся информация находится в стабильной версии.
На этом примере видно, что новый алгоритм синхронизации обрабатывает только те элементы и события, данные об изменениях которых были получены из файловой системы или облака, а не все дерево, как это было ранее.
Родительские или дочерние узлы будут обрабатываться по мере необходимости (например, при перемещении папки).
Другие улучшения
В новой версии мы также поработали над другими улучшениями, затронувшими производительность.Сохранение дерева сделано инкрементным, что позволяет записывать в файл только самые последние изменения.
Яндекс.
Диск использует дайджесты ша256 И MD5 для проверки целостности файлов, обнаружения измененных фрагментов и дедупликации файлов на бэкенде.
Поскольку эта задача очень ресурсоемка, реализация дайджест-вычислений в новой версии была значительно оптимизирована.
Скорость получения файлового дайджеста увеличена примерно в два раза.
Числа
Синхронизация уникальных 20 000 файлов по 10Кб каждый| Версия ПО | Загрузка в процессор.
Расчет дайджеста |
загрузка процессора загрузить | Использование оперативной памяти, МБ |
|---|---|---|---|
| Яндекс.
Диск 1.3.3 |
28% (1 ядро 100%) | Примерно 1% | 102 |
| Яндекс.
Диск 1.2.7 |
48% (2 ядра 100%) | Примерно 10% | 368 |
| Версия ПО | загрузка процессора | Время, сек | Использование оперативной памяти, МБ |
|---|---|---|---|
| Яндекс.
Диск 1.3.3 |
25% (1 ядро 100%) | 190 | 82 |
| Яндекс.
Диск 1.2.7 |
50% (2 ядра 100%) | 200 | 245 |
| Версия ПО | загрузка процессора | Время, сек | Использование оперативной памяти, МБ |
|---|---|---|---|
| Яндекс.
Диск 1.3.3 |
25% (1 ядро 100%) | 10 | 55 |
| Яндекс.
Диск 1.2.7 |
50% (2 ядра 100%) | 22 | 125 |
Wi-Fi соединение 10 Мбит
| Версия ПО | загрузка процессора | Время, сек |
|---|---|---|
| Яндекс.
Диск 1.3.3 |
5% | 1106 |
| Яндекс.
Диск 1.2.7 |
5% | 2530 |
Что случилось
На примерах видно, что новая версия ПО Яндекс.Диск использует примерно в 3 раза меньше оперативной памяти и примерно в 2 раза меньше нагружает процессор.
Обработка небольших изменений не увеличивает объем используемой памяти.
В результате внесенных изменений количество файлов, с которыми программа без проблем справляется, значительно увеличилось.
В версии для Windows — 300 000, а в Mac OS X — 900 000 файлов.
Теги: #Алгоритмы #Разработка сайтов #Яндекс.
диск #деревья #синхронизация файлов
-
Пришло Время Создавать Совместимые Веб-Сайты
19 Oct, 24 -
Seo Для Малого Бизнеса – Большая Ошибка
19 Oct, 24 -
Распознавание Эскизов
19 Oct, 24 -
Еще Одна «Новая Жизнь» Героев
19 Oct, 24
