После прочтения всех ваших вопросов ( уникальное ограничение делает хэши бесполезными? , 512-битный хеш против 4 128-битного хеша и сжатие текста URL (не сокращается) и сохранение в mysql ), я понял, что ваша проблема более или менее следующая:
"Мне нужно хранить + 150M URL-адресов в mySQL, используя 8 ГБ ОЗУ, и при этом сохранять хорошую производительность при их записи и извлечении, потому что каждый день я буду обновлять их, поэтому я получу множество URL-адресов проверьте их по базе данных. На самом деле она имеет 50 миллионов URL-адресов и будет расти примерно на 1 миллион каждый день в следующие 3 месяца. "
Это так?
Важны следующие моменты:
Как формат URL, который вы сохраните? Вам нужно будет прочитать URL-адрес обратно или просто обновить информацию о нем, но никогда не выполнять поиск по частичным URL-адресам и т. Д.?
Предполагая, что URL = "http://www.somesite.com.tv/images/picture01.jpg", и что вы хотите сохранить все, включая имя файла. Если оно отличается, пожалуйста, предоставьте более подробную информацию или исправьте мои предположения об ответе .
Если можно сэкономить место, заменив некоторую группу символов в URL. Не все символы ASCII допустимы в URL, , как вы можете видеть здесь: RFC1738 , поэтому вы можете использовать их для представления (и сжатия) URL. Например: использование символа 0x81 для обозначения «http://" может заставить вас сохранить 6 символов, 0x82 для обозначения« .jpg »может сэкономить еще 3 байта и т. Д.
Некоторые слова могут быть очень распространенными (например, «изображение», «картинка», «видео», «пользователь»). Если вы выбираете пользовательские символы от 0x90 до 0x9f + любой другой символ (например, 0x90 0x01, 0x90 0x02, 0x90 0xfa) для кодирования таких слов, вы можете иметь 16 * 256 = 4096 «словарных статей» для кодирования наиболее часто используемых слов. Вы будете использовать 2 байта для представления 4 - 8 символов.
Редактировать: , как вы можете прочитать в упомянутом выше RFC, в URL вы можете иметь только печатные символы ASCII. Это означает, что должны использоваться только символы от 0x20 до 0x7F с некоторыми замечаниями, сделанными в RFC. Таким образом, любой символ после 0x80 (шестнадцатеричное обозначение будет десятичным символом 128 в таблице ASCII) не должен использоваться. Итак, если можно выбрать один символ (скажем, 0x90) в качестве одного флага, чтобы указать «следующий байт - это указатель в словаре, индекс, который я буду использовать». Один символ (0x90) * 256 символов (от 0x00 до 0xFF) = 256 записей в словаре. Но вы также можете использовать символы от 0x90 до 0x9f (или от 144 до 159 в десятичном виде), чтобы указать, что они являются флагом для словаря, что дает вам 16 * 256 возможностей ...
Эти 2 метода могут сэкономить вам много места в вашей базе данных и являются обратимыми, без необходимости беспокоиться о коллизиях и т. Д. Вы просто создадите словарь в своем приложении и будете кодировать / декодировать URL-адреса, используя его, очень быстро, делая вашу базу данных намного легче.
Поскольку у вас уже есть + 50M URL, вы можете генерировать статистику на их основе, чтобы создать лучший словарь.
Использование хэшей : Хэши в этом случае являются компромиссом между размером и безопасностью. Насколько плохо будет, если вы столкнетесь?
И в этом случае вы можете использовать парадокс дня рождения , чтобы помочь вам.
Прочитайте статью, чтобы понять проблему: если бы все входные данные (возможные символы в URL) были эквивалентны, вы могли бы свести на нет вероятность столкновения. И можно рассчитать обратное: учитывая вашу приемлемую вероятность столкновения и количество файлов, насколько широким должен быть ваш диапазон? И поскольку ваш диапазон точно связан с количеством битов, сгенерированных хэш-функцией ...
Редактировать: если у вас есть хеш-функция, которая дает вам 128 битов, у вас будет 2 ^ 128 возможных результатов. Итак, ваш «диапазон» в парадоксе дня рождения равен 2 ^ 128: это похоже на то, что в вашем году 2 ^ 128 дней вместо 365. Итак, вы вычисляете вероятности столкновения («два файла равны * 1056»). * родился в тот же день с годом , у которого 2 ^ 128 дней вместо 365 дней. Если вы решите использовать хеш, который дает вам 512 бит, ваш диапазон будет от 0 до 2 ^ 512 ...
И, опять же, помните RFC: не все байты (256 символов) являются действительными в мире Интернета / URL. Итак, вероятность столкновений уменьшается. Лучше для вас:).