Implementaciones de contadores: balance entre corrección y eficiencia

Contexto

Razonar sobre la corrección de un algoritmo concurrente es un desafío. Existen nociones de corrección que definen lo que es un comportamiento válido a partir de transformar una historia concurrente (con hilos ejecutándose al mismo tiempo) en una historia secuencial (como si ocurrieran uno tras otro) para analizar si el resultado tiene sentido.

Esta transformación sigue reglas que van de más a menos estrictas:

Linealizabilidad (Linearizability (M. P. Herlihy y Wing 1990)): Es el modelo más fuerte. Cada operación parece tener efecto de forma instantánea y atómica en un punto único en el tiempo real, ubicado estrictamente entre su invocación y su respuesta.
Consistencia Secuencial (Sequential Consistency (Lamport 1979)): Relaja el tiempo real. Exige que exista un orden global único de todas las operaciones que respete el orden de programa de cada hilo de forma individual.
Consistencia en la Inactividad (Quiescent Consistency (M. Herlihy y Shavit 2008)): No impone un orden estricto entre operaciones concurrentes superpuestas. Solo garantiza el orden a través de los periodos de inactividad: si la operación A termina antes de que la operación B comience (separadas por un instante donde nadie hace nada), A precederá a B.
Consistencia Eventual (Eventual Consistency (Vogels 2009)): El modelo más relajado. Si cesan las actualizaciones, todas las réplicas del sistema convergerán eventualmente al mismo estado. Tolera que diferentes hilos vean estados distintos temporalmente.

Los algoritmos concurrentes que garantizan linealizabilidad suelen imponer un cuello de botella único (como un candado global o una variable fuertemente sincronizada). Esto destruye la escalabilidad a medida que aumenta el número de hilos.

La solución propuesta en la literatura (Shavit 2011) para alcanzar el máximo rendimiento es relajar nuestras exigencias de corrección. Al pasar de estructuras linealizables a estructuras con consistencia quiescente o eventual, permitimos que las operaciones se "dispersen" en el espacio de memoria, evitando que los hilos choquen entre sí y maximizando la eficiencia.

En los sistemas distribuidos masivos, la consistencia fuerte no solo es ineficiente, sino matemáticamente imposible frente a particiones de red (Teorema CAP (Gilbert y Lynch 2002)). Por ejemplo, en contadores escalables a nivel global, los mensajes se atrasan, se pierden o se reordenan. Exigir linealizabilidad requeriría detener internet por cada incremento. Por ello, se adopta la Consistencia Eventual: un cliente puede incrementar su contador local inmediatamente, y el protocolo se encarga de reconciliar estos valores en segundo plano para que, eventualmente, el total sea preciso (Almeida y Baquero 2019).

Distintos Sabores de Contadores

A continuación, analizaremos tres implementaciones de contadores, desde la más estricta y lenta, hasta las más relajadas y rápidas.

Contador Linealizable

El enfoque clásico y seguro. Al delegar la operación al hardware subyacente mediante incrementAndGet(), garantizamos el nivel de corrección más alto.

import java.util.concurrent.atomic.AtomicLong;

public class LinearizableCounter {
    private final AtomicLong count = new AtomicLong(0);

    public void increment() {
        count.incrementAndGet(); 
    }

    public long fetch() {
        return count.get();
    }
}

¿Por qué es Linealizable?
Porque la instrucción incrementAndGet() se ejecuta a nivel de procesador como una operación indivisible. Si el Hilo A y el Hilo B llaman al método al mismo tiempo, el hardware formará una fila instantánea en tiempo real.

Ejemplo de ejecución: Si A llama al método a las 10:00:01 y B a las 10:00:02, es matemáticamente imposible que B no vea el incremento de A. Al cumplir con el tiempo real, cumple automáticamente con todas las consistencias inferiores (Secuencial, Quiescente, etc.). El costo de esto es la alta contención: si 1,000 hilos llaman a incrementAndGet(), 999 tendrán que esperar su turno.

—

