Как стать автором
Обновить

Комментарии 88

1. т.е. оркестратор для того, чтобы выполнять атомарные операции на серверах оказалось делать менее выгодно, чем делать решение с magic-числами?

2. в каком диапазоне генерируется magic, рассматривали ли вариант «только простые числа» для него?

3. считали ли вероятность отказа при создании этого алгоритма из-за событий малой вероятности?
1. А как конкретно оркестратор решит поставленную проблему и сколько для этого понадобится железа?

2. Это не принципиально поле все равно переполняется

3. Считали, огромное количество нулей после запятой
НЛО прилетело и опубликовало эту надпись здесь
Разве где-то сказано что можно наоборот?
Пока письмо у пользователя в списке писем есть — все его части должны быть доступны, иначе не поймут=)
НЛО прилетело и опубликовало эту надпись здесь
В статье рассмотрен вариант: файл прикреплен к двум письмам (counter=2), при удалении первого письма произошел сбой и запрос на удаление файла ушел дважды. Письмо-то при этом удалилось… и счетчик обнулился… вот только файл не знает что он должен быть еще и в другом письме. Именно эту проблему и решает magic.
> Если файл удалять(уменьшать counter) после того как письмо успешно удалено

Это иллюзия. Если во время сброса dirtypages возникнет ошибка, либо допустим машина перезагрузится — письмо потом «удалится» еще раз. Эта ситуация по сути и есть «откат базы», мейджик защищает от нее в том числе.

> при удалении письма произошел сбой, то письмо останется без файла

В обычной ситуации — да, но не в нашем случае=) Дело в том, что декремент не завязан на само действие пользователя (удаление письма). Удалив письмо — пользователь и никто другой его больше не увидит. Однако двойной декремент прийти в теории может, вот именно этот риск и страхуется. Это если очень вкратце, на самом деле индексы писем — очень большая и важная подсистема почты, о ней я надеюсь сможем рассказать отдельно и более детально, там много интересностей.
Обходное решение интересное, но неужели нет возможности сделать четкий контроль по удалению? Какие ситуации ведут к двойному уменьшению count?
Какой процент таких проблемных файлов накопился сейчас в системе? Например если оценить это в % от всех транзакций?
Защиту от коллизий sha1 вообще не стали делать? Всмысле — то что стащить чужой файл не получится — я понял из апдейта поста. А если коллизия произойдет — то файл в новом письме просто не сохранится?
К сожалению, железо несовершенно и разработчики тоже. Как ни крути — будут баги программные, хардварные и разные ситуации. Наивно надеятся, что багов не будет, как бы вы не были аккуратны. При большой нагрузке ошибки будут, причем самые неожиданные. В этом ключе существует только 2 варианта: counter умеет ошибаться с бОльшую сторону, либо в меньшую. Конечно, лучше первое=) Процент неудаляемых файлов реально очень мал (<0.001%).
Небольшой перечень ситуаций, ведущих к ошибкам в counter:
— Ребут сервера
— Отказ диска
— Сетевая проблема (запрос на уменьшение дошел, а ответ на этот запрос — нет)
— Перегруз сервера filedb (запрос будет исполнен, но уже после таймаута)
— Баги (вклюючая segfault в любой части этой системы)
— Затуп в диск при логировании в async приложении приведет к таймаутам
— Наверняка еще 100500 кейсов, которые я сейчас не вижу

