[Este post también aparece en Blog de Dustin en github].
Esto es algo que surge de vez en cuando. 
mientras. Suelo describir una forma de hacerlo que creo que tiene sentido, pero creo que nunca la he descrito muy lo suficientemente bien. La gente tiende a pensar que es complicado o lento o cosas así. Voy a intentar resolver ese problema aquí.
Restricciones
Para que sea útil para bastantes aplicaciones, vamos a trabajar con los siguientes supuestos:
- debe minimizar los viajes de ida y vuelta a los servidores
- O(1) añadir (tanto para el tamaño actual como para los nuevos artículos que lleguen)
- O(1) eliminar (tanto para el tamaño actual como para los elementos que se eliminan)
- Búsqueda O(1)
- bloquear y esperar gratis
- fácil de usar
- fácil de entender
- no requiere mantenimiento explícito
Y, por supuesto, ¡tiene que ser a escala web!
Ingredientes
El concepto es sencillo y hace uso de tres operaciones de memcached con garantías de atomicidad.
Se crea un índice con añada. Esto debería ser bastante obvio.
Siempre que necesitemos añadir o eliminar elementos, utilizaremos añadir. Para que esto funcione, tenemos que codificar los elementos de forma que representen elementos positivos o negativos. He creado un ejemplo sencillo de codificación de +clave para representar la suma de clave al conjunto y -clave para representar la eliminación de clave del conjunto. A continuación, utilizo espacios para separar varios elementos.
Por ejemplo: +a +b +c -b representa {a, c}. La secuencia es, por supuesto, importante.
Un conjunto cuyos miembros entran y salen con bastante frecuencia puede necesitar ser compactado. Para ello, recodificamos el conjunto y utilizamos cas para asegurarnos de que podemos volver a añadirlo sin pisar a otro cliente.
Acompáñame
Estoy usando python para este ejemplo. Idealmente esto se implementa en su cliente y todo está bien para ir.
En primer lugar, necesitamos codificadores y decodificadores. En realidad, esta es la parte difícil y, a la hora de la verdad, es trivial.
El codificador
Empezamos con la representación más básica de los datos dentro de nuestros conjuntos.
def encodeSet(llaves, op=‘+’):
"""Codificar un conjunto de claves para modificar el conjunto.
>>> encodeSet(['a', 'b', 'c'])
'+a +b +c '
“””
devolver ”.únase a(op + k + ‘ ‘ para k en llaves)
Esto es más documentación que código, pero está bastante claro. Si en lugar de esto quieres un conjunto de JPEGs, podrías crear una simple codificación binaria con una longitud y un cuerpo en lugar de tenerlo separado por espacios en blanco.
Modificar un conjunto
La modificación es sólo añadir, con la única diferencia entre añadir y eliminar una operación de codificación. Esto es útil porque podemos escribir el mismo código para ambos casos.
def modificar(mc, indexName, op, llaves):
codificado = encodeSet(llaves, op)
pruebe:
mc.añadir(indexName, codificado)
excepto KeyError:
# Si no podemos añadir, y estamos añadiendo al conjunto,
# estamos tratando de crear el índice, por lo que hacer eso.
si op == ‘+’:
mc.añada(indexName, codificado)
def añada(mc, indexName, *llaves):
"""Añade las claves dadas al conjunto dado."""
modificar(mc, indexName, ‘+’, llaves)
def eliminar(mc, indexName, *llaves):
"""Eliminar las claves dadas del conjunto dado."""
modificar(mc, indexName, ‘-‘, llaves)
Permito un efecto secundario de añada para crear el índice si no existe.
En una aplicación real, hay una probabilidad no nula de que el añadir fallaría porque falta el elemento y el inmediatamente posterior añada fallaría debido a una condición de carrera. No escribí el código para cubrir eso aquí, pero es bastante simple. Si te importa, simplemente repite todo el método modify hasta que ambos fallen. Tendrías que estar intentando que fallara más de una vez.
El descodificador
Para poder utilizar los datos, vamos a necesitar decodificarlos, así que vamos a montar un decodificador rápido que pueda invertir lo que hace el codificador anterior (incluyendo los anexos para añadir y eliminar).
def decodeSet(datos):
"""Decodificar un elemento de la caché en un conjunto impl.
Devuelve un indicador de suciedad (pista de compactación) y el conjunto
>>> decodeSet('+a +b +c -b -x')
(2, set(['a', 'c']))
“””
llaves = configure()
suciedad = 0
para k en datos.dividir():
op, clave = k[0], k[1:]
si op == ‘+’:
llaves.añada(clave)
elif op == ‘-‘:
llaves.descarte(clave)
suciedad += 1
devolver suciedad, llaves
Esta es la parte más complicada.
Recuperar los artículos
Ahora que podemos codificar, establecer y modificar nuestros datos, la recuperación debería ser bastante trivial. Un pase básico se vería así:
def artículos(mc, indexName):
"""Recuperar los valores actuales del conjunto."""
banderas, cas, datos = mc.consiga(indexName)
suciedad, llaves = decodeSet(datos)
devolver llaves
Eso es todo. Sin embargo, este es un buen momento para hacer la compactación. suciedad mide cuántas fichas de eliminación hay en el conjunto. Si hay demasiados, queremos eliminarlos.
Imagina un UMBRAL_SUCIEDAD que decide dónde queremos hacer la autocompactación. Si tenemos más suciedad que esto, compactamos al recuperar (convirtiendo un único get en un único get y un único CAS.
Para este caso de uso, en realidad no nos importa si el CAS tiene éxito la mayoría de las veces, así que disparamos y nos olvidamos. Es seguro (es decir, no destruirá ningún dato), pero no se garantiza que funcione.
He aquí una modificación artículos función de compactación condicional:
def artículos(mc, indexName, forceCompaction=Falso):
"""Recuperar los valores actuales del conjunto.
Esto puede desencadenar una compactación si se lo pides o la codificación es
demasiado sucio."""
banderas, casid, datos = mc.consiga(indexName)
suciedad, llaves = decodeSet(datos)
si forceCompaction o suciedad > UMBRAL_SUCIEDAD:
compactado = encodeSet(llaves)
mc.cas(indexName, casid, compactado)
devolver llaves
Y hemos terminado.
En resumen
En el peor de los casos, añadir al conjunto: 2 viajes de ida y vuelta (cuando el conjunto no existe y hay que crearlo, pero no tenemos por qué saberlo).
Normal añadir a set: 1 ida y vuelta independientemente del número de miembros que se añadan. (Ni siquiera es necesario recuperar el valor actual para añadir o eliminar correctamente elementos en bloque, y mucho menos transferirlo todo de vuelta).
Recuperación en el peor de los casos2 viajes de ida y vuelta (cuando la compactación es un efecto secundario).
Recuperación normal: 1 viaje de ida y vuelta (sólo hay que coger una llave).
Advertencias
Aunque el número de conjuntos es prácticamente ilimitado, hay un tamaño práctico para un solo conjunto con esta implementación. Sería trivial "fragmentar" el conjunto en varias claves (y por tanto en varios servidores) si se necesitaran conjuntos muy grandes (más de, digamos, 4.000 elementos de 250 bytes).
Dado que la compactación se realiza en la lectura en esta implementación, un caso en el que usted está modificando muy pesadamente, pero la lectura rara vez podría no ser un perfecto para este código. En ese caso, yo empezaría a compactar en escrituras aleatorias (haciendo que en el peor de los casos añadir/eliminar lleve unos tres saltos donde de otro modo hubiera sido uno).