Sloppy Counter (Consistencia Eventual)

Este contador asigna memoria privada a cada hilo (ThreadLocal) y solo vuelca los datos a la variable global cuando supera un umbral. Es ultrarrápido, pero sacrifica la frescura de los datos.

public class SloppyCounter {
    private final AtomicLong globalCount = new AtomicLong(0);
    private final int threshold = 100;
    private final ThreadLocal<Long> localCount = ThreadLocal.withInitial(() -> 0L);

    public void increment() {
        long current = localCount.get() + 1;
        if (current >= threshold) {
            globalCount.addAndGet(current);
            localCount.set(0L);
        } else {
            localCount.set(current);
        }
    }

    public long fetch() {
        return globalCount.get(); // Lectura aproximada (eventual)
    }
}

¿Por qué es Consistente Eventualmente?
Porque si todos los hilos dejaran de incrementar y forzaran un volcado de sus variables locales, todos verían el mismo valor final correcto.

¿Por qué NO alcanza la Consistencia Secuencial?
Para ser secuencialmente consistente, el sistema global debe respetar el orden de programa de cada hilo.

Ejemplo de ejecución que falla:

El Hilo A realiza 50 incrementos. (Su código local avanza).
El Hilo A cambia una variable compartida: bandera = true.
El Hilo B espera a ver la bandera. Ve bandera == true y procede a llamar a fetch().
El Hilo B lee 0 (porque A no alcanzó el umbral de 100 para volcar).

En una historia secuencial válida, si el Hilo B actuó después de ver la bandera del Hilo A, obligatoriamente debió ver los incrementos que A hizo antes de levantar la bandera. Como lee 0, se rompe el orden lógico.

—

Contador con Balanceador (Consistencia Quiescente)

El balanceador. Un balanceador (balancer) recibe tokens (hilos) y los manda alternadamente a una salida u otra: el 1.º va a la salida 0, el 2.º a la 1, el 3.º a la 0, etc. Se implementa con un toggle y una operación atómica de “leer y avanzar”. En quiescencia siempre se cumple \(y_0 = y_1\) o \(y_0 = y_1 + 1\) (step property), sin importar cuántos hilos pasaron ni en qué orden.

De balanceadores a contador. Si cada salida termina en un contador local \(i,\,i+w,\,i+2w,\dots\), la propiedad anterior hace que en quiescencia los valores repartidos sean exactamente \(\{0,\dots,n-1\}\). Con 3 balanceadores (raíz \(R\), hijos \(L\) y \(D\)) y 4 hojas, seis tokens que pasan uno tras otro:

Token	Raíz	Segundo nivel	Hoja	Valor devuelto
1	0 \(\to\) izq	\(L\): 0 \(\to\) izq	\(H_0\)	0
2	1 \(\to\) der	\(D\): 0 \(\to\) izq	\(H_2\)	1
3	2 \(\to\) izq	\(L\): 1 \(\to\) der	\(H_1\)	2
4	3 \(\to\) der	\(D\): 1 \(\to\) der	\(H_3\)	3
5	4 \(\to\) izq	\(L\): 2 \(\to\) izq	\(H_0\)	4
6	5 \(\to\) der	\(D\): 2 \(\to\) izq	\(H_2\)	5

Las hojas se numeran de izquierda a derecha (\(H_0,H_1,H_2,H_3\)), pero reciben tokens en el orden \(H_0,H_2,H_1,H_3\). Por eso cada hoja arranca en un valor distinto: \(H_0\!:0\), \(H_2\!:1\), \(H_1\!:2\), \(H_3\!:3\), y todas suman 4.

Versión simplificada (la que usaremos). Un solo balanceador de ancho 4:

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;

public class FourWireCounter {
    private final AtomicInteger toggle = new AtomicInteger(0); // balanceador
    private final AtomicLong[] wire = new AtomicLong[4];

    public FourWireCounter() {
        for (int i = 0; i < 4; i++) wire[i] = new AtomicLong(i);
    }

