Экспедиция в Экспедицию

UPDATE: Меряемся с женой бложиками - альтернативное изложение событий, в комментариях голосуем, у кого лучше вышло :)

Без особого планирования собрались с женой отпраздновать её ДР походом в ресторан. Так как Славца спихнуть было не к кому, круг подозреваемых для выездного отдыха сузился до узкого круга мест с террасами, в итоге решили съездить в Экспедицию - слышал хорошие отзывы. Плюс, насколько я помню, там раньше был ресторан Советский, мы там Ёхелевскую свабьду отмечали, то есть территория знакомая.

Пока Лена кормила нашего разбойника, я отправился осваивать территорию. Выбрал столик, посмотрел меню - посмурнел, инстинктивная жадность засосала под ложечкой. Так что если собрались, то готовьтесь к тратам.

Появление жены расставило все на свои места, для неё ничего не жалко :) Официантка, простив нам наше не знание терминологии северной кухни и подробно объяснив нам состав блюд, была сражена Славкиной улыбкой и, махнув ему напрощание хвостом (смешной такой, мохнатый), убежала оформлять заказ. Славке, как взрослому, было выделено отдельное место за столом, и заказаны свои, детские, блюда.

Решили поменять место дислокации на поближе к природе - отдельное спасибо персоналу за оперативную помощь - и устроились в тени яблоньки. Попивая облепиховый морс, провели рекогнисцировку местности, совмещая её с фотосессией.

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

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

Но не тут было - Ленино кольцо! Решив, что было просто снято где-то до ресторана, все же выдвинулись домой. Отсмотрели фотки:

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

Ситуация до смешного напомнила сходный случай в Болгарии, где была утоплена в море любимая сережка. Тоже отлично развлеклись, поплавали в море и фотосессия показала, что сережка была утеряна в море (в кои-то веки взяли с собой фотик и вообще достали его из сумки). Безуспешные поиски морских сокровищ в Несебре не добавили оптимизма.

Созвонились с персоналом ресторана, выдвинулись обратно на поисковую экспедицию в экспедицию. Поискали вокруг стола, поискали и не очень вокруг, море густой травы здорово напомнило поиски сережки на морском дне.

Порядком расстроенные вернулись домой. И вот, разбирает Лена рюкзак, достает пакет с сушками и с характерным звуком кольцо падает на ковер. Самое смешное, что поначалу Лена подумала, что я её разыгрываю и отмахнулась от меня, мол это баранка выпала :)

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

ConcurrentBag and BlockingCollection

В .NET 4.0 появился ряд новых классов для многопоточных приложений, в частности BlockingCollection и несколько Concurrent коллекций, к примеру, ConcurrentQueue и ConcurrentBag.

BlockingCollection удобно использовать для построения пайплайна обработки данных:

static void ProcessFile(string inputPath, string outputPath)
{
  var inputLines = new BlockingCollection<string>();
  var processedLines = new BlockingCollection<string>();

  // Stage #1
  var readLines = Task.Factory.StartNew(() =>
  {
    try
    {
      foreach (var line in File.ReadLines(inputPath)) inputLines.Add(line);
    }
    finally { inputLines.CompleteAdding(); }
  });

  // Stage #2
  var processLines = Task.Factory.StartNew(() =>
  {
    try
    {
      foreach(var line in inputLines.GetConsumingEnumerable()
.Select(line => Regex.Replace(line, @"\s+", ", ")))
      {
        processedLines.Add(line);
      }
    }
    finally { processedLines.CompleteAdding(); }
  });

  // Stage #3
  var writeLines = Task.Factory.StartNew(() =>
  {
    File.WriteAllLines(outputPath, processedLines.GetConsumingEnumerable());
  });

  Task.WaitAll(readLines, processLines, writeLines);
}

Однако, BlockingCollection - это обертка над интерфейсом IProducerConsumerCollection, коий реализуют выше указанные Concurrent коллекции. Так вот мы активно используем BlockingCollection. И недавно выяснилось, что по умолчанию BlockingCollection использует ConcurrentQueue, то есть поддерживает порядок обработки данных. Что зачастую нам не требуется. ConcurrentBag же не поддерживает порядок, но, как вы уже догадались, работает быстрее.

