Вычисление счетчиков токенов на огромном наборе данных

Question

Мне нужно перебрать огромное количество текста (> 2 Тб, полный дамп Википедии) и сохранить два счетчика для каждого увиденного токена (каждый счетчик увеличивается в зависимости от текущего события).Единственная операция, которая мне понадобится для этих счетчиков, - увеличение.На втором этапе я должен вычислить два числа с плавающей запятой на основе этих счетчиков и сохранить их.

Он должен выполнить следующие шаги:

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

Требования и другие сведения:

• Он должен масштабироваться до O (10 ^8) жетоны.
• Конечный результат должен быть запрошен очень быстро!
• При просмотре текстов будет сделано только увеличение двух счетчиков.Это однократная обработка, поэтому при обработке запросов не будет.Только обновление значения.
• Нет необходимости в динамической / обновляемой схеме.

Я пробовал CouchDB и MongoDB без слишком хороших результатов.

Что вы думаете, этолучший подход к этой проблеме?

Спасибо!

РЕДАКТИРОВАТЬ 1: Мне предложили попробовать Patricia trie и проверить, если всеключи вписываются в память (подозреваю, что нет).Возможным решением может быть пользовательская строка Патрисии с дополнительным оператором для увеличения значений каждого ключа за один шаг.

РЕДАКТИРОВАТЬ 2: Уточнил, что я имею в виду под "огромным":> 2Tb текста.Дополнительные пояснения.

РЕДАКТИРОВАТЬ 3: Уникальная оценка токена.По предложению Майка Данлавей, я попытался быстро оценить уникальные токены.В первых 830 МБ набора данных уникальные токены растут линейно до 52134. Если количество уникальных токенов не увеличивается после обработки большего количества данных (что вероятно), должно быть O (10 ^ 8) уникальных токенов.

РЕДАКТИРОВАТЬ 4: Решения Java и Python предпочтительнее, но любой другой язык тоже подходит.

РЕДАКТИРОВАТЬ 5: Обычно токены содержат только печатные символы ASCII, номожет содержать любой печатный символ Unicode.Я попробую один и тот же процесс как с прописными, так и с прописными буквами без изменений;и только в нижнем регистре.

Answer 1

ОК, если MongoDB и CouchDB не работают для вас, то у вас в основном одна проблема: недостаточно мощности .

Давайте посмотрим на список белья:

Он должен масштабироваться до O (10 ^ 8) токенов.

Сколько у вас оперативной памяти?Вы говорите о сотнях миллионов токенов и , вы говорите о потоковой передаче 7zip-файла.Если вы хотите быстро выдавать «приращения», вам нужно иметь возможность хранить всю структуру данных в памяти, или все будет происходить очень медленно.

Окончательный результат необходимо запрашивать очень быстро!

Как быстро?Микросекунды, миллисекунды, сотни миллисекунд?Если вы хотите запросить 500M записей на машине с 8 ГБ оперативной памяти, вы в значительной степени удручены.Данные просто не помещаются, не имеет значения, какую базу данных вы используете.

Набор данных> 2Tb

Хорошо, давайте предположим, что ваш компьютер может в среднем около50 МБ / с постоянной пропускной способности и , чтобы ваш процесс мог действительно распаковывать данные с такой скоростью.В этом темпе вы говорите о 11+ часах времени обработки только для потоковой передачи данных (вы хотели, чтобы это было сделано в выходные?) Пропускная способность 1027 *

50 МБ / с в течение 11 часов - это не маленькая картошка, этонастоящий драйв.И если вы попытаетесь что-то записать на диск во время этого процесса (или замены ОС), то это быстро ухудшится.

Посмотрите с точки зрения БД, MongoDB может справиться с обоимиобновление интерфейса и запросы к серверу.Но он должен сбрасываться на диск каждую минуту или около того, и это значительно увеличит ваше 11-часовое время выполнения.

Это общее время выполнения будет становиться все хуже и хуже, если вы не справитесь со всей БДв памяти и весь поток в памяти.

Моя точка зрения *

довольно проста, вам нужно больше энергии.

