Skip to content

Масштаб: как большое количество информации меняет мир

25/11/2008

Так как многие знают что я работаю в Google, мне приходит множество писем со странными вопросами или жалобами на политику Google, вопросами о том как в Google делаются те или иные вещи. Очевидно, я не могу отвечать на вопросы о Google. И даже если бы мог — не стал бы. Это не блог Google — это мой личный блог, хобби, которым я занимаюсь в свободное от работы время.

Но между моей работой и моим хобби существуют пересечения. И одна из идей, входящая во многие из приходящих вопросов, также касается моей работы и моего хобби. И это идея масштаба. Масштаб — это понятие о том как изменяются вещи становясь больше. В частности, я говорю о масштабе информации; количество информации с которой мы имеем дело каждый день значительно увеличилось, и что удивительно — это увеличение прошло незаметно для большинства людей.

Что же такое масштаб?

Возьмите некоторое количество информации, и подумайте — как его можно анализировать? Предположим, у вас есть список музыкальных треков. У меня на компьютере их 4 426. Теперь, предположим что я хочу просмотреть их и составить список. Если всё что вам нужно узнать — простая информация вроде названия песни, исполнителя, длины, жанра и т.д., это достаточно просто. Любой современный компьютер сделает это за несколько секунд. Черт, многие современные телефоны сделают это за несколько секунд.

Теперь предположим что вместо 4 000 треков у вас их 4 миллиона. Это ещё не так много. Я могу проанализировать информацию 4 миллионов треков разными способами в течении нескольких минут. Для современного компьютера это пустяк.

Но что если я хочу сделать что нибудь поинтереснее — например, заглянуть в файлы и попытаться вычислить темп? Вместо 4 миллионов наборов строк для вычисления темпа надо перелопатить полное содержание песен. В моей музыкальной коллекции файлы занимают в среднем по несколько мегабайт; для простоты возьмём размер одной композиции в мегабайт. Проанализировать 4000 песен по одному мегабайту каждая — вполне посильная задача для современного настольного ПК, но это займёт приличное время. Сделать то же самое с 4 миллионами песен можно даже не пытаться. Я могу купить диск на который влезет такой объём информации, но у меня не получится провести их анализ за сколько-нибудь приемлимое время.

Музыкальные сервисы вроде LastFM, Pandora или MusicBrainz хранят информацию о десятках милионов треков, и многие из нас пользуются ими каждый день не задумываясь над тем что там происходит. LastFM и Pandora анализируют миллионы музыкальных треков, чтобы можно было предложить вам композиции, максимально похожие на то что вы слушаете сейчас — основываясь на структуре музыкального файла (не уверен насчёт Pandora, но MusicBrainz анализирует именно структуру — прим. переводчика). Ещё десять лет назад сделать это на компьютере было невозможно. Сейчас это обычное явление.

Это и есть масштаб — изменение вещей с увеличением размера задачи. Объёмы данных растут и растут, и рано или поздно размер задачи пересекает некую черту за которой задача меняется не только количественно, но и качественно.

Эффекты масштаба иногда противоречат интуиции. В некоторых случаях увеличивая размер проблемы вы делаете её легче. Есть вещи которые проще сделать с большим массивом данных, чем с маленькой выборкой; и есть вещи, легко выполнимые на малом объёме данных, но невозможные на больших объёмах.

Начнём с первого. Масштаб позволяет вам делать некоторые замечательные вещи, ранее бывшие невозможными. Например, можно записать целые геномы большого количества организмов. На прошлой неделе мой знакомый блоггер Тара Смит на Этиологии написала статью о недавнем изучении вируса Эбола; врачи, изучающие его распространение, захотели узнать с каким штаммом вируса они имеют дело. Они выделили его ДНК, секвенировали её, сравнили с существующей библиотекой геномов вируса Эбола и идентифицировали её как новый штамм вируса, но происходящий от одного из известных штаммов. Сейчас учёные часто секвенируют ДНК вирусов и сравнивают с уже известными вариантами. На самом деле, они сделали куда больше; цитата с одного профильного сайта:

«Благодаря взрывному росту данных в генетике, несколько баз данных содержащих полностью секвенированные геномы множества вирусов были созданы и выложены в Интернет. Взяв данные генома нового вируса Эбола, учёные сравнили его с другими вирусами. Когда расшифрованный геном и его части были сверены с базой, выяснились интересные детали. Были найдены совпадения между иммуноподавляющими последовательностями в онкогенных ретровирусах, мышином и кошачьем вирусах лейкемии и частью нового штамме Эбола.»

Если перевести это на человеческий язык: они не просто сравнили новую разновидность вируса Эбола с уже известными — это не так трудно, т.к. геном вируса Эбола составляет всего около 19 килобайт. Они сравнили его со всеми известными секвенированными геномами вирусов, и нашли практически идентичные участки в вирусе Эбола и вирусе кошачьей лейкемии!