В целом же разница исчисляется во многих разах:

For mixed producer-consumer scenarios that do not require item ordering, ConcurrentBag(T) can be dramatically more efficient than ConcurrentStack(T) , ConcurrentQueue(T), and other synchronized collections.

Подробнее со статистикой здесь:
Thread-safe Collections in .NET Framework 4 and Their Performance Characteristics

Parallel Computing in MS

Слышали про новую фичу Excel 2010? Обработка таблиц на HPC Server 2008 R2 кластере. Это не шутка, фича позиционируется как серьезное улучшение в 2010 экселе. Это значит, что есть пользователи, у которых в Excel зашито столько логики, что им действительно имеет смысл просчитывать таблицы на кластере. А вы все со своими дотнетами бегаете.

Вообще, HPC Server 2008 R2 - это еще один шаг от Microsoft в стороную параллельных/распределенных вычислений. Он используется не только для обработки экселевских таблиц :) Краткий список возможностоей - собственно HPC кластер для распределенных вычислений (на основе MPI, насколько я понимаю), поддержка HPC Server в VS2010, возможность использовать в том числе и Linux машины в кластере, возможность использовать spare processing cycles компьютеров под Windows 7 в сети (grid computing), поддержка GPGPU. Тем, кто хочет знать больше, - сюда, первые несколько постов содержат дорожную карту по HPC и MPI.

Интересно еще будет почитать про усилия Microsoft в сфере GPGPU...

Йога по-дилетантски

Физкультпривет.

Скажу я вам следующую вещь. Спорт для программистов - это необходимость. Иначе прирастете попой к стулу и уже никогда с него не подниметесь.

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

Для начала хочу упомянуть, что занятие йогой - вовсе не такая халява, какой кажется сначала. Первые занятия я прилично вымокал, пот тек на коврик ручями. Не зазорно попробовать и крутым перцам :)

Для йоги практически ничего не нужно (кроме желания) и я с успехом (переменным) занимался ей в командировках.

Что мы обычно делаем на йоге?

1. Упражнения (асаны, ага) на гибкость
2. Статика и более активная нагрузка на мышцы
3. Упражнения на равновесие
4. Упражнения на расслабление и дыхание

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

Под гибкостью я долгое время понимал упражнения на растяжку ног (чтобы типа на шпагат сесть). В йоге всего больше - тянется все. Спина, руки, ноги, шея, стопы, кисти :) Оказывается есть много мышц, которые можно здорово порастягивать. Ну а о важности таких упражнений надеюсь говорить много не надо - мышцы просто работают эффективнее и меньше болят по утрам, если вы регулярно растягиваетесь.

Некоторые упражнения выглядят обманчиво простыми. Например, даже если просто развести руки в стороны и чуть-чуть вверх с большими пальцами назад, то это уже дает хорошее натяжение по всем мышщам груди и рук.

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

Упражнения на равновесие мне до сих пор даются тяжело. Чтобы удержать равновесие я напрягаю слишком много мышц, что после статических упражнений не просто :)

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

Ну и несколько хинтов напоследок:

1. Если асана дается легко, то скорее всего что-то делаем неправильно - обязательно что-то должно тянутся или напрягаться, надо поелозить, попробовать поменять положение
2. В некоторых асанах тяжело дышать, к примеру, при скручивании, или "лодке" на животе, попробуйте дышать по-другому - грудью вместо живота или наоборот или и то и другое
3. Спина должна быть прямой - тогда и ноги лучше тянуться и сами мышцы спины тоже; и да, лицам мужеского пола нужно уделять этому дополнительное внимание :) Смотрите в зеркало или ложите руки на поясницу, чтобы понять, как все запущено
4. Чтобы меньше падать, советуют фиксировать взгляд на неподвижной точке или вертикальной прямой; не знаю, мне не помогает, я лузер? :)

В общем, вот мой способ поддерживать себя в относительной форме. А у вас есть другие способы держать себя в форме? Буду рад услышать, велком в каменты.

State machine CSV parser

Понадобилось нам парсить CSV файлы.

