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

    Многие ли из нас сталкивались на практике с этим модным словом "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` = <random 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'];
    }

    Заключение


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

    Поделиться публикацией

    Похожие публикации

    Комментарии 113
      +7
      Если честно, не понимаю необходимости «случайности». Т.е. запрет на логины 0001, 0002, 0003 исходит из чисто эстетических хотелок заказчика. Единственное «разумное» объяснение, что он хочет скрыть количество зарегистрированных человеков. Я бы просто брал порядковый номер и обфусцировал/шифровал его, пока он не займёт необходимое количество бит. Т.е. нужно хранить только одно число — порядковый номер следующего пользователя. Учитывая, что речь идёт о 30 битах, то написать порождающую функцию без коллизий не выглядит сложной задачей.
        –1
        Вопрос безопасности не последний. Так что это не только вопрос эстетики. Часть взломов как раз базируется на том, что некий ID (в данном случае логин) известен в силу своей инкрементальности.
          +1
          Если у вас уже 700 млн пользователей, то любой случайный ID соответствует какому-то пользователю. Если в качестве порождающей функции использовать шифрование, то проблема безопасности если и не снимается, то снижается (т.е. простым инкрементом id не получить уже).
          Опять же, сам по себе идентификатор пользователя не несёт угрозы безопасности, потому что как минимум надо знать ещё и пароль. Если же злоумышленнику достаточно знать id пользователя, то «у вас что-то не так».
          Но я не настаиваю.
          0
          Мне попадалась задача сделать генерацию случайных кодов. По порядку решили их не выдавать, чтобы избежать случайных опечаток при вводе. С безопасностью это никак не связано, нужна была статистика. Сделал, как было описано в начале статьи, рекурсивно генерируя коды и проверяя, что они не существуют. Коды не долго живут, поэтому такой способ подходит. Но если бы они существовали долгое время и их было бы много, пришлось бы придумывать что-то подобное описанному.
          +9
          А чем вам изначальный вариант с генерацией случайного логина на лету не подошел? Скорость ответа будет реально деградировать лишь при приближении количества пользователей к лимиту (т.е. к 700 млн). То есть, если пользователь один — нам потребуется 1 запрос к базе для проверки его существования, если 350 млн — в среднем, два, если 467 млн — в среднем, три, и тд.
          Неужели у вас действительно столько пользователей? Неужели при таком количестве пользователей самая серьезная проблема — это генерация логинов?

          Пожалуйста, объясните, видимо, я чего-то не понял.
            0
            У нас генерируется номер сертификата по такой же логике, пока доходит до 2-х тысяч в день, и с каждым годом только растёт.
              –2
              Полученную строку можно рассматривать не только как логин, но и как уникальный номер. Сертификата, купона и т.п. Поэтому было решено написать алгоритм, который работал бы одинаково быстро при любом количестве уже сформированных строк.
                0
                Если число пользователей (сертификатов, купонов, чего угодно) будет приближаться к максимально допустимому, нужно будет срочно расширять диапазон, в любом случае, это не будет штатным режимом работы. Зачем закладываться на это случай? Ради вероятности того, что кто-то даст гарантию, что будет 699 млн пользователей, но не будет 700 млн?
                В качестве упражнения задача интересная, но куда более красивым (и эффективным) было бы следующее решение:
                1. Генерим 700 млн логинов по порядку и складываем в массив — это всего 5.6 Гб
                2. Когда приходит запрос — генерируем случайное число от 0 до текущего размера массива — 1, включительно
                3. В качестве ответа на запрос выдаем логин, лежащий в массиве на позиции, указанной этим случайным числом
                4. Удаляем этот логин из массива, методом «поменять местами с последним и уменьшить размер на 1»

                Вот и все. Оптимально как по памяти, так и по времени. Конечно, возникнут вопросы, если нужно high availability, но в вашем решении оно тоже никак не освещено.
                  0
                  «Всего» 6 гигов памяти на хранение не созданных (по сути бесполезных) логинов. Это правда красиво и эффективно?
                    0
                    Если требуется, чтобы они все были созданы, да еще и с жесткими ограничениями на время генерации одного логина — да. Если знаете решение лучше в этих условиях (O(1) на время генерации одного логина), поделитесь.
                    А вот если, как у автора, пользователей никогда не станет даже 350 млн, первый же подход «на лету» лучше всего.
                      0
                      При наличии требования «чтобы не требовалось памяти больше, чем O(число уже запрошенных логинов)», можно сделать немного более сложный алгоритм:
                      Храним все уже выданные логины в боре.
                      В каждом узле бора храним еще размер поддерева.
                      Для генерации нового логина проходимся по бору сверху вниз, каждый раз выбирая поддерево рандомно, с вероятностью, пропорциональной числу свободных логинов в нем. Если поддерева нет, то его размер считается равным 0, число свободных логинов посчитать несложно, и при переходе мы создаем новый пустой узел.

                      Такой алгоритм будет требовать больше памяти (на хранение размеров и указателей на детей в боре) при приближении к лимиту логинов, но в начале будет гораздо экономнее.
                    0
                    У сертификата как минимум внутри должна быть зашифрована чексумма, которая даст дополнительную защиту от перебора в лоб.
                  +3
                  Ожидал, что в конце получится микросервис по выдаче случайной строки с кластером из Cassandra-нод. И вывод из статьи типа «Теперь все уже почти работает, осталось только решить проблемы с консистентностью и наши пользователи наконец-то смогут насладиться своими уникальными логинами».

                  Присоединюсь, однако, к тем, кто не совсем понял — вот в последнем абзаце параграфа «Новый подход» — я так понял у нас есть файлик с 700 млн. логинов, мы потихоньку пэхэпэшкой берем из него случайные строки и запихиваем их в бд. Где тут плохое распределение?
                    –1
                    Распределение будет хорошее. Но взять из такого большого файла одну случайную строку не быстрее, чем из базы. Верно?
                      +3
                      Ну, во-первых, скорее всего быстрее ( мы не парсим SQL, мы не работаем с буффером базы и т.д. )
                      во-вторых, если мы понимаем, что наша строка фиксированной длины, то заммапив файл в память мы просто читаем данные по фиксированному сдвигу ( уверен в PHP есть механизмы как это сделать )
                      и в-третьих и в главных — мы можем это делать оффлайн — кинули, например 100 тысяч уникальных чисел в случайном порядке, достали в память соответсвующие строки ( и удалили из файла ), записали их в базу.
                      Это мы сделали оффлайн. После этого онлайн остается только достать из базы следующую по порядку запись ( а там уже лежат наши логины в случайном порядке ), это быстро. Когда эти 100 тысяч начнут кончаться — запишем в базу еще 100 тысяч
                        0
                        Это точно быстрее, если каждая запись занимает одну длину и они уже случайно перемешаны.
                        Не уверен, что есть функция в php, которая сотрёт запись из середины без перезаписи всего файла.

                        Была у меня подобная задача, я затирал начало файла пробелами и записывал сдвиг. Ночью переписывал файл, удаляя пробелы. В этом момент можно ещё раз отсортировать.
                          0
                          Я тут подумал, зачем затирать? это глупо. Просто сдвиг и хватит
                            0
                            Если мы боимся удаления из файла, то можно просто сгенерировать 700 миллионов уникальных чисел, записать в файл рядышком и это будет тот порядок, в котором мы забираем строки из первоначального файла ( то, на какой строке в этом файле мы сейчас находимся нужно запоминать отдельно ).
                            Но реально, поскольку это оффлайн операция, то окей, пусть даже мы постоянно переписываем файл — сколько это займет на ноутбуке разработчика — минуты? десятки минут? ну и окей.
                    0
                    Спасибо за предложенное решение, и описание всего процесса поиска. У нас сейчас используется Алгоритм генерации “на лету”, пока проблем нет, но меня это уже беспокоит. Есть номер подарочного сертификата, который должен быть уникальным, и при этом случайным. Сам шаблон похож на ваш: ZZ-888-999999999. Конечно шаблон менее важен, интересно само решение данной проблемы.
                      +1
                      А что беспокоит-то? Если у вас (как вы написали в другой ветке) около 2 тысяч генераций в день, то за 10 лет накопится около 7.3 млн записей в базе. При этом пространство значений очень велико, коллизий почти никогда не возникает, т.е. на одну генерацию потребуется 1 поиск в базе (и добавление). Неужели один-единственный поиск в MySQL таблице на 7.3 млн записей выполняется ощутимое время?
                        0
                        Проблем со скоростью пока нет, хотя я и не проверял, сколько запросов и времени используется при поиске свободного сертификата. Мне интересно, насколько проблема надумана мной, и когда надо начать беспокоиться. Проекту уже 8 лет, правда пока приблизились только к 2 млн.
                          0
                          Определенно, беспокоиться не стоит. Но интересно же найти элегантное решение, правда?
                            +3
                            По вашему хранить в базе 700 миллионов строк это элегантно? Вы же еще наверное бэкапы базы делаете. Сколько в итоге места это все занимает?
                              0
                              Итак, что же хочет заказчик
                              Есть конечный набор логинов. Необходимо каждому новому пользователю генерировать случайный логин из этого набора. Логин должен быть уникальным для каждого пользователя, он формируется по шаблону XX999999, где X — буква английского алфавита, 9 — цифра от 0 до 9.
                              Не хватает одного важного параметра — максимального времени на генерацию такого логина.
                              Т.к. разное время предполагает разные способы решения. Например если надо не дольше чем за 3 секунды, то можно предложить и «более элегантные» решения.
                              0
                              Дык по рассчетам получается, что проблем и не будет — запросов к базе в среднем будет 1, пока число сгенерированных сертификатов не приблизится к половине от возможных (я так понял, в вашем случае это случится через многие тысячи лет). Насчет скорости работы самой базы я не уверен — вроде как, при настроенном индексе тоже от размера зависеть не должно, но даже если и будет — сделаете шардирование, и дело с концом.
                              Не переживайте, проблема высосана из пальца.
                          +9
                          Берём пристойный симметричный шифр с произвольным размером блока, выбираем ключ наугад и шифруем им последовательные номера, получаем кажущуюся случайной последовательность с хорошими статистическими характеристиками, с гарантией отсутствия повторов. Скорость алгоритма не зависит от количества записей.
                            0
                            Это если есть возможность изменения заданного шаблона. Это не всегда возможно, т.к. ограничение может быть продиктовано другими связанными системами.
                              0
                              Изменять шаблон не требуется. Шифр — это по сути функция от целого числа, работающая в определённом диапазоне. Шаблон у ТС без труда преобразуется в число в диапазоне от 0 до 675999999 и обратно, так что нам всего лишь нужно хорошее преобразование, работающее в том же диапазоне.
                                0
                                А какой механизм гарантирует, что в ходе преобразования выдается новое уникальное рандомное число из диапазона от 0 до 675999999 (без похода в базу/кэш/файл/память что бы убедиться, что оно ранее не выдавалось)?
                                  0
                                  Счётчик выдаёт каждый раз новое уникальное число, шифр делает его похожим на случайное.
                                    0
                                    А где гарантия, что шифр 100% обратим, т.е. что числам 0 и 1 будут соответствовать разные шифротексты? Обычно от шифров это не требуется.
                                      0
                                      base64 c иным набором или порядком алфавита :)
                                        0
                                        Ещё как требуется-то, потому что если шифр не биекция, то как его вообще расшифровывать?
                                          0
                                          Да, что-то я хрень сказал, надо больше спать.
                                          Прошу понять и простить.
                              +10
                              Странная задача.
                              Можно сгенерировать весь набор доступных логинов на стороне вашего языка, 700кк это не много, и перемешать случайной сортировкой, например взяв md5 от логина. Положить их в базу и отдавать новый по порядку.
                              Последнего не занятого хранить в потокобезопасном кэше.
                              Собственно говоря, можно обойтись даже без базы, просто файликом и читать его со смещением по памяти на нужную строку. Благо длину строки можно сделать стандартной.
                              Если для вас 700кк 8ми символьных строк — это много, можно выбрать несколько произвольных диапазонов и по мере нужды генерить новые диапазоны.
                                0
                                Но в статье же описано что по порядку из базы не получится. Индексов в таблице с логинами у них нет (там только одно поле), а делать OFFSET у них долго, так как для этого MySQL перебирает все строки подряд с первой.
                                  0
                                  Так о чем nightwolf_du и говорит: «и перемешать случайной сортировкой», т.е. речь о том, что бы как угодно долго нагенерить, перемешать и записать. А уже потом последовательно вычитывать (т.е. предгенерация не только самих значений, но и рандомность).
                                    0
                                    Да я про генерацию рандомности понял. Вопрос именно вот в этом «последовательно вычитывать».
                                    К примеру, как вы будете последовательно вычитывать?
                                      0
                                      Банально тупо в лоб я бы добавил сюда инкремент в redis-е. Атомарно, быстро, гарантированно без коллизий.
                                        0
                                        Конкретно в данной задаче одно из условий стоит не использовать NoSQL.
                                          0
                                          Если <id, запись> не подходит — можно либо попробовать вычитку по внутреннему уникальному id записи в базе, (если это возможно для myssql, для pg насколько я знаю — варианты есть).
                                          Но самый лучший способ — просто положить в обычный файл на диске и читать со смещением по строкам в памяти.
                                            0
                                            SM + семафоры и «NoSQL» не требуется.
                                          0
                                          Но это для конкретно предложенного тут в треде варианта. Потому как изначально в базе я бы вообще не стал хранить данные автора.
                                              +1
                                              Другой вариант, безопасный для транзакций, проверялся в тестах на генерацию миллиона идентификаторов в 100 потоков — не было пропусков или дублирующихся идентификаторов.

                                              --- таблица для хранения идентификаторов
                                              DROP TABLE IF EXISTS `sequence`;
                                              CREATE TABLE `sequence` (
                                                `name` varchar(80) COLLATE utf8_bin NOT NULL,
                                                `value` int(20) unsigned NOT NULL,
                                                PRIMARY KEY (`name`)
                                              ) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_bin;
                                              
                                              -- процедура для получения очередного идентификатора
                                              DROP FUNCTION IF EXISTS `sequence_next`;
                                              DELIMITER ;;
                                              CREATE FUNCTION `sequence_next`(sequence_name char(80))
                                              RETURNS int(20)
                                              NOT DETERMINISTIC
                                              BEGIN
                                                  -- last_insert_id() умеет устанавливать новое значение
                                                  -- из-за MyISAM работает вне транзакции
                                                  update sequence set value=last_insert_id(value+1) where name=sequence_name;
                                                  return last_insert_id();
                                              END ;;
                                              DELIMITER ;
                                              
                                              -- инициализация последовательности
                                              INSERT INTO `sequence` (`name`, `value`) VALUES ('login',123456789); -- инициализация не с нуля, для примера
                                              


                                              Взять следующий
                                              SELECT sequence_next(:sequence_name) as `value`;
                                              


                                              Видел в интернет вариации таблицы sequence чтобы там были значения минимума, максимума, инкремента, но на практике не сталкивался с тем, чтобы прирост был отличный от единицы и счётчика останавливался.

                                              Если надо — допишу такое :)
                                                +1
                                                Вообще мой ответ такой же как Ваш.
                                                Извините, весь тред ответов на SO не прочитал заранее.
                                        +4
                                        Может стоило объяснить заказчику, что хранить 700 млн записей, которые и данных то не содержат, это как бы моветон? Тут и требования, и компетенция того, кто их составлял, вызывают вопросы…
                                          +5
                                          Хм. У меня на проекте генерируются случайные токены для каждой сессии, которые тоже должны быть уникальным и хранятся в БД.

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

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

                                          Кстати, могли бы использовать какой-нибудь Elasticsearch. Он вам и рандомную запись выберет очень-очень быстро и все что угодно. И ставить/настраивать довольно просто.
                                            0
                                            Нагенерировать заранее 700 млн случайных чисел, однозначно отображающихся в нужный алфавит, собрать табличку с полями
                                            id(непрерывный список из 700 млн чисел)
                                            login (случайный, заранее сгенерённый логин, про который заранее предпроверена уникальность. Прожку написать на C, она вам быстро сгенерит, чего надо. Для проверки незанятости можно в битмап положить имеющиеся логины — вам понадобиться всего ~80 мегабайт оперативки).
                                            табличу с пользователями сделать c id-никами и с автоинкрементом, login копировать при создании пользователя и не показывать в интерфейсе.
                                              0
                                              Да, когда останется ~ 1% свободных логинов, придется их переложить в какую-нибудь другую структуру данных — в массив, например и выбирать рандомно уже только из свободных.
                                              +3
                                              Зачем сразу то все генерировать? Пишите ф-цию, типа gen_login, она выплевывает вам готовый логин, рандомный, идете в кеш, если не попали, то используете этот логин, при этом пишете хеш от этого логина в БД и кеш в рамках транзакции, если попали, повторить, при старте приложения загоняете все использованные хеши в кеш.
                                              Как-то так.
                                                –1
                                                Можно и в базу записывать, тоже будет быстро и не скоро начнет тормозить. Но хотелось решить задачу «идеально».
                                                +1
                                                Транзакци… 100% когдато кто-то 2 юзера попытаются получить одинаковые логины
                                                  0
                                                  А если все сразу нагенерить, то придется вешать локи на бд при выборке, кому это нужно? в случае с кешем и функцией, это вероятность стремится к 0, да, и тут человек давал дельный совет по поводу очереди типа rabbitMQ
                                                  +3
                                                  гуиды надо было выдавать,
                                                  ну то есть алгоритм поставить в зависимость от времени, географии или еще чего нибудь
                                                  и сравнивать с уже существующими
                                                  итого не держать кучу ненужной инфы
                                                    0
                                                    Тоже в перую очередь подумал про UUID. Если не дают создавать сови логины, значит никто не расчитывает что пользователи их будут запоминать, значит можно вообщ любой делать, какая разница что пользователь будет копировать из тектовика/письма.
                                                      0
                                                      ...UUID и их предгенерация и складирование в быстрый кэш. Потому как хорошая реализация UUID все равно на генерацию требует времени больше, чем просто взять готовую запись их хранилища. Сам использую минутный крон который заполняет очередь Redis (обычные FIFO через lpush/rpop команды) не более чем Х готовыми UUID (Х зависит от требуемой скорости отдачи и потребляемой памяти). Получается очень простая и быстрая реализацию не требующая много памяти и не допускающая коллизий.
                                                    +3

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




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

                                                      0
                                                      Откуда 20Гб? Всего лишь 5.6 Гб. А если вместо текста логина выдавать его номер — будет всего 2.8 Гб.
                                                      0
                                                      (удалено)
                                                        +3
                                                        Масштабы катастрофы

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

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

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

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

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

                                                        Если требуется криптостойкость — то нужно потратить время на подбор алгоритма.
                                                          0
                                                          Тут видимо частью задачи является читаемость и запоминаемость для пользователей. Вроде как «мой логин XX00534».
                                                            +1
                                                            Вы можете преобразовать к любому формату. Это легко делается.
                                                              +1
                                                              Расскажите, пожалуйста, как преобразовывать к требуемому формату.
                                                                0
                                                                Наш формат XX999999, где XX — две буквы латинского алфавита. Всего возможных вариантов 10^6 * 26^2 = 676 млн., то есть любое число от 0 до 676 млн. соответствует красивому значению. Преобразовать такое число — остаток от деления на 10 — находите последнюю цифру, потом делите на 10 целочисленно и опять остаток отделения на 10 (вторую цифру)… потом остаток от деления на 26 для получения буквы.

                                                                Ваши ID-шки тоже должны быть не более 676 млн.

                                                                Остается сделать так, чтобы после преобразования ID-а число не выходило за пределы 676 млн. Так как преобразования закольцованы (т.е. результирующих чисел столько же, сколько входящих), то если ваше результирующее будет больше 676 млн., просто вычитайте из него 676 млн. При обратном преобразовании пробуйте придется прибавать 676 млн. Примерно так, детально нужно смотреть.
                                                            0
                                                            Автор упомянул, логин используется также в качестве ключа доступа (наверное, API)

                                                            Можно отдельно хранить бесполезно «красивый» короткий ключ, а для API выдавать 64-символьную свёртку sha256 «солёного» id пользователя
                                                            0
                                                            Как по мне, раз уж городить огород, то один раз загнать в любую БД/файл уже случайно-сортированную последовательность — это несложно. Ну и как верно заметили, два параллельных запроса создадут коллизию. Можно пробовать использовать DELETE вместо SELECT и, если строка была затронута, — считать этот логин доступным.
                                                              +1
                                                              Для этого существуют sequence.
                                                                0
                                                                загнать в любую БД/файл уже случайно-сортированную последовательность — это несложно

                                                                ну вот, оказалось что сложно
                                                                  0
                                                                  Складываем в атомарную очередь (сам использую Redis) и валя, коллизий нет.
                                                                  +4
                                                                  Реально вот так вот взяли, и воткнули в бд таблицу на 700М записей?
                                                                    0
                                                                    Да, отличный опыт.)
                                                                    +10
                                                                    Тут недавно была волна на тему необходимости знаний алгоритмов и структур данных. КМК данный пост наглядно демонстрирует ответ на этот вопрос.
                                                                      +1
                                                                      В тему того, насколько бывает важно быстро получить простые, уникальные и не идущие по порядку числовые или буквенные коды:

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

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

                                                                      Понятное дело, что уровней защиты должно быть несколько, и уникальный код, только один из них.
                                                                        +2
                                                                        Искренне надеюсь, что весь пост написан всерьез, а не ради троллинга. 20 гигабайт табличка ради генерации псевдослучайного числа это не очень хорошо. А если бы заказчик попросил XX99999999999?

                                                                        «Оказалось, что на деле получится около 700 миллионов логинов» звучит как «мы сначала написали, запустили, потом узнали сколько это итого, ого!». Это комбинаторика же, базовая формула любая подходящая, сразу можно было посчитать.

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

                                                                        А финальное решение очень похоже на открытый метод разрешения коллизий в хеш-таблицах, здорово что вы его переизобрели.
                                                                          –2
                                                                          Если бы условия задачи были другие, то и решение было бы другое. Количество вариантов было заранее посчитано, с комбинаторикой у нас все в порядке.

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

                                                                          Да, так и есть. Хотелось «идеального решения», поэтому смысл заморочиться с этим был. Интересная задача
                                                                          0
                                                                          И еще. Раз уж формат это две буквы и число, что мешало хранить его в базе в двух колонках, первая для букв как varchar и вторая уже для цифр как int или кто там в mysql минимален по размеру и вмещает 999999?
                                                                          Можете проверить, занимаемое таблицей место ведь в разы уменьшится?
                                                                            0
                                                                            занимаемое таблицей место ведь в разы уменьшится?

                                                                            Я не совсем понял вашу идею. Если уменьшится количество строк, то занимаемое место уменьшится, да.
                                                                            А как дальше быть с таблицей? Как выбирать случайную строку, как удалять. Поясните, хотя бы кратко.
                                                                              +1
                                                                              идея не количество строк изменить а другой тип данных использовать для сохранения. Сейчас, чтобы хранить в базе AA123456, вы используете грубо по одному байту на каждую позицию, тот самый varchar(8), хотя тут надо просто char(8). Итого 8*700M = 5.6 Gb чисто данных в базе минимум. Откуда там 20 Gb кстати?

                                                                              Если хранить как char(2) и mediumint, то есть insert into logins (valueLetters, valueNumber) values ('AB', '123456'), то есть получится 2 байта на буквы и еще 3 байта на номер, итого 5 байт, 8*700=3.5Gb, процентов 40 выигрыш по объёму.

                                                                              Запрос на поиск: select * from logins where valueLettes='AZ' and valueNumber=123456. Инкремент станет чуть-чуть сложнее, конечно.

                                                                              Mediumint тут хватает, у него максимальное значение 8388607 в mysql.
                                                                            +1

                                                                            Честно говоря, я такую задачу всегда на собеседовании спрашиваю (найти случайного юзера который выиграл в лотерею). И в случае с цифровыми id надо делать where id >= $phprand (вы в статье сравниваете)
                                                                            Но задача получилась в стиле — вначале придумаем проблему, потом стойко ее будем решать.

                                                                              0
                                                                              Согласен, хороший вопрос для собеседования. Можно оценить уровень знаний кандидата, ну или посмотреть, как он рассуждает.
                                                                              На счет решения проблем — именно на таких задачах и нарабатывается опыт. Можно было бы остановиться на генерации «на лету» и это прекрасно работало бы несколько лет. Но была возможно сделать чуть более идеальнее, почему нет.
                                                                                +1
                                                                                Без обид, но если бы у меня на проекте джун написал такое «чуть более идеальное решение», я бы ему руки оторвал.
                                                                                Потому что генерация «на лету» перестала бы работать лишь при приближении числа пользователей к общему доступному числу логинов, скажем, после 600-650 млн. Даже если предположить, что все остальные системы без проблем переживают такую нагрузку, в этот момент возникает важная бизнес-проблема: пользователям вот-вот перестанет хватать логинов и все рухнет, и поэтому принимается волевое решение добавить к логину одну цифру, после чего все работает.
                                                                                Вывод: вы существенно снизили читаемость кода в угоду случаю «нам гарантируется, что пользователей будет меньше 700 млн, но мы ожидаем 699 млн». Только вот в реальности таких гарантий никогда не бывает, так что вы снизили читаемость кода просто так.

                                                                                В качестве упражнения, «олимпиадной задачки», это, конечно, интересно, но в этом случае тут база вообще не нужна, массива хватит.
                                                                              +2
                                                                              Как вариант — готовить пул рандомных логинов заранее, резервируя их в нужном количестве (например 100 штук) в хранилище откуда их можно очень быстро достать, а саму генерацию пула вынести в отдельную задачу, за рамки запроса посетителя, которому требуется логин. Тогда время требуемое на генерацию рандомного логина уже не будет влиять на работу приложения которому эти логины нужны. Стратегий обновления такого пула можно придумать массу как и фоллбеков если вдруг всплеск нагрузки и пул исчерпан.
                                                                                0
                                                                                Берете два больших простых числа q и m, причем m в районе 700 миллионов, ну или какая нужна мощность множества логинов. И делаете как при сравнении по модулю m, т.е. решаете уравнение q = mt + r, где q и m — выбранные простые числа, t — порядковый номер очередного пользователя, r — искомый случайный айдишник, который потом нехитрыми преобразованиями можно конвертировать в нужный вам флрмат с буквами и цифрами.
                                                                                  0
                                                                                  Мне кажется все гораздо проще. Достаточно хранить интервалы пустых значений в БД (таблица из 2 колонок):
                                                                                  1. выбрать интервал из БД случайным образом
                                                                                  2. выбрать случайное значение в рамках выбранного интервала
                                                                                  3. удалить найденный на 1 шаге интервал из БД
                                                                                  4. разделить интервал найденный на 1 шаге на два, так чтобы он не содержал выбранного на 2 шаге значения
                                                                                  5. сохранить 2 новых интервала в БД
                                                                                    0
                                                                                    Мне кажется намного более простым хранение одного целого для порядкового номера пользователя и функцию свёртки числа в строку в виде перевода в N-значную систему исчисления, как делается для base64, только алфавит использовать свой, ещё и рандомно отсортированный.

                                                                                    Класс симметричного перевода числа в строку (PHP) github.com

                                                                                    Пример использования:

                                                                                    $alphaId= new AlphaId(array(
                                                                                    	'min_length' => 8, // какой длины символьный код
                                                                                    	'passkey' => 'соль',
                                                                                    ));
                                                                                    
                                                                                    $login = $alphaId->toAlpha($userId); // $userId = порядковый номер пользователя
                                                                                    
                                                                                    // можно сохранить в БД, а можно "развернуть обратно"
                                                                                    $userId = $alphaId->toId($login);
                                                                                    


                                                                                    Чтобы подогнать под требование «код должен быть XX999999» — переписывайте функцию свёртки и развёртки.

                                                                                    Например, комбинацией двух AlphaId, один из которых работает с буквами, а второй c цифрами.

                                                                                    P.S. Дурацкие логины у вас. Смысл делать их рандомными, если они всё равно в итоге, при 100% заполнении, будут последовательными.
                                                                                      0
                                                                                      И несмотря на определённую закономерность в последовательности, логины — это не купоны.
                                                                                      Ну и что в том, что они предсказуемо последовательны?
                                                                                      К логину ещё пароль добавляется.

                                                                                      Защищайтесь от брутфорса паролей, а не от подбора логинов.
                                                                                      +2
                                                                                      1. В вашем случае, можно хранить целые числа в одной колонке, это уменьшит размер таблицы как минимум в два раза. Максимальное значение будет 675999999, и оно спокойно умещается в Integer. Кодировать числа в логины можно следующим образом:
                                                                                      Encode to integer
                                                                                      <?php
                                                                                      global $alpabet;
                                                                                      $alpabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
                                                                                      
                                                                                      function encode($value) {
                                                                                      	global $alpabet;	
                                                                                      		
                                                                                      	$part3 = $value % 1000000;
                                                                                      	$value /= 1000000;
                                                                                      	
                                                                                      	$part2 = $alpabet[$value % strlen($alpabet)];
                                                                                      	$value /= strlen($alpabet);
                                                                                      		
                                                                                      	$part1 = $alpabet[$value % strlen($alpabet)];
                                                                                      	
                                                                                       	return sprintf("%s%s%'.06d", $part1, $part2, $part3);
                                                                                      }
                                                                                      
                                                                                      function decode($value) {
                                                                                      	global $alpabet;	
                                                                                      		
                                                                                      	$result = strpos($alpabet, $value[0]);
                                                                                      	$result *= strlen($alpabet);
                                                                                      	
                                                                                      	$result += strpos($alpabet, $value[1]);
                                                                                      	$result *= 1000000;
                                                                                      	
                                                                                      	$result += intval(substr($value, 2));
                                                                                      		
                                                                                       	return $result;
                                                                                      }
                                                                                      
                                                                                      echo decode("ZZ999999");
                                                                                      echo "<br>";
                                                                                      echo encode(675999999);
                                                                                      echo "<br>";
                                                                                      echo decode("BA999999");
                                                                                      echo "<br>";
                                                                                      



                                                                                      2. Так же в глаза бросается проблема с concurrency.
                                                                                      Чем меньше будет оставаться записей в базе, тем больше вероятность того, что два потока смогут взять один и тот же логин.
                                                                                      Её можно решить, добавив проверку кода возврата при удалении логина. Т.е. нужно выбирать другой логин (делать retry) если удалить не получилось, значит этот логин уже взял другой поток.

                                                                                        +2
                                                                                        Всегда думал, что знания у full stack девелопера должны быть достаточно сильные, чтобы так себя называть.
                                                                                        А так… Н — некомпетентность.
                                                                                          0
                                                                                          Это вопрос терминологии. Для меня full stack означает ширину знаний, а не только глубину. Вполне естественно, что в каких-то областях опыта больше, а в каких-то меньше.
                                                                                            0
                                                                                            А какой опыт работы в отрасли в режиме full time? Особо подчеркиваю, что не фриланс, а именно как основная работа и основной способ заработка? И сколько именно в звании «full stack»?

                                                                                            P.S. Вопрос «Сколько времени суммарно в часах от момента возникновения задачи до выкатки в прод?» так и остался без ответа.
                                                                                              0
                                                                                              Алексей, к чему эти личные вопросы? Вы что хотите доказать?
                                                                                                0
                                                                                                Ничего. Просто для статистики плюс просто отвечаю на комментарий чуть ниже. Если вопросы слишком личные — не отвечайте. Вопрос в P.S. к личным не относится и задается безотносительно уровня человека/проекта.
                                                                                          +2
                                                                                          Приведенное в статье решение плохо по многим критериям (в принципе в комментариях их уже все перебрали) и такой уровень для "full stack web developer" явно слабоват. Статью нужно ставить под тег «как НЕ нужно делать».
                                                                                            0
                                                                                            Новички часто спрашивают пример разбора полёта задачи по проектированию.
                                                                                              0
                                                                                              Но не виде же хабр статьи! Помилуйте, милейший, нас же читают дети!
                                                                                              0
                                                                                              Раз уж даете такую резкую оценку статье и моему уровню, хотелось бы получить более развернутый ответ, чем плохо решение.
                                                                                                0
                                                                                                1. Нет гарантии, что 2 паралельных запроса не выберут одну запись.
                                                                                                2. Бесполезная таблиа на ~700кк записей
                                                                                                  +1
                                                                                                  В комментариях критики более чем достаточно. На «Big Data» задача не тянет ни как. Это небыло бы в принципе проблемой, не будь написано так пафосно. Прометей несет огонь людям… А задача тривиальная даже для мидла.
                                                                                                  Сколько времени суммарно в часах от момента возникновения задачи до выкатки в прод?
                                                                                                    +1
                                                                                                    У меня как-то еще в студеньчества была следующая задача: необходимо было сделать анимацию, показывающую картинку попиксельно, причем пиксели должны были зажигаться в случайном порядке, и зажечься все за конечное время. Решено было следующим образом:
                                                                                                    — в цикле все пиксели перебирались последовательно
                                                                                                    — порядковый номер пикселя прогонялся через самодельную функцию шифрования, о которой ниже
                                                                                                    — функция шифрования выдавала номер пикселя, который нужно зажечь.
                                                                                                    Функция шифрования принимала параметром число в некоем диапазоне, а результатом выдавала другое число в том же самом диапазоне. Главное требование к функции: одному входному значению соответсвует одно выходное, и соответственно, наоборот. Примеры таких функций:
                                                                                                    — операции сложения, вычитания, XOR с фиксированным параметром
                                                                                                    — циклические сдвиги
                                                                                                    — перестановки битов
                                                                                                    — функция маппинга 1->1 по заранее рассчитанной случайной таблице
                                                                                                    — любые другие подобные обратимые операции, которые не теряют биты
                                                                                                    — их комбинации
                                                                                                    В моем случае функция состояла из нескольких таких шагов, чтобы визуально анимация воспринималась без повторений, все работало быстро, естественно, без использования SQL, NoSQL и прочих излишних вещей.
                                                                                                    Ваша задача могла бы быть решена подобным образом.
                                                                                                    0
                                                                                                    такой уровень для «full stack web developer» явно слабоват.

                                                                                                    написал в этом комментарии свое мнение по поводу уровня
                                                                                                    0
                                                                                                    Хранить в базе все логины, отсортированные по имени будет сложно?
                                                                                                      0

                                                                                                      У меня есть мысль, что раз нужны случайные логины, то между ними должны быть промежутки. Потому что иначе в предельном случае нет разницы, сгенерировали мы 700 млн вразброс или по порядку. Все равно куда ни ткни попадешь в существующий логин.


                                                                                                      Для какой цели это делалось, если не секрет?

                                                                                                        0
                                                                                                        Если не вдаваться в детали, то это сервис, который генерирует логины по заранее заданному шаблону.
                                                                                                          0

                                                                                                          Это понятно, а почему нельзя последовательно генерировать?

                                                                                                            0
                                                                                                            Нельзя по условиям задачи.
                                                                                                        0
                                                                                                        Этж элементарно. При генерации прицепите еще рэндомный ключ от 1 до 700KK, сортируйте по этому ключу и выбирайте по очереди.
                                                                                                          0
                                                                                                          звучит гениально. Может, такая случайность их не устраивала?
                                                                                                            0
                                                                                                            это добавление еще одного поля — увеличит вес таблицы. Да и я не уверен, что сортировка по этому полю будет быстрее чем RAND(). Точнее, приемлемо быстрой
                                                                                                              0
                                                                                                              Да и я не уверен, что сортировка по этому полю будет быстрее чем RAND().
                                                                                                              Она делается оффлайн, при подготовке данных. Пусть хоть месяц занимает.
                                                                                                            0
                                                                                                            Почему бы, в самом начале при генерации всех логинов, не расположить их в случайном порядке? А в базе добавить поле «использован». Тогда, логины можно было бы использовать по очереди, не опасаясь повторений и прямой итерации.
                                                                                                            3 поля в БД: id(PRIMARY, AUTO INCRREMENT), login(VARCHAR 8), isUsed(bool).
                                                                                                            тогда, брать одну строку по ключу и с isUsed = false.
                                                                                                              0
                                                                                                              Почему бы, в самом начале при генерации всех логинов, не расположить их в случайном порядке?

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

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

                                                                                                            Самое читаемое