Это хорошая сторона масштаба. Вещи, которые мы не могли даже представить всего несколько лет назад стали не просто возможными, но и привычными. Учёные работают с чудовищными объёмами информации, и это помогает продвигать науку вперёд в таких областях, о каких они раньше и не мечтали. Если бы учёным 10 лет назад выдали современное оборудование, учёные изучающие вирус Эбола скорее всего смогли бы его секвенировать. Но они и мечтать не могли о том чтобы сравнить её со всеми известными вирусами. Но с масштабами на которых мы работаем сейчас, сложнее исключить некоторые нерелевантные вирусы, чем забить на это и прогнать сравнение по всем — а вдруг что интересное найдётся.

В некоторой степени это то о чём писал Дуглас Адамс в «Автостопом по Галактике» — мы можем получать ответы на вопросы которые мы даже не задали, в накопленных нами данных лежат ответы на вопросы о которых мы даже помыслить не можем. Находя закономености в больших наборах данных мы можем найти ответы ещё до того как узнаем каков был вопрос. (И уж конечно, как и в книге, потом нам придётся узнать сам вопрос). Масштаб сильно изменил науку: мы без труда можем найти неожиданные закономерности и корелляции, ставящие всё новые вопросы.

Это хорошая сторона масштаба: способность анализировать огромные объёмы данных — очень полезный инструмент в научных исследованиях. Но есть и другая сторона: вещи которые легко сделать с обычным набором данных становятся невыполнимыми в большом масштабе.

Граница между вычислимым и вычислимым, но за неприемлимое время, обычно проводится по вычислительной сложности алгоритмов. В традиционной теории алгоритмов вычислимыми считаются алгоритмы с полиномиальной сложностью и ниже, невычислимыми — с экспоненциальной сложностью и выше. Но масштаб это меняет. На больших объёмах данных алгоритм с полиномиальной сложностью тоже оказывается непригоден. Даже если вы делаете что нибудь тривиальное — вроде сортировки.

Великолепным примером работы с большими объёмами данных можно считать реляционые базы данных. Давным давно, журнал о базах данных опубликовал статью, в которой критиковался алгоритм MapReduce — за то что был непохож на реляционный подход в большинстве БД. Я написал им ответ, объясняя почему они неправы. Мне всё ещё приходят письма от фанатов реляционных БД, считающих что то что делает MapReduce может быть с успехом реализовано на обычной базе данных.

Базы данных были созданы для работы с тем что считалось большим количеством данных. И, как не перестают мне напоминать сторонники реляционного подхода, базы данных поддерживают разделение на кластеры — используя параллельно несколько компьютеров чтобы быстрее производить вычисления — так что они более масштабируемы, чем я считаю.

Но есть большие объёмы данных, и есть большие. БД великолепно справляются с большим объёмом данных. Но существуют наборы данных которые попросту слишком велики для современных баз данных. И по большей части так получается не потому что базы данных изначально не планировались для сетевой обработки массивов информации, но потому что сами алгоритмы и структуры данных традиционной БД не приспособлены для работы на таком масштабе.

Проще всего объяснить это не примере. В прошлые выходные команда инженеров Google (я не имею к ним отношения; я даже не знаю никого из задействованных в задаче) объявила результаты сортировки одного петабайта данных. Это действие потребовало 4 000 компьютеров и 48 000 жёстких дисков. Весь процесс занял шесть часов.

Когда фанаты БД говорят о кластеризации, они обычно имеют в виду несколько машин (я только что просмотрел информацию по БД IBM в сети, и нигде не нашёл упоминаний об использовании более чем 12 процессоров.)

Есть большая разница между 12 CPU и гигабайтами информации, и 4 000 CPU и петабайтом данных, хранящимся на 48 000 винчестерах! Современные масштабируемые системы больше имеют дело со вторым вариантом, чем с первым. В записи о результатах сортировки в блоге Google указывалось что в день Google обрабатывает 20 петабайт данных. Я уверен что другие большие компании работают со сравнимым количеством информации.

Это и есть масштаб, и иногда он бывает просто пугающим. Для простой сортировки одной двадцатой ежедневной порции данных Google потребовалась команда гениальных инженеров, тысяч компьютеров и десятков тысяч жёстких дисков!

Представьте, сколько необходимо компьютеров чтобы зашифровать всю эту информацию! Такие компании как Google, Yahoo, Amazon и Ebay обрабатывают миллиарды запросов ежедневно, и они не хранят информацию в обычном текстовом виде. Просто подумайте — что такое шифровать 20 петабайт данных каждый день.

(прим. переводчика — я не думаю что все 20 петабайт данных обязательно шифруются. С одной стороны это пишет работник Google, а с другой — у любого хакера мысль о скачивании такого количества информации заставит шевелиться волосы на спине)

Это и есть природа масштаба. Задачи каторые были простыми, становятся трудными или даже невыполнимыми, потому что не могут быть реализованы на таком масштабе. Некоторые задачи бывшие невозможными, напротив, становятся выполнимыми. Масштаб всё меняет.

Реклама
Добавить комментарий

Добавить комментарий

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

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: