Меня всегда немного смущало, как связаны пакеты crypto/rand и math/rand или как они должны работать (вместе). Это то, что все уже поняли, или это просто говорит мой синдром самозванца? Что ж, однажды я решил посмотреть, смогу ли я победить свое невежество, и этот пост в блоге — результат этого исследования.

math" Один

Если вы когда-нибудь ковырялись в пакете math/rand, то согласитесь, что он представляет собой довольно удобный API. Мой любимый пример — func Intn(n int) int, функция, которая возвращает случайное число в заданном вами диапазоне. СУПЕР ПОЛЕЗНО!

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

Однако при использовании этого пакета есть несколько ошибок. Базовое использование обеспечивает только псевдослучайные числа в зависимости от начального числа. Это означает, что если вы создаете два экземпляра Rand, используя функционально эквивалентное начальное число, эквивалентные вызовы (по порядку и функциям) к двум экземплярам будут давать параллельные выходные данные. (Я обнаружил, что эта концепция лично бросает вызов моему пониманию «случайного», потому что я не ожидал, что смогу предвидеть «случайный» результат.) Если два экземпляра Rand заполнены разными значениями, параллельное поведение будет не наблюдаться.

«crypto" Один

Теперь давайте посмотрим на crypto/rand. Хорошо, у него красивая и лаконичная поверхность API. Насколько я понимаю, это зависит от генератора случайных чисел базовой платформы ОС, который намерен быть недетерминированным. Единственный вопрос: КАК Я ЭТО ИСПОЛЬЗУЮ?!? Я вижу, что обычно могу получить фрагменты байтов из случайных 1 и 0, но что мне с ними делать?!? Это далеко не так полезно, как math/rand, верно?

Хрм. Можно ли получить недетерминированное поведение crypto/rand, но с более доступным API math/rand? Может быть, реальный вопрос заключается в следующем: как я могу объединить эти два совершенно разных пакета?

Два великолепных вкуса, которые прекрасно сочетаются друг с другом

(Примечание: https://www.youtube.com/watch?v=DJLDF6qZUX0)

Давайте более подробно рассмотрим пакет math/rand. Мы создаем экземпляр rand.Rand, предоставляя rand.Source. Но Source — это, как почти все замечательные вещи в Go, интерфейс! Мое паучье чутье кольнуло, может здесь есть возможность?

Основная рабочая лошадка в rand.Source — это функция Int63() int64, которая возвращает неотрицательное int64 (т. е. старший бит всегда равен нулю). Дальнейшее уточнение в rand.Source64 просто возвращает uint64 без каких-либо ограничений на старший бит.

Что, скажем, мы пытаемся создать rand.Source64, используя наши инструменты из crypto/rand? (Вы можете следить за этим кодом на Go Playground.)

Во-первых, давайте создадим структуру для нашего rand.Source64. (Также обратите внимание: поскольку math/rand и crypto/rand могут столкнуться при использовании, мы будем использовать mrand и crand соответственно, чтобы различать их в следующем коде.)

Давайте обратимся к функции Seed(...) из интерфейса. Нам не нужно семя для взаимодействия с crypto/rand, так что это просто бесполезна.

Поскольку функция Uint64() возвращает «самое широкое» значение, требующее 64-битной случайности, мы сначала реализуем эту функцию. Мы используем инструменты из encoding/binary, чтобы прочитать 8 байтов из io.Reader, предоставленных crypto/rand, и превратить их непосредственно в uint64.

Функция Int63() похожа на функцию Uint64(), но нам просто нужно убедиться, что старший бит всегда равен 0. Это довольно легко сделать с помощью быстрой битовой маски, примененной к значению, созданному Uint64().

Здорово! Теперь у нас есть полностью рабочий rand.Source64. Давайте проверим, что он делает то, что нам нужно, проверив его шаги.

Компромиссы

Круто, поэтому с приведенным выше кодом, состоящим примерно из дюжины строк, у нас есть простой способ подключить криптографически защищенную генерацию случайных данных к красивому и удобному API, предоставляемому пакетом math/rand. Однако я пришел к выводу, что ничего не дается бесплатно. От чего мы можем отказаться, используя это? Давайте проверим, что происходит, когда мы бенчмарким этот код.

(Примечание: мне нравится использовать простые числа в своих тестах, поэтому вы увидите много 7919, 1000-е простое число, в качестве параметра.)

Какую производительность мы получаем от функций верхнего уровня из пакета math/rand?

Неплохо! Около 38 нс/оп на моем ноутбуке.

Что, если мы создадим новый экземпляр типа rand.Rand, заполнив его текущим временем?

При ~23 нс/оп это тоже очень хорошо!

Теперь давайте проверим новое семя, которое мы написали.

Oof, при ~ 900 нс / операция это как минимум на порядок дороже. Это что-то мы сделали неправильно в коде? Или это, может быть, «стоимость ведения бизнеса» с crypto/rand?

Давайте создадим тест, чтобы увидеть, сколько времени занимает чтение из crypto/rand в отдельности.

Хорошо, результаты показывают, что подавляющее большинство времени, проведенного в нашем новом инструменте, связано с базовой стоимостью взаимодействия с пакетом crypto/rand.

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

Еще один Тэк?

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

И это проблема при использовании по умолчанию функций верхнего уровня math/rand (которые неявно задаются 1) или при использовании часто наблюдаемого шаблона заполнения time.Now().UnixNano(). Если ваши службы появятся в одно и то же время, вы просто можете оказаться в случайной синхронизации по отношению к детерминированному случайному выводу.

Как насчет того, чтобы использовать наши возможности crypto/rand во время создания экземпляра для заполнения инструментов math/rand, после чего мы все еще можем наслаждаться преимуществами производительности при использовании детерминированных случайных инструментов?

Мы можем запустить тесты для этого нового кода, но мы уже знаем, что просто вернемся к детерминированным случайным характеристикам производительности.

И теперь мы доказали, что наши предположения были верны.

об авторе

Привет, я Нелз Карпентье. Я старший инженер-программист в Orion Labs в Сан-Франциско. Я пишу на Go уже около 3 лет, и после знакомства он быстро стал одним из моих любимых языков.

Отказ от ответственности: я не эксперт по безопасности и не эксперт по реализации crypto/rand на разных платформах; вы можете проконсультироваться с местным экспертом по безопасности, если вы используете эти инструменты в критически важных случаях безопасности.

Вы можете найти перегонку этих примеров здесь. Он имеет лицензию Apache 2.0, так что не стесняйтесь нарезать, нарезать кубиками и/или брать у него все, что вам нужно!

Первоначально опубликовано как часть серии GopherAcademy Advent 2017 наhttps://blog.gopheracademy.com/advent-2017/a-tale-of-two-rands/.