Конкурентност

Досега?

Програми с мощността на ламбда смятането/машината на Тюринг
Последователни изчисления, не се влияят от времето
Нямат връзка с околния свят
вход => предвидима трансформация => изход
Трансформиращи програми
Добре изучени

IO

import Console._

val program = for {
  _     <- putStrLn("What is your name?")
  name  <- getStrLn
  _     <- putStrLn("Hello, " + name + ", welcome!")
} yield ()

program.unsafeRun()

doSomethingElse()

Връзка с външния свят
Но синхронна – програмата не прави нищо друго докато чака
Интерактивни програми

Реалният свят

Светът навън е силно паралелен и конкурентен
Нещо повече, участниците в него си взаимодействат
Развива се във времето
Как да моделираме такива програми?

Конкурентност и паралелизъм

parallel: from παρά + ἄλληλος, along each other

concurrent: present active participle of concurrō (“happen at the same time with”), from con- (“with”) + currō (“run”)

concurrent computing: a form of computing in which several computations are executed during overlapping time periods—concurrently—instead of sequentially

Дистрибутираност

Независими компоненти със собствени изчислителни ресурси и памет, които комуникират помежду си чрез съобщения и изграждат цялостна система

Реактивност

Свойството на програмите/компонентите да реагират
на света около тях (с което да са част от него)

Конкурентност

В изчислителен контекст:

конкурентността се отнася към структурата на програмата,
паралелизмът, дистрибутираността – към хардуера и как тя ще бъде изпълнявана.

Конкурентните програми са композитност от unit-и от изчисления, които, веднъж дефинирани, могат да бъдат изпълнени независимо едно от друго.

Конкурентни модели

Нишки
I/O и TCP/IP конкурентност
Callbacks
Event loop
Future и Promise
Конкурентни опашки
Агенти
Актьорски модел
Communicating Sequential Processes
Software Transactional Memory
Stream/dataflow конкурентност
…

Какво прави един модел подходящ?

Лесен за проследяване и за разсъждаване върху твърдения за него
Предоставя изразни средства, с които да решим проблемът, който моделираме, но ни предпазва от сложността на по-общи проблеми
Не скрива особеностите на света на проблема – недетерминизъм, възможност за грешки, латентност и други
Предпазва ни от състояния, до които не искаме да стигаме, ако не са в домейна на проблема – race conditions, недетерминизъм и други
Композитен
Минимизира недетерминистичното влияние на времето
Functional programming to the rescue

Нишки

Комуникация между конкурентни примитиви

За да бъде смислен, всеки конкурентен примитив е нужно да има поне една интеракция с околния свят или с други примитиви
Границите с дистрибутираните системи се размиват
Нишки – чрез споделена памет и средства на процесора и ОС

Happens-before

Запис във volatile променлива се случва преди последващо нейно прочитане (от същата или друга нишка).
За всеки два последователни statement-а в една нишка, първият се случва преди вторият.
Релацията е транзитивно затворена.
Happens-before образува частична наредба.
Стартирането на нишка се случва преди всеки statement от стартираната нишка.

Happens-before

JVM ни гарантира, че всяка референция към immutable обект сочи към обект с напълно валидно състояние.

Затова неизменямостта улеснява reasoning-а значително и премахва огромен клас от възможни грешки при конкурентни програми.

Проблеми на нишките

Какво прави един модел подходящ?

Лесен за проследяване и за разсъждаване върху твърдения за него
Предоставя изразни средства, с които да решим проблемът, който моделираме, но ни предпазва от сложността на по-общи проблеми
Не скрива особеностите на света на проблема – недетерминизъм, възможност за грешки, латентност и други
Предпазва ни от състояния, до които не искаме да стигаме, ако не са в домейна на проблема – race conditions, недетерминизъм и други
Композитен
Минимизира недетерминистичното влияние на времето

Проблеми на нишките

Тежки – всяка има стек, регистри, превключването е бавно и минава през ядрото на ОС, стартират бавно
Трудни за проследяване – недетерминизъм е възможен във всяка една част, споделяща данни с други нишки
Фин контрол на недетерминизма – чрез мютекси и други средства за синхронизация (race conditions, deadlocks)
Некомпозитни, не поддържат трансформации
Всяка последваща задача трябва да бъде създадена императивно от самата нишка
Синхронност срещу асинхронност
The Problem with Threads

Предния път

Програми, взаимодействащи с външния свят
Конкурентност, паралелализъм, дистрибутираност, реактивност
Конкурентни модели. Какво прави един модел добър?
Нишки. Комуникация между нишки (и happens-before)
Immutability – гарантираност за валидно състояние

Конкурентните програми са композитност от изчислителни примитиви (unit-и), които, веднъж дефинирани, могат да бъдат изпълнени независимо едно от друго

Конкурентни изчислителни примитиви

Колко да са големи, колко дълго да живеят?
Как други примитиви могат да реагират на тяхно действие или на тяхното завършване (реактивност)?
Как да си говорят едни с други?
Как да се композират?

Нишките

Липсва реактивност
- но могат активно да създадат други нишки
- и да променят споделено състояние
Комуникират
- чрез споделено състояние
- чрез синхронни и блокиращи операции – докато операцията не завърши нишката не може да прави нищо друго
Не се композират

Callbacks?

def doSomething(onComplete: Result => Unit): Unit

Асинхронни и реактивни
Задействат се при завършване на работа или при определено събитие (естествени за event loop)
Ще ги изпълним върху pool от нишки (брой = ~брой ядра)

def doSomethingDangerous(onComplete: Try[Result] => Unit): Unit

Callbacks – негативи

Императивни, работят с mutable state
Некомпозитни. Callback hell
Ако се изпълняват в различни нишки, изискват синхронизация
Ръчно спряване с грешки

Future

Какво бяхме постигнали с IO?

Страничен ефект => функционален ефект
Който можем да третираме като стойност
Функционално композиране на ефекти (по определена операция)
Странични ефекти само при изпълнение

Да създадем Future

Изрази

val a = 42
val b = 4

val c = a + b // операция
val d = (a + b) * 10 // композиция на операции
val e = f(g(a)) // композиция на функции

Императивно срещу функционалнo

Императивните програми
- описват постъпкови промени във времето
- всяка стъпка зависи от всички предишни
- всяка нишка е императивна програма със собствена времева линия
- споделената памет води до преплитане на много времеви линии
Функционалните програми
- са изградени от изрази
- изразите описват зависимости. По декларативен начин
- резултатът на един израз зависи от неговите операнди, но самите операнди са независими
- те могат да се изчислят паралелно
- композиция на изрази/функции описва зависимост. Тя се изчислява последователно
- редът на дефинициите няма значение. В какъвто и ред да се изпълнят изразите, стига да се спазят зависимостите, ще се получи един и същи резултат

Eager vs lazy

Future се изчислява асинхронно => допустимо е да се изчисляват eagerly
т.е. изчислението да започне веднага след дефинирането и когато станат готови всички зависимости
Ще разгледаме и двата варианта

Реактивност на `Future`

Future комуникира с други Future-и
- при стартиране (стартира когато неговите зависимости са готови)
- и при завършване (“уведомява” зависимите от него)
Как да го вържем с други източници на събития?
Promise
Promise-ите ще генерират първоначални Future-и в нашата система
Адаптер към външния свят, например позволяват реактивност към събития за вход/изход
Ще ги скриваме за функционален интерфейс

Immutability

Future е безопасен, само ако стойностите в него са immutable!

Ако не са, то тяхното състояние може да е неизвестно

`Future` в Scala

scala.concurrent.Future
Използва ExecutionContext вместо Executor
default: import scala.concurrent.ExecutionContext.Implicits.global

Съществуваща стойност към `Future`

Future.successful(value)
Future.failed(exception)

Recover

def doSomethingForUser(userId: Id): Future[HttpResponse] =(for {
  user <- retrieveUser(userId)
  result <- doService(user, input)
} yield Ok(constructBody(result))) recover {
  case UserNotFound(userId) => NotFound
  case _: ActionNotPermitted => Unauthorized
}

Recover with друга, по-стабилна алтернатива

def dangerousService(input: ServiceInput): Future[Result] = ???
def safeService(input: ServiceInput): Future[Result] = ???

def calculate(input: ServiceInput): Future[Result] = {
  dangerousService(input).recoverWith {
    case _: ServiceFailure => safeService(input)
  }
}

Състезание

def algorithm1(input: String): Future[Int] = ???
def algorithm2(input: String): Future[Int] = ???

def calculation(input: Stirng): Future[Int] =
  Future.firstCompletedOf(List(algorithm1(input), algorithm2(input)))

Неопределен брой независими изчисления

def retrieveAge(userId: Id): Future[Int] = ???

def averageFriendsAge(user: User): Future[Option[Int]] = for {
  friendIds: List[Id] <- user.friends
  friendsAges: List[Future[Int]] = friendIds.map(retrieveAge)
  ages <- Future.sequence(friendsAges): Future[List[Int]]
} yield average(ages)

Асинхронност срещу синхронност

И двете имат и ползи и недостатъци
Подходящи за различни случаи
Асинхронността позволява конкурентните примитиви да продължат работа с нещо друго
- Позволява гъвкавост, код, описващ зависимости и лесно паралелизиране
- За разлика от синхронността, не създава строга зависимост между два компонента
- По-точно описва физическия свят
- По-голяма гъвкавост при спряване с недетерминизма от физическия свят (напр. загуба на съобщения)
Синхронността кара синхронните примитиви да изчакват резултат
- По-лесно за проследяване
- Тъй като не се случват няколко неща едновременно, най-много едно
- Изисква допълнителни ресурси, но при подходяща имплементация носи гарантиран throughput (например чрез синхронен clock)

Асинхронен вход/изход чрез `Future`

HTTP client
HTTP server

Task – lazy Future

Ще разгледаме Task имплементацията на Monix

Task – създаване

Task.now (= Future.successful)
Task.apply – за асинхронно изчисление (Task { 1 + 1})
Task.deferFuture

Task – композиране

Task.zip2,…, Task.zipN
Task.zipMap2,…, Task.zipMapN
map, flatMap
Task.sequence
Task.chooseFirstOfList(List(a, b))

Task – изпълнение

Task(1 + 1).runOnComplete {
  case Success(value) => ???
  case Failure(e) => ???
}

val result: Future[Int] = Task(1 + 1).runAsync
Task(1 + 1).foreach(???)
Нуждае се от monix.execution.Scheduler – подобно на ExecutionContext

Task – създаване (прод.)

Task.evalOnce – мемоизация на резултата при последващи изпълнения

Task

Подобно на IO, първо описаме план от трансформации
Като всеки план, може да се изпълнява множество пъти

Актьорски модел

Математически модел за конкурентни процеси, представен от Carl Hewitt през 1973-та
Актьорите са универсиални изчислителни примитиви
Те комуникират помежду си чрез съобщения
Erlang независимо имплементира този модел през 80-те

Актьори

Всеки актьор изпълнява функционална/Тюринг програма
Всеки актьор си има “адрес”, на който могат да бъдат изпращани съобщения
Програмата се нарича “поведение” и се задейства при получаване на съобщение
Изходът от поведението, задействано от съобщението, съдържа:
- Поведението, което ще бъде изпълнено при следващото съобщение
- Списък от актьори, които да бъдат създадени, и начално поведение за тях
- Списък от съобщения и съответни адреси на получатели, които да бъдат изпратени

С други думи

trait ActorRef
case class Actor(ref: ActorRef, startingBehavour: Behaviour)
case class Envelope(message: Any, recipient: ActorRef)
type Behaviour = Any => (Behaviour, List[Actor], List[Envelope])

Актьори – недетерминизъм

Поведението на актьора е детерминирано
Всичко останало моделира недетерминизма на физическия свят. Съобщенията:
- могат да бъдат изгубени – няма гаранция, че ще стигнат до получателя
- могат да пристигнат в произволен ред
- пристигат след неопределено време

Akka

Актьорите като конкурентен примитив

Комуникацията със съобщения е напълно асинхронна
Те са реактивни от гледна точка на получаването на съобщения
Трудни са за композиране (но може да се изградят композитни абстракции над тях)
За сметка на по-реалистично моделиране на физическия свят
Не споделят памет и не се нуждаят от средства за синхронизация. Всичко се оркестрира чрез комуникацията със съобщенията
Съобщенията могат да бъдат трансформирани и обработвани чрез чисто програмни средства. Това позволява изграждането на произволни комуникационни топологии
Могат да бъдат дистрибутирани

Конкурентност

Досега?

IO

Реалният свят

Конкурентност и паралелизъм

Дистрибутираност

Реактивност

Конкурентност

Конкурентни модели

Какво прави един модел подходящ?

Нишки

Комуникация между конкурентни примитиви

Happens-before

Happens-before

Проблеми на нишките

Какво прави един модел подходящ?

Проблеми на нишките

Предния път

Конкурентни изчислителни примитиви

Нишките

Callbacks?

Callbacks – негативи

Future

Изрази

Императивно срещу функционалнo

Eager vs lazy

Реактивност на Future

Immutability

Future в Scala

Съществуваща стойност към Future

Recover

Recover with друга, по-стабилна алтернатива

Състезание

Неопределен брой независими изчисления

Асинхронност срещу синхронност

Асинхронен вход/изход чрез Future

Task – lazy Future

Task – създаване

Task – композиране

Task – изпълнение

Task – създаване (прод.)

Task

Актьорски модел

Актьори

С други думи

Актьори – недетерминизъм

Akka

Актьорите като конкурентен примитив

Реактивност на `Future`

`Future` в Scala

Съществуваща стойност към `Future`

Асинхронен вход/изход чрез `Future`