Esclarecimento sobre a importância da imutabilidade do estado dentro de um MVar no contexto de concorrência

Marlow está contrastando a abordagem Haskell de dados imutáveis ​​com linguagens que permitem que todas as estruturas de dados sejam mutadas.

Em uma linguagem como Java ou JavaScript, não seria suficiente bloquear apenas a variável que contém o Map, pois pode haver outra thread que o tenha obtido Mape o esteja modificando. Portanto, você precisaria bloquear toda a estrutura enquanto estivesse acessando-a.

Em Haskell, já sabemos que o Mapé imutável. Qualquer coisa que queira pegar o Mape modificá-lo deve criar um novo valor. Portanto, precisamos bloquear apenas o MVarque contém o Map, e não o todo Map(embora, se você planeja escrever o mapa modificado de volta no original MVar, precisa manter um bloqueio para toda a operação).

A parte sobre estruturas "sem bloqueio" é explicada com mais detalhes neste artigo da Wikipédia . Resumidamente, é praticamente possível criar uma árvore ordenada na qual várias threads podem alterar o conteúdo sem que nada dê errado. Mas a definição e a comprovação de tais estruturas são magia profunda , não algo a ser tentado durante o desenvolvimento normal.

Aqui está um exemplo completo que pode ajudar a ilustrar o problema. Tenho certeza de que você entenderá se eu não quiser escrever uma implementação completa de mapa mutável para responder a essa pergunta, mas considere o seguinte mapa mutável simplificado, capaz de armazenar apenas um par chave-valor. Ele suporta as operações "new", "lookup" e "replace". (Chamei-o de "replace" em vez de "insert" porque o mapa só pode armazenar um par chave-valor, então a entrada anterior se perde quando um novo é inserido.)

data MMap k v = MMap (IORef k) (IORef v)

mmapNew :: k -> v -> IO (MMap k v)
mmapNew k v = MMap <$> newIORef k <*> newIORef v

mmapReplace :: k -> v -> MMap k v -> IO ()
mmapReplace k v (MMap k_ v_) = do
  writeIORef k_ k
  writeIORef v_ v

mmapLookup :: (Eq k) => k -> MMap k v -> IO (Maybe v)
mmapLookup k (MMap k'_ v_) = do
  k' <- readIORef k'_
  if k == k'
    then Just <$> readIORef v_
    else pure Nothing

Agora, suponha que queremos escrever uma interface concorrente e segura para threads para uma lista telefônica usando esta estrutura de dados mutável. O código revisado lookupé mais ou menos o mesmo que o original:

type Name = String
type PhoneNumber = String
type PhoneBook = MMap Name PhoneNumber
newtype PhoneBookState = PhoneBookState (MVar PhoneBook)

lookup :: PhoneBookState -> Name -> IO (Maybe PhoneNumber)
lookup (PhoneBookState m) name = do
  book <- takeMVar m
  putMVar m book
  mmapLookup name book   -- no `return`, because this is an IO operation

onde realizamos o real mmapLookupapós desbloquear o estado.

O código API correspondente para newe replaceprovavelmente seria algo como isto:

new :: Name -> PhoneNumber -> IO PhoneBookState
new name number = do
  book <- mmapNew name number
  PhoneBookState <$> newMVar book

replace :: PhoneBookState -> Name -> PhoneNumber -> IO ()
replace (PhoneBookState m) name number = do
  book <- takeMVar m
  mmapReplace name number book
  putMVar m book

Observe que, diferentemente de lookup, adotamos uma abordagem conservadora com replace, mantendo o bloqueio durante toda a operação de substituição.

No entanto, esta implementação tem uma condição de corrida para o par lookup/ replace. Para entender o porquê, vamos adicionar um atraso a mmapLookup:

mmapLookup :: (Eq k) => k -> MMap k v -> IO (Maybe v)
mmapLookup k (MMap k'_ v_) = do
  k' <- readIORef k'_
  threadDelay 2000000
  if k == k'
    then Just <$> readIORef v_
    else pure Nothing

e considere a seguinte mainfunção, que cria uma lista telefônica para o número de telefone de "Alice" e então inicia dois threads — um para procurar "Alice" e outro para substituir a entrada pelo número de "Bob":

main = do
  pbs <- new "Alice" "555-1234"
  forkIO $ do
    aliceno <- lookup pbs "Alice"
    putStrLn $ "Alice's number is " ++ show aliceno
  threadDelay 1000000
  forkIO $ replace pbs "Bob" "555-9876"
  threadDelay 5000000
  putStrLn "Done!"

Quando este programa é executado, ele recupera incorretamente o número de Bob na pesquisa de Alice:

Alice's number is Just "555-9876"
Done!

Obviamente, o problema é que a operação de substituição ocorre entre a comparação das chaves e a recuperação do valor.

Se você modificar lookuppara liberar o bloqueio somente após a conclusão da pesquisa:

lookup :: PhoneBookState -> Name -> IO (Maybe PhoneNumber)
lookup (PhoneBookState m) name = do
  book <- takeMVar m
  number <- mmapLookup name book
  putMVar m book
  return number

então não haverá condição de corrida. Não importa como você intercale as operações (e não importa quão cuidadosamente você coloque os atrasos), você recuperará o número de Alice Just "555-1234"da lista telefônica original ou não conseguirá recuperar o número de Alice e retornará Nothingda lista telefônica revisada (onde ele foi substituído pelo número de Bob).

Então, para um mutável MMap, temos que manter o bloqueio em torno da mmapLookupoperação para operar com segurança na estrutura de dados sem permitir que outros threads modifiquem a estrutura de dados sem que precisemos fazer nada enquanto estivermos executando o lookup.

Em contraste, se usássemos uma estrutura de dados imutável análoga:

data IMap k v = IMap k v

imapNew :: k -> v -> IMap k v
imapNew k v = IMap k v

imapReplace :: k -> v -> IMap k v -> IMap k v
imapReplace k v _ = IMap k v

imapLookup :: (Eq k) => k -> IMap k v -> Maybe v
imapLookup k (IMap k' v) | k == k' = Just v
                         | otherwise = Nothing


type Name = String
type PhoneNumber = String
type PhoneBook = IMap Name PhoneNumber
newtype PhoneBookState = PhoneBookState (MVar PhoneBook)

então as implementações correspondentes de new, lookup, e replaceseriam:

new :: Name -> PhoneNumber -> IO PhoneBookState
new name number = PhoneBookState <$> newMVar (imapNew name number)

lookup :: PhoneBookState -> Name -> IO (Maybe PhoneNumber)
lookup (PhoneBookState m) name = do
  book <- takeMVar m
  putMVar m book
  return $ imapLookup name book

replace :: PhoneBookState -> Name -> PhoneNumber -> IO ()
replace (PhoneBookState m) name number = do
  book <- takeMVar m
  let book' = imapReplace name number book
  putMVar m book'

Fundamentalmente, quando replacese retira bookdo MVar, que pode muito bem ser o mesmo bookacessado simultaneamente pela imapLookupchamada em lookup, ele não sofre mutação, bookmas cria um novo book'por meio da imapReplacechamada sem afetar o original book. Esta é a essência das estruturas de dados imutáveis, e é por isso que a imapLookupoperação pode continuar a ser executada com segurança no inalterado, bookmesmo ao replacecriar um novo book'e gravá-lo de volta no vago MVar.

Mesmo se fizéssemos um esforço para reescrever imapLookupcomo uma IOoperação com ampla oportunidade para outro thread ser executado entre o acesso de chave e valor:

imapLookup :: (Eq k) => k -> IMap k v -> IO (Maybe v)
imapLookup k m = do
  k' <- evaluate $ (\(IMap k v) -> k) m    -- force retrieval of the key
  threadDelay 1000000                      -- allow another thread to run
  v' <- evaluate $ (\(IMap k v) -> v) m    -- fetch the value
  pure $ if k == k' then Just v' else Nothing

ainda assim não dispararíamos uma condição de corrida, porque o book :: IMap k vobjeto acessado imapLookup name booké imutável, independentemente de como ele está sendo acessado em outras threads.

Aqui está o exemplo completo ilustrando a condição de corrida com uma MMapestrutura mutável:

import Prelude hiding (lookup)
import Data.IORef
import Control.Concurrent

data MMap k v = MMap (IORef k) (IORef v)

mmapNew :: k -> v -> IO (MMap k v)
mmapNew k v = MMap <$> newIORef k <*> newIORef v

mmapReplace :: k -> v -> MMap k v -> IO ()
mmapReplace k v (MMap k_ v_) = do
  writeIORef k_ k
  writeIORef v_ v

mmapLookup :: (Eq k) => k -> MMap k v -> IO (Maybe v)
mmapLookup k (MMap k'_ v_) = do
  k' <- readIORef k'_
  threadDelay 2000000  -- allow another thread to do mischief
  if k == k'
    then Just <$> readIORef v_
    else pure Nothing

type Name = String
type PhoneNumber = String
type PhoneBook = MMap Name PhoneNumber
newtype PhoneBookState = PhoneBookState (MVar PhoneBook)

new :: Name -> PhoneNumber -> IO PhoneBookState
new name number = do
  book <- mmapNew name number
  PhoneBookState <$> newMVar book

lookup :: PhoneBookState -> Name -> IO (Maybe PhoneNumber)
lookup (PhoneBookState m) name = do
  book <- takeMVar m
  putMVar m book
  mmapLookup name book

replace :: PhoneBookState -> Name -> PhoneNumber -> IO ()
replace (PhoneBookState m) name number = do
  book <- takeMVar m
  mmapReplace name number book
  putMVar m book

main = do
  pbs <- new "Alice" "555-1234"
  forkIO $ do
    aliceno <- lookup pbs "Alice"
    putStrLn $ "Alice's number is " ++ show aliceno
  threadDelay 1000000
  forkIO $ replace pbs "Bob" "555-9876"
  threadDelay 2000000  -- wait for children to finish
  putStrLn "Done!"

e a versão imutável sem a condição de corrida:

module ImmutableMap where

import qualified Data.Map as Map
import Prelude hiding (lookup)
import Control.Concurrent
import Control.Exception

data IMap k v = IMap k v

imapNew :: k -> v -> IMap k v
imapNew k v = IMap k v

imapReplace :: k -> v -> IMap k v -> IMap k v
imapReplace k v _ = IMap k v

imapLookup :: (Eq k) => k -> IMap k v -> IO (Maybe v)
imapLookup k m = do
  k' <- evaluate $ (\(IMap k v) -> k) m    -- force retrieval of the key
  threadDelay 1000000                      -- allow another thread to run
  v' <- evaluate $ (\(IMap k v) -> v) m    -- fetch the value
  pure $ if k == k' then Just v' else Nothing

type Name = String
type PhoneNumber = String
type PhoneBook = IMap Name PhoneNumber
newtype PhoneBookState = PhoneBookState (MVar PhoneBook)

new :: Name -> PhoneNumber -> IO PhoneBookState
new name number = PhoneBookState <$> newMVar (imapNew name number)

lookup :: PhoneBookState -> Name -> IO (Maybe PhoneNumber)
lookup (PhoneBookState m) name = do
  book <- takeMVar m
  putMVar m book
  imapLookup name book

replace :: PhoneBookState -> Name -> PhoneNumber -> IO ()
replace (PhoneBookState m) name number = do
  book <- takeMVar m
  let book' = imapReplace name number book
  putMVar m book'

main = do
  pbs <- new "Alice" "555-1234"
  forkIO $ do
    aliceno <- lookup pbs "Alice"
    putStrLn $ "Alice's number is " ++ show aliceno
  threadDelay 1000000
  forkIO $ replace pbs "Bob" "555-9876"
  threadDelay 2000000  -- wait for children to finish
  putStrLn "Done!"