?

Log in

No account? Create an account
   Journal    Friends    Archive    Profile    Memories
 

Scala - morfizm


Aug. 2nd, 2016 12:27 am Scala

Пока я ещё не разучился писать не на Скале (а я чувствую, что это уже возможно), надо бы чиркнуть пару слов про Скалу для тех, кто не очень знаком с функциональными языками, но знаком с чем-то вроде {C, C++, Java/C#, Python}.

Скала не тотально функциональный язык. На ней можно писать императивно, будет очень похоже на классическую Java. Обычно императивно пишут отдельные кусочки, не связанные с ожиданием I/O или сервис-calls, но вся целиком структура скорее функциональная, чем императивная.

Напомню основные различия парадигм программирования:

1. Императивное (наиболее распространённое, C, C++, Basic, Assembler, etc). Есть базовые структурные элементы - такие как команда, последовательность команд, ветвление, цикл, подпрограмма, и есть память: переменные, параметры. Из всего этого складывается программа целиком, её можно мысленно представить как блоксхему, являющуюся ацикличным графом, с одним входом и одним выходом. В однопоточном случае в каждый момент времени исполняется какая-то одна команда, какая-то точка в этом графе - "текущая". Текущее состояние описывается этой точкой, а также совокупностью значений всех переменных. В принципе, это отдалённо напоминает конечный автомат. Изменение состояния - это, возможно, запись в какую-то переменную, исполнение команды, а также переход в следующее состояние.

В многопоточном случае отдельный поток императивен, они работают параллельно, и между ними происходит обмен при помощи различных thread-safe структур данных, локов, семафоров и прочего. Многолетняя практика софтварной индустрии показала, что ничего сложнее threadpool'а и thread-safe очередей которые только на чтение или только на запись, программист написать не способен. Вернее, написать-то способен, но потом он не способен будет прочитать. Будет всё коряво и с багами.

2. Декларативное (типичные примеры: Пролог, Lex/Yacc, SQL, HTML, некоторые языки для конфигов). Есть набор каких-то данных. Есть язык, позволяющий выразить какие-то взаимосвязи (предикаты, условия, желаемый результат). Выражаешь то, что хочешь получить, и система сама как-то вы-figure-out-ит, как это посчитать. В общем случае, как оно будет считаться, ты не знаешь и тебе это не интересно. На практике, к сожалению, очень даже знаешь, иначе всё работает экспоненционально медленно.

3. Функциональное (Lisp, ML, Haskell, Erlang, Scala). Базовые элементы построения - это функции, в наиболее широком, абстрактном и математическом смысле этого слова, а также их композиции. Состояние определяется не какими попало переменными, а параметрами всех функций текущего stack frame, и передаваемыми назад результатами.

Есть вещи, которые считаются плохим тоном и рушат парадигму: это глобальные переменные (если в императивном программировании за них просто били по рукам, то в функциональном должны сажать на электрический стул) и другие всевозможные "побочные эффекты" функций. Чистые функции, не имеющие побочных эффектов, очень клёвые, потому что компилятор/интерпретатор языка может с ними делать разные прикрольные вещи (кэшировать значения, распараллеливать с минимальным оверхедом и т.п.). Это функции, результат которых полностью зависит от параметров, и больше ни от чего. Конечно, простейшие вещи вроде ввода-вывода, или вызова удалённого сервиса - это тоже побочные эффекты, и от них никуда не денешся, но их стараются выносить в самые внешние блоки программы, а все промежуточные вычисления делать уже в строго функциональном стиле. Также функциональный стиль предполагает немутабельные переменные, параметры, объекты, структуры данных. Мутабельные возможны, но крайне не желательны, если их можно избежать, то их нужно избежать.

Последовательность двух команд, вроде "A; B" - это, на самом деле функция, которая принимает два параметра, функцию A и функцию B, вычисляет обе по очереди, выкидывает результат первой и возвращает результат второй. A + B это, конечно, двухарная функция +(A, B). Scala очень добра к людям и в обоих случаях позволяет писать привычным способом, вроде блока:
A
B + C

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

Но есть ли разница? Для однозадачного случая - разницы практически нет. Всё это можно назвать syntactic sugar, и мы уже видели его в Питоне. Там есть и map, и filter, и itertools, и лямбды (колбеки), и функторы (колбеки с контекстом). Да, красиво, но при этом понятно, что должным образом извратившись можно такое же написать и на C. Да, будет геморнее. Поэтому не C, а C++. Поэтому не C99, а C++ 11/14 (в котором тоже есть и foreach'и, и функторы, и чего там только нет). Синтактический сахар помогает жить.

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

Ключевые для понимания концепты - это фьючеры (Future) и промисы (Promise). Если x: Int это переменная x, в которой может храниться целое число, то x: Future[Int] это контейнер для значения, которое будет доступно когда-нибудь потом. Оно может быть вычислено где-то на тредпуле, или даже в текущем треде, ты можешь не знать детали. Но ты можешь с этим фьючером делать две вещи. Первая вещь - это подождать, пока там наверняка появится значение (обычно там появляется либо значение, либо exception в случае ошибки, фьючер его wrap'ает тоже, и он может быть успешным или failed). Эту вещь стараются делать как можно более потом, а лучше в самом конце один раз. Вторая вещь, самая главная, это ты можешь написать код, который выполнится потом, в момент, когда у фьючера появится значение. Но написать ты его можешь уже сейчас. Например, ты можешь написать:

val y = x.map { z => z + 1 }

Теперь y имеет implicit type Future[Int], как и у x, но y это другой фьючер. Это фьючер, который когда-нибудь в будущем получит значение z+1, но только после того, как в x будет записан z. Можно представить себе, что в момент "исполнения" этого кода куда-то на тредпул отправляется колбек с кодом "взять значение, записанное во фьючер x, прибавить к нему 1, и потом записать результат во фьючер y, просигнализировав, что этот фьючер получил значение (кстати, для этого используется близкий родственник фьючера - промис. Промис это single-write контейнер, в который можно записать нечто, что запишется в связанный с ним фьючер и сделает его завершённым). Этот код будет за-schedule'н таким образом, что он выполнится ровно в тот момент, когда нужно - только после того, как x получит своё значение. Понятно, что можно продолжить последовательность и написать где-нибудь: val p = z.map { f => f + 1 } и это продолжит отложенную цепочку вычислений. "map" называется монадой (Monad), единственный смысл этого слова в контексте Скалы - это "нечто, позволяющее комбинировать отложенные вычисления", связующая хрень. Кроме "map" их есть ещё несколько, но это не важно. После => может следовать много строк кода, только последняя строка будет конечным результатом.

Получается, что исполнение программы - это процесс, в котором одновременно идёт немедленное исполнение команд в классическом (императивном) стиле, и при этом создание ацикличного графа с отложенными вычислениями, которые вообще говоря могут начать исполняться немедленно где-то на тредпуле. Отладка этой мешанины, конечно, сложнее, чем отладка обычного однопоточного приложения на C++, но в легче, чем отладка многопоточного. Брейкпоинты работают, как внутри map'ов, так и снаружи, только "step over" будет перешагивать через отложенные куски.

Этот стиль позволяет довести до абсурда идею отложенных вычислений: любые фундаментально медленные действия, обычно блокирующие, вроде записи в файл или вызова удалённого API, обычно возвращают управление немедленно, но возвращают Future[X]. Не дожидаясь, что в этом Future, вызывающий поток может немедленно начать генерировать цепочкую новых отложенных действий, которые выполнятся как только значение таки будет получено.

Практический пример у меня случился буквально сегодня. Я опишу задачу и решение, подсказанное колегой. На Скале писать одно удовольствие. На императивном языке, уверен, что затрахался бы. Но главное не это. Главное то, что с привычками, связанными с императивным программированием, красивая идея решения просто могла бы не прийти в голову, а тут она приходит естественно.

Задача: есть какая-то обработка данных - скажем, батч 20 миллионов записей. У записей есть поле X - это короткий ключ к куда более длинному значению Y, доступному через внешний lookup service (ну, допустим, для простоты, что храним в S3 или в базе данных). Известно, что разных значений Y, равно как и X, не очень много - скажем, 5 тысяч. Нужно сгруппировать записи по Y и для каждого Y напечатать количество записей.

Решение: берём мутабельную хэштаблицу с ключами типа X и значениями Int. Для каждого документа пишем что-то вроде:

if (table.contains(X)) { table(X) += 1 }
else { table(X) = 0 }


В конце делаем что-то вроде:

table.map { (X, count) => (fetchY(X), count) }

чтобы преобразовать таблицу с ключом X в искомую таблицу с ключом Y.
Хорошее ли это решение? Вроде неплохо: для каждого ключа X вызовы fetchY(X) будут параллельны, но, на самом деле, не очень:
(1) перед печатью нам всё равно нужно будет ждать, пока вернётся самый долгий,
(2) для небольшого количества записей (5 тыс) внешний lookup storage сервис вполне может плохо пошардить, и если все 5000 запросов пойдут на один шард, это может превысить лимиты. Придётся возиться с retry/backoff, в худшем случае будут ошибки, а в лучшем оно просто будет очень долго (может быть, минуты).

Пробуем улушить: заводим кеш и делаем fetch'и по ходу дела:

val Y = if (cache.contains(X)) { cache.get(X) } else { cache(X) = fetchY(X); cache(X) }
if (table.contains(Y) { table(Y) += 1 }
else { table(Y) = 0 }


Теперь bottleneck'а с одновременным 5 тыс запросов больше нет, но и плюса от параллельности тоже нет. Суммарно всё замедлится ровно на столько, сколько нужно, чтобы сделать 5 тыс fetch'ей. Да и таблица будет больше размером, Y-то большие.

Улучшаем дальше. X: String, Y: String, но теперь примем, что fetchY(X) возвращает Future[String] (в принципе, обычно так и есть по умолчанию, а в сихнронных вызовах, вроде как в примерах выше, нужно дополнительно писать ожидание результата Future).

if (!cache.contains(X)) { cache(X) = fetchY(X) } // кэшируем future Y, но не более одной на каждое значение X
if (table.contains(X) { table(X) += 1 }
else { table(X) = 0 }


А в конце мы можем преобразовать таблицу вот так:

val listFutures = table.map{ (X, count) => cache(X).map { Y => Y, count } } // это будет список фьючерсов от пар (Y, count)
val futureList = Future.sequence(listFutures) // преобразовываем в один большой фьючер от списка пар
Await.result(futureList, 3.minutes) { seq => seq.toMap } // или можно просто написать (_.toMap) - ждём пока этот фьючер весь выполнится и преобразовывами список пар обратно в таблицу, обратите внимание, что Map это класс для немутабельной хештаблицы, а map это монада. Они пишутся похожим образом, но совершенно разный смысл.


Чем этот пример хорош? Тем что он (а) человеку, пописавшему на Скале полгода, приходит в голову как естественный, (б) на самом деле крайне эффективен: мы начинаем prefetch'и каждого значения Y ровно в тот момент, когда мы впервые узнали о том, что Y нам в будущем потребуется, при этом мы не блокируем основные вычисления на батче документов, и не делаем кучу запросов в конце. Этот последний фьючер в большинстве случаев не будет ждать вовсе, потому что всё уже закешилось, а в худшем случае подождёт окончания тех нескольких lookup'ов, которые были за-schedule'ны в последнюю очередь.

Пожалуй, это всё, что я хотел сказать о Скале, чтобы создать о ней какое-то впечатление.

Добавлю ещё пару общих наблюдений:

1. Очень steep ramp-up curve, но потом видно преимущество. Я работаю почти три месяца. Первые два я не мог прочесть ни одного код ревью. Третий месяц я себя чувствую как рыба в воде, и, по ощущениям, разбираюсь в существующем коде быстрее, чем в традиционном, именно потому что хороший функциональный стиль фундаментально улучшает читаемость: когда почти всё немутабельное и без побочных эффектов, куда ниже когнитивная нагрузка чтобы понять, в чём состоит state.

2. На Scala появилось ощущение, что "templates done right". Меня, если честно, тошнило от C++ темплейтов (надеюсь, Степанов не читает). STL ещё куда ни шло, но Boost уже borderline, а custom'ные темплейты - просто сходу рвотный рефлекс. На Scala, напротив, мне самому захотелось писать generic code, потому что темплейты там first-class в языке, сделаны по-человечески.

3. Важный плюс Скалы - это лёгкая переносимость кода, написанного на Scala для многопоточности на одной машине в распределённую среду, в которой много отдельных нодов на разных хостах. Фреймворки вроде Flink и Spark дают интерфейс, синтаксически очень похожий на то, что в Scala пишут для одной машины. Тот же flatMap, только ты понимаешь, что блок отложенных вычислений будет исполняться распределённо, а входные и выходные значения сериализуются и marshall'ятся.

4. Есть неприятные моменты - напр., Scala-стиль предполагает почти никогда явно не указывать типы. Типизация строгая, но типы должны infer. Почти всегда так и происходит. Но когда так не происходит, это, извините, жопа, потому что типы приходится расставлять везде и долго дебаггать где же произошла неверная подстановка. Это как бы побочный эффект от слишком большой гибкости темплейтов. Но, в целом, терпимо.

13 comments - Leave a commentPrevious Entry Share Next Entry

Comments:

From:rezkiy
Date:August 2nd, 2016 07:39 am (UTC)
(Link)
ухтыблин, лонгрид. Не думаешь копипастнуть на хабр? И хочешь ли дискуссию?
From:morfizm
Date:August 2nd, 2016 05:49 pm (UTC)
(Link)
Сложно сказать. Я бы не прочь почитать про другие взгляды, дополнения, показательные истории получше, и, конечно, не возражаю если кто-то заметит неточности и напишет как правильно. Я даже могу обновить пост. Но времени вдумчиво обсуждать у меня нет, так что если я буду получать много провокационных вопросов или указаний на неточности, но без своей корректной версии, то мне будет некомфортно.

Что посоветуешь исходя из этого - копипастнуть или нет?
From:rezkiy
Date:August 2nd, 2016 07:43 am (UTC)
(Link)
>> 4. Scala-стиль предполагает почти никогда явно не указывать типы
А ты пробовал писать на цпп с almost always auto? Ну чтобы почти никогда не указывать явно типы?

Edited at 2016-08-02 08:30 am (UTC)
From:archaicos
Date:August 2nd, 2016 08:33 am (UTC)
(Link)
В плюсах тоже грядёт этот вот футуризм. Одна большая помойка получается.
From:rezkiy
Date:August 2nd, 2016 08:51 am (UTC)
(Link)
не соглашусь про помойку. Пока кривовато, я пробовал кодить с фучурами, немного пока не то, но скоро будет.

Уже есть приятные моменты. Например кто-то хочет колбек. Айо например. Нублин, completion_type io(parameters_type, std::function< void(completion_type) >); Если completion_type говорит что айо уже завершился, сам вызывай свой комплишен, иначе io() запомнит второй параметр и вызовет на тредпуле, когда завершится. Можно сделать так чтобы io() возвращал фучер, но пока кривовато.

Вообще идея о том, что your program is an asynchronous sea of very single threaded pieces of code that almost never wait, продуктивная. И вполне втыкается в современный спп. Но стандартная библиотека пока сосет.

Edited at 2016-08-02 08:53 am (UTC)
From:archaicos
Date:August 2nd, 2016 09:05 am (UTC)
(Link)
Язык не нравится. В ленивых/асинхронных операциях смыл есть, конечно.
From:fenikso
Date:August 2nd, 2016 04:07 pm (UTC)
(Link)
Вот после Haskell все эти скобочки и точки с запятой очень удручают. А так, неплохая штука.
From:morfizm
Date:August 2nd, 2016 05:37 pm (UTC)
(Link)
В реальном коде точек с запятой не видел. Это я здесь написал, чтобы компактнее изложить.
From:yau_hen
Date:August 2nd, 2016 10:21 pm (UTC)
(Link)
Тебе тогда http://reactivex.io/ должно еще понравиться
From:ermouth
Date:August 3rd, 2016 02:29 am (UTC)
(Link)
> пописавшему на Скале полгода, приходит в голову как естественный

На JS кстати тоже )

> захотелось писать generic code

Подкину тебе хороший текст на почитать http://milessabin.com/blog/2011/06/09/scala-union-types-curry-howard/
From:soloviewoff
Date:August 4th, 2016 05:13 am (UTC)
(Link)
В последнем примере, если исходный массив начинается с 5 тысяч разных значений, то все равно QPS spike будет?
From:morfizm
Date:August 4th, 2016 05:25 am (UTC)
(Link)
Будет, но (а) retry or rate throttling loop позволят зачитать их в бэкграунде, параллельно с основной работой, (б) я подразумевал случайное распределение. Шанс, что будет spike, пренебрежительно мал.

Будет чуть хуже, если 5 тысяч разных значений будут в конце, т.к. не будет пункта (а). Но будет п.(б) :)
From:soloviewoff
Date:August 4th, 2016 06:14 am (UTC)
(Link)
Согласен. Еще: итерация по 20 миллионам записей в памяти это порядок секунды, а если побить на куски и в параллель - порядок сотен миллисекунд. RPC внутри региона - десятки миллисекунд. Ну т.е. есть ощущение, что эти 5000 вызовов все равно доминировать будут, и что возможно нужна еще одна киянка, типа batch API добавить?