Выборка случайной записи из таблицы с 700*10^6 строк28.03.2017 22:48

Многие ли из нас сталкивались на практике с этим модным словом «Big Data», работая в заурядных компаниях веб-разработчиками? Скорее вы, как и мы, разрабатываете каждый день одинаковые сайты на одинаковых CMS, часто даже не задумываясь об их производительности.


Однако и в жизни веб-разработчика настает такой день, когда приходит заказчик с интересной задачей. Вы наливаете кофе, прогоняете кота с клавиатуры и вдохновенно начинаете проектирование.


Это рассказ о том, как пара амбициозных веб-разработчиков впервые столкнулась с задачей обработки «больших данных».


image



Итак, что же хочет заказчик


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


Задача была решена на уже существующем сайте, который работает на Apache (PHP 5.6) и СУБД MySQL.


Масштабы катастрофы


Для начала нужно было написать алгоритм генерации логинов и оценить масштабы катастрофы.
Сам алгоритм генерации очень прост.


$alphabet = range('A', 'Z');
$alphabetLength = count($alphabet);
for ($i = 0; $i < $alphabetLength; $i++) {
    for ($j = 0; $j < $alphabetLength; $j++) {
        $arLogins = [];
        for ($k = 0; $k < 1000000; $k++) {
            $k = strval($k);
            $arLogins[] = '("' . $alphabet[$i] . $alphabet[$j] . str_pad($k, 6, '0', STR_PAD_LEFT) . '")';
        }
        // insert 1 000 000 by single query
        $strSql = "INSERT INTO logins VALUES " . implode(',', $arLogins);
        $DB->Query($strSql);
    }
}

Оказалось, что на деле получится около 700 миллионов логинов. Стало быть, вариант генерировать их «на лету» тут не пройдет.


Алгоритм генерации «на лету»

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


  • Количество пользователей увеличивается, а количество свободных логинов уменьшается. Значит количество итераций, которое уходит на подбор свободного логина, будет возрастать вместе со временем получения ответа сервера
  • Количество запросов к базе данных так же будет постоянно возрастать

Значит нужно их где-то запоминать — отдельная таблица в базе данных прекрасно подойдет для этой цели. На радостях создали таблицу, сгенерировали туда логинов, сделали единственное поле PRIMARY. Получилась вот такая простая таблица.


value
AA000000
AA000001
AA000002
…

А потом вспомнили, что логин нужно выбрать случайный.


Первые шаги


Конечно, первое, что решили испробовать, это всем известный ORDER BY RAND() LIMIT 1. Результат заставил себя ждать, с сервером можно было попрощаться на неопределенное время. Наличие индекса оказалось совершенно бесполезно в этом случае. 


SELECT `value` FROM `logins` ORDER BY RAND() LIMIT 1;

Что делать?


Пришло время узнать у гугла ответ на вопрос «Что делать?».


Первое, что предлагает гугл — способы оптимизации с ORDER BY, но это сразу не для нас, так как они круты и производительны, только если у вас в базе несколько тысяч записей. Нашлось несколько способов оптимизации с JOIN и подзапросами, они не сработали по той же причине.


Все эти способы очевидно предназначены для того случая, когда речь идет об оптимизации времени выполнения запроса с 500 мс до 50 мс, в нашем же случае речь шла скорее о том, чтобы за 10 минут, пока выполняется запрос, не уронить сервер.


Однако все это было честно испробовано, stackoverflow проштудирован от корки до корки, но так и не дождались, пока выполнится запрос, так что о приросте производительности судить не можем :)


В первой же ссылке предлагается вынести всю работу по рандомизации на сторону PHP-сервера — выбрать минимальный и максимальный id, сгенерировать случайное число между ними и вуаля — у нас есть id случайной записи. 


SELECT MAX(`id`) FROM `logins`;
SELECT `value` FROM `logins` WHERE `id` = ;

Отличный вариант, работать должен идеально быстро. Однако у нас нет возможности добавить каждой записи целочисленный id, таблица и так уже перешагнула за 20 Гб, а ресурсы сервера не резиновые. Да и даже если бы такая возможность была, логины должны быть уникальными, а значит, когда мы отдаем пользователю очередной логин, из таблицы его нужно сразу удалить. Что будет, если наткнемся на уже несуществующий логин? Возвращаемся к варианту с огромным количеством циклов.


Следующий испробованный вариант — случайный OFFSET и LIMIT 1. Значение OFFSET генерирует PHP-сервер и подставляет его в запрос. Казалось бы, на стороне MySQL никакой сортировки и рандомизации нет, однако сам OFFSET не так прост. В случае генерации большого значения для смещения MySQL сначала переберет все строки до смещения и только потом отдаст нужную. Немного лучше сортировки, но в общем случае ждать результата можно очень долго. Да и выбор количества записей не такая уж быстрая операция.