    public long getAndIncrement() {
        int w = toggle.getAndIncrement() & 3;  // paso 1: elegir hoja
        return wire[w].getAndAdd(4);           // paso 2: tomar valor de la hoja
    }
}

La hoja \(i\) reparte \(i,\,i+4,\,i+8,\dots\) Con 6 operaciones secuenciales se devuelve \(0,1,2,3,4,5\). Cada operación toca solo dos variables y no hay candados.

¿Por qué es Consistente en la Inactividad?

El toggle asigna a cada operación un número distinto, así que en quiescencia con \(n\) operaciones cada hoja repartió su parte y los valores devueltos son exactamente \(\{0,\dots,n-1\}\).

¿Por qué NO es Linealizable?

Ejecución con toggle en 0:

\(A\) obtiene toggle\(=0\) (hoja 0) y se pausa antes de tocar wire[0].
\(B\) obtiene hoja 1 y devuelve 1. Termina.
\(C\) obtiene hoja 2 y devuelve 2. Termina.
\(D\) obtiene hoja 3 y devuelve 3. Termina.
\(E\) empieza después de que \(B\) terminó, obtiene hoja 0 (wire[0] sigue en 0) y devuelve 0. Termina.
\(A\) se reanuda y devuelve 4.

\(B\) terminó antes de que \(E\) empezara, así que cualquier linealización pone a \(B\) antes que \(E\), y en un contador secuencial el primero recibe el valor menor. Pero \(B\) devolvió 1 y \(E\) devolvió 0. Contradicción.

Sí es QC: \(A\) está pendiente todo el tiempo, así que nunca hay inactividad entre \(B\) y \(E\) y pueden reordenarse. La historia secuencial \(E\!\to\!0,\ B\!\to\!1,\ C\!\to\!2,\ D\!\to\!3,\ A\!\to\!4\) es válida, y al final los valores son \(\{0,\dots,4\}\).

¿Por qué NO es Secuencialmente Consistente?

Con toggle en 0, el hilo \(Q\) hace una operación y devuelve 0. Después \(A\) obtiene hoja 1 y se pausa. \(Q\) hace dos más y devuelve 2 y 3. Ahora el hilo \(P\) hace dos operaciones seguidas: la primera cae en la hoja 0 y devuelve 4; la segunda cae en la hoja 1, que sigue en 1 porque \(A\) no ha avanzado, y devuelve 1. Al final \(A\) devuelve 5. En el orden de programa de \(P\) su primera operación precede a la segunda, pero en un contador secuencial 4 se entrega después de 1. Ningún orden global respeta esto.

Ejercicios

Instrucciones:

Entrega en un PDF las respuestas de los ejercicios teóricos. Para los que requieran código, añade una breve descripción de los programas entregados.
Solo un integrante del equipo debe subir la práctica. Los demás deben marcar la tarea como entregada y escribir un comentario privado con el nombre de quien entregó.
El formato y el medio de entrega los indicará tu ayudante de laboratorio.
Utilizar Java 21 LTS. Se penalizará si no compila en esta versión.

Tiempo estimado: \(\approx\) 1.5 hr
Puntaje total: 100

Ejercicio 1: El Sloppy Counter Modificado
Se sugiere hacer una pequeña modificación al SloppyCounter para "mejorar" su consistencia. Propone que siempre que un hilo llame al método fetch(), el código primero obligue a ese mismo hilo a volcar su localCount actual al globalCount, y recién entonces retorne el valor global.
```
public long fetch() {
        long currentLocal = localCount.get();
        if (currentLocal > 0) {
            globalCount.addAndGet(currentLocal);
            localCount.set(0L); 
        }
        return globalCount.get();
    }
```
Analiza este escenario con múltiples hilos trabajando. ¿Esta modificación hace que la estructura sea Linealizable, Secuencialmente Consistente o se mantiene Eventualmente Consistente? Argumenta tu respuesta detallando qué sucede con el estado local de los otros hilos que no llamaron a fetch().
Ejercicio 2: El Contador de Dos Hojas
Considera una versión reducida del contador con balanceador, con solo dos hojas. La hoja 0 reparte \(0,2,4,\dots\) y la hoja 1 reparte \(1,3,5,\dots\)
```
public class TwoWireCounter {
    private final AtomicInteger toggle = new AtomicInteger(0);
    private final AtomicLong[] wire = { new AtomicLong(0), new AtomicLong(1) };

    public long getAndIncrement() {
        int w = toggle.getAndIncrement() & 1;  // paso 1: elegir hoja
        return wire[w].getAndAdd(2);           // paso 2: tomar valor de la hoja
    }
}
```
1. No es Linealizable. Con tres hilos \(A\), \(B\) y \(C\), describe una ejecución en la que \(B\) termina antes de que \(C\) empiece, pero \(B\) devuelve un valor mayor que \(C\). Indica en cada paso el valor de toggle, la hoja elegida y el valor que devuelve cada hilo. Explica por qué ninguna historia secuencial que respete el tiempo real puede producir esos valores.
2. Sí es Consistente en la Inactividad. Para la ejecución del inciso (a):
  - Explica por qué no hay un periodo de inactividad entre \(B\) y \(C\).
  - Da una historia secuencial válida de un contador que produzca los mismos valores.
  - Argumenta en general por qué, cuando todas las operaciones terminan, los valores devueltos son exactamente \(\{0,\dots,n-1\}\).
3. Cambiando el balanceador (análisis). Se propone ahorrar la operación atómica del balanceador y escribirlo como una variable volatile int toggle, con int w = toggle++ & 1;. Antes de programar nada, analiza:
  - ¿Qué pasos componen toggle++? Con dos hilos que ejecutan una operación cada uno, ¿puedes construir una ejecución en la que los valores devueltos al terminar no sean \(\{0,1\}\)?
  - Según tu análisis, ¿se mantiene la unicidad de los valores devueltos? ¿Se mantiene la Consistencia en la Inactividad?
4. Cambiando el balanceador (experimento). Implementa la variante del inciso (c) y pruébala:
  - Lanza varios hilos que ejecuten muchas veces getAndIncrement() y guarda todos los valores devueltos.
  - Cuando todos los hilos terminen (join), hay inactividad. Verifica si los valores son exactamente \(\{0,\dots,n-1\}\): cuenta cuántos valores se repiten y cuáles faltan.
  - Repite el experimento varias veces (con distinto número de hilos y de operaciones) y reporta los resultados en una tabla.
  - Haz lo mismo con la versión original (con AtomicInteger) y compara.
  Responde: de acuerdo con tu análisis y con tus resultados, ¿la variante sigue siendo consistente en la inactividad? Si en alguna corrida no observaste ningún error, ¿eso demuestra que la variante es correcta? Justifica.

Almeida, Paulo Sérgio, y Carlos Baquero. 2019. «Scalable eventually consistent counters over unreliable networks». Distrib. Comput. 32 (1): 69-89. https://doi.org/10.1007/s00446-017-0322-2.

Gilbert, Seth, y Nancy Lynch. 2002. «Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services». SIGACT News 33 (2): 51-59. https://doi.org/10.1145/564585.564601.

Herlihy, Maurice P., y Jeannette M. Wing. 1990. «Linearizability: a correctness condition for concurrent objects». ACM Trans. Program. Lang. Syst. 12 (3): 463-92. https://doi.org/10.1145/78969.78972.

Herlihy, Maurice, y Nir Shavit. 2008. The Art of Multiprocessor Programming. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.

Lamport. 1979. «How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs». IEEE Transactions on Computers C-28 (9): 690-91. https://doi.org/10.1109/TC.1979.1675439.

Shavit, Nir. 2011. «Data Structures in the Multicore Age». Commun. ACM 54 (3): 76-84. https://doi.org/10.1145/1897852.1897873.

Vogels, Werner. 2009. «Eventually consistent». Commun. ACM 52 (1): 40-44. https://doi.org/10.1145/1435417.1435432.

← Volver al índice de prácticas