haskell - Memoria transaccional del software-Ejemplo de composibilidad

clojure transactional-memory

Question

Una de las principales ventajas de la memoria transaccional de software que siempre se menciona es la composabilidad y la modularidad. Se pueden combinar diferentes fragmentos para producir componentes más grandes. En programas basados ​​en bloqueo, a menudo este no es el caso.

Estoy buscando un ejemplo simple que ilustre esto con código real. Preferiría un ejemplo en Clojure, pero Haskell también está bien. Puntos de bonificación si el ejemplo también muestra algún código basado en bloqueo que no se puede componer fácilmente.

Answer 1

Aquí hay un ejemplo de Clojure:

Supongamos que tiene un vector de cuentas bancarias (en la vida real, el vector puede ser algo más largo ...):

(def accounts 
 [(ref 0) 
  (ref 10) 
  (ref 20) 
  (ref 30)])

(map deref accounts)
=> (0 10 20 30)

Y una función de "transferencia" que transfiere con seguridad una cantidad entre dos cuentas en una sola transacción:

(defn transfer [src-account dest-account amount]
  (dosync
    (alter dest-account + amount)
    (alter src-account - amount)))

Que funciona de la siguiente manera:

(transfer (accounts 1) (accounts 0) 5)

(map deref accounts)
=> (5 5 20 30)

Luego puede componer fácilmente la función de transferencia para crear una transacción de nivel superior, por ejemplo, transferir desde varias cuentas:

(defn transfer-from-all [src-accounts dest-account amount]
  (dosync
    (doseq [src src-accounts] 
      (transfer src dest-account amount))))

(transfer-from-all 
  [(accounts 0) (accounts 1) (accounts 2)] 
  (accounts 3) 
  5)

(map deref accounts)
=> (0 0 15 45)

Tenga en cuenta que todas las transferencias múltiples ocurrieron en una sola transacción combinada, es decir, fue posible "componer" las transacciones más pequeñas.

Hacer esto con los bloqueos se complicaría muy rápidamente: suponiendo que las cuentas debían estar bloqueadas individualmente, entonces tendría que hacer algo como establecer un protocolo en el orden de adquisición del bloqueo para evitar puntos muertos. Como Jon señala correctamente, puede hacer esto en algunos casos ordenando todos los bloqueos en el sistema, pero en la mayoría de los sistemas complejos esto no es factible. Es muy fácil cometer un error difícil de detectar. STM te salva de todo este dolor.

Answer 2

Un ejemplo donde los bloqueos no se componen en Java:

class Account{
  float balance;
  synchronized void deposit(float amt){
    balance += amt;
  }
  synchronized void withdraw(float amt){
    if(balance < amt)
      throw new OutOfMoneyError();
    balance -= amt;
  }
  synchronized void transfer(Account other, float amt){
    other.withdraw(amt);
    this.deposit(amt);
  }
}

Entonces, el depósito está bien, el retiro está bien, pero la transferencia no está bien: si A comienza una transferencia a B cuando B comienza una transferencia a A, podemos tener una situación de interbloqueo.

Ahora en Haskell STM:

withdraw :: TVar Int -> Int -> STM ()
withdraw acc n = do bal <- readTVar acc
                    if bal < n then retry
                    writeTVar acc (bal-n)

deposit :: TVar Int -> Int -> STM ()
deposit acc n = do bal <- readTVar acc
                   writeTVar acc (bal+n)

transfer :: TVar Int -> TVar Int -> Int -> STM ()
transfer from to n = do withdraw from n
                        deposit to n

Dado que no hay un bloqueo explícito, withdraw y deposit componer naturalmente en la transfer . La semántica sigue asegurando que si la retirada falla, la transferencia completa falla. También garantiza que el retiro y el depósito se realizarán de forma atómica, ya que el sistema de tipo garantiza que no se pueda realizar una transferencia externa desde una atomically .

atomically :: STM a -> IO a

Este ejemplo proviene de esto: http://cseweb.ucsd.edu/classes/wi11/cse230/static/lec-stm-2x2.pdf Adaptado de este documento, es posible que desee leer: http://research.microsoft.com/pubs/74063/beautiful.pdf

Answer 3

Una traducción del ejemplo de Ptival a Clojure:

;; (def example-account (ref {:amount 100}))

(defn- transact [account f amount]
  (dosync (alter account update-in [:amount] f amount)))

(defn debit [account amount] (transact account - amount))
(defn credit [account amount] (transact account + amount))
(defn transfer [account-1 account-2 amount]
  (dosync
    (debit account-1 amount)
    (credit account-2 amount)))

Por lo tanto, el debit y el credit están bien para llamar por su cuenta, y al igual que la versión de Haskell, las transacciones se anidan, por lo que toda la operación de transfer es atómica, los reintentos se realizarán en colisiones de compromiso, podría agregar validadores para la consistencia, etc.

Y, por supuesto, la semántica es tal que nunca se bloquearán.

Answer 4

Y para hacer que el ejemplo de trprcolin sea aún más idiomático, sugeriría cambiar el orden de los parámetros en la función de transacción y hacer que las definiciones de débito y crédito sean más compactas.

(defn- transact [f account amount]
    ....  )

(def debit  (partial transact -))
(def credit (partial transact +))