Murmurhash -criando um rollout progressivo via backend

Ao ler o ttulo deste post o desenvolvedor mais experiente provavelmente vai se perguntar: "Mas j no existem vrias formas de se liberar uma nova funcionalidade para usurios progressivamente ?"

E a resposta sim, de fato existem algumas maneiras.
Por exemplo, se voc estiver em um ambiente com k8s e istio pode por exemplo usar um Virtual Service para isso, voc ainda pode fazer isso fora mesmo do k8s com um simples proxy reverso na frente de instncias diferentes da sua aplicao (uma com a nova feature, e outra sem) alm de vrias outras.

Porem aqui neste artigo, vou lhe apresentar uma forma de atingir o mesmo objetivo usando um algoritmo de hash bem conhecido, o Murmurhash que pode ser bem til dependendo do seu cenrio.

Murmurhash

O murmurhash um algoritmo de hash no criptogrfico.

Ser um algoritmo de hash significa que dado um input ele converte isso para um output encriptado.
Quer um exemplo simples no nosso dia a dia ?
Se voc estiver em um linux ou mac pode usar o sha256 da seguinte maneira:

echo -n teste de mensagem sha256 | shasum -a 2568785c54a5c506d0c4f031a76b7170c35b2bde862a2bbd7ab2d0485570b75bc06

J a parte do no criptogrfico se refere ao fato de muitas funes hash terem como principal caracterstica tornar impossvel a reverso da sada de volta no texto original, o que especialmente til se voc estiver trabalhando com segurana onde isto uma premissa. Este no o caso do murmurhash que no se preocupa tanto com esta caracterstica em detrimento de outras.

Ao contrrio da famlia de algoritmos criptogrficos, o murmurhash foi criado para ser rpido devido a sua otimizao, com uma boa resistncia a colises e outras caractersticas interessantes.
O algoritmo Murmurhash foi criado por Austin Appleby e a implementao de referncia em C++ pode ser encontrada no github.

Para demonstrar um pouco do que o algoritmo pode fazer, vamos olhar um simples cdigo em java:

    public static void main(String[] args) {        String input = "hebert freitas";        byte[] inputBytes = input.getBytes(Charset.forName("UTF8"));        HashCode hashCode = Hashing.murmur3_128().hashBytes(inputBytes);        byte[] outputBytes = hashCode.asBytes();    }

Neste simples cdigo estamos aplicando o murmurhash e fazendo o hash de um array de bytes que foi gerado a partir de uma simples string com o meu nome.
Optei por usar uma implementao do murmurhash disponvel dentro da lib guava mas nada lhe impede de usar outra implementao.

O algoritmo do murmurhash tambm determinstico, de maneira que para uma mesma entrada sempre haver uma mesma sada.

Neste exemplo, estamos optando por pegar o resultado do hash tambm como um array de bytes, mas seria possvel tambm pegar o resultado como um inteiro ou long.

Todas estas caractersticas fazem com que o murmurhash seja usado em cenrios interessantes, vamos ver a seguir um possvel cenrio.

Aplicabilidade

Voc sabia que quando usa a lib para interagir com o kafka na sua aplicao o murmurhash usado por debaixo dos panos para definir em qual partio de um tpico a mensagem ser postada com base na sua key ?
A referencia pode ser vista aqui e basicamente o que feito usar o murmurhash aplicado a key da mensagem e busca o resto da diviso sobre o total de parties.
Lembram-se tambm do fato de que o kafka consegue garantir a ordeno de mensagem apenas dentro de uma partio de um tpico mas no dentro de todas as parties ?
Eis outro benefcio do murmurhash neste cenrio, como sempre teremos o mesmo valor de sada para a mesma entrada mensagens com a mesma key sempre sero direcionadas para a mesma partio.
O murmurhash tambm muito eficaz no chamado efeito avalanche que nada mais do que uma caracterstica onde caso modifiquemos minimamente o input teremos um resultado totalmente diferente, e devido a isso, tambm eficaz em distribuir uniformemente entre as parties de um tpico mensagens com keys distintas.

A seguir vamos ver como algumas destas caractersticas podem ser aplicadas em um cenrio real.

Criando um rollout progressivo com o murmurhash

Imagine que voc est diante do seguinte cenrio:
"Uma determinada aplicao possui uma base de usurios relativamente grande e voc deseja liberar uma nova funcionalidade que foi implementada de forma progressiva para estes usurios, primeiro para 10% da base, depois 20%, e assim sucessivamente at atingir todos os usurios"

Uma das melhores formas de fazer isso implementar uma feature toogle que permite ligar ou desligar a nova feature na sua aplicao, mas neste caso, no pode ser uma toogle esttica que representa o mesmo valor para todos os usurio da aplicao, ela teria que identificar se um determinado cliente entraria ou no nela naquele determinado momento baseado em alguma lgica.
Uma outra alternativa que voc pode pensar marcar os seus usurios na base de dados dizendo quem entra e quem no, atualizando isso aos poucos conforme voc vai expandindo o fluxo, mas esta soluo no parece ser muito eficiente e de difcil manuteno.

Para atender essa demanda podemos aplicar o murmurhash, usando como input alguma coisa que sempre seja nica e nunca mude para um usurio ( id, cpf, etc)
Vamos ver um simples exemplo:

private static double calculatePercentage(String userId){        HashCode hashCode = Hashing.murmur3_32_fixed().hashBytes(userId.getBytes(Charset.forName("UTF8")));        long hashedValueInLong = Integer.toUnsignedLong(hashCode.asInt());        var percentual = hashedValueInLong  / Math.pow(2,32);        System.out.println("Percentual: " + percentual);        return percentual;    }

Detalhando cada um dos passos:

1. Aplicamos o murmurhash a uma string de input da mesma maneira que fizemos ateriormente.
2. Pegamos o resultado do murmurhash como um inteiro e convertermos para um unsigned long (vamos aprofundar este detalhe a seguir)
3. Dividimos o numero resultado do murmurhash por 2 elevado a 32 porque este o valor mximo que pode ser atingido.
4. O resultado um percentual, um valor em 0.1 e 1.0 aplicado a um usurio.

Neste exemplo, estamos usando a verso de 32 bits do murmurhash, que pode gerar um hash de at 32 bits.
Na linha 3 do cdigo convertermos um int para um long usando porque valores inteiros podem ser negativos e esta uma forma simples de se obter o valor sem sinal, para mais detalhes veja a documentao do mtodo Integer.toUnsignedLong
Se voc executar este mtodo com o input 836d473d-56be-4ef9-9b13-1fc8f36ef98e ter como resultado o valor 0.913....
Com este valor basta comparar com o percentual mximo que voc deseja disponibilizar a nova feature. Neste exemplo, se estivermos liberando para 20% da base com certeza este usurio no entraria, mas se j estivermos liberando para 95% da base este usurio entraria porque seu percentual 91%.

possvel ter exatido mxima com este mtodo ?

Considerando as caractersticas do algoritmo murmurhash ele funciona melhor conforme o publico alvo vai aumentando, ou neste caso, conforme maior sua base de usurios.

Projeto de exemplo

Para exemplificar tudo o que discutimos criei um projeto de exemplo, onde a partir de uma lista fictcia de 10.000 usurios e um valor predeterminado de 10% classificamos esta lista para demonstrar que o algoritmo consegue distribuir uniformemente os hashs e filtrar um valor muito prximo de 10% de usurios mesmo sem conhecer toda a base.

O projeto est disponvel neste link = https://github.com/hebertrfreitas/murmurhash-example