Системный дизайн Google Trends?

Question

Я пытаюсь выяснить системный дизайн за Google Trends (или любую другую такую ​​масштабную функцию тренда, как Twitter).

Проблемы:

• нужно обрабатывать большое количество данных для расчета тренда.

• поддержка фильтрация - по времени, регион, категория и т.д.

• Нужен способ хранения для обработки архивирования/в автономном режиме. Для поддержки фильтрации может потребоваться многозадачное хранилище.

Это то, что мое предположение (у меня нулевой опыт Практической технологий MapReduce/NoSQL)

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

Как и ведение списка запросов по временной метке, области поиска, категории и т.д.

Пример:

Поиск Kurt Cobain термина:

Kurt-> (Time stamp, Region of search origin, category ,etc.) 

Cobain-> (Time stamp, Region of search origin, category ,etc.) 

Вопрос:

• Как они эффективно вычисляют частоту поискового запроса?

• Другими словами, учитывая большой набор данных, как они находят 10 наиболее распространенных элементов в распределенной масштабируемой манере?

Answer 1

Ну ... выяснение верхних K-терминов на самом деле не является большой проблемой. Одной из ключевых идей в этой области была идея «потоковой обработки», то есть выполнить операцию за один проход данных и пожертвовать некоторой точностью, чтобы получить вероятностный ответ.Таким образом, предположим, что вы получите поток данных, как следующее:

A B K A C A B B C D F G A B F H I B A C F I U X A C

Что вы хотите, верхние элементы K. Наивно, можно было бы поддерживать счетчик для каждого элемента, а в конце сортировать по количеству каждого элемента. Это занимает O(U) пространство и O(max(U*log(U), N)) время, где U - количество уникальных предметов, а N - количество элементов в списке.

В случае, если U невелик, это не большая проблема. Но как только вы попадаете в область поисковых журналов с миллиардами или триллионами уникальных поисков, потребление пространства начинает становиться проблемой.

Итак, люди придумали «подсчеты» (вы можете читать больше здесь: count min sketch page on wikipedia). Здесь вы поддерживаете хэш-таблицу А длины n и создать два хэшей для каждого элемента:

h1(x) = 0 ... n-1 с равновероятно

h2(x) = 0/1 каждая с вероятностью 0,5

Затем вы делаете A[h1[x]] += h2[x]. Главное наблюдение состоит в том, что, поскольку каждое значение случайным образом хешируется до +/- 1, E[ A[h1[x]] * h2[x] ] = count(x), где E - ожидаемое значение выражения, а count - количество раз x, появившееся в потоке.

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

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

Answer 2

Как именно конкретная частная компания делает это, вероятно, не является общедоступной, и как оценить эффективность такой системы на усмотрение разработчика (будь то вы или Google или кто)

Но многие инструменты и исследования там, чтобы вы начали. Ознакомьтесь с некоторыми из инструментов Big Data, включая многие из проектов Apache верхнего уровня, например Storm, что позволяет обрабатывать потоковые данные в режиме реального времени.

. . .

Также ознакомьтесь с некоторыми из конференций «Большие данные и веб-наука» как KDD или WSDM, а также документы, потушить Google Research

Как разработать такую ​​систему, является сложной задачей, без правильного ответа, но инструменты и исследования доступны, чтобы вы начали