Если вы не выполняете эту операцию с 24 ГБ + ОЗУ, то все, что вы делаете, будет работать медленно.Если у вас нет 24 ГБ + ОЗУ, то ваш окончательный набор данных не будет «молниеносным», в лучшем случае «200 мс-быстрым».Вы можете просто индексировать 500M строк и ожидать, что найдете запись, если не можете сохранить индекс в ОЗУ.

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

Я знаю, что вам нужна помощь, я знаю, что вы дали щедрость на этот вопрос, нодействительно трудно решить следующую проблему:

Я пробовал CouchDB и MongoDB без слишком хороших результатов.

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

Answer 2

Высокоуровневое решение:

1. Анализировать входные данные, выводя строки "[token] + X + Y" в выходные файлы размером 1 из N (каждый из этих "заштрихованных" выходных файлов достаточно мал для обработки в памяти.)
2. [Для каждого файла] считывать его в память, выводить отсортированный файл со строками "[token] [count1] [count2] ..."
3. Во время запроса выполните бинарный поиск в правильном файле

Подробнее: Вот псевдокод Python для шага 1)

NUM_SHARDS = 1000  # big enough to make each file fit in memory  
output_files = [open("file" + str(n), "w") for n in xrange(NUM_SHARDS)]
for token in input_stream:
   shard_id = hash(token) % NUM_SHARDS
   output_files[shard_id].write(token + " +0 +1\n")
   # TODO: output the correct +X and +Y as needed

Вот псевдокод Python для шага 2)

input_files = [open("file" + str(n)) for n in xrange(NUM_SHARDS)]
for file in input_files:
   counts = {}   # Key: token   Value: { "count1": 0, "count2": 1 }

   # read the file, and populate 'counts'
   for line in file:
      (token, count1, count2) = line.split(" ")
      # make sure we have a value for this token
      counts.setdefault(token, { "count1": 0, "count2": 0 })
      counts[token]["count1"] += int(count1)
      counts[token]["count2"] += int(count2)
      # TODO: compute those floats, and stuff those inside 'counts' also

   # now write 'counts' out to a file (in sorted order)
   output_file = open(file.name + ".index", "w")
   for token, token_counts in sorted(counts.items()):
      output_file.write(token + " " + token_counts["counts1"] + " " + token_counts["counts2"] + "\n")
      # TODO: also write out those floats in the same line

Вот код Python для шага 3):

# assume 'token' contains the token you want to find
shard_id = hash(token) % NUM_SHARDS
filename = "file" + str(shard_id) + ".index"
binary_search(token, open(filename), 0, os.path.getsize(filename))

# print out the line in 'file' whose first token is 'token'
# begin/end always point to the start of a line
def binary_search(token, file, begin, end):
    # If we're close, just do brute force
    if end - begin < 10000:
            file.seek(begin)
            while file.tell() < end:
                    line = file.readline()
                    cur_token = line.strip().split(" ")[0]
                    if cur_token == token:
                            print line
                            return True
            return False  # not found

    # If we're not close, pivot based on a line near the middle
    file.seek((begin + end) / 2)
    partial_line = file.readline()  # ignore the first fractional line
    line = file.readline()

    cur_token = line.strip().split(" ")[0]
    if cur_token == token:
            print line
            return True
    elif cur_token < token:
            return binary_search(token, file, file.tell(), end)
    else:  # cur_token > token
            return binary_search(token, file, begin, file.tell() - len(line))

Answer 3

Если у вас много памяти, вы можете просто использовать redis для хранения счетчиков (10 ^ 8 уникальных токенов с двумя счетчиками каждый, вероятно, займет около 12 ГБ).

Если у вас недостаточно памяти, вы все равно можете использовать redis, но с небольшой стратегией хеширования и vm_enabled, чтобы она соответствовала памяти:

У вас могут быть токены, разделенные на первую и вторую буквы (aa, ab, ac ... zz) для имени хеша, и фактический идентификатор слова + токена в качестве ключа хеша, и счетчик в качестве значения. Это будет выглядеть так:

hash ab
- absence_c1 5
- absence_c2 2
- abandon_c1 2
- abandon_c1 10
hash st
- stack_c1 10
- stack_c2 14

Но при таком подходе, поскольку redis не может "incr" для хэшей, вы получите предыдущее значение, а затем его incr и установите его обратно (псевдокод):

var last = redis("hget st stack_c1")
var actual = last + 1
redis("hset st stack_c1 actual")

