среда, февраля 28, 2007

Статья про вызов чисто виртуальной функции

Я как-то давно уже писала как можно вызвать чисто виртуальную функцию. В статье "Pure Virtual Function Called": An Explanation этот вопрос рассматривается гораздо подробнее, объясняется что как и почему. Повествование сопровождается психоделическими картинками.

суббота, февраля 24, 2007

Открылся сайт Startupping

Сайт Startupping задуман как помощь в создании Интернет-стартапа. Стартапперы будут там общаться и друг другу помогать.
Его основатель - Марк Флетчер (Mark Fletcher) сделал Bloglines (знаю, пользуюсь, ничего себе сервис) и ONElist (первый раз слышу).

Нашла по ссылке с Geeking with Greg

вторник, февраля 20, 2007

Передовые технологии Гугла

Сравнительно недавний пост в "Интернетных штучках" со списком сервисов Гугла приобрел весьма большую популярность в Рунете. Примечательно, что этот неофициальный список несколько длиннее официальных: и русскоязычного, и англоязычного.
Но гораздо интереснее то, что лежит за этими сервисами: технологии на основе которых они работают. Гугл не зря собирает конференцию по масштабируемым системам. Когда счет пользователей идет на миллионы, технологическия решения должны быть соответствующими.
По ссылке с hrg_tech я нашла слайды с интригующим названием Google Internals. Там перечислены основные Гугловские технологии с кратким описанием. Есть даже более-менее секретная - это то, что Гугл делает собственные свитчи, ну и количественных оценок серверов я раньше не встречала. На слайдах приводится цифра 450000 серверов.
Дальше я перечислю некоторые из известных Гугловских технологий, плюс ссылки, по которым по каждой из них можно узнать подробнее.

Архитектура кластера Гугла
Официальная статья: Web Search for a Planet: The Google Cluster Architecture
Речь идет о Гугловском кластере, который занимается обработкой поисковых запросов. В статье говорится, что для этого используется 15000 серверов средней мощности, но это было некоторое время назад, информация устарела.
Зачем так сложно, почему бы не использовать суперкомпьютеры? А так дешевле. Если объединить кучу серверов средней мощности, вместо того, чтобы использовать несколько очень мощных машин, соотношение цена/качество будет значительно лучше.
Вся система состоит не из одного кластера, а из нескольких, которые находятся в разных точках мира. Очень похоже на то, для чего придумывалась ARPA-net. Только ARPA боялась вооруженного вторжения, а Гугл опасается замелятресений и тому подобных катаклизмов.
При поступлении запроса система балансировки загрузки перенаправляет запрос одному из кластеров, который географически наиболее близок к пользователю. Дальше работа происходит с этим одним конкретным кластером, в котором есть своя балансировка загрузки.
Парочка интересных фактов: Гугл хранит дюжины копий всего веба на своих кластерах; при таком большом количестве серверов у них возникли проблемы с потреблением энергии и охлаждением.

Файловая система Google File System (GFS)
Официальная статья: The Google File System
Эта файловая система проектировалась под миллионы файлов, размером от 100 мб. Ожидались и многогигабайтные файлы. Файлы меньшего размера тоже планировалось поддерживать, но оптимизация для работы с ними не предусматривалась.
Основная идея такая: каждый файл дробится на куски, каждый кусок в нескольких копиях содержится на разных машинах. Размер такого куска - 64 мегабайта и это довольно большой размер для подобных систем. Но в ходе размышлений гугловцы пришли именно к этой цифре. Один файл в среднем хранится в трех копиях, но это количество можно настраивать. По ходу статьи несколько раз упоминается, что они реализовали не POSIX API.
Машины, на которых лежат куски файлов, называются чанксерверы (chunkserver). Ими всеми управляет некая мастер-машина. Мастер занимается балансировкой загрузки, осуществляет сборку мусора, периодически посылает HeartBeat сообщение и делает еще много чего интересного. Клиент, которому нужен файл, обращается сначала к мастеру, который отсылает клиента к нужному чанксерверу. При работе с файлами гарантируется атомарность доступа.
По такому описанию сразу видно слабое место - Мастер-сервер. Если вдруг что с ним случится, то система становится неработоспособной. Чтобы такого не происходило на случай проблем с мастером предусмотрен целый комплекс мер. Текущее состояние мастера постоянно копируется. Как и логи, как и чекпониты. Если с ним вдруг чего случится мониторинговая инфраструктура GFS практически немедленно стартует где-нибудь новый процесс-мастер на основе скопированных данных. Есть еще Теневые Мастеры, которые могут обеспечивать доступ только на чтение, когда с основным Мастер что-нибудь случилось.