SELECT COUNT(*) FROM `logins`;
SELECT `value` FROM `logins` OFFSET 123456789 LIMIT 1;

Новый подход


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


В голову приходят все те же два варианта — на стороне БД и на стороне PHP.


«Ну теперь то мы можем сделать случайную сортировку в MySQL, пользователь же не будет ждать» — подумали мы. Создали пустую копию таблицы, запускаем запрос: 


INSERT INTO `new_logins` (SELECT * FROM `logins` ORDER BY RAND());

Но не тут то было. Чтобы отсортировать все записи в случайном порядке, MySQL выгрузит их все в оперативную память и только после этого отсортирует, а как мы уже выяснили выше — ресурсы сервера ограничены. Да и базу положить часов на 8 на рабочем сервере таким запросом не хотелось бы.
Тогда попробуем сортировку на PHP — set_time_limit(0) + консоль и дело в шляпе, пусть себе выполняется. Алгоритм генерации подразумевал вставку 1 миллиона записей за 1 запрос к БД.


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


Господин NoSQL


Начали думать в сторону NoSQL. Но как и на любом коммерческом проекте, времени на реализацию было катастрофически мало, а времени на тестирование и того меньше. Практического опыта использования NoSQL хранилищ не было, какой бы они дали прирост в производительности, могли только предполагать. Было бы неприятно в день дедлайна обнаружить, что время выполнения запроса сократилось с 10 минут до 1 минуты. Так что от этой идеи пришлось отказаться.


Если у кого-то был опыт использования NoSQL-хранилищ для соизмеримого количества данных, поделитесь в комментариях.


Свет в конце тоннеля


Путем долгих экспериментов и поисков решение нашлось. Стало очевидно, что пытаться добиться чего-то от MySQL бесполезно, а использовать NoSQL не представляется возможным.


А что если вернуться к варианту с рандомизацией значения на стороне PHP-сервера? У нас есть поле varchar(8) и PRIMARY индекс. Мы не можем сгенерировать случайный логин и выбрать его из базы из-за вероятности попадания в «дыру» (уже удаленный логин) и последующего зацикливания, однако мы можем сравнивать строки. Почему бы не сгенерировать случайный логин и не выбрать те, которые больше него, добавив при этом LIMIT 1? Индекс здесь отлично поможет ускорить выборку. Пробуем — на этот раз результат не заставил себя ждать, меньше, чем за секунду, получаем нужную запись. Осталось только исключить один крайний случай — если логин, который сгенерировал PHP-сервер, последний в таблице. Тогда получим пустой результат и выберем из таблицы первый по порядку логин одним дополнительным запросом. 


function generateRandomLogin()
{
    $alphabet = range('A', 'Z');

    $firstLetter = $alphabet[mt_rand(0, count($alphabet) - 1)];
    $secondLetter = $alphabet[mt_rand(0, count($alphabet) - 1)];
    $number = mt_rand(0, 999999);

    return $firstLetter . $secondLetter . $number;
}

function createLogin()
{
    $randomLogin = generateRandomLogin();

    $newLogin = $DB->Query('SELECT * FROM `logins` WHERE value > "' . $randomLogin . '" LIMIT 1')->Fetch();
    if ($newLogin) {
        // if login was found delete it from database
        $DB->Query('DELETE FROM `logins` WHERE `value`="' . $newLogin['value'] . '"');
        return $newLogin['value'];
    }

    // if login was last in table, select first
    $newLogin = $DB->Query('SELECT * FROM `logins` LIMIT 1')->Fetch();
    if (!$newLogin) {
        throw new \Exception('All logins are already used');
    }
    $DB->Query('DELETE FROM `logins` WHERE `value`="' . $newLogin['value'] . '"');
    return $newLogin['value'];
}

Заключение


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

