Cassandra - Particionamento de Dados

Sistemas Distribuídos

Douglas MacedoHugo Lourenço

Sumário

● Introdução●Conceito●Anel●Multíplos Data center●Fatores envolvidos ●Arquitetura do Sistema●Módulo de Particionamento●Particionamento em Banco de Dados Distribuídos●Experiências Práticas ●Conclusão

Slide 3 de 30

Introdução

Vem se tornando cada vez mais popular entre as equipes de desenvolvimento que estão migrando para o NoSQL.Une:

○ design completamente distribuído do Dynamo (Amazon)

○ modelo de dados baseado em Column-Family do BigTable (Google)

O maior cluster em produção tem cerca de 300 TB em mais de 400 máquinas

Slide 4 de 30

IntroduçãoNoSQL

* Not only SQL (não somente sql) e não NO SQL (não ao sql)

*Escalabilidade e Desempenho

Cassandra VS MySQL (50GB)*

Write:

~0.12 ms vs ~300 ms

Read:

~15 ms vs ~350 ms

*(tempos médios)

Slide 5 de 30

Introdução

1. Um particionador que determina qual dos nós irá armazenar os dados;

2. O número de cópias de dados, que são determinados pela "estratégia de replicação";

3. A topologia do cluster: ○ Número de nós;○ Distribuição de nós nos racks;○ Número de data centers.

Slide 6 de 30

Conceito● Cassandra particiona de forma transparente os

dados em seus nodes participantes do

database no cluster.

● Cada node fica

responsável por uma

parte do database global.

Slide 7 de 30

Conceito

Estrutura comum a

NOSQL

● KeySpace

● Column Family

● Column

key = "row key" (chave de

linha)

Slide 8 de 30

Conceito

● Cada linha de dados é identificada de forma única pela

chave de linha da coluna.

● A distribuição no cluster se da pelo valor do Token.

Slide 9 de 30

Anel do Cluster● O número total de dados armazenados pelo cluster é

representado pelo anel:

○ Dividido em intervalos iguais ao número de nós;○ Cada nó pode ser responsável por um ou mais intervalos

de dados.

● Um nodo (ex: um PC adicionado) pode-se juntar a um anel,onde lhe é atribuído um token, este determina:

○ Posição do nodo no anel;○ Faixa de dados.

Slide 10 de 30

Anel do Cluster Determinando onde o nodo irá ficar no anel:

● Em sentido horário se localiza o nodo com valor de chave maior do que a chave do nodo a entrar (ou da "row key").

● Cada nó é responsável pela região entre si e de seu antecessor.

● No exemplo, nodo ZERO de 75 a 0.

Slide 11 de 30

Múltiplos Data Center Clusters● NetworkTopologyStrategy: principal estratégia de

colocação de réplicas em múltiplos data center, ela

especifica quantas réplicas se quer em cada data center

1. Se coloca a primeira réplica para cada linha

considerando o valor atribuído em cada nó.

2. As réplicas adicionais são colocadas no mesmo data

center, percorrendo em sentido horário até alcançar o

próximo data center

Slide 12 de 30

Múltiplos Data Center Clusters

Distribuição de dados não-uniforme Distribuição de dados uniforme

Considerando os nós individualmente a distribuição deve ser uniforme

Valores dos tokens não devêm entrar em conflito

Slide 13 de 30

Geração de Token● Cassandra inclui uma ferramenta para geração de tokens

o a no intervalo máximo possível (0 to 2^127 -1)para uso

com o RandomPartitioner

● Cada nó no cluster precisa ser atribuído um token antes

de começar pela primeira vez.

○ initial_token = é configurado no arquivo cassandra.

yaml

Slide 14 de 30

Geração de Token● Single data center:

./tools/bin/token-generator 4

Node #1: 0Node #2: 42535295865117307932921825928971026432Node #3: 85070591730234615865843651857942052864Node #4: 127605887595351923798765477786913079296