Кто-то быстренько заимплементил свою версию. По инерции своя версия поддерживалась какое-то время, пока не стало понятно, что задача сильно осложняется различными вариациями формата CSV, различными формами экранирования, обработки пустых значений, выяснилось, что и формата есть несколько вариаций. Код оброс специальными случаями и условиями, стал нечитаем.

Задача стандартная, возник запрос, зачем делать самим. Быстрый поиск по интернету готовой версии выдал несколько левеньких вариантов со своими проблемами, а также более серьезные версии типа FileHelpers. Более серьезные версии как выяснилось не очень вписываются в нашу структуру классов. К примеру, FileHelpers как бы десериализует запись в объект класса. Звучит неплохо, однако для каждой колонки в целевом классе нужно было поле. А у нас файлы по 200-400 колонок.

Попробовали порефакторить – не впервой. Пошаговый рефакторинг не сильно улучшил ситуацию, попытки придумать новый подход тоже как-то не дали результата. В итоге все же наткнулись на идею написать парсер в виде конечного автомата – догадались не сами, но все же.

Конечный автомат – это по сути набор состояний системы и переходов из одного состояния в другое. Паттерн State эксплуатирует это математическое понятие. У каждого состояния есть свой способ обработки этого состояния и свои правила перехода в другие состояния. Конечный автомат также легко визуализируется при помощи UML State Chart диаграммы (ниже можно увидеть упрощенный пример).

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

Основная задача - распарсить одну строку файла:

private string[] SplitCsvLine(string line)

Идея в том, что мы пробегаемся по символам в строке и при встрече какого-либо специального символа мы переходим в новое состояние. В разных состояниях один и тот же символ переводит в различные состояния. Пример:

Код перехода из состояний в состояние:

CsvStateHandler currentState = HandleValueStart;

for (int i = 0, lineLength = line.Length; i < lineLength; i++)
{
       currentState = currentState(line[i], currentValue, values);
}

CurrentState – это делегат вида:

private delegate CsvStateHandler CsvStateHandler(
     char currentChar, 
     StringBuilder currentValue, 
     List<string> values);

Пример обработчика состояний:

private CsvStateHandler HandleValueStart(
        char currentChar, 
        StringBuilder currentValue, 
        List<string> values)
{
        currentValue.Clear();

        if (currentChar == quoteChar)
        {
            return HandleQuotedValue;
        }

        if (currentChar == delimiter)
        {
            values.Add(String.Empty);
            return HandleValueStart;
        }

        currentValue.Append(currentChar);

        return HandleSimpleValue;
}

Таким образом сложные многоэтажные ифы превратились в одноуровневые простые и целиком распределелись по простым компактным методам. Изменение логики и добавление очередного перехода стало простым и быстрым. Код стал понятен и поддерживаем.

День Победы

Порывшись по просторам интернета выяснил несколько интересных фактов:

• В течение 20 лет после войны этот день был рабочим
• Вообще, военные парады проводились только по круглым датам

Первый пункт мне, наверное, понятен. Что праздновать? Войну? Подозреваю, что большинство вовсе не хотело "помнить", скорее наоборот поскорее забыть.

По поводу последнего - в этом году 65 лет, юбилей, однако, ведь был парад и в прошлом году, разве не так? К. О. как бы подсказывает, что 64 тоже круглое число, но что-то я все равно сомневаюсь :)

Интересно еще и то, что победу в ВОВ 1941-1945 гг. празднуют, а победу в Отечественной Войне 1812 г. - нет. Оказывается, раньше праздновали - до 1917 г., то есть больше ста лет. 25 декабря, в Рождество, по старому стилю, естесственно. Видимо, после октября победы царской России потеряли свою ценность. Показательно, что распад СССР не привел к такому же эффекту. Прогресс :)

UPD: Сколько стоит Парад Победы в Минске

Wide records – wide table

К примеру, есть csv файл с записями. В сжатом виде 3 мегабайта, в распакованном 18 мегабайт. Заголовок определяет около 200 полей (естественно не все записи содержат). Нужно загрузить файл в Staging Area.

Первый вопрос, который возникает, - как хранить данные?

