Сегодня я настроен поговорить о технологиях, которые были весьма модны и породили вал публикаций, но по прошествии лет так и не привели к каким-либо значимым практическим результатам, либо их ниша оказалась настолько узка, что её сопоставление с первоначальными ожиданиями создаёт сатирический эффект. Как правило, такие технологии создают у новичков при первом ознакомлении впечатление «магии», чего-то, решающего все проблемы невероятно хитрым образом, но трезвая профессиональная оценка в биг-О, реальных числах и обстоятельствах заканчивается диагнозом: «пустышка».
Как показывает опыт, у таких модных штучек более или менее ярко присутствуют четыре качества: «магичность» (восхищает сложностью), неестественность (идёт против шерсти, естественного порядка вещей), сложность (это всегда плохо) и неприменимость (лишь в конкретных обстоятельствах, но какие обстоятельства ни возьми — оно неприменимо).
Итак, приступим к вскрытию.
В плане магичности неоспоримый лидер — фильтры Блюма. Напомню, фильтр Блюма — вероятностная структура данных, которая позволяет закодировать некоторый набор значений так, чтобы исключить false negatives (если значение принадлежит набору — фильтр ответит положительно), а false positives сделать маловероятными (иногда фильтр пропустит посторонние значения, увы). С практической точки зрения, фильтр позволяет снизить затраты памяти на хранение набора в десять раз, с той издержкой, что теряется детерминизм, появляется вероятностность. Т.о. выигрыш — коэффициент, и в понятиях биг-О его вообще нет. Тем не менее, фильтры Блюма очень часто воспринимаются типичным аспирантом, как «серебряная пуля», особенно когда тот налажает с порядком сложности и пытается залечить проблему, оптимизируя коэффициенты. На практике фильтры Блюма применяются, но редко и в особых обстоятельствах, как дополнительная оптимизация.
Уникальный сплав магичности и неестественности — цифровые фонтаны. Простыми словами, это что-то вроде RAID-5, но по сети. Данные разбиваются на серии по p кусочков, но в сеть посылаются p+q рекомбинированных кусочков — так, что получив любые p рекомбинированных, можно восстановить оригиналы. Единственная сложность, что алгоритмы рекомбинации с хорошими свойствами весьма сложны в реализации алгоритмически. В обычных компьютерных сетях, если пакет потерялся — его проще перезапросить (это редко занимает больше 0.1 секунды), чем мутить с рекомбинациями. Но есть особые ниши, куда цифровые фонтаны пытались приспособить — как правило, в системы односторонней связи. Митценмахер пытался фонтанами спасти мультикаст, например. Я лично общался с одним русским немцем, который двигает стандарт цифрового радио, основанный на цифровых фонтанах. Возможно, когда космические корабли начнут бороздить просторы, цифровые фонтаны массово пойдут в продакшн, но пока это экзотическая игрушка.
Выгодно сочетает все четыре главных качества другая технология — DHT, распределённые хэш-таблицы. Казалось бы, в распределённой сети можно разделить пространство ключей между множеством узлов и маршрутизировать между ними запросы — так, что каждый узел будет отвечать лишь за некоторый сегмент хэш-таблицы, а её общая вместимость достигнет астрономических величин. Увы, возник ряд вопросов. Например, разные сегменты могут иметь разную популярность, и пока одни узлы бездельничают, других похоронят под валом запросов. Также, у узлов нет никакой мотивации работать честно — в обработке чужих запросов можно и схалтурить. Но самое важное и неизлечимое — это то, что DHT необходимо логарифмическое количество раунд-трипов, чтобы найти узел, отвечающий за нужный участок таблицы. RTT (round trip time, время ходки пакета в интернете) принципиально неулучшаемо, поскольку определяется скоростью света. В то время, как ёмкость памяти и дисков растёт экспоненциально, позволяя хранить всё больше данных в дата-центрах, RTT остаётся на месте. Увы, хоть «логарифмическое» это и мало, но всё равно это кратно больше одного раунд-трипа, необходимого для запроса в дата-центр. Получилось, что технология оптимизирует ресурс, который и так экспоненциально растёт (память), но проигрывает на ресурсе, который не может быть улучшен в принципе (раунд-трипы). DHT сейчас, c грехом пополам, применяется для трекинга пиров в бит-торрент системах, но, как написал один из отцов-основателей DHT Paul Francis,
Отстаёт от лидеров по всем качествам, кроме неприменимости, ещё одна когда-то модная технология — пир-ту-пир (в смысле BitTorrent, а не в смысле Skype). Идея поднимать траффик с пользовательских машин обещала солидные дивиденды — ведь в отличие от централизованных систем, в пир-ту-пир системе доступные ресурсы растут пропорционально количеству участников, а значит флеш-крауд и эффект Слешдота не убьют систему, а только сделают её сильней. Казалось бы, с биг-О всё в порядке. Увы, компьютеры и интернет-соединения конечных пользователей — не такие удобные объекты для эксплуатации. Проброс соединения к конечному пользователю — это работа в полях, потребляющая 90% бюджета при строительстве сетей. Компактно, в стерильных условиях, проапгрейдить дата-центр — существенно проще и выгодней. Экономия масштаба в действии — магистральные каналы и датацентры развивались гораздо быстрей пользовательских соединений и серверный траффик стал неизмеримо дешевле и надёжней поднятого с последней мили. На сегодня, пир-ту-пир интересен лишь как легальная лазейка для распространения пиратского контента технически подкованными студентами. Экономически тема не интересна абсолютно, научный интерес сходит на нет.
Тут ещё можно добавить мультикаст, но он был моден, ещё когда я пятнадцать копеек на мороженое у мамы просил.
Какие из этого можно сделать выводы? Это просто. Не следует увлекаться красотой и модностью технологии, нужно лишь прагматически оценить её возможности и издержки. Здравого смысла вполне достаточно.
Как показывает опыт, у таких модных штучек более или менее ярко присутствуют четыре качества: «магичность» (восхищает сложностью), неестественность (идёт против шерсти, естественного порядка вещей), сложность (это всегда плохо) и неприменимость (лишь в конкретных обстоятельствах, но какие обстоятельства ни возьми — оно неприменимо).
Итак, приступим к вскрытию.
В плане магичности неоспоримый лидер — фильтры Блюма. Напомню, фильтр Блюма — вероятностная структура данных, которая позволяет закодировать некоторый набор значений так, чтобы исключить false negatives (если значение принадлежит набору — фильтр ответит положительно), а false positives сделать маловероятными (иногда фильтр пропустит посторонние значения, увы). С практической точки зрения, фильтр позволяет снизить затраты памяти на хранение набора в десять раз, с той издержкой, что теряется детерминизм, появляется вероятностность. Т.о. выигрыш — коэффициент, и в понятиях биг-О его вообще нет. Тем не менее, фильтры Блюма очень часто воспринимаются типичным аспирантом, как «серебряная пуля», особенно когда тот налажает с порядком сложности и пытается залечить проблему, оптимизируя коэффициенты. На практике фильтры Блюма применяются, но редко и в особых обстоятельствах, как дополнительная оптимизация.
Уникальный сплав магичности и неестественности — цифровые фонтаны. Простыми словами, это что-то вроде RAID-5, но по сети. Данные разбиваются на серии по p кусочков, но в сеть посылаются p+q рекомбинированных кусочков — так, что получив любые p рекомбинированных, можно восстановить оригиналы. Единственная сложность, что алгоритмы рекомбинации с хорошими свойствами весьма сложны в реализации алгоритмически. В обычных компьютерных сетях, если пакет потерялся — его проще перезапросить (это редко занимает больше 0.1 секунды), чем мутить с рекомбинациями. Но есть особые ниши, куда цифровые фонтаны пытались приспособить — как правило, в системы односторонней связи. Митценмахер пытался фонтанами спасти мультикаст, например. Я лично общался с одним русским немцем, который двигает стандарт цифрового радио, основанный на цифровых фонтанах. Возможно, когда космические корабли начнут бороздить просторы, цифровые фонтаны массово пойдут в продакшн, но пока это экзотическая игрушка.
Выгодно сочетает все четыре главных качества другая технология — DHT, распределённые хэш-таблицы. Казалось бы, в распределённой сети можно разделить пространство ключей между множеством узлов и маршрутизировать между ними запросы — так, что каждый узел будет отвечать лишь за некоторый сегмент хэш-таблицы, а её общая вместимость достигнет астрономических величин. Увы, возник ряд вопросов. Например, разные сегменты могут иметь разную популярность, и пока одни узлы бездельничают, других похоронят под валом запросов. Также, у узлов нет никакой мотивации работать честно — в обработке чужих запросов можно и схалтурить. Но самое важное и неизлечимое — это то, что DHT необходимо логарифмическое количество раунд-трипов, чтобы найти узел, отвечающий за нужный участок таблицы. RTT (round trip time, время ходки пакета в интернете) принципиально неулучшаемо, поскольку определяется скоростью света. В то время, как ёмкость памяти и дисков растёт экспоненциально, позволяя хранить всё больше данных в дата-центрах, RTT остаётся на месте. Увы, хоть «логарифмическое» это и мало, но всё равно это кратно больше одного раунд-трипа, необходимого для запроса в дата-центр. Получилось, что технология оптимизирует ресурс, который и так экспоненциально растёт (память), но проигрывает на ресурсе, который не может быть улучшен в принципе (раунд-трипы). DHT сейчас, c грехом пополам, применяется для трекинга пиров в бит-торрент системах, но, как написал один из отцов-основателей DHT Paul Francis,
This paper is one of the original «big three» DHT papers published all around the same time (along with Chord and Pastry). While these papers spawned a cottage industry in DHT research, I've since come to believe that the useful niche for DHT technology is awfully small (those applications where the economic model doesn't support a data-center approach, and the hash semantics are appropriate, and the scale is so large that a gossip-style approach doesn't work.. .).
Отстаёт от лидеров по всем качествам, кроме неприменимости, ещё одна когда-то модная технология — пир-ту-пир (в смысле BitTorrent, а не в смысле Skype). Идея поднимать траффик с пользовательских машин обещала солидные дивиденды — ведь в отличие от централизованных систем, в пир-ту-пир системе доступные ресурсы растут пропорционально количеству участников, а значит флеш-крауд и эффект Слешдота не убьют систему, а только сделают её сильней. Казалось бы, с биг-О всё в порядке. Увы, компьютеры и интернет-соединения конечных пользователей — не такие удобные объекты для эксплуатации. Проброс соединения к конечному пользователю — это работа в полях, потребляющая 90% бюджета при строительстве сетей. Компактно, в стерильных условиях, проапгрейдить дата-центр — существенно проще и выгодней. Экономия масштаба в действии — магистральные каналы и датацентры развивались гораздо быстрей пользовательских соединений и серверный траффик стал неизмеримо дешевле и надёжней поднятого с последней мили. На сегодня, пир-ту-пир интересен лишь как легальная лазейка для распространения пиратского контента технически подкованными студентами. Экономически тема не интересна абсолютно, научный интерес сходит на нет.
Тут ещё можно добавить мультикаст, но он был моден, ещё когда я пятнадцать копеек на мороженое у мамы просил.
Какие из этого можно сделать выводы? Это просто. Не следует увлекаться красотой и модностью технологии, нужно лишь прагматически оценить её возможности и издержки. Здравого смысла вполне достаточно.
