Обнаружение дублирования для 3K входящих запросов в секунду, рекомендуемая структура данных / алгоритм? - PullRequest
Новая
       3

Обнаружение дублирования для 3K входящих запросов в секунду, рекомендуемая структура данных / алгоритм?

5 голосов
/ 16 ноября 2011

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

Эти запросы будут затем сохранены в mysql.

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

Мне нужно только хранить уникальные данные в mysql, так что бы вы посоветовали использовать для дублирования?

Опубликованные данные будут выглядеть так: 

<root>
<prop1></prop1>
<prop2></prop2>
<prop3></prop3>
<body>
maybe 10-30K of test in here
</body>
</root>

Я напишу метод, который будет хэшировать prop1, prop2, pro3 для создания уникального хеш-кода (тело может отличаться и все еще считаться уникальным).

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

У них больше шансов на дублирование опубликованных данных в течение 24 часов . Поэтому я могу удалять данные из этого словаря через каждые x часов.

Есть предложения по структуре данных для хранения дубликатов? А как насчет очистки и количества записей, которые я должен хранить, учитывая 3K запросов в секунду, то есть он очень быстро увеличится.

Примечание. Это 10К различных источников, которые будут публиковаться, и вероятность дублирования возможна только для данного источника. Это означает, что у меня может быть более одного словаря для группы источников, чтобы распространять информацию. Это означает, что если источник1 публикует данные, а затем источник2 публикует данные, изменения дублирования очень и очень низки. Но если source1 публикует сообщения 100 раз в день, вероятность дублирования очень высока.

Примечание: пожалуйста, пока игнорируйте задачу сохранения опубликованных данных в mysql, так как это отдельная проблема, обнаружение дублирования - мое первое препятствие, с которым мне нужна помощь.

Ответы [ 6 ]

1 голос
/ 16 ноября 2011

1) Настройте свою базу данных следующим образом 

ALTER TABLE Root ADD UNIQUE INDEX(Prop1, Prop2, Prop3);

INSERT INTO Root (Prop1, Prop2, Prop3, Body) VALUES (@prop1, @prop2, @prop3, @body) 
ON DUPLICATE KEY UPDATE Body=@body

2) Вам не нужны какие-либо алгоритмы или необычные ADT хэширования 

shell> mysqlimport [options] db_name textfile1 [textfile2 ...]

http://dev.mysql.com/doc/refman/5.1/en/mysqlimport.html Используйте флаги --replace или --ignore, а также --compress.

3) Все, что сделает Java, это ...

a) генерировать CSV-файлы, использовать класс StringBuffer, а затем каждые X секунд, менять местами свежий StringBuffer и передавать .toString старого в поток, чтобы сбросить его в файл / temp / SOURCE / TIME_STAMP. CSV

b) иногда запускает Runtime.getRuntime (). Exec команды mysqlimport

в) удалить старые файлы CSV, если есть проблема с пространством, или заархивировать их на сетевое хранилище / устройство резервного копирования

1 голос
/ 16 ноября 2011

Похоже, вам нужна структура хеширования, которая может добавлять и проверять наличие ключа в постоянное время. В этом случае попробуйте реализовать фильтр Bloom . Будьте осторожны, это вероятностная структура, т. Е. Она может сказать вам, что ключ существует, когда его нет, но вы можете сделать вероятность сбоя чрезвычайно низкой, если тщательно настроить параметры.

Редактировать : Хорошо, поэтому фильтры Блума не принимаются. Чтобы по-прежнему поддерживать постоянный поиск (хотя и не постоянную вставку), попробуйте заглянуть в Cuckoo hashing .

1 голос
/ 16 ноября 2011

Интересный вопрос.

Я бы, вероятно, посмотрел на некую структуру HashMap структуры HashMaps, где первый уровень HashMaps будет использовать источники в качестве ключей, а второй уровень будет содержать фактические данные (минимальные для обнаружения дубликатов) и использовать вашу функцию хеш-кода для хеширования. Для реальной реализации Java ConcurrentHashMap, вероятно, будет выбором.

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

Что касается очистки, я думаю, что вы должны измерить точное поведение с данными, подобными данным. Вам нужно узнать, как быстро растут данные, когда вы успешно удаляете дубликаты, и как они распределяются в HashMaps. С хорошим распределением и не слишком быстрым ростом я могу себе представить, что это достаточно хорошо, чтобы время от времени делать уборку. В противном случае, возможно, политика LRU будет хорошей.

0 голосов
/ 22 ноября 2011

Если вы используете строгую хеш-формулу , такую ​​как MD5 или SHA-1, , вам не нужно будет хранить какие-либо данные вообще .Вероятность дублирования практически равна нулю, поэтому, если вы найдете один и тот же результат хеширования дважды, второй является дубликатом.Учитывая, что MD5 составляет 16 байтов, а SHA-1 - 20 байтов, это должно снизить требования к памяти, что позволит сохранить больше элементов в кэше ЦП, что значительно повысит скорость.

Хранение этих ключей требует всего лишь небольшого хэшатаблица, за которой следуют деревья для обработки столкновений.

0 голосов
/ 16 ноября 2011

Используйте java.util.ConcurrentHashMap для построения карты из ваших хэшей, но убедитесь, что у вас есть правильный initialCapacity и concurrencyLevel, назначенные карте во время создания.

API-документы для ConcurrentHashMap содержат всю необходимую информацию:

initialCapacity - начальная емкость.Реализация выполняет внутреннее определение размеров для размещения этого множества элементов.

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

Вы должны иметь возможность использовать putIfAbsent для обработки запросов 3K, если правильно инициализировали ConcurrentHashMap - убедитесь, что это настроенокак часть вашего нагрузочного тестирования.

В какой-то момент попытка обработать все запросы на одном сервере может оказаться слишком большой, и вам придется балансировать нагрузку между серверами.В этот момент вы можете рассмотреть возможность использования memcached для хранения индекса хэшей вместо CHP.

Интересные проблемы, которые вам все равно придется решать, это:

  • загрузка всех хэшей в память при запуске
  • определение момента, когда выбрасывать хэши из карты в памяти
0 голосов
/ 16 ноября 2011

Ну, вы в основном ищете какой-то очень большой Hashmap и что-то вроде

if (map.put(key, val) != null) // send data

Существует множество различных реализаций Hashmap, но вы можете посмотреть на NBHM .Неблокирующие элементы, разработанные с учетом масштабируемых проблем, могут работать очень хорошо.На карте также есть итераторы, которые НЕ генерируют исключение ConcurrentModificationException при их использовании для обхода карты, что по сути является требованием для удаления старых данных, как я вижу.Также putIfAbsent - это все, что вам действительно нужно - но не знаю, если это эффективнее, чем просто пут, просто попросите Клиффа или проверьте источник.

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...