Правильный ответ – грузить в Staging Area не надо. Лучше хранить в памяти :) Ладно, предположим таких файлов штук 50. 50*18<1GB. Нет, все еще стоит подумать о просто загрузке в память. Ну скажем файлов у нас 200, нам еще и другие данные в памяти нужны, да и памяти у нас мало (бедные-бедные, но все равно потом придется выложить деньги на быстрые диски).

В случае с базами данных есть три варианта:

1. Создать таблицу с 200ми колонками 
2. Выделить в колонки только важные поля, остальные сериализовать в bulk column 
3. Таблица с колонками name-value

Три варианта обусловлены тем, что реляционные базы данных требуют строгой схемы. То есть 4й вариант – не использовать реляционную базу данных, читайте у Ayende - NoSQL.

Wide table

200 колонок в таблице - звучит непривычно, однако вариант вполне хороший.

Минусы:

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

- если данные сильно разрежены (из 200 полей одна запись имеет только 5-10), то такие таблицы занимают больше, чем могли бы – значит большая нагрузка на диск, больше места на диске

- вообще говоря, в ряде случаев есть ограничения на размер одной записи; если ограничений нет, то будьте готовы, что если превышается определенный объем, то в целом работа с такой таблицей будет замедлятся

Плюсы:

- если данные разрежены не сильно, то это наиболее эффективный способ хранения данных (это станет понятно, когда мы рассмотрим остальные варианты)

- иметь типизированные колонки удобно

Применительно к SQL Server, приведенные выше минусы в чем-то решены новым механизмом wide tables, появившемся в 2008 версии. Wide tables используют sparse columns и column sets. Вы определяете набор sparce columns и объединяете их в column set.

Если записи сильно разрежены, то sparce columns требуют меньше места для полей, у которых нет значений. Для этого используются дополнительные биты, то есть в случае наличия всех значений, запись будет занимать больше места, чем обычно.

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

Column set добавляет новую специальную xml колонку и позволяет получить все sparce columns в xml виде, также позволяет напрямую изменять xml и транслирует эти изменения в таблицу. Удобно, но имеет свою цену.

Если вы работаете с такой таблицей из .NET, то будьте готовы к багу в SqlBulkCopy (Мы ведь говорим об ETL, правда? Значит, мы загружаем данные при помощи bulk insert).

SqlBulkCopy видит только колонки, не включенные в column set, и xml колонку, созданную column set-ом. Вкратце, чтобы определить набор колонок в таблице, он далает select *, и этот запрос не возвращает sparce columns (тоже надо иметь ввиду). По сути, чтобы добавить запись в такую таблицу при помощи SqlBulkCopy, вам придеться сериализовать запись в xml и надеятся на механизм column set-ов. Естественно, производительность падает.

Staging Area

Неожиданно. Пост на техническую тему.

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

Один из паттернов, используемых для ETL является Staging Area или Staging Database, то есть промежуточное хранилище (стоит, правда, отдельно отметить, что это хранилище может быть и не базой, по крайней мере не реляционной базой).

Staging Area полезен в случае, когда у вас есть два источника данных, которые асинхронно поставляют вам информацию по одним и тем же сущностям.

К примеру, один из источников поставляет информацию по условиям ценных бумаг, а другой поставляет цены. Предположим, что цены поставляются раз в день после закрытия торгов на бирже. Общая информация по ценным бумагам поставляется постоянно. Информацию по ценам можно загрузить в промежуточное хранилище и проиндексировать. Когда приходит очередное обновление по ценным бумагам то для того, чтобы поднять цены, мы делаем запрос в Staging Area используя ранее созданные индексы. Действительно, не делать же нам поиск по файлам каждый раз.

Staging Area также используется в случаях, когда мы хотим, чтобы база данных сделала за нас некую работу, к примеру join. Полезно в случаях, когда мы сами не можем сделать join, к примеру, по причине объема данных - ни один из входных наборов данных не влазит в память. Если вы используете серьезный ETL tool, то это может и не быть проблемой. В случае нехватки памяти ETL tool может делать дамп на диск. Естественно, это замедлит обработку, но все же может быть быстрее, чем полная вгрузка данных в базу. Однако, если мы пишем ETL process на традиционных языках, то база может быть простым решением этой проблемы.

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

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