MapReduce
Официальная статья: MapReduce: Simplified Data Processing on Large Clusters. В Wikipedia про MapReduce есть неплохая статья.
MapReduce - повзаимствованная из Лиспа идея, которая очень хорошо подходит для обработки больших объемов данных. Обрабтка данных происходит в две стадии. Первая Map, выполняет одну и ту же операцию над независимыми данными. Эту часть удобно выполнять параллельно. Вторая, Reduce, группирует полученные от Map результаты по каким-либо признакам. Ее сложнее выполнять параллельно, но тоже можно. В статье рассказывается о реальных задачах, которые хорошо ложатся на MapReduce.

Bigtable

Офицальная статья Bigtable: A Distributed Storage System for Structured Data. Видеолекция про BigTable.
Собственная база данных Гугла. Когда о ней говорят, ее пытаются не называть "базой данных". Употребляется обычно термин вроде "многомерное отображение". Я так понимаю, по каким-то формальным признакам BigTable базой данных не является. Но поскольку "база данных" произнести гораздо проще, чем, скажем, "распределенная система для управления стурктурированными данными", ее все равно называют базой данных и не заморачиваются. Я тоже так поступлю.
BigTable - это распределенная база данных. Там хранят свои данные система индексирования, Google Finance, Google Earth и др. Петабайты данных разбросаны по тысячам серверов.
BigTable разрабатывается с 2004 года. Предполагалось быстрое чтение колонок, а не строк. Каждая таблица многомерна, ячейка определяется не только колонкой и строкой, там еще есть время, версии. Таблицы оптимизированы для хранения в GFS путем разбиения на куски 200 мегабайт размером. Разбиение идет по строкам. Если размер куска начинает сильно увеличиваться, его архивируют.
От использования какой-либо коммерческой базы данных они отказались, ибо не влезало. Плюс дорого очень получалось.

Sawzall

Официальная статья - Interpreting the Data: Parallel Analysis with Sawzall
Sawzall - придуманный гугловцами язык для анализа больших объемов распределенных данных. С помощью него реализуется вышеупомянутый MapReduce. SQL им не хватило. Питон и Awk - не подошли, поскольку у них нет встроенных возможностей для работы на нескольких машинах. C, C++ - все что нужно могут, но это уж очень тяжелая артиллерия в данном случае.
Программа на Sawzall выглядит так

count: table sum of int;
total: table sum of float;
sum_of_squares: table sum of float;
x: float = input;
emit count <- 1;
emit total <- x;
emit sum_of_squares <- x * x;



Оригинальных решений у Гугла много, это лишь некоторые из них. Предполагаю, что подавляющее большинство из них не обнародуется.
Мне вообще очень понравилось как они принимают решения. Они исходят из имеющихся задач и только из них. Их не волнует "как принято" или "как у соседа". Попробовали несколько языков - они не подошли? Придумаем свой. При этом стоимость решения для них тоже является важным фактором, несмотря на то, что в деньгах они могут себя не ограничивать.

воскресенье, февраля 18, 2007

Статья Meet Larrabee, Intel's answer to a GPU