Комментарии (30)

  • 28 марта 2017 в 18:09

    +2

    ↑

    ↓

    Если честно, не понимаю необходимости «случайности». Т.е. запрет на логины 0001, 0002, 0003 исходит из чисто эстетических хотелок заказчика. Единственное «разумное» объяснение, что он хочет скрыть количество зарегистрированных человеков. Я бы просто брал порядковый номер и обфусцировал/шифровал его, пока он не займёт необходимое количество бит. Т.е. нужно хранить только одно число — порядковый номер следующего пользователя. Учитывая, что речь идёт о 30 битах, то написать порождающую функцию без коллизий не выглядит сложной задачей.

  • 28 марта 2017 в 18:17

    +6

    ↑

    ↓

    А чем вам изначальный вариант с генерацией случайного логина на лету не подошел? Скорость ответа будет реально деградировать лишь при приближении количества пользователей к лимиту (т.е. к 700 млн). То есть, если пользователь один — нам потребуется 1 запрос к базе для проверки его существования, если 350 млн — в среднем, два, если 467 млн — в среднем, три, и тд.
    Неужели у вас действительно столько пользователей? Неужели при таком количестве пользователей самая серьезная проблема — это генерация логинов?

    Пожалуйста, объясните, видимо, я чего-то не понял.

    • 28 марта 2017 в 18:55

      0

      ↑

      ↓

      У нас генерируется номер сертификата по такой же логике, пока доходит до 2-х тысяч в день, и с каждым годом только растёт.

    • 28 марта 2017 в 22:18

      0

      ↑

      ↓

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

  • 28 марта 2017 в 18:43

    –1

    ↑

    ↓

    Ожидал, что в конце получится микросервис по выдаче случайной строки с кластером из Cassandra-нод. И вывод из статьи типа «Теперь все уже почти работает, осталось только решить проблемы с консистентностью и наши пользователи наконец-то смогут насладиться своими уникальными логинами».

    Присоединюсь, однако, к тем, кто не совсем понял — вот в последнем абзаце параграфа «Новый подход» — я так понял у нас есть файлик с 700 млн. логинов, мы потихоньку пэхэпэшкой берем из него случайные строки и запихиваем их в бд. Где тут плохое распределение?

    • 28 марта 2017 в 22:25

      0

      ↑

      ↓

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

  • 28 марта 2017 в 18:43

    0

    ↑

    ↓

    Спасибо за предложенное решение, и описание всего процесса поиска. У нас сейчас используется Алгоритм генерации «на лету», пока проблем нет, но меня это уже беспокоит. Есть номер подарочного сертификата, который должен быть уникальным, и при этом случайным. Сам шаблон похож на ваш: ZZ-888–999999999. Конечно шаблон менее важен, интересно само решение данной проблемы.

    • 28 марта 2017 в 19:07

      0

      ↑

      ↓

      А что беспокоит-то? Если у вас (как вы написали в другой ветке) около 2 тысяч генераций в день, то за 10 лет накопится около 7.3 млн записей в базе. При этом пространство значений очень велико, коллизий почти никогда не возникает, т.е. на одну генерацию потребуется 1 поиск в базе (и добавление). Неужели один-единственный поиск в MySQL таблице на 7.3 млн записей выполняется ощутимое время?

      • 28 марта 2017 в 19:23

        0

        ↑

        ↓

        Проблем со скоростью пока нет, хотя я и не проверял, сколько запросов и времени используется при поиске свободного сертификата. Мне интересно, насколько проблема надумана мной, и когда надо начать беспокоиться. Проекту уже 8 лет, правда пока приблизились только к 2 млн.

        • 28 марта 2017 в 22:34

          0

          ↑

          ↓

          Определенно, беспокоиться не стоит. Но интересно же найти элегантное решение, правда?

  • 28 марта 2017 в 18:58

    +3

    ↑

    ↓

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

  • 28 марта 2017 в 19:15 (комментарий был изменён)

    +2

    ↑

    ↓

    Странная задача.
    Можно сгенерировать весь набор доступных логинов на стороне вашего языка, 700кк это не много, и перемешать случайной сортировкой, например взяв md5 от логина. Положить их в базу и отдавать новый по порядку.
    Последнего не занятого хранить в потокобезопасном кэше.
    Собственно говоря, можно обойтись даже без базы, просто файликом и читать его со смещением по памяти на нужную строку. Благо длину строки можно сделать стандартной.
    Если для вас 700кк 8 ми символьных строк — это много, можно выбрать несколько произвольных диапазонов и по мере нужды генерить новые диапазоны.

  • 28 марта 2017 в 19:18

    0

    ↑

    ↓

    Может стоило объяснить заказчику, что хранить 700 млн записей, которые и данных то не содержат, это как бы моветон? Тут и требования, и компетенция того, кто их составлял, вызывают вопросы…

  • 28 марта 2017 в 19:33

    0

    ↑

    ↓

    Хм. У меня на проекте генерируются случайные токены для каждой сессии, которые тоже должны быть уникальным и хранятся в БД.

    Сгенерил — проверил на уникальность. Если не катит — все по новой.
    При 16000 зарегистрированных пользователях вообще никаких проблем.

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

    Кстати, могли бы использовать какой-нибудь Elasticsearch. Он вам и рандомную запись выберет очень-очень быстро и все что угодно. И ставить/настраивать довольно просто.

  • 28 марта 2017 в 19:55

    0

    ↑

    ↓

    Нагенерировать заранее 700 млн случайных чисел, однозначно отображающихся в нужный алфавит, собрать табличку с полями
    id (непрерывный список из 700 млн чисел)
    login (случайный, заранее сгенерённый логин, про который заранее предпроверена уникальность. Прожку написать на C, она вам быстро сгенерит, чего надо. Для проверки незанятости можно в битмап положить имеющиеся логины — вам понадобиться всего ~80 мегабайт оперативки).
    табличу с пользователями сделать c id-никами и с автоинкрементом, login копировать при создании пользователя и не показывать в интерфейсе.

    • 28 марта 2017 в 19:57

      0

      ↑

      ↓

      Да, когда останется ~ 1% свободных логинов, придется их переложить в какую-нибудь другую структуру данных — в массив, например и выбирать рандомно уже только из свободных.

  • 28 марта 2017 в 20:17 (комментарий был изменён)

    +1

    ↑

    ↓

    Зачем сразу то все генерировать? Пишите ф-цию, типа gen_login, она выплевывает вам готовый логин, рандомный, идете в кеш, если не попали, то используете этот логин, при этом пишете хеш от этого логина в БД и кеш в рамках транзакции, если попали, повторить, при старте приложения загоняете все использованные хеши в кеш.
    Как-то так.

    • 28 марта 2017 в 22:45

      0

      ↑

      ↓

      Можно и в базу записывать, тоже будет быстро и не скоро начнет тормозить. Но хотелось решить задачу «идеально».

  • 28 марта 2017 в 20:29

    0

    ↑

    ↓

    Транзакци… 100% когдато кто-то 2 юзера попытаются получить одинаковые логины

  • 28 марта 2017 в 21:06

    +1

    ↑

    ↓

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

    • 28 марта 2017 в 21:44

      0

      ↑

      ↓

      Тоже в перую очередь подумал про UUID. Если не дают создавать сови логины, значит никто не расчитывает что пользователи их будут запоминать, значит можно вообщ любой делать, какая разница что пользователь будет копировать из тектовика/письма.

  • 28 марта 2017 в 21:13 (комментарий был изменён)

    +1

    ↑

    ↓

    я бы предложил использовать простейшую очередь из свободных логинов, например, на основе beanstalkd или rabbitMQ. Чтение очередного сообщения (в данном случае свободного логина) займёт микроскопическое время, сам сервер очередей гарантирует, что одинаковый логин не достанется двум разным потребителям.
    Конечно, все 20Гб в очередь пихать не стоит, а лучше состряпать демона, который в бекграунде будет периодически проверять эту очередь и наполнять её новыми логинами.



    но всё это конечно при условии, что нельзя изменить немного дикую постановку задачи.

  • 28 марта 2017 в 21:21 (комментарий был изменён)

    0

    ↑

    ↓

    (удалено)

  • 28 марта 2017 в 21:22

    +1

    ↑

    ↓

    Масштабы катастрофы

    Элегантное решение вашей задачи находится в области криптографии.

    В базе каждому пользователю присваиваете порядковый номер (identity), а наружу отдаете криптографически преобразованное значение. И обратная операция — снаружи принимаете криптографически преобразованное значение (в нужном вам формате), применяете обратную функцию и получаете порядковый номер.

    А вот с необходимыми алгоритмами как раз и нужно подумать.

    Блочный шифр вам не подходит, так как размер блока редко менее 8 байт, числа будут слишком громоздкими.

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

    Если требуется криптостойкость — то нужно потратить время на подбор алгоритма.

    • 28 марта 2017 в 21:34

      0

      ↑

      ↓

      Тут видимо частью задачи является читаемость и запоминаемость для пользователей. Вроде как «мой логин XX00534».

  • 28 марта 2017 в 21:39 (комментарий был изменён)

    0

    ↑

    ↓

    Как по мне, раз уж городить огород, то один раз загнать в любую БД/файл уже случайно-сортированную последовательность — это несложно. Ну и как верно заметили, два параллельных запроса создадут коллизию. Можно пробовать использовать DELETE вместо SELECT и, если строка была затронута, — считать этот логин доступным.

    • 28 марта 2017 в 21:49

      0

      ↑

      ↓

      Для этого существуют sequence.

  • 28 марта 2017 в 22:03

    +1

    ↑

    ↓

    Реально вот так вот взяли, и воткнули в бд таблицу на 700М записей?

  • 28 марта 2017 в 22:03

    +3

    ↑

    ↓

    Тут недавно была волна на тему необходимости знаний алгоритмов и структур данных. КМК данный пост наглядно демонстрирует ответ на этот вопрос.

  • 28 марта 2017 в 22:44

    0

    ↑

    ↓

    В тему того, насколько бывает важно быстро получить простые, уникальные и не идущие по порядку числовые или буквенные коды:

    https://habrahabr.ru/company/boxowerview/blog/201308/
    https://habrahabr.ru/company/boxowerview/blog/201590/

    Там, из-за того, что все коды купонов шли один за другим, их очень быстро подобрали.

    Понятное дело, что уровней защиты должно быть несколько, и уникальный код, только один из них.

© Habrahabr.ru