После прочтения всех ваших вопросов (уникальное ограничение делает хеши бесполезными?, 512-битный хэш против 4 128-битного хэша и сжатие текста url (не сокращение) и сохранение в mysql), я понял, что ваша проблема в большей или минус следующее:
"Мне нужно хранить 150 миллионов 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-адреса, используя его, очень быстро, делая ваша база данных намного легче.
Поскольку у вас уже есть более 50 миллионов URL-адресов, вы можете генерировать статистику на их основе, чтобы создать лучший словарь.
Использование хешей. В данном случае хеши представляют собой компромисс между размером и безопасностью. Насколько плохо будет, если вы попадете в столкновение? И в этом случае вы можете использовать парадокс дня рождения, чтобы помочь вам.
Прочтите статью, чтобы понять проблему: если бы все входные данные (возможные символы в URL-адресе) были эквивалентны, вы могли бы стимулировать вероятность столкновения. И мог бы вычислить обратное: учитывая вашу приемлемую вероятность столкновения и количество файлов, насколько широким должен быть ваш диапазон? И поскольку ваш диапазон точно связан с количеством бит, генерируемых хеш-функцией ...
Изменить: если у вас есть хеш-функция, которая дает вам 128 бит, у вас будет 2 ^ 128 возможных результатов. Итак, ваш «диапазон» в парадоксе дня рождения равен 2 ^ 128: это похоже на то, что в вашем году 2 ^ 128 дней вместо 365. Итак, вы вычисляете вероятность столкновения («два файла являются < em> родился в тот же день, с годом, в котором 2 ^ 128 дней вместо 365 дней). Если вы решите использовать хэш, который дает у вас 512 бит, ваш диапазон будет от 0 до 2 ^ 512 ...
И, опять же, помните о RFC: не все байты (256 символов) действительны в мире Интернета / URL. Таким образом, вероятность столкновений снижается. Для тебя лучше :).
person
woliveirajr
schedule
15.09.2011
