Быстрое сравнение случайных строк в MySQL DB

Question

Мне нужно хранить 1000-е (и, возможно, скоро 100 000 или, возможно, миллионы) уникальные случайные строки из 12 символов в базе данных. Каждый раз, когда мне приходится генерировать новый код (фактически выполняемый партиями в 10 000 + с), мне нужно сравнить его с существующей базой данных, чтобы убедиться, что не будет дубликатов, - но также когда код «выкуплен» пользователем, Мне нужно обеспечить его существование.

Обе эти задачи, вероятно, будут очень медленными, поэтому я хочу сделать их максимально упрощенными. Для начала я убедился, что строки хранятся в формате BINARY в БД с индексом на них. Это, очевидно, быстрее, чем CHAR, VARCHAR и VARBINARY.

Я думал о попытках сделать дальнейшие улучшения, и я придумал эту простую идею: Хранение первого символа в качестве TINYINT в индексированном столбце и сравнение этого в первую очередь - таким образом, мы надеемся быстрее найти совпадающие записи.

Например:

public function getFirstCharAsNum($code) { 
    $firstChar = substr($code, 0); 
    $firstCharHex = bin2hex($firstChar); 
    $prefix = hexdec($firstCharHex); 
    return $prefix; 
} 

public function isDuplicate($generatedCode) { 

    $result = false; 

    $params["code"] = $generatedCode; 
    $params["prefix"] = getFirstCharAsNum($generatedCode); 

    $STH = $this->_db->prepare("SELECT count(*) FROM codes 
     WHERE prefix = :prefix AND code = :code;"); 

    try { 
     $result = $STH->execute($params); 
    } catch (PDOException $e) { 
     throw new Exception($e->getMessage()); 
    } 

    $result = $STH->fetch(PDO::FETCH_COLUMN); 

    if($result) { 
     return true; 
    } else { 
     return false; 
    }   

} 

Идея заключается в том, что он будет пытаться второй частью операции И если он находит совпадение, и поиск TINYINTs должен быть намного быстрее, чем в целом BINARY (12).

Действительно ли это быстрее? Или добавляет дополнительный поиск, чтобы замедлить меня?

Спасибо.

Answer 1

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

Вы могли бы вместо этого подготовить таблицу с заранее сформированными случайными кодами. Затем запомните смещение в таблице Codes. Всякий раз, когда вам нужен новый код, просто введите смещение -я строка из таблицы Кодов и приращение смещение на единицу; это, конечно, нужно делать атомарно, с READ LOCK.

независимый поток может генерировать случайные коды всякий раз, когда подходит (например, всякий раз, когда нагрузка системы достаточно низка, в ночное время; и т.д.) и INSERT IGNORE их в таблице: Codes

CREATE TABLE Codes (
    offset INTEGER PRIMARY KEY NOT NULL AUTO_INCREMENT, 
    sequence BINARY(12) 
); 

Для того, чтобы «генерировать» код теперь вам нужно выполнить только один запрос, который выполняется в O (1), поскольку он является выборкой для фиксированного адреса. Может быть, два запроса, если вы храните адрес в код смещения нуля:

LOCK TABLES test WRITE; 
SELECT datum.sequence FROM Codes AS datum 
    JOIN Codes AS ndx ON (datum.offset = ndx.sequence AND ndx.offset = 0); 
UPDATE Codes SET sequence = sequence + 1 WHERE offset = 0; 
UNLOCK TABLES; 

Нить, которая вставляет новые коды будут испытывать замедление, но не очень много этого (он также будет использовать LOCK TABLES LOW PRIORITY WRITE на каждом блоке INSERT с). Но все процессы, требующие новых кодов, будут быстро разряжаться.

Конечно, поток «пополнения» будет считывать текущее смещение и COUNT(*) из таблицы Codes и отказываться работать, если имеется больше, чем количество доступных кодов.

Проверка и искупительная

Чтобы сделать это, мы можем просто добавить «искупил» булево столбец.Для дальнейшего повышения скорости вы можете использовать горизонтальный partitioning, разделив таблицу кодов на N хэшированных разделов. Таким образом, не только любые поисковые запросы будут выполняться только на небольшом подмножестве данных (это не отличное улучшение над индексированием b-дерева ...), но блокировка и обновление могут быть распределены между таблицами.

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

Answer 2

Мне нужно хранить 1000s (и, возможно, в ближайшее время 100,000s возможно даже миллионы) уникальных случайных строк из 12 символов в базе данных

Если они действительно случайным образом, вероятность столкновения является {число действительных записей}/{число возможных записей}

Даже если CharacterSet вы выбираете из только содержит цифры, а затем, с 10 миллионов существующих записей вероятность столкновения 10000000/1, 0 00 000 000 000 = 1/100 000, поэтому то, что вы описываете, действительно пустая трата времени. Добавьте уникальный индекс в значения в базе данных - если вы получаете уникальное нарушение ограничений, пытающееся добавить новое значение, а затем восстановите значение.

(с 36 символов репертуара, вероятность столкновения составляет около 1/473838000000)