разработать систему, поддерживающую массовое хранение данных и запросы

Question

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

Описание:

В IDC генерируется огромное количество записей, каждая запись состоит из URL-адреса, IP-адреса, который посещает URL-адрес, и времени, когда происходит посещение.Запись, вероятно, можно сформулировать как структуру, подобную этой, но я не уверен, какой тип данных я должен выбрать, чтобы представить их:

struct Record {
    url;  //char *
    IP;   //int?
    visit_time;   //time_t or simply a number?
}

Требования:

Разработайте систему для хранения 100 миллиардов записей, а также система должна поддерживать как минимум 2 вида запросов:

Сначала, с учетом периода времени (t1, t2) и IP, запросите, сколькоURL-адрес, который этот IP-адрес посетил за указанный период.

Во-вторых, учитывая период времени (t1, t2) и URL-адрес, запросите, сколько раз этот URL-адрес был посещен.

Я оступился, и вот мое глупое решение:

Анализ:

, потому что каждый запрос выполняется в определенный период времени , то есть:

1. Создайте набор , поместите все время посещения в набор и сохраняйте его в порядке, соответствующем значению времени от старшего к последнему.

2.Создание хеш-таблицы с использованием хеш-функции (visit_time) в качестве ключа , эта хеш-таблица называется time-hash-table, tкурица каждый узел в определенном сегменте имеет 2 указателя , указывающих на еще 2 хеш-таблицы соответственно.

3. еще 2 хеш-таблицы будет ip-hash-table и url-hash-table .

ip-hash-table использует хеш (ip) в качестве ключа ивсе ips в одной хэш-таблице ip имеют одинаковое время посещения;

url-hash-table использует хеш (url) в качестве ключа, и все URL-адреса в одной и той же хэш-таблице url имеют одинаковое время посещения.

Дайте чертеж следующим образом:

time_hastbl
  []
  []
  []-->[visit_time_i]-->[visit_time_j]...[visit_time_p]-->NIL
  []                     |          |
  []               ip_hastbl       url_hastbl
                      []               []
                      :                :
                      []               []
                      []               []

Итак, при выполнении запроса к (t1, t2):

1. найти самое близкое совпадение из установленного времени, скажем, совпадение (t1 ', t2'), то все действительное время посещения попадет в часть набора, начиная с t1 'до t2';

2. для каждого времени посещения t в установленном времени[t1 ': t2'], сделайте хеш (t) и найдите ip_hastbl или url_hastbl для t, затем посчитайте и зарегистрируйте, сколько раз данный ip или URL появляются.

Вопросы:

1.Мое решение глупо, надеюсь, вы можете дать мне другое решение.

2.В отношении хранения больших массивов на диске, какой-нибудь совет?Я думал о B-дереве, но как его использовать или B-дерево применимо в этой системе?

Answer 1

Я полагаю, что интервьюер ожидал решения на основе распределенных вычислений, особенно когда речь идет о «100 миллиардах записей».Обладая ограниченными знаниями в области распределенных вычислений, которые у меня есть, я бы посоветовал вам изучить Распределенную хеш-таблицу и map-Reduce (для параллельной обработки запросов)

Answer 2

Старый вопрос, но недавно столкнулся, так что вот еще несколько вещей, о которых стоит подумать:

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

Сначала, с учетом периода времени (t1, t2) и IP-адреса, запросите, сколько URL-адресов посетил этот IP-адрес за указанный период.

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

Секунда, учитывая период времени (t1, t2) и URL-адрес, запросите, сколько раз этот URL-адрес был посещен.

В зависимости от того, сколько URL-адресов у вас в системе, например, 1000, это снова означает, что при простом сканировании получается 999 из 1000отсканированные записи не возвращаются.

Допустим, у вас есть только 100 000 уникальных URL, вы можете значительно уменьшить пространство, занимаемое базой данных (используя вместо этого внешний ключ guid / int), thтакже означает, что к вашим URL-адресам в 100-миллионных записях обращаются 1 миллион раз.

Даже при всем этом он нам ничего не говорит полностью, потому что у нас нет цифр / статистики о том, как кластеризованы по времени записи дляучитывая время поиска.Получаем ли мы 1000 запросов страниц в секунду и ищем 12-месячный временной диапазон, или мы получаем 100 запросов в секунду и ищем 1-часовой блок времени (360 000 запросов).

Предполагая, что 100 миллиардов представляют данные за 12 месяцевэто 3170 запросов в секунду.Это звучит разумно?

Почему это важно?Потому что это подчеркивает одну ключевую вещь, которую вы пропустили в своем ответе.

С записями в 100 миллиардов за последние 12 месяцев, это означает, что через 12 месяцев у вас будет 200 миллиардов записей для работы.Если 100-миллиардные записи рассчитаны на 20 лет, то это не такая проблема, вы можете ожидать, что в ближайшие 5 лет вырастет всего лишь на 25-30 млрд. ... но вряд ли ваши существующие данные превысили столь длительный период времени.

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

Если вы вставляете записи 3k, а каждая запись - только 3x 64bitцелые числа, представляющие время (в тиках), IP-адрес и внешний ключ к URL.Тогда это всего лишь ~ 75 КБ / с записи данных, которые будет хорошо поддерживать.Если каждый URL предполагается уникальным, вы можете легко столкнуться с проблемами производительности из-за скорости ввода-вывода (игнорируя требования к пространству).

Еще одна вещь, которую интервьюер будет заинтересован в том, чтобы увидеть ваши мысли о поддержке IPv6.

Наконец, если вы предоставили такое решение, как у вас, интервьюер должен был задать дополнительный вопрос.«Как будет работать ваша система, если я теперь захочу узнать, когда конкретный IP-адрес последний раз обращался к определенному URL?»

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

Answer 3

По моему мнению, создайте дерево B +, используя время в качестве ключа, чтобы помочь вам быстро найти диапазон записей в течение заданного периода времени (t1, t2) на диске. Затем используя записи во время (t1, t2) для построения IP-адреса и URL-таблицы хэша соответственно.

Answer 4

Это будет дерево интервалов, которое также является B-деревом. Дерево интервалов, потому что все запросы имеют вход только в качестве временного интервала, а B-дерево - из-за размера ввода (миллиарды).