Software engineering

Параллельный доступ и ссылочная прозрачность

Для будущих учащихся на курсе Scala-разработчик приготовили перевод материала.

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

*Concurrency конкурентность, допускающая одновременное выполнение нескольких вычислительных процессов.

Ref и Deferred являются основными строительными блоками в FP, используемыми параллельно, в манере concurrent. Особенно при использовании c tagless final (неразмеченной конечной) абстракцией, эти два блока, при построении бизнес-логики, могут дать нам и то, и другое: параллельный доступ (concurrent access) и ссылочную прозрачность (referential transparency), и мы можем использовать их для построения более продвинутых структур, таких как counters (счетчики) и state machines (конечные автоматы).

Перед тем, как мы углубимся в Ref и Deferred, нам полезно узнать, что concurrency в Cats строится на Java AtomicReference, и здесь мы и начнем наше путешествие.

Atomic Reference

AtomicReference это один из элементов пакета java.util.concurrent.atomic. В Oracle docs мы можем прочитать, чтоjava.util.concurrent.atomic это:

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

Экземпляры классов AtomicBoolean, AtomicInteger, AtomicLong, и AtomicReference обеспечивают доступ и обновление от одиночных переменных к соответствующему типу (функционального блока).

AtomicReference с нами начиная с Java 1.5 и используется для получения лучшей производительности, чем синхронизации (хотя это не всегда так).

Когда вам приходится совместно использовать некоторые данные между нитями (threads), вы должны защитить доступ к этой части данных. Самым простым примером будет увеличение некоторого количества int: i = i + 1. Наш пример состоит из фактически 3 операций, сначала мы читаем значение i , затем добавляем 1 к этому значению, а в конце снова присваиваем вычисленное значение i . В отношении многопоточных приложений, мы можем столкнуться с ситуацией, когда каждый thread будет выполнять эти 3 шага между шагами другого thread, а конечное значение i предсказать не удастся.

Обычно в вашей голове появляется слово synchronised или механизм класса lock, но с atomic.* вам больше не нужно беспокоиться о явной синхронизации, и вы можете перейти на предоставленные atomic (атомарные) типы утилит, где проверка выполнения операции в один шаг включается автоматически.

Давайте, возьмем для примера AtomicInteger.incrementAndGet:

/**     * Atomically increments by one the current value.     *     * @return the updated value     */    public final int incrementAndGet() {        for (;;) {            int current = get();            int next = current + 1;            if (compareAndSet(current, next))                return next;        }    }

С помощью операции compareAndSet мы либо обновляем наши данные, либо терпим неудачу, но никогда не заставляем thread ждать. Таким образом, если операция compareAndSet в incrementAndGet не удаётся, мы просто пытаемся повторить всю операцию заново, извлекая текущее значение наших данных с помощью функции get() в начале. С другой стороны, при использовании синхронизированных механизмов нет ограничений на количество операторов (statement), которые вы хотите выполнить во время блокировки, но этот блок никогда не выйдет из строя и может заставить вызывающий thread ждать, предоставляя возможность заблокировать или снизить производительность.

Теперь, зная определенные основы, давайте перейдем к нашей первой мега-звезде concurrency.

Ref

Ref в Cats очень похож на упомянутую выше atomic (атомарную) ссылку Java. Основные отличия заключаются в том, что Ref используется с tagless final абстракцией F . Он всегда содержит значение, а значение, содержащееся в Ref типа A, всегда является неизменным (immutable).

abstract class Ref[F[_], A] {  def get: F[A]  def set(a: A): F[Unit]  def modify[B](f: A => (A, B)): F[B]  // ... and more}

Ref[F[_], A] это функциональная изменяемая (mutable) ссылка:

• Concurrent ( конкурентная)

• Lock free ( без блоков)

• Всегда содержит значение

Она создается путем предоставления начального значения, и каждая операция осуществляется в
F, например, cats.effect.IO.

Если мы внимательно посмотрим на сопутствующий объект для Cats Ref, мы увидим, что наша F должна соответствовать некому требованию, а именно быть Sync.

def of[F[_], A](a: A)(implicit F: Sync[F]): F[Ref[F, A]] = F.delay(unsafe(a))

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

Sync дает нам возможность приостанавливать любые побочные эффекты с помощью метода
delayдля каждой операции на Ref.

Ref довольно простая конструкция, мы можем сосредоточиться в основном на ее get, set и of чтобы понять, как она работает.

Метод get and set

Допустим, у нас есть объект (для этого блога мы назовем его Shared), который нужно обновить несколькими threads, и мы используем для этого наши методы get и set , создавая утилитный метод, который поможет нам в дальнейшем:

def modifyShared(trace: Ref[IO, Shared], msg: String): IO[Unit] = {for {sh <- trace.get()_ <- trace.set(Shared(sh, msg))} yield ()}

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

Я только что создал Shared(prev: Shared, msg: String) для данной статьи.

В нашем примере выше F был заменён конкретным IO из Cats Effect, но имейте в виду, что Ref является полиморфным в F и может быть использован с другими библиотеками.

С помощьюmonadic (монадический) IO мы применяем функцию flatMap на каждом шаге и устанавливаем значение, сохраненное в нашем Ref на желаемое значение или... подождите, может быть, мы этого не делаем.

При таком подходе, когда modifyShared будет вызываться одновременно, и мы можем потерять обновления! Это происходит потому, что мы можем столкнуться с ситуацией, когда, например, двое threads могут прочитать значение с помощью get и каждый из них будет выполнять set одновременно. Методы get и set не вызываются атомарно (atomically) вместе.

Atomic (атомарный) update

Конечно, мы можем улучшить приведенный выше пример и использовать другие доступные методы из Ref. Для совместной реализации get и set мы можем использовать update.

def update(f: A => A): F[Unit] 

Это решит нашу проблему с обновлением значения, однако update имеет свои недостатки. Если мы захотим обратиться к переменной сразу после обновления, аналогично тому, как мы использовали get и set , мы можем в итоге получить устаревшие данные, допустим, наш Ref будет содержать ссылку на Int:

for {_ <- someRef.update(_ + 1)curr <- someRef.get_ <- IO { println(s"current value is $curr")}} yield ()

Нас спасет modify

Мы можем немного улучшить вышеупомянутую ситуацию, используя modify , которая будет делать то же самое, что и update , но тем не менее, modify вернет нам обновленное значение для дальнейшего использования.

def modify[B](f: A => (A, B)): F[B] = {      @tailrec      def spin: B = {        val c = ar.get        val (u, b) = f(c)        if (!ar.compareAndSet(c, u)) spin        else b      }      F.delay(spin)    }

Как видите, это практически та же имплементация, что и в примере с AtomicInteger.incrementAndGet, который я показывал в начале, но только в Scala. Нам четко видно, что для выполнения своей работы Ref также работает на основе AtomicReference .

Ref ограничения

Вы, вероятно, уже заметили, что в случае неудачи при обновлении значения функция, переданная update/ modify, должна быть запущена недетерминированно (nondeterministically) и, возможно, должна быть запущена несколько раз. Хорошая новость заключается в том, что это решение в целом оказывается намного быстрее, чем стандартный механизм блокировки и синхронизации, и гораздо безопаснее, так как это решение не может быть заблокировано.

Как только мы узнаем, как работает простой Ref, мы можем перейти к другому классу Cats Concurrent: Deferred (Отложенный вызов).

Deferred

В отличие от Ref, Deferred:

• создается пустым (отложенный результат выполнения)

• может быть выполнен один раз

• и после установки его нельзя изменить или снова сделать пустым.

Эти свойства делают Deferred простым и в то же время довольно интересным.

abstract class Deferred[F[_], A] {  def get: F[A]  def complete(a: A): F[Unit]}

Deferred используется для явной функциональной синхронизации. Когда мы вызываем get в пустой Deferred мы устанавливаем блокировку до того момента, как значение станет вновь доступно. В соответствии с документацией из самого класса:

• Блокировка указана только семантическая, никакие реальные threads (нити) не блокируются имплементацией

Тот же вызов get непустого Deferred немедленно вернет сохраненное значение.

Другой метод complete заполнит значение, если экземпляр пуст и при вызове непустого Deferred приведет к сбою (неудачная попытка IO).

Здесь важно отметить, что Deferred требует, чтобы F было Concurrent, что означает, что его можно отменить.

Хорошим примером использования Deferred является ситуация, когда одна часть вашего приложения должна ждать другую.

Пример ниже взят из великолепного выступления Фабио Лабеллы на выставке Scala Italy 2019 Composable Concurrency with Ref + Deferred available at Vimeo

def consumer(done: Deferred[IO, Unit]) = for {c <- Consumer.setup_ <- done.complete(())msg <- c.read_ <- IO(println(s"Received $msg"))} yield ()def producer(done: Deferred[IO, Unit]) = for {p <- Producer.setup()_ <- done.getmsg = "Msg A"_ <- p.write(msg)_ <- IO(println(s"Sent $msg"))} yield ()def prog = for {  d <- Deferred[IO, Unit]  _ <- consumer(d).start  _ <- producer(d).start} yield ()

В приведенном выше примере у нас есть producer (производитель) и consumer (потребитель), и мы хотим, чтобы producer ждал, пока consumer setup закончится, прежде чем писать сообщения, в противном случае все, что бы мы ни написали в producer, будет потеряно. Для преодоления этой проблемы мы можем использовать общий экземпляр Deferred и блокировать get до тех пор, пока не будет заполнен экземпляр done Deferred со стороны consumer (значение в данном случае простая Unit () ).

Конечно, вышеуказанное решение не обошлось без проблем, когда consumer setup никогда не прекращался, мы застревали в ожидании, а producer не мог отправлять сообщения. Чтобы преодолеть это, мы можем использовать таймаут с get , а также использовать Either[Throwable, Unit] или какую-либо другую конструкцию вместо простой Unit внутри нашего объекта Deferred.

Deferred довольно прост, но в сочетании с Ref он может быть использован для построения более сложных структур данных, таких как semaphores (семафоры).

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

Узнать подробнее о курсе Scala-разработчик.

Смотреть открытый вебинар по теме Эффекты в Scala.

До 10 апреля продолжается набор на вечерние курсы по математике и программированию в CS центре. Computer Science Center это совместный проект Школы анализа данных Яндекса, JetBrains и Computer Science клуба при ПОМИ РАН. Курсы проходят очно в Санкт-Петербурге и Новосибирске, жители других городов могут заниматься дистанционно. Обучение в Computer Science Center бесплатное.

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

Большинство наших студентов учатся в вузах или работают, поэтому расписание составлено так, чтобы занятия можно было совмещать с основной деятельностью. Однако будьте осторожны: на учёбу в Computer Science Center придется тратить не менее 15 часов в неделю. Если у вас недостаточно времени (или мотивации), советуем начать с онлайн-курсов на платформе Stepik.

Длительность обучения два или три года по выбору студента. За это время нужно пройти не менее 12 курсов: часть из них обязательная, часть вы выбираете сами. Обязательные курсы зависят от направления обучения. Для поступающих в 2021 году будут открыты три направления (позже вы сможете выбрать одно из них или даже несколько сразу):

• Computer Science,

• Data Science,

• Software Engineering.

Подробнее обо всех направлениях на сайте. Для выпуска студенты проходят три семестра практики или научно-исследовательской работы (примеры есть на этой странице).

Чтобы стать студентом или студенткой CS центра, нужно справиться с вступительными испытаниями:

• заполните анкету на сайте до 10 апреля,

• решите задания онлайн-теста до 11 апреля,

• участвуйте в онлайн-экзамене в конце апреля-начале мая,

• пройдите собеседование в мае-июне.

Для кандидатов, которые успешно прошли отбор, занятия начнутся в сентябре 2021 года.

Если вы еще не решили, стоит ли ввязываться в эту авантюру, посмотрите на отзывы выпускников:

Станислав Гордеев, разработчик игрового движка в People Can Fly (Варшава), выпускник 2018 года направления Software Engineering:

Когда-то давно, в сентябре 2014, будучи ещё студентом-физиком, я случайно наткнулся на хабро-статью про онлайн-курсы на Stepik, заинтересовался и прошёл курсы по C++ и алгоритмам, кроме того, узнал о CSC. На тот момент у меня помимо интереса появилась довольно амбициозная цель попасть в большой gamedev. Поступление оказалось совсем не лёгким и до последнего дня с письмом о зачислении я не верил, что всё получится. Моё обучение началось в 2016, и с тех пор я семимильными шагами приближался к своей цели. А все из-за неповторимой атмосферы знаний, амбиций, дружелюбия, которая не позволяет сидеть на месте, которая заставляет поверить в себя. Сейчас я с уверенностью могу сказать, что моя цель осуществилась в первую очередь благодаря CS центру, потому что это больше, чем просто курсы. Старайтесь, и у вас всё получится.

Анна Атаманова, разработчица в Яндексе, выпускница 2016 года направления Data Science:

Почему СS центр это дико круто:

курсы! (всё новое и интересное по основным направлением центра тут-тут-тут);

увлечённые своим делом преподаватели (таких людей в любом случае приятно слушать);

мотивированные, заинтересованные студенты (да у них можно узнать чуть ли не больше, чем на паре);

проекты! стажировки! (опыт, реальные задачи);

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

Артемий Пестрецов, разработчик в JetBrains, преподаватель CS центра, выпускник 2019 года направлений Data Science и Software Engineering:

Как я и ожидал, CSC стал важной поворотной точкой в моей карьере. Все три года я кайфовал от процесса обучения, сумел закрыть старые пробелы в знаниях и узнать много нового. Наверное, самое важное следствие гибкой системы выбора курсов и практик возможность пробовать разные дисциплины и в итоге найти себя. За время обучения в центре я разрабатывал распределенные системы, занимался машинным обучением и создавал инструменты для разработчиков. В итоге я нашел работу в интересующем меня направлении в крутой компании. А ещё в центре очень классная тусовка, с которой вы так или иначе будете пересекаться на протяжении всей карьеры.

Все отзывы можно посмотреть на этой странице.

Для тех, кто нашел в себе силы дочитать до этого места, бонус! Перед тестом вы можете потренироваться и порешать задачи прошлых лет. Но помните, что 10 апреля тренажёр превратится в тыкву, так что лучше не откладывать.

Ну и самое последнее: 31 марта состоится День открытых дверей для поступающих в CS центр. Кураторы подробно расскажут про направления и формат обучения и ответят на все ваши вопросы. Зарегистрироваться можно здесь.

Ждем будущих студентов Computer Science Center!