Использование этого хэш-паттерна и с включенным vm redis сохранит низкое использование памяти, хотя все еще достаточно быстро. Я смог хранить 2 миллиона токенов по 15 символов в каждом, используя меньше 100 МБ оперативной памяти и почти 4 ГБ диска.

Answer 4

Как я понял, вы хотите только считать токены. Первое решение может быть просто использование хэш-карты в памяти. 52-100 тыс. Токенов (а длина слова в английском языке составляет около 5,1) + 4 байта на каждый токен для подсчета - это не так много данных. Вы можете легко сохранить карту в памяти компьютера разработчика.

Второе решение заключается в использовании apache lucene для хранения новых токенов - если у вас нет записей 1M, вам не нужно разбивать индекс - и значение счетчика, которое я буду хранить в базе данных, например, sqllite (потому что обновление индекса lucene - не лучшая идея).

Чтобы ускорить процесс - для обоих решений - я бы просто разделил ваш набор данных на набор данных k * 100 и запустил их отдельно на разных машинах (или параллельно), а затем объединил их результаты. Результаты вашего подсчета вы можете суммировать без проблем.

Ваш вариант использования является классическим примером в учебниках по Apache Hadoop, но я думаю, что его развертывание будет слишком трудоемким.

Answer 5

Стратегия, а не решение;

Невозможно избежать чтения входных данных одним процессом, т. Е. Я не вижу, как распараллелить начальную операцию, если файл не находится напараллельная система ввода-вывода, и даже тогда я думаю, что может быть трудно работать с файлом 7z параллельно.

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

Как только первый блок записан, вы запускаете процесс на другом ядре (у вас есть многоядерный, не так ли? Возможно, даже кластер или сеть рабочих станций).?) чтобы начать переваривать этот кусок.Этот процесс записывает частичные результаты в файл (ы).

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

... вы получаете изображение

После того, как весь ввод был обработан, вы затем разрабатываете задачи для объединения результатов из выходных данных задач, обрабатывающих каждый блок.Вы сделали бы это каким-то каскадом (например, если у вас было 32 блока и 16 процессоров, каждый из них мог бы объединить 2 блока, тогда 8 из них объединяли 2 из объединенных блоков и т. Д.).

Мое лучшее предположение состоит в том, что для этого у вас должно быть все в порядке с плоскими файлами, если вы не уверены, что дополнительная мощность БД стоит дополнительных затрат (с точки зрения производительности и сложности программирования).Я полагаю, что вы, возможно, захотите записать окончательные результаты в базу данных для поддержки запросов.

РЕДАКТИРОВАТЬ: хорошо, если все ваши запросы имеют форму «получить мне счетчики для токена XXX», то вы могли бы избежатьбинарный поиск через один отсортированный текстовый файл.Я не предполагаю, что вы должны, но это может указать вам направление решения.Забыв на время, что токены могут начинаться с любого символа (что является просто вопросом алфавита), у вас может быть 26 файлов, один для токенов, начинающихся с A, один для токенов, начинающихся с B, и т. Д.

Или вы можете создать индекс в мастер-файле с записями для A (смещение 0 от начала файла) B (смещение 12456 от начала) и так далее.

Лично я немного поэкспериментировал с подходом «один отсортированный текстовый файл на начальную букву», пока не нашел работающее решение, а затем выяснил, достаточно ли оно быстрое.Но у меня есть доступ к большим кластерам с кучей дисков и объемами оперативной памяти, и ваша платформа может диктовать другой, возможно, более сложный подход.

Answer 6

Должны ли вы использовать БД вместо чтения текстового файла?

Простой скомпилированный язык C-типа может запустить простой синтаксический анализатор за долю времени, которое требуется для чтения файла, поэтому он долженбыть в основном "I / O связанный".Это была бы программа, похожая на unix wc, подсчет слов.

Похоже, математика тривиальна и даже не должна быть заметна.

РЕДАКТИРОВАТЬ: ОК, я не понялчто вы хотите создать словарь уникальных токенов и посчитать каждый.В этом случае достаточно использовать словарь, основанный на tree или хэше.Размер хранилища будет зависеть от типичной длины токенов и их количества.Это может быть похоже на идиому Unix sort | uniq.