● Mútiplos data centers usando NetworkTopologyStrategy (por padrão):

./tools/bin/token-generator 4 4

DC #1: Node #1: 0 Node #2: 42535295865117307932921825928971026432 Node #3: 85070591730234615865843651857942052864 Node #4: 127605887595351923798765477786913079296DC #2: Node #1: 169417178424467235000914166253263322299 Node #2: 41811290829115311202148688466350243003 Node #3: 84346586694232619135070514395321269435 Node #4: 126881882559349927067992340324292295867

Slide 15 de 30

Geração de Token● Evitar colisão de tokens, colocando valores com offsset nos tokens, que permite um intervalo

uniforme entre os novos nós

Slide 16 de 30

Cassandra 1.2● Não é preciso cálculo de tokens se estiver usando virtual nodes (vnodes,

novidade na versão)

○ Remoção/Adição de nós sem precisar rebalancemento manual no

cluster

○ Reconstroi nós mortos mais rapidamente

○ Melhora o uso de máquinas heterogêneas no cluster

● Murmur3Partitioner

○ Provém um hash mais rápido e aumenta a performance do que a

versão padrão anterior (RandomPartitioner)

■ Usa função MurmurHash (o RandomPartitioner usa hash MD5)

Slide 17 de 30

● Os SGBDs oferecem recursos eficazes para realizar buscas sobre os dados usando relações de igualdade e de ordem total existentes nos dados armazenados (números e textos curtos)

● Com dados complexos nas buscas por igualdade ou por ordem não se aplicam. Para esses tipos de dados é mais relevante fazer uso de consultas por similaridade, que consistem em procurar por elementos em um conjunto que, segundo algum critério de similaridade, sejam mais “parecidos” ou mais “distintos” com/de um determinado elemento.

Consultas por Similaridade

Slide 18 de 30

Consulta por abrangência (Range query – Rq): retorna todos os elementos dissimilares de um elemento de consulta até no máximo um certo limiar;

Consultas por SimilaridadeConsulta aos k-vizinhos mais próximos (k-Nearest Neighbors query – k-NNq): retorna os k elementos mais similares ao elemento de consulta sq, isto é, os k elementos si pertence S com menor valor para S(si;sq).

Slide 19 de 30

Dynamo é uma tecnologia interna desenvolvida pela Amazon para a necessidade de ter escalabilidade e alta disponibilidade no sistema de armazenamento de key-value.

A tecnologia possibilita: ● "trade-off"(custo | conflitos);● consistência; ● durabilidade; ● desempenho; ● alta disponibilidade.

Arquitetura do Sistema

Slide 20 de 30

Arquitetura do Sistema

Dynamo usa hashing consistentes para o particionamento. Os objetos e caches usam a mesma função hash. Vantagens:

○ As máquinas terão um intervalo da escala de função hash e máquinas vizinhas pode levar mais porções do intervalo de seus nós adjacentes se sair e pode ceder parcelas de sua intervalo se algum nó novo membro se junta e é mapeado para um intervalo de perto.

○ Os clientes podem facilmente determinar os nós para executar operações de leitura ou gravação.

Slide 21 de 30

Arquitetura do Sistema

Cada nó é mapeado para vários pontos no anel em vez de um único ponto. Usando o conceito de virtual tem vantagens:

○ Distribuição da carga de trabalho de um nó para os nós disponíveis quando um nó se torna indisponível;

○ Quando um novo nó é adicionado ou quando um se recupera de acidente, começará com carga 'igual' ao dos outros.

Slide 22 de 30

NoSQL Data Stores

Slide 23 de 30

Tabela de Comparação

Slide 24 de 30

Importante na implantação do Cassandra: escolha de tokens para cada nó

Qual nó armazenará os dados?

●Uso do OPP requer cautela na escolha de tokens;●Na distribuição desequilibrada: mais dados são

