Прежде всего, я рекомендую вам избавиться от .replace(/[\/\+\=]/g, ''), так как это теряет случайность и, фактически, отображает некоторые уникальные orderIds, которые отличаются только по тем символам, чтобы они были одинаковыми.
Моя рекомендация будет использовать кодировщик base58 base-x , который будет напрямую кодировать то, что вы хотите. Эта библиотека кодировщика позволяет вам передавать точный набор символов, который вы хотите использовать для кодирования, и он просто использует его.
Вот мой предложенный код, который вы можете вставить:
const base58Encode = require('base-x')('123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz').encode;
А затем, когда вы создаете orderID, измените его на:
const idSeed = crypto.randomBytes(16)
const orderId = base58Encode(idSeed);
Я не знаю Я не знаю о вероятности дублирования (вам понадобится крипто / статистика для этого), но я запустил 10 000 000 orderId значений без дублирования, и я повторил это 10 раз, но до сих пор не получил дубликат. Очевидно, это не значит, что это не может произойти, но я делаю этот быстрый огонь, где Date.now() может даже не сильно отличаться. Я не мог запустить его более 10 000 000 раз, потому что у меня не хватило памяти, пытаясь сохранить все предыдущие значения orderId в объекте Set для проверки на наличие ошибок. Вы можете увеличить память для nodejs и запустить ее с еще более высокими значениями или поместить в сценарий оболочки и запускать ее снова и снова.
Вот моя программа для проверки дуплекса, если вы хотите запустить ее самостоятельно снова и снова:
const crypto = require('crypto');
function addCommas(str) {
var parts = (str + "").split("."),
main = parts[0],
len = main.length,
output = "",
i = len - 1;
while(i >= 0) {
output = main.charAt(i) + output;
if ((len - i) % 3 === 0 && i > 0) {
output = "," + output;
}
--i;
}
// put decimal part back
if (parts.length > 1) {
output += "." + parts[1];
}
return output;
}
let set = new Set();
const numToTry = 10_000_000;
const debugMultiple = 100_000;
for (let i = 0; i < numToTry; i++) {
if (i !== 0 && i % debugMultiple === 0) {
console.log(`Attempt #${addCommas(i)}`);
}
const idSeed = crypto.randomBytes(16).toString('base64') + '' + Date.now();
const orderId = Buffer.from(idSeed).toString('base64').replace(/[\/\+\=]/g, '');
//console.log(orderId);
if (set.has(orderId)) {
console.log(`Found conflict after ${addCommas(i)} attempts`);
console.log(`Conflicting orderId = ${orderId}`);
process.exit(1);
}
set.add(orderId);
}
console.log(`No dups found after ${addCommas(numToTry)} attempts`);
Прежде чем тратить на это много времени, я бы изучил вашу базу данных, чтобы узнать, сгенерирует ли она для вас уникальный ключ, который мог бы работать как orderId. Это распространенная проблема с базой данных.
Вот более новая версия, через которую я смог запустить до 1 000 000 000 идентификаторов. По-прежнему никаких конфликтов. Поскольку я никак не мог иметь в памяти гигантский объект Set с 1 000 000 000 идентификаторов, я подумал о нескольких способах сделать это. Я думал об использовании сервера Redis и сохранении там идентификаторов, поскольку он может использовать намного больше памяти. Но потом я предложил решение на основе дисков, которое можно масштабировать настолько высоко, насколько вы захотите. Вот основная идея c:
Одно из ваших значений orderId выглядит следующим образом:
zz6h6q6oRELJXmh4By4NUw1587006335064`
Когда я генерирую новый orderId, могу ли я его отделить в дисковое «ведро», которое содержит только идентификаторы с одинаковыми начальными символами, тогда я могу разделить все идентификаторы среди множества разных файлов.
Идея состоит в том, что если каждый идентификатор который начинается с тех же двух символов, хранится в том же файле, тогда никакие другие идентификаторы в любом другом файле не могут совпадать с идентификаторами в этом файле.
Затем вы можете выполнять свою работу в два прохода. При первом проходе генерируется 1 000 000 000 идентификаторов, и по мере их создания они записываются в соответствующий файл корзины на основе символов, с которых начинается идентификатор.
После того, как все идентификаторы сгенерированы и записаны в соответствующие им файлы сегментов, второй проход состоит в том, чтобы перебирать каждый из файлов сегментов по одному, загружать все идентификаторы в Set возьмите объект и посмотрите, есть ли конфликт. Если ничего не найдено, очистите этот Set и go для следующего файла. Это позволяет вам разделить часть памяти (связанную с объектом Set) по частям, чтобы использовать меньше памяти для большого числа идентификаторов.
Итак, вопрос в том, как разделить идентификаторы в ведро файлы? Поскольку каждый байт в значении идентификатора base64 представляет до 64 возможных значений, если вы используете только первые два символа идентификатора для определения сегмента, вы получите до 64 * 64 = 4096 сегментов. По какой-то причине (что должно быть связано с тем, как работает crypto.randomBytes(16)), я обнаружил, что в фактических значениях orderId на самом деле произошло только ~ 3800 сегментов.
Но если вы разделите 1 000 000 000 значений на 3800 сегментов, вы получите около 263 000 идентификаторов на сегмент. Мы уже показали, что раньше мы могли легко обрабатывать 15 000 000 идентификаторов в памяти, поэтому их должно быть более чем достаточно, чтобы можно было обрабатывать каждый сегмент в памяти по одному. На самом деле, если бы я был достаточно терпелив, мы могли бы, вероятно, от go до 10 000 000 000 с ведрами, основанными только на первых двух символах.
Если вам нужно больше сегментов, они могут основываться на первых трех символах, хотя тогда вы начнете получать слишком много файлов для одного каталога и вам придется начать разбивать файлы по каталогам, что может быть сделано, но это усложняет. вещи.
Итак, мне нужно создать имя файла корзины, основанное на первых двух символах идентификатора. Идентификаторы чувствительны к регистру (base64 использует верхний и нижний регистр для представления различных значений). Моя Windows файловая система нечувствительна к регистру, поэтому я не могу просто использовать первые две буквы в качестве имени файла. Итак, я создал простой алгоритм, который принимает двухсимвольный префикс смешанного регистра и превращает его в четырехзначное строчное имя. Он отображает строчные буквы «a» в «a_» и не строчные буквы, такие как «B» в «bb». Таким образом, за строчными буквами следует _, а за заглавными буквами следует вторая их копия. Таким образом, у вас должны быть такие идентификаторы:
"ab" => "a_b_"
"AB" => "aabb"
"aB" => "a_BB"
"Ab" => "aab_"
Не-буквенные символы (например, числа) просто сопоставляются с удвоением самих себя, как любые нестрочные символы. Таким образом, с помощью этого я могу получить значение идентификатора, взять первые два символа, посмотреть, к какому имени он принадлежит и добавить его в этот файл.
По соображениям производительности я создал Класс Bucket, который поддерживает кэш идентификаторов, ожидающих записи в память. Когда кэш внутри определенного сегмента достигает определенной длины (которую я сейчас установил на 3000), я сразу добавляю их все в файл и очищаю кэш сегмента. Когда я закончу генерировать все идентификаторы, я перебираю все сегменты и выкидываю все оставшиеся идентификаторы. При таком типе кэширования записи генерация идентификаторов в основном связана с процессором, а не с диском. Использование диска составляет около 30%. Одно ядро ЦП привязано во время генерации идентификатора. Вероятно, это может быть ускорено с помощью некоторых WorkerThreads.
Итак, когда все идентификаторы записаны в файлы корзины, а в памяти вообще ничего нет, пришло время прочитать каждую корзину файлы по одному, загрузите все свои идентификаторы в набор и посмотрите, есть ли конфликты. Каждый файл корзины представляет собой список идентификаторов, разделенных строками, все они начинаются с одного и того же префикса, например:
zzoexm2FE8DIrHnXpp8qw1587003338798
zzuP6LpusKIMeYrfl0WJnQ1587003338885
zz1itmTqA3yaFNo1KFUhg1587003338897
zz3TEFeqH965OTFCrFTjJQ1587003338904
zz8XQKvq11fCqn9kB4O2A1587003338904
zzaKMTFPct5ls7WW3YmcQ1587003338927
zzyX3htzIqi4zOq4Cxdg1587003338928
zzoHu6vIHMEgNMVY46Qw1587003338962
Итак, я просто читаю данный файл корзины, строка за строкой, проверяю каждый идентификатор на соответствие множеству ведро файл. Если это уже в наборе, есть конфликт. Выведите этот конфликт и прервите. Если это не набор, добавьте его в набор и продолжите с остальными идентификаторами в этом файле корзины. Поскольку этот файл корзины содержит все идентификаторы, начинающиеся с тех же двух символов, никакие другие идентификаторы в любом другом файле корзины не могут конфликтовать с ними, поэтому вы можете просто сравнить все эти идентификаторы друг с другом.
Чтение Bucket Files тесно связан с диском. При запуске 1 000 000 000 идентификаторов в 3844 файлах сегментов каждый файл занимает около 5 МБ, что составляет 22 ГБ данных. Каждый файл должен быть прочитан и разбит на строки, а затем каждый идентификатор добавлен в набор.
Я попробовал несколько разных механизмов для чтения файлов построчно и нашел их довольно медленными. Я начал с интерфейса readLine, который позволяет перебирать построчно через readStream. Это было бездарно. Затем я просто прочитал весь файл в память с fs.readFile() в гигантскую строку и затем вызвал .split("\n"), чтобы разбить его на строки. Это было на самом деле лучше, чем readLine, но все еще медленно. Я предположил, что копий данных было слишком много, что означало, что сборщику мусора приходилось работать много. Итак, наконец, я написал свою собственную версию readFile, которая считывает весь файл в многократно используемый буфер и разбивает его на строки, анализируя двоичный буфер напрямую. Это позволило сохранить как минимум пару копий данных и сэкономить много работы G C. Это было не быстро, но было быстрее. Повторное использование буфера также сэкономило мне много отдельных выделений в 5 МБ.
Первый проход (генерация идентификаторов) связан с ЦП. Я предположил, что мог бы немного ускорить это, запустив несколько рабочих потоков (вероятно, около 6, так как у меня 8-ядерный процессор) и позволив им создавать свои идентификаторы. Я раздавал 1/6 от количества каждому рабочему потоку, и когда они набирали 1000 или около того, они посылали эти 1000 обратно в основной поток, который вставлял их в нужные корзины. Но перед тем, как приступить к использованию WorkerThreads, мне нужно сделать несколько сравнительных тестов, чтобы увидеть, сколько общего времени первого прохода находится в функции crypto.randomBytes() по сравнению с другими, чтобы убедиться, что оно того стоит.
Второй проход полностью связан с диском, но фактическая пропускная способность диска ужасна (например, 60 МБ / с). Либо мой диск действительно отстой, nodejs не очень хорош в этом типе файлового ввода-вывода, либо есть большие издержки при обработке 3800 больших файлов (чтение записи в каталоге, поиск на диске для первого сектора, чтение как можно большего количества последовательных файлов). секторы, как можете, ищите еще раз, et c ...). Я мог бы попробовать это на моем самом быстром SSD, но я не хочу go записывать 20GB на мой SSD каждый раз, когда я играю с этим.
Я играл с увеличением UV_THREADPOOL_SIZE, думая, что, возможно, nodejs находился в очереди слишком много операций чтения / записи. Но производительность фактически ухудшилась, когда я увеличил размер пула потоков. Я полагаю, что по умолчанию 4 более чем достаточно, чтобы занять один контроллер диска. Больше, чем это, и вы просто просите головку диска переключаться между различными файлами, когда будет более эффективно прочитать все один файл, затем go к следующему файлу и т. Д.
Несмотря на то, что второй проход в основном связан с диском, все еще остается около 30% времени, затрачиваемого на не связанные с дисками вещи (на основе некоторых таймеров с высоким разрешением, которые я вставил). Таким образом, если это не принесло слишком большого вреда из-за конфликта на диске, возможно, вы могли бы распределить обработку различных файлов сегментов между группами WorkerThreads. По крайней мере, вы получите параллелизм в процессорной части этого процесса. Вы, вероятно, получите больше места на диске, хотя я не уверен, поможет ли это.
Наконец, файлы корзины могут быть разделены между дисками и даже в идеале между отдельными контроллерами SATA. У меня есть множество накопителей и пара контроллеров SATA, чтобы попробовать это, но затем он довольно точно задает c для моей системы.
Вот код для системы корзины.
// unique-test.js
const crypto = require('crypto');
const readline = require('readline');
const fs = require('fs');
const fsp = fs.promises;
const path = require('path');
const {fastReadFileLines} = require('./fast-read-file.js');
function delay(t, v) {
return new Promise(resolve => {
setTimeout(resolve, t, v);
})
}
function addCommas(str) {
var parts = (str + "").split("."),
main = parts[0],
len = main.length,
output = "",
i = len - 1;
while(i >= 0) {
output = main.charAt(i) + output;
if ((len - i) % 3 === 0 && i > 0) {
output = "," + output;
}
--i;
}
// put decimal part back
if (parts.length > 1) {
output += "." + parts[1];
}
return output;
}
// make a unique filename using first several letters of
// the string. Strings are case sensitive, bucket filenames
// cannot be so it has to be case neutralized while retaining
// uniqueness
function makeBucketKey(str) {
let piece = str.substr(0,2);
let filename = [];
// double up each character, but
for (let ch of piece) {
filename.push(ch);
if (ch >= 'a' && ch <= 'z') {
filename.push("_")
} else {
filename.push(ch);
}
}
return filename.join("").toLowerCase();
}
// this value times the number of total buckets has to fit in memory
const bucketCacheMax = 3000;
class Bucket {
constructor(filename, writeToDisk = true) {
this.items = [];
this.filename = filename;
this.cnt = 0;
this.writeToDisk = writeToDisk;
// We dither the bucketCacheMax so that buckets aren't all trying to write at the same time
// After they write once (and are thus spread out in time), then they will reset to full cache size
let dither = Math.floor(Math.random() * bucketCacheMax) + 10;
if (Math.random() > 0.5) {
dither = -dither;
}
this.bucketCacheMax = bucketCacheMax + dither;
}
// add an item to cache, flush to disk if necessary
async add(item) {
++this.cnt;
this.items.push(item);
if (this.items.length > this.bucketCacheMax) {
// the dithered cache size is only used on the first write
// to spread out the writes. After that, we want a full cache size
let priorBucketCacheMax = this.bucketCacheMax;
this.bucketCacheMax = bucketCacheMax;
await this.flush();
}
}
// write any cached items to disk
async flush() {
if (this.writeToDisk && this.items.length) {
let data = this.items.join("\n") + "\n";
this.items.length = 0;
if (this.flushPending) {
throw new Error("Can't call flush() when flush is already in progress");
}
function flushNow() {
this.flushPending = true;
return fsp.appendFile(this.filename, data).finally(() => {
this.flushPending = false;
});
}
// we write to disk with retry because we once go EBUSY (perhaps from a backup program)
let retryCntr = 0;
const retryMax = 10;
const retryDelay = 200;
const retryBackoff = 200;
let lastErr;
function flushRetry() {
if (retryCntr > retryMax) {
throw lastErr;
}
return flushNow.call(this).catch(err => {
lastErr = err;
console.log("flushNow error, retrying...", err);
return delay(retryDelay + (retryCntr++ * retryBackoff)).then(() => {
return flushRetry.call(this);
});
});
}
return flushRetry.call(this);
}
this.items.length = 0;
}
delete() {
return fsp.unlink(this.filename);
}
get size() {
return this.cnt;
}
}
class BucketCollection {
constructor(dir, writeToDisk = true) {
// map key is bucketID, value is bucket object for that key
this.buckets = new Map();
this.dir = dir;
}
add(key, data) {
let bucket = this.buckets.get(key);
if (!bucket) {
let filename = path.join(this.dir, key);
bucket = new Bucket(filename, writeToDisk);
this.buckets.set(key, bucket);
}
return bucket.add(data);
}
async flush() {
// this could perhaps be sped up by doing 4 at a time instead of serially
for (let bucket of this.buckets.values()) {
await bucket.flush();
}
}
async delete() {
// delete all the files associated with the buckets
for (let bucket of this.buckets.values()) {
await bucket.delete();
}
}
get size() {
return this.buckets.size;
}
getMaxBucketSize() {
let max = 0;
for (let bucket of this.buckets.values()) {
max = Math.max(max, bucket.size);
}
return max;
}
}
// program options
let numToTry = 100_000;
let writeToDisk = true;
let cleanupBucketFiles = true;
let skipAnalyze = false;
let analyzeOnly = false;
// -nodisk don't write to disk
// -nocleanup erase bucket files when done
// -analyzeonly analyze files in bucket directory only
if (process.argv.length > 2) {
let args = process.argv.slice(2);
for (let arg of args) {
arg = arg.toLowerCase();
switch(arg) {
case "-nodisk":
writeToDisk = false;
break;
case "-nocleanup":
cleanupBucketFiles = false;
break;
case "-skipanalyze":
skipAnalyze = true;
break;
case "-analyzeonly":
analyzeOnly = true;
break;
default:
if (/[^\d,]/.test(arg)) {
console.log(`Unknown argument ${arg}`);
process.exit(1);
} else {
numToTry = parseInt(arg.replace(/,/g, ""), 10);
}
}
}
}
let bucketDir = path.join(__dirname, "buckets");
let collection = new BucketCollection(bucketDir, writeToDisk);
console.log(`Running ${addCommas(numToTry)} random ids`);
const debugMultiple = 100_000;
async function analyze() {
let cntr = 0;
const cntrProgress = 10;
const cntrProgressN = 10n;
let buffer = null;
let times = [];
async function processFile(file) {
if (cntr !== 0 && cntr % cntrProgress === 0) {
let sum = 0n;
for (let i = 0; i < cntrProgress; i++) {
sum += times[i];
}
console.log(`Checking bucket #${cntr}, Average readFileTime = ${sum / cntrProgressN}`);
times.length = 0;
}
++cntr;
let set = new Set();
let startT = process.hrtime.bigint();
let buffer = null;
let result = await fastReadFileLines(file, buffer);
let data = result.lines;
// keep reusing buffer which may have been made larger since last time
buffer = result.buffer;
//let data = (await fsp.readFile(file, "utf8")).split("\n");
let afterReadFileT = process.hrtime.bigint();
for (const lineData of data) {
let line = lineData.trim();
if (line) {
if (set.has(line)) {
console.log(`Found conflict on ${data}`);
} else {
set.add(line);
}
}
}
let loopT = process.hrtime.bigint();
let divisor = 1000n;
let readFileTime = (afterReadFileT - startT) / divisor;
times.push(readFileTime);
// console.log(`readFileTime = ${readFileTime}, loopTime = ${(loopT - afterReadFileT) / divisor}`);
/*
let rl = readline.createInterface({input:fs.createReadStream(file), crlfDelay: Infinity});
for await (const line of rl) {
let data = line.trim();
if (data) {
if (set.has(data)) {
console.log(`Found conflict on ${data}`);
} else {
set.add(data);
}
}
}
*/
}
if (analyzeOnly) {
let files = await fsp.readdir(bucketDir);
for (let file of files) {
let fullPath = path.join(bucketDir, file)
await processFile(fullPath);
}
} else {
for (let bucket of collection.buckets.values()) {
await processFile(bucket.filename);
}
}
}
async function makeRandoms() {
let start = Date.now();
if (analyzeOnly) {
return analyze();
}
for (let i = 0; i < numToTry; i++) {
if (i !== 0 && i % debugMultiple === 0) {
console.log(`Attempt #${addCommas(i)}`);
}
const idSeed = crypto.randomBytes(16).toString('base64') + '' + Date.now();
const orderId = idSeed.toString('base64').replace(/[\/\+\=]/g, '');
//console.log(orderId);
let bucketKey = makeBucketKey(orderId);
await collection.add(bucketKey, orderId);
}
console.log(`Total buckets: ${collection.size}, Max bucket size: ${collection.getMaxBucketSize()}`);
//console.log(`No dups found after ${addCommas(numToTry)} attempts`);
await collection.flush();
let delta = Date.now() - start;
console.log(`Run time for creating buckets: ${addCommas(delta)}ms, ${addCommas((delta / numToTry) * 1000)}ms per thousand`);
if (!skipAnalyze) {
console.log("Analyzing buckets...")
await analyze();
}
if (cleanupBucketFiles) {
console.log("Cleaning up buckets...")
await collection.delete();
}
}
makeRandoms();
И, вот мой зависимый файл (находится в том же каталоге) для моей более быстрой функции чтения файла:
// fast-read-file.js
const fsp = require('fs').promises;
async function fastReadFile(filename, buffer = null) {
let handle = await fsp.open(filename, "r");
let bytesRead;
try {
let stats = await handle.stat();
if (!buffer || buffer.length < stats.size) {
buffer = Buffer.allocUnsafe(stats.size);
}
// clear any extra part of the buffer so there's no data leakage
// from a previous file via the shared buffer
if (buffer.length > stats.size) {
buffer.fill(0, stats.size);
}
let ret = await handle.read(buffer, 0, stats.size, 0);
bytesRead = ret.bytesRead;
if (bytesRead !== stats.size) {
// no data leaking out
buffer.fill(0);
throw new Error("bytesRead not full file size")
}
} finally {
handle.close().catch(err => {
console.log(err);
});
}
return {buffer, bytesRead};
}
async function fastReadFileLines(filename, buf = null) {
const {bytesRead, buffer} = await fastReadFile(filename, buf);
let index = 0, targetIndex;
let lines = [];
while (index < bytesRead && (targetIndex = buffer.indexOf(10, index)) !== -1) {
// the buffer may be larger than the actual file data
// so we have to limit our extraction of data to only what was in the actual file
let nextIndex = targetIndex + 1;
// look for CR before LF
if (buffer[targetIndex - 1] === 13) {
--targetIndex;
}
lines.push(buffer.toString('utf8', index, targetIndex));
index = nextIndex;
}
// check for data at end of file that doesn't end in LF
if (index < bytesRead) {
lines.push(buffer.toString('utf8', index, bytesRead));
}
return {buffer, lines};
}
module.exports = {fastReadFile, fastReadFileLines};
// if called directly from command line, run this test function
// A file of ids named "zzzz" must exist in this directory
if (require.main === module) {
let buffer = Buffer.alloc(1024 * 1024 * 10, "abc\n", "utf8");
fastReadFileLines("zzzz", buffer).then(result => {
let lines = result.lines;
console.log(lines[0]);
console.log(lines[1]);
console.log(lines[2]);
console.log("...");
console.log(lines[lines.length - 3]);
console.log(lines[lines.length - 2]);
console.log(lines[lines.length - 1]);
}).catch(err => {
console.log(err);
});
}
Сначала вы создаете подкаталог с именем "buckets", в котором вы работаете это. Затем вы запускаете это из командной строки:
node unique-test.js 1,000,000,000
Существуют некоторые поддерживаемые параметры командной строки (в основном используются при отладке):
-nodisk Don't write to disk
-nocleanup Don't cleanup generated disk files when done
-skipAnalyze Just generate bucket files, don't analyze them
-analyzeOnly Use previously generated bucket files and analyze them
Число, которое вы передаете в командной строке сколько идентификаторов генерировать. Если вы ничего не передаете, по умолчанию это 100 000. Для удобства чтения он обрабатывает запятые.