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

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

Описание:

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

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

Требования:

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

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

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

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

Анализ:

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

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

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

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

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

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

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

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

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

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

  • для каждого времени посещения t в заданном времени [t1 ': t2'], do hash (t) и найти t ip_hastbl или url_hastbl, затем подсчитывать и регистрировать, сколько раз появляется данный ip или url.

Вопросы:

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

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

Ответы

Ответ 1

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

Ответ 2

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

Ответ 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ответ 4

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