В статье Meet Larrabee, Intel's answer to a GPU рассказывается о том, что Intel делает нечто, что в статье названо CGPU. Все это чревато проблемами для NVidia и AMD. Но AMD все же не зря купила ATI, то есть какой-то ответ они всему этому готовят. В конце статьи предрекается, что скоро (года через два) GPU начнут уходить с рынка.

понедельник, февраля 12, 2007

Google PageRank

Статья о том, как Google вычисляет "важность" страниц. How Google Finds Your Needle in the Web's Haystack. Аналогичная информация по-русски:.
PageRank и Цепи Маркова. Часть I
PageRank и Цепи Маркова. Часть II
Если вы интересуетесь этой темой, то на labs.google.com есть страничка Сергея Брина, там есть ссылки на их с Ларри Пейджем работы.

суббота, февраля 10, 2007

Вопросы для интервью на toodoo.ru

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

Updated 27.02.2007
Интервью можно почитать здесь: Девушка и код

среда, февраля 07, 2007

Посты The Practice of Game Programming

Пит Исенси пишет на своем блоге чем, по его мнению, отличаются выдающиеся разрабочики игр. Замечательная фраза оттуда "Good programmers work on games. Great programmers ship games." Всего постов пока три, сколько будет всего Пит не писал. Если еще чего напишет, я сюда ссылки добавлю.
The Practice of Game Programming, part I
The Practice of Game Programming, part II
The Practice of Game Programming, Part III

вторник, февраля 06, 2007

Блоги по математике

Нашла сразу два блога по математике.
По ссылке с 11011110.livejournal.com - Carnival of Mathematics. Это свежеоткрывшийся блог. Обещают много интересного.

По ссылке с brainslugs.blogspot.com - Good Math, Bad Math.

понедельник, февраля 05, 2007

Видео с Пажитновым


По сслыке с dtf.блогов набрела на видео с Алексеем Пажитновым. Это тот самый, который тетрис придумал. Очень приятный, обаятельный человек.

Updated: 05.02.2007
В комментариях MyasNick привел ссылку на полный фильм BBC о Пажитнове. Вот он: From Russia With Love - BBC Tetris Documentary. Продолжительность около часа. О создании Тетриса рассказывается немного вначале, а потом начинается зловещий триллер про борьбу за авторские права. Периодически звучит тревожная музыка.

Ну и оттуда же комикс на злобу дня.

суббота, февраля 03, 2007

Wow?

Что-то Windows Vista все ругают. В блогах выкладывают фотографии и скриншоты с язывительными комментариями.
Вот это с блога Сета Година.


Сет справедливо замечает, что Wow обычно произносится немного с другим выражением лица.

Вот эта фотография Гейтса, рассказывающего о том как же работает Виста, очень широко разошлась. Я ее взяла отсюда, но она много где есть.


Ну и человек, опробовавший Висту, рассказывает о своих впечатлениях (много мата): Давайте посмотрим, что такое Windows Vista

пятница, февраля 02, 2007

Посты Shaders and stuff

Весьма увлекательные посты на блоге sim0nsays.livejournal.com про шейдеры. Постов две штуки
Shaders and stuff - part 1: ATI
Shaders and stuff - part 2: NV

четверг, февраля 01, 2007

Блоггер все еще глючит

Глюки, вызванные переходом Блоггера на новую версию все еще продолжаются. Сегодня был вообще апокалиптический день. Весь день, до последнего момента, нельзя было зайти на страницы отдельных постов. Часть дня не был доступен весь блог целиком.

Таинственным образом из профайла пропал мой email. Сейчас я его уже вернула.

Сортировка последних комментариев не работала несколько дней, потому что я сортировала их по id, а блоггеровцы сменили эти id'шки и они перестали идти по возрастающей. Я написала сортировку по датам, заняло это у меня довольно много времени, потому что JavaScript я уже успела основательно подзабыть, давно на нем ничего не писала.

Сейчас вроде все в порядке, будем надеяться, что так оно и останется.