А как можно «защитить» sha1 от коллизий? Есть проверка, что это именно тот sha1, который был в письме (путем подсчета еще одной контрольной суммы). А защититься в полном смысле я думаю нельзя. Так что да, файл в новом письме не сохранится, в этом случае мы будем первыми в мире, кто найдет такой коллизию=) Пока на 12млрд хешей такого не произошло, по подсчетам z3apa3a этого не произойдет, пока хранилище не увеличится еще в 1e20 раз. Так что реально нет причин полагать, что такая проблема есть фактически.
P.S. Интересно вот что: ваши вопросы натолкнули меня на мысль) Почему так много вопросов про коллизии и так мало про счетчик? А ведь вероятность ошибиться в счетчике в результате бага и железной проблемы в миллиарды раз выше, чем вероятность коллизии. Перефразирую: есть сотни реальных(вероятность >1e1000) кейсов, когда счетчик разойдется и ни одного прецедента с коллизией.
Magic не используется в нормальном режиме работы, это решение на случай сбоя, примерно такое же, как зеркалирование. Сбои происходят относительно редко. Вероятность коллизии для 32-битного счетчика на много порядков меньше вероятности, что два диска с данными на которых хранятся две копии одного файла выйдут из строя с интервалом не более минуты и обе копии файла будут гарантированно утеряны, не смотря на зеркалирование в разных датацентрах. Еще больше вероятность утери информации из-за действий пользователя. Вероятность отказа есть всегда, ее нельзя свести к нулю, ее можно свести к допустимому уровню. Эта технология не пригодна для хранения информации стоимостью миллиард долларов за файл (возможно, она может быть доработана до такого уровня, но такой задачи нет), но она вполне пригодна для хранения корпоративной и пользовательской переписки и корпоративных и пользовательских данных, т.к. она заведомо надежней чем RAID 1 или 5 в корпоративном сервере и уж тем более, чем незеркалированный диск в домашнем компьютере.
Спасибо за подробный ответ!
Рад что натолкнул на новые мысли :)
А если коллизию вы найдете, а файл не сохранится — как будете предъявлять миру? :)
Надо однако, если sha1 один, а размеры или crc разные — срочно емейлить оба файла в Книгу Гинесса! Ну или мне, я то уж донесу весть миру! Надеюсь файлы окажутся с приличным содержимым :)))
Емайлить файлы мы не будем. Это пользовательские данные и они принадлежат пользователям ))
Почему так много вопросов про коллизии и так мало про счетчик? Перефразирую: есть сотни реальных(вероятность >1e1000) кейсов, когда счетчик разойдется и ни одного прецедента с коллизией.
Потому что счётчик — это борьба с энтропией. Когда можно набирать статистику и т.п.

Коллизии — это борьба с саботажем. Статистика тут не работает. Вернее работает как в XKCD. Или как Перельмановский батальон солдат
Нет, раз уж опять про коллизии, давайте окончательно разделим 2 кейса:
1. Случайное совпадение — об этом см пост выше. Гораздо вероятнее, что вы допустите ошибку и все разломается до того, как возникнет шанс на такой случай.
2. Саботаж (направленная атака). Статистика тут действительно не работает, однако: 1)хеш соленый 2) хеш наружу не отдается никогда 3)атакуемый хеш не известен 4) сложно подобрать подходящий атакуемому хешу файл 5) еще сложнее — если он соленый 6) еще сложнее — если он неизвестно как соленый 7) подобрав саботажную коллизию (в чем я категорически сомневаюсь с учетом вышесказанного) остается вопрос — в файле будут данные или мусор? 8) Если мусор то такой «саботаж» отклоняется за 5минут отправкой ссылки в любое другое хранилище документа, либо его изменением.
Обобщая все вопросы в комментариях про коллизии я для себя выводы сделал. Все слышали про теоретическую возможность; никто не делал ни единого верного шага на предмет как это сделать(и я тоже). Так что простите великодушно, я уже все что мог на эту тему написал.
На счет п.2 я так полагаю спрашивали, когда magic_number_1 = n * magic_number_2 (и мы возвращаемся к ситуации, для которой вводили magic)
Для этого надо, чтобы сбой на одном письме произошел n раз.

Нет, ну тогда counter будет -n+1, а не ноль.
По простому двумя файлами сложно сломать magic, тремя файлами уже можно достаточно просто (magic = 7, 11, 15, второй файл удаляется три раза, magic и counter нули).

В вашем примере чтобы такое произошло, нужно чтобы при заданном magic2 значения magic1 и magic3 были вполне конкретные (возможны варианты, но их множество очень ограничено). Выходит, что вероятность этого события сопоставима с 1/ (2^32 * 2^32)
1) Почему вместо magic не использовать еще один счетчик?
2) Правильно ли я понял, что случайно перебирая sha1 пользователь может читать чужие файлы в почте?
1) Именно случайный magic дает защиту от декремента «чужой» единицы счетчика. Если он у всех одинаковый — то желаемый эффект не достигается.
2) Во-первых, хеши соленые, так что его нельзя угадать. Во-вторых, перебирать — этож сколько вариантов? В третьих — снаружи вообще нет интерфейса, позволяющего взять файл по хешу. Туда ходит только библиотека доступа к storage, и только она внутри себя знает как работать с этим хешом.
Помимо того что публичного интерфейса нет, надо еще и авторизацию получить чтобы читать файлы другого ящика.
sha-1 имеет длину 160 бит. При наличии 12 000 000 000 файлов, чтобы случайным перебором наткнуться на файл, надо перебрать порядка 10^38 (2^120) комбинаций.
Интересно, а что и как делает Яндекс Почта в этом направлении?
А что делать когда файлы разные, а sha1 одинаковый?
Приведите пример таких файлов.
в сложном документе, например PDF или картинке, где лишние байты будут игнорироваться :) можно совершить атаку и подобрать мусор что бы два разных (по содержанию отображаемому пользователю) документа имели одинаковый хеш.

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

Например для md5 я с ходу нашел такую очень старую (~10 лет) работу: http://cryptography.hyperlink.cz/md5/MD5_collisions.pdf
А примеры файлов дайте :)
Давай я тебе лучше ссылку дам где находят коллизию для SHA1 за 76 шагов: https://marc-stevens.nl/research/sha1freestart/

:)

Но я согласен что если начать считать стоимость нахождения этой коллизии то это на amazon ec2, то это будет пара сотен тысяч долларов.
Если я верно понял там оперируют бессмысленным набором бит?
В пару сотен тысяч долларов входит нахождение коллизий реальных файлов, фотографий или документов?

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

Дальше, если соли нет, атака — тривиальна: посылаем документ, в котором даём банковские реквизиты для перевода денег куда-нибудь в оффшор с одного специально заведённый аккаунта на mail.ru на другой.

А настоящий документ (с той же sha1 суммой) — чуть позже уже тому, кто, собственно, должен перевести этих денег.

После чего эти временные аккаунты удаялем — и готово дело: mail.ru подменил реквизиты платёжки, потому деньги ушли неизветно куда.

Конечно человек, у которого есть такие деньги и который при этом пользуется ящиком на mail.ru — несколько странен, но… атака — вполне реальная.
Не совсем так. Вы описали chosen-prefix collision attack, в то время как сейчас для SHA-1 пока идет речь о возможности просто нахождения коллизии с теоретической оценкой сложности 2^80 вычислений. Для сравнения, для MD5 сейчас существуют алгоритмы нахождения коллизии за ~2^16 вычислений, в то время как для заданного префикса требуется ~2^50 вычислений.
P.S. Ну и сама описанная атака на практике мало что дает атакующему — если он контролирует содержимое обоих писем, то что ему мешает сразу отправить подмененные реквизиты?
Проблема критична, например, в случае SSL, т.к. можно сделать два разных запроса на получение сертификата, и получить подпись, которая действительна для обоих. При этом например один запрос на свой домен, а другой на чужой, или один простого сертификата на имя домена, а во втором добавить роль удостоверяющего центра. Это как раз примеры, в которых использовались коллизии MD5.
Размер есть в индексах. Также, там есть crc по другому алгоритму, который при заборе тоже сверяется. Сам забор письма, собирание его из разных частей, сверка консистентности, форматирование и много чего реализовано в отдельной либе/сервисе. Это довольно обширный топик тоже, поэтому мы его не затрагиваем пока.
В общем, теоретическая возможность коллизии все же есть, однако она теоретическая, еще не встречалась и легко обнаруживается при доступе к «подмененному» файлу. Также напомню, что хеш соленый не известно чем, если даже известно — то это еще надо подобрать чтобы все сошлось=)

Спасибо за действительно хороший технический ответ. Было приятно прочитать, в отличии от ответов AndrewSumin

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

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


Ого.
ну хеш коллизии никто не отменял.
Вероятность не большая даже на 12 лярдов файлов, но всеже.
Учитывая что уже были известны аттаки на sha1 хеш коллизии, то теоритически, имея файл, я могу методом чудо-перебора не дать ему быть послланным в будущем адресатам мэил.ру заняв его место файлом с идентичным хэшем.
У нас sha1 соленый
Это кстати не только затрудняет подбор, но и скрывает атакуемый хеш.
На самом деле на текущий момент нет известных публично вычисленных примеров коллизии самого SHA-1, есть примеры коллизии для инициализирующих векторов на функцию компресии (SHA-1 freestart collision). Вероятность что на 12млрд файлах произойдет случайная коллизия менее 10^-38.
Разберём, что происходит во время upload. Для демона, который реализует этот интерфейс...

