Меня всегда немного смущало, как связаны пакеты 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/.