armazenados em um número menor de nós.●O ideal é particionar de forma uniforme.

Módulo de Particionamento

Slide 25 de 30

●Cassandra é escalável de forma incremental, as máquinas podem entrar e sair de um cluster;

●Os dados devem ser particionadas e distribuídas entre os nós de um cluster de uma forma que permite que reparticionamento e redistribuição;

●As tabelas no Cassandra são divididas e distribuídas em hashing consistentes como no Dynamo.

Módulo de Particionamento

Slide 26 de 30

Particionamento em Banco de Dados Distribuídos

Hashing Consistente x Ordem de Presevação

Uso de hash consistentes fornece um melhor esquema ("brain-dead") de balanceamento de carga a partir do algoritmo de hash espalhando chaves no anel;

Não apresentou bons resultados na prática, a solução foi atribuir vários tokens para cada nó no cluster e existem várias abordagens para isso;

No Cassandra o projeto original considerava o Hashing Consistente uma preferência de balanceamento de carga real.

As chaves são distribuídas para os nós em sua ordem natural;

Principal vantagem sobre o Hashing Consistente: Capacidade de fazer consultas de intervalo entre as chaves no sistema;

O particionador usa a key para determinar em qual nó o dado está;

Cada chave pode ter vários dados associados; [modelo de dados]Flexibilidade em consultas de abrangência por propagar os dados entre várias chaves.

Slide 27 de 30

Particionador: qualquer IPartitioner pode ser usado, incluindo o seu, desde que ele esteja no classpath. Fora da caixa, Cassandra fornece org.apache.cassandra.dht.RandomPartitioner, org.apache.cassandra.dht.OrderPreservingPartitioner, org.apache.cassandra.dht.ByteOrderedPartitioner, e org.apache.cassandra.dht.CollatingOrderPreservingPartitioner. (CollatingOPP colates acordo com as regras EN, dos EUA, não ordena byte. Use isso como um exemplo, se você precisa localidade ciente.) A única diferença entre BOP e OPP é que a OPP requer chaves codificadas em UTF-8. Range exigem consultas usando um particionador ordem de preservação.

● Achtung!A alteração deste parâmetro limpa seus diretórios de dados, já que o particionador modifica o formato !sstable no disco.

● Se você estiver usando um particionador fim de preservação e você sabe que a sua distribuição de chaves, você pode especificar o

símbolo para este nó usar. (As chaves são enviadas para o nó com os "mais próximos" token, para a distribuição de seus tokens igualmente ao longo do espaço de distribuição de chaves que vai se espalhar as chaves uniformemente no cluster.) Essa configuração só é verificada a primeira vez que um nó é iniciado.

● Isto pode também ser útil com RandomPartitioner forçar espaçamento igual em torno do espaço de hash, em especial para aglomerados

com um pequeno número de nós.

● Cassandra usa hash MD5 internamente para colocar a hash das chves do anel em um RandomPartitioner. Portanto, faz sentido dividir o

espaço de hash igualmente pelo número de máquinas disponíveis usando InitialToken ou seja, se existem 10 máquinas, cada um vai lidar com 1/10th de valor máximo hash) e esperar que as máquinas terão uma carga razoavelmente igual.

● Com OrderPreservingPartitioner as próprias chaves são utilizadas para armazenar no anel. Uma desvantagem do potencial desta

abordagem é que, se as linhas são inseridas com chaves sequenciais, toda a carga de gravação irá para o mesmo nó.

● Padrão: 'org.apache.cassandra.dht.RandomPartitioner'. Atribuir manualmente os tokens é altamente recomendável para garantir uma

distribuição uniforme de carga.

Wiki Cassandra: Informações de configurações do particionador

Slide 28 de 30

Dentro do arquivo de configuração conf/cassandra.yaml

Partitioner: qualquer IPartitioner pode ser usado, inclusive um próprio, desde que esteja no classpath. Cassandra provém:

○ org.apache.cassandra.dht.RandomPartitioner (RP)○ org.apache.cassandra.dht.OrderPreservingPartitioner (OPP)○ org.apache.cassandra.dht.ByteOrderedPartitioner (BOP)○ org.apache.cassandra.dht.CollatingOrderPreservingPartitioner (COPP)

CollatingOPP agrupa de acordo com as normas do idioma EN,US, não sobre a ordem de byte nativo. É usado quando se precisa de agrupamento de cliente por localidade.

A única diferença entre BOP e OPP é que requer chaves para ser codificado em UTF-8. "Consultas por abrangência" (" Range queries" ) requerem um particionador por ordem.

A alteração deste parâmetro requer que você limpe os diretórios de dados, desde que o particionador pode modificar o formato de disco e !sstable .

Utilizando o particionador por ordem " order-preserving partitioner" e sabendo a distribuição de chaves, pode-se especificar o token que seu nó usa (as chaves são enviadas para os nós com os tokens mais próximos, então a distribuição de tokens vai se espalhar uniformemente através do cluster). Essa configuração só é verificada na primeira vez que um nó e iniciado.

Útil também com RandomPartitioner para forçar espaçamento uniforme de tokens em torno do espaço de hash, em especial de aglomerados com um pequeno número do nodos.

Cassandra usa hash MD5 internamente para fazer hash das chaves para colocar o anel em um RandomPartitioner. Faz sentido dividir o espaço de hash uniformemente pelo número de maquinas usando um tokenInicial (initianToken). Por exemplo: se tiver 10 máquinas, cada uma vai lidar com 1/10 de valor máximo do hash e esperar que as máquinas terão uma carga razoavelmente uniforme.

Com OrderPreservingPartitioner as chaves delas próprias são colocadas sobre o anel. Uma potencial desvantagem desta abordagem é que estas linhas são inseridas com chaves sequências, toda a carga de gravação irá para o mesmo nó.

O padrão é : 'org.apache.cassandra.dht.RandomPartitioner'. Tokens atribuídos de forma manual são recomendáveis para garantir uma distribuição uniforme de carga..

Experiências Práticas

Slide 29 de 30

O particionamento no Cassandra se dá através da técnica de hash consistente. Garante:

■ melhor distribuição dos dados entre os nós existentes ■ melhor balanceamento de carga■ nós servirão a múltiplas requisições ao mesmo tempo.

Somada ao protocolo Gossip permite que um nó possa prever aonde está a linha referente à chave pesquisada, de maneira muito eficiente.

Entretanto, a existência de um nó coordenador para um determinado conjunto de chaves ainda representa um ponto único de falha, ao menos para esse conjunto de dados. Por isso, o Cassandra replica de forma assíncrona os dados gravados em cada nó coordenador

PARTICIONAMENTO + PROTOCOLO GOSSIP + REPLICAÇÃO = sem pontos de falha

Conclusão

Slide 30 de 30

● Referências:

○ http://www.ijecse.org/wp-content/uploads/2012/12/Volume-2Number-1PP-133-140.pdf

○ http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html○ http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf○ http://www.cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf○ https://dl.dropbox.com/u/45289918/Big%20Data/cassandra-principios%20e%

20arquitetura.pdf○ https://www.cloudkick.com/blog/2010/mar/02/4_months_with_cassandra/○ http://techne.cesar.org.br/usando-o-cassandra/○ http://otaviosantana.blogspot.com.br/2012/01/persistindo-com-o-cassandra-em-

java.html○ http://rubyscale.com/blog/2011/03/06/basic-time-series-with-cassandra/○ http://www.ijecse.org/wp-content/uploads/2012/12/Volume-2Number-1PP-133-

140.pdf○ http://blogdomariomarroquim.files.wordpress.com/2012/06/artigo-

mariomarroquim-cassandra.pdf

Referências

FIM