Когда пользователь прикрепляет вложение к письму во фронтенде, файл загружается, но не сразу передается демону? Где-то кэшируется?

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

Сам loader, как написано в статье потоковый. http сервер который принимает файлы от пользователя (nginx) не потоковый, но там мы не упираемся в ресурсы поэтому эту проблему не решали.
Меня интересует вероятность коллизии — так как используеться sha1 она очень мала но все-же есть.
Были ли такие случаи, когда вместо договора человек при открытии письма получит открытку с котиками?
Насколько мне известно с осмысленными файлами таких коллизий до сих пор не обнаружено, у вас есть пример?
На одно-двухбайтовых файлах проверяли?
Дописал в конец статьи отдельный блок про sha1 раз тема такая популярная.
Она не работает при такой большой разности множеств (2^34 vs 2^160). В статье о парадоксе есть табличка. Там к сожалению нет значений подохящих для SHA-1 (160 бит), на 128 битном хеше на 26 миллиардах файлов вероятность коллизии 10^-18.
Для 160-битного хэша и 12 миллиардов файлов можно оценить вероятность коллизии сверху примерно как 10^-38.
~10^-28 вероятность что произойдет хотя бы одна коллизия между любыми файлами. 10^-38 это коллизия для конкретного файла. Какого либо заметного влияния birthday paradox здесь нет.
К сожалению примеров нет, но на всякий случай я бы сохранил еще mime файлов и размер. Но как уже выше проинформировал PSIAlt эти данные уже включены в crc и даже если случиться коллизия — это будет обнаружено и файл с приватной информацией будет доступен только из того письма, к которому он принадлежит.
позволили нам долгое время не покупать новое железо


а какой рост хранимой информации за месяц? на сколько этого объема вам может хватить? были ведь просчеты
Речь идет про годы.
Почта пользователя хранится на одном сервере на диске объединенном в райд 1?
Простите, уточню. Если я правильно понял, то файлы раскладываются по двум дискам. Эти диски обязательно в двух разных ДЦ и зеркалируются ли они в райде?
Диски в разных подсетях. В рейде не заркалируются.
Скажите, а вообще наша почта и наши файлы в вашем облаке как то защищены от потери в случае программного или аппаратного сбоя? И, если да, то каким образом? Резервное копирование, какой-либо массив или что-то еще?
Волнует вопрос: делать ли локальный бэкап или хватит облака?
Пол статьи про то как мы защищаемся от программного и аппаратного сбоя.
Все мои личные и рабочие письма и файлы находятся на наших серверах.

Делать бэкап писем нужно обязательно. Самый простой способ forward писем в любой другой почтовик.
Даже если все пойдёт безупречно и ваши данные будут целы, вы можете потерять доступ к ящику по зависящим от вас причинам.

Судя по схеме у вас файл имеет в имени результат хэш функции еще до заливки на сервер в какой момент она расчитывается?
До заливки в это облачко файл лежит в письме, которое естественно есть целиком у сервиса, который хочет положить письмо в ящик (например, MX). Соответственно, имея все письмо целиком он легко считает хеш каждого из его партов и может дать его вместе с телом файла.
А что с форматами файлов? Если в основном это документы, текстовые файлы, то их дополнительно можно архивировать — высокий процент сжатия позволит еще более освободить диски
Это было сделано ранее, до внедрения этой схемы.
Что будет, если magic два раза посчитается одним числом?
Имеем count: 2 и magic: 200 (100 на каждое письмо).
Происходит сбой и по первому письму приходит два раза команда на удаление.
Вычитаем из magic 100 дважды, соответственно, magic становится равным нуля. Как и count.
Файл удалён. Теперь он не доступен для второго письма.
Я не прав?
Все так. Максимальная вероятность такого события = p * 1/2^32, где p — вероятность ошибки при удалении. Если взять ее как 0.001(что явно много) то получается вероятность случайного удаления в таком случае ниже 2.3e-13. Но по факту она еще ниже, потому что в этой формуле не учитываются другие факторы, которые тоже уменьшают вероятность (например, что счетчик равен именно 2).
Также напомню что кроме этого уровня есть еще 3 уровня защиты от окончательной потери самого файла, но до них ни разу за 1.5 года не дошло (тфу-тфу) =)
Поделитесь тем, что представляют из себя эти три уровня?
Описанные в статье (в разделе про валькирию) 2 вида карантина, плюс отложенное удаление на одной из пар. В случае чего — можно легко найти потерянный файл и закинуть обратно в облако с пометкой «не удалять», а потом устроить масштабные разборы полетов=) К счастью, пока не доводилось)
А что, если одинаковые файлы лежат в архивах и запакованы они с разной степенью сжатия?
Положатся как разные объекты. В рамках этой системы внутрь архивов мы не залезаем, а все файлы рассматриваем как просто blob-объекты.
НЛО прилетело и опубликовало эту надпись здесь
Спасибо за комментарий, идея действительно хорошая. Признаюсь, она мне в голову не приходила=)
Однако тут есть 2 фактора: 1) мы бы все равно не убрали проверку RC в валькирии потому что существует вероятность и 2) реализация потребует дополнительного поля в filedb, а для 12млрд записей это довольно прилично по памяти.
У вас в записи на длины полей, которые фиксированы и известны уходит около 10% (5 из 57) от длины записи. Можно ли исключить подобное?
Их добавляет сам таранул для того чтобы уметь разобрать тапл на поля. По крайне мере в 1.5 так. Тут хотелось бы напомнить, что сам тарантул тоже должен уметь разбирать на поля т.к. работает с многими полями записей filedb на уровне луашек. Можно было бы это обойти, но тогда возникли бы вопросы по атомарности изменений в этих полях, так что я бы не стал=)
А что всё-таки происходит с проблемными файлами? Они как-то дополнительно обрабатываются magic корректируется?
Если кратко то пока никак не корректируется. Ставится флаг, что удалять нельзя.
В принципе, в планах есть приблизительно такой вариант: запомнить какой был counter&magic у таких хешей и начать обход по индексам. В результате обхода получаем какой должен быть counter&magic и обновляем их в filedb а-ля «compare and swap». Пока(тфутфу) таких «бессмертных файлов» особо и нет(по факту есть в тестовых ящиках) — задача не горит. Мы больше концентрируемся на том, чтобы они в этот разряд не попадали, т.к. любая подобная сверка — масштабная нежелательная операция. Так что на мой взгляд тут задача №1 — не давать попадать файлам в этот разряд и задача №2 — не сломать возможность сверки, если вдруг Вселенная восстанет против нас.=)
По сути magic — это компактная замена списка обратных ссылок на письма, верно?
Я бы не сказал. Скорее я бы назвал его вторым counter-ом, который инкрементится на неизвестную никому(кроме того, кто заинкрементил) величину.
Ну получается что это неявный checksum тех, кто заинкрементил.
Т.е. можно тоже самое сделать имея явный список
Да, можно было просто содержать список, грубо говоря email — id_письма — id_парта. И при декременте сверять с ним.
Вот. Именно это первое и приходит в голову. И контроль проще в случае чего. И приходит же в голову очевидная проблема — огромные подсписки писем для «популярных» файлов. Но ведь тогда «популярные» можно просто помечать неудаляемыми и успокоиться. Почему-то же отказались от этой идеи и ввели довольно экзотический механизм?
Ну если самих хешей 12млрд, а у каждого счетчик >=1, то сколько же таких записей будет?
Это затратно по ресурсам. Плюс еще есть такой фактор как консистентность: сейчас авторитетным источником для любого рода информации являются индексы писем. Если начать хранить обратные ссылки то рано или поздно возникнет ситуация, что информация не сходится, что тогда делать?
Грубо прикинул — стандартное решение подкинуло бы пару-тройку ТБ к объему базы, которую предполагается хранить в оперативке. Более чем довод. Статье очень не хватает обоснований принятых решений, чтобы было понятно, зачем все именно так, и почему это относительно безопасно.
Вопрос — премию то дали за проделанную работу? 18 Pb не шутки. Это не только экономия на железе, но и обслуживании.
А еще это экономия на росте. Скорость роста тоже уменьшилась на 35%.
Ну это уже считай на 3 премии накапало!
Дали конечно=) Правда, я планировал что хватит на Ferrari F12, но не хватило (
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.