Самая быстрая реализация c # для обработки конфликтов коротких ссылок

Question

Я предварительно генерирую короткие коды для создаваемой мной службы, которая сокращает ссылки. Это не обычное средство сокращения ссылок, поэтому я не могу использовать его с полки, поскольку нам нужно обрабатывать почти 1000 сокращений в секунду.

У меня есть служба, которая запускается каждые 12 часов, чтобы добавить еще 200 000 коротких ссылок в таблицу поиска для быстрой генерации ссылок.

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

Таблица сокращенных ссылок - 1.8M строк. У нас осталось 280 тысяч ссылок, прежде чем мы закончили. И теперь генерация 200 тыс. Ссылок занимает более 1 часа.

Я, очевидно, делаю что-то не так, возможно, тот факт, что я использую только List<string> для сравнения. Ниже приведен блок кода:

Stopwatch sw = Stopwatch.StartNew();
LtsDataContext ldc = new LtsDataContext();
List<string> currentCodes = ldc.ShortUrls.Select(s => s.ShortCode).ToList();
currentCodes = 
    currentCodes.Union(ldc.FastShortCodes.Select(s => s.ShortCode)).ToList();

int count = args.Length > 0 ? int.Parse(args[0]) : 200000;

List<string> newCodes = new List<string>(count);

for (int i = 0; i < count; i++)
{
    string newCode = Guid.NewGuid().ToString("N").Substring(0, 8);
    while (currentCodes.Contains(newCode) || newCodes.Contains(newCode))
        newCode = Guid.NewGuid().ToString("N").Substring(0, 8);
    newCodes.Add(newCode);
}

ldc.FastShortCodes.InsertAllOnSubmit(newCodes.Select(s => 
    new FastShortCode() { ShortCode = s }));
ldc.SubmitChanges();
Console.Write((decimal)sw.ElapsedMilliseconds / (decimal)1000);
Console.ReadKey();

Answer 1

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

Я предполагаю, что вы не хотите создавать последовательные ключи, потому что они уязвимы для разброса URL-адресов, но тогда вам следует начать с чего-то последовательного, а затем скрыть это.

Редактировать

Следуя предложению комментатора, я бы:

1. take a sequential key
2. shift left 8
3. add a random value between 0 and 255
4. encode base-62 (0-9,A-Z,a-z)

У вас не будет коллизий, и случайные биты будут означать, что человек, случайно пробующий URL, получит только один удар из каждых 255 попыток.

Answer 2

Поправьте меня, если я ошибаюсь, но похоже, что вы загружаете всю свою таблицу коротких ссылок (1,8 миллиона) в список, а затем ищете ее с помощью функции Contains, которая, как указал @Jeff Foster, является O (n) операция.

Почему бы не использовать более оптимистичный метод? В вашей базе данных добавьте уникальное ограничение в столбец ShortCode таблицы ShortUrls / FastShortCodes. Затем просто сгенерируйте новые короткие коды и попытайтесь вставить их. Если они не выполняют уникальное ограничение (что не должно происходить слишком часто), просто перехватите исключение и попробуйте снова.

Я также согласен с @egruin, что, используя подстроку GUID, вы ограничиваете себя только пятнадцатью символами (0-9, A-F). Я бы искал способ использовать по крайней мере все буквенно-цифровые символы (0-9, A-Z), которые бы значительно сократили число столкновений, с которыми вы сталкиваетесь.

Answer 3

Почему бы вам не использовать Dictionary для currentCodes и newCodes? Метод Contains для List должен обходить все записи списка O (n), в отличие от Dictionary, который выполняется в O (1).

EDIT1 Если вы все равно сохраняете все ссылки в базе данных, зачем вам Guid? Почему вы просто не используете первичный ключ базы данных в своих ссылках?

EDIT2 Поскольку вероятность того, что код уже существует, очень мала, вы можете попробовать вставить и поймать исключение, а затем повторить его (оптимистичная вставка).

Answer 4

Вот ваша проблема в этой строке:

currentCodes.Contains(newCode) || newCodes.Contains(newCode)

Это займет все больше и больше с каждым дополнением, которое описывает проблему.Я сомневаюсь, если вы заинтересованы в математической сложности этого, но это будет близко к (N * N) /2.

Решение заключается в использовании HashTable.