[Esta postagem também aparece em Blog do Dustin no github].
Isso é algo que surge de vez em quando 
enquanto isso. Normalmente, descrevo um meio de fazer isso que acho que faz sentido, mas acho que nunca o descrevi bastante bem o suficiente. As pessoas tendem a achar que é complicado, lento ou coisas do gênero. Vou tentar resolver esse problema aqui.
Restrições
Para que seja útil para aplicativos suficientes, trabalharemos com as seguintes premissas:
- deve minimizar as viagens de ida e volta para os servidores
- O(1) add (tanto para o tamanho atual quanto para os novos itens que estão chegando)
- O(1) remove (tanto para o tamanho atual quanto para os itens que estão sendo removidos)
- O(1) busca
- lock and wait free
- Fácil de usar
- fácil de entender
- sem necessidade de manutenção explícita
E, é claro, tem que ser em escala web!
Ingredientes
O conceito é simples e faz uso de três operações do memcached com garantias de atomicidade.
Um índice é criado com adicionar. Isso deve ser bastante óbvio.
Sempre que precisarmos adicionar ou remover itens, usaremos anexar. Para que isso funcione, precisamos codificar os itens de forma que eles representem itens positivos ou negativos. Criei um exemplo simples de codificação de +chave para representar a adição de chave para o conjunto e -chave para representar a remoção de chave do conjunto. Em seguida, uso espaços para separar vários itens.
Exemplo: +a +b +c -b representa {a, c}. A sequência é, obviamente, importante.
Um conjunto com membros que entram e saem com frequência suficiente pode precisar ser compactado. Para isso, recodificamos o conjunto e usamos cas para garantir que possamos adicioná-lo de volta sem pisar em outro cliente.
Me acompanhe até o fim
Estou usando python para este exemplo. O ideal é que isso seja implementado em seu cliente e tudo esteja pronto para funcionar.
Primeiro, precisamos de codificadores e decodificadores. Essa é, na verdade, a parte mais difícil e é realmente trivial quando se trata disso.
O codificador
Começamos com a representação mais básica dos dados em nossos conjuntos.
def encodeSet(chaves, op=‘+’):
"""Codifique um conjunto de chaves para modificar o conjunto.
>>> encodeSet(['a', 'b', 'c'])
'+a +b +c '
“””
retorno ”.unir-se(op + k + ‘ ‘ para k em chaves)
Isso é mais documentação do que código, mas é bastante claro. Se, em vez disso, você quiser um conjunto de JPEGs, poderá criar uma codificação binária simples com um comprimento e um corpo em vez de separá-los por espaços em branco.
Modificação de um conjunto
A modificação é somente de acréscimo, sendo que a única diferença entre adicionar e remover é uma operação de codificação. Isso é útil porque podemos escrever o mesmo código para ambos os casos.
def modificar(mc, indexName, op, chaves):
codificado = encodeSet(chaves, op)
tentar:
mc.anexar(indexName, codificado)
exceto KeyError:
# Se não pudermos acrescentar, e estivermos adicionando ao conjunto,
# estamos tentando criar o índice, portanto, faça isso.
se op == ‘+’:
mc.adicionar(indexName, codificado)
def adicionar(mc, indexName, *chaves):
"""Adicione as chaves fornecidas ao conjunto fornecido."""
modificar(mc, indexName, ‘+’, chaves)
def remover(mc, indexName, *chaves):
"""Remove as chaves fornecidas do conjunto fornecido."""
modificar(mc, indexName, ‘-‘, chaves)
Eu permito um efeito colateral de adicionar para criar o índice, caso ele não exista.
Em um aplicativo real, há uma chance diferente de zero de que o anexar falharia porque o item está faltando e o item imediatamente subsequente adicionar falharia devido a uma condição de corrida. Não escrevi o código para cobrir isso aqui, mas é bem simples. Se isso for importante para você, basta repetir todo o método modify até que ambos falhem. Você teria que estar tentando fazer com que ele falhasse mais de uma vez.
O decodificador
Para usar os dados, precisaremos decodificá-los, portanto, vamos criar um decodificador rápido que possa reverter o que o codificador acima faz (incluindo os acréscimos para adicionar e remover).
def decodeSet(dados):
"""Decodifique um item do cache em um conjunto impl.
Retorna um indicador de sujeira (dica de compactação) e o conjunto
>>> decodeSet('+a +b +c -b -x')
(2, set(['a', 'c']))
“””
chaves = definir()
sujeira = 0
para k em dados.dividir():
op, chave = k[0], k[1:]
se op == ‘+’:
chaves.adicionar(chave)
elif op == ‘-‘:
chaves.descartar(chave)
sujeira += 1
retorno sujeira, chaves
Essa é a parte mais complicada.
Recuperação dos itens
Agora que podemos codificar, definir e modificar nossos dados, a recuperação deve ser bastante trivial. Uma passagem básica seria assim:
def itens(mc, indexName):
"""Recupere os valores atuais do conjunto."""
bandeiras, cas, dados = mc.obter(indexName)
sujeira, chaves = decodeSet(dados)
retorno chaves
É basicamente isso. No entanto, este é um bom momento para fazer a compactação. sujeira acima mede a quantidade de fichas de remoção existentes no conjunto. Se houver muitos, queremos eliminá-los.
Imagine um LIMITE DE SUJEIRA conjunto de números que decide onde queremos fazer a autocompactação. Se tivermos mais sujeira do que isso, compactaremos na recuperação (transformando um único get em um único get e um único CAS.
Para esse caso de uso, não nos importamos se o CAS é bem-sucedido na maioria das vezes, portanto, simplesmente disparamos e esquecemos. É seguro (ou seja, não destrói nenhum dado), mas não é garantido que funcione.
Então, aqui está uma modificação itens função de compactação condicional:
def itens(mc, indexName, forceCompaction=Falso):
"""Recupere os valores atuais do conjunto.
Isso pode acionar uma compactação se você solicitar ou se a codificação for
muito sujo."""
bandeiras, casid, dados = mc.obter(indexName)
sujeira, chaves = decodeSet(dados)
se forceCompaction ou sujeira > DIRTINESS_THRESHOLD:
compactado = encodeSet(chaves)
mc.cas(indexName, casid, compactado)
retorno chaves
E terminamos.
Em resumo
Na pior das hipóteses, adicionar ao conjunto: 2 viagens de ida e volta (quando o conjunto não existe e precisa ser criado, mas não precisamos saber disso).
Adicionar normal ao conjunto: 1 ida e volta, independentemente do número de membros que estão sendo adicionados. (Você nem precisa recuperar o valor atual para adicionar ou remover corretamente itens em massa, muito menos transferir tudo de volta).
Recuperação na pior das hipóteses: 2 viagens de ida e volta (quando a compactação é um efeito colateral).
Recuperação normal: 1 viagem de ida e volta (basta buscar a única chave).
Advertências
Embora o número de conjuntos seja praticamente ilimitado, há um tamanho prático de um único conjunto com essa implementação. Seria trivial "fragmentar" o conjunto em várias chaves (portanto, em vários servidores) se fosse necessário ter conjuntos muito grandes (mais de, digamos, 4.000 itens de 250 bytes).
Como a compactação é feita na leitura nessa implementação, um caso em que você esteja modificando muito, mas lendo raramente, pode não ser perfeito para esse código. Nesse caso, eu começaria a compactar em gravações aleatórias (fazendo com que, na pior das hipóteses, a adição/remoção leve cerca de três saltos, onde, de outra forma, seria um).
