Algumas semanas atrás o Facebook liberou sem chamar muita atenção sua implementação de uma base de dados robusta e replicada inspirada do BigTable do Google e utilizando conceitos de distribuição de dados do Dynamo da Amazon.
É um código feito em Java de cerca de 40 mil linhas que parece implementar um núcleo funcional mas sem todas as liberdades que existem nos sistemas da Google e da Amazon.
Foi implementado recentemente por uma equipe pequena interna a Facebook como uma alternativa mais simples que a plataforma Hadoop que já está sendo usada a algum tempo no Facebook.
O código está no Google Code e existe uma apresentação sobre o projeto discutindo alguns detalhes internos.
Mostrando postagens com marcador google. Mostrar todas as postagens
Mostrando postagens com marcador google. Mostrar todas as postagens
08 julho 2008
Consistência eventual de dados no eBay
A revista Queue da ACM publicou na edição maio/junho de 2008 um artigo chamado "ACID vs. BASE" de Dan Pritchett (eBay) falando do conceito de consistência eventual em armazenamento escalável de dados.
É uma ótima introdução dos conceitos de gerenciamento de dados distribuídos aonde a consistência perfeita "ACID" é abandonada para permitir níveis de performance e escalabilidade que são impossíveis de atingir numa plataforma monolítica.
Já fiz vários comentários sobre o conceito de dados distribuídos, o interessante é como que todos os grandes serviços na Internet (Google, Amazon, eBay, etc) só conseguiram atingir o público mundial abandonando a segurança da consistência tão defendida pelos fornecedores convencionais de banco de dados comerciais.
Na prática, quando os dados passam a ser divididos em milhares de servidores separados para conseguir a performance, a consistência "global" acaba sendo impossível de ser atingida.
É uma ótima introdução dos conceitos de gerenciamento de dados distribuídos aonde a consistência perfeita "ACID" é abandonada para permitir níveis de performance e escalabilidade que são impossíveis de atingir numa plataforma monolítica.
Já fiz vários comentários sobre o conceito de dados distribuídos, o interessante é como que todos os grandes serviços na Internet (Google, Amazon, eBay, etc) só conseguiram atingir o público mundial abandonando a segurança da consistência tão defendida pelos fornecedores convencionais de banco de dados comerciais.
Na prática, quando os dados passam a ser divididos em milhares de servidores separados para conseguir a performance, a consistência "global" acaba sendo impossível de ser atingida.
13 junho 2008
Megadata, nova tendência para os banco de dados
Interessante este artigo de Joe Gregorio onde ele expõe uma tendência de crescimento do uso de quantidades absurdas de dados, exigências de robustez, facilidade para alteração constante da forma da representação dos dados e buscas praticamente instantâneas neste universo.
Os servidores de banco de dados comerciais já não dão conta desta demanda a vários anos. A Google, a Amazon, o eBay (leia isso!), e muitos outros já aprenderam na prática que vários conceitos aprendidos no passado de depender de uma caixa preta (banco de dados) para implementar garantias transacionais e integridade referencial não é mais viável.Joe Gregorio tenta formular o conceito do Megadata:
- dados distribuidos em múltiplas máquinas, em vez de centralizado num servidor gigante;
- Joinless, sem joins e sem integridade referencial, pelo menos não no local de armazenamento;
- De-normalizado, para evitar os joins;
- Sem transações. Se as transações numa máquina separada já é cara, transações distribuidas em servidores torna isso completamente inviável pela perda de performance.
O banco de dados da Google
Falei sobre o armazenamento, administração de alterações e servidores de processamento nas plataformas do Google e da Amazon. Agora resta saber como se utilizar destas ferramentas para construir abstrações mais convencionais de base de dados.
No caso do Google, a principal ferramenta hoje é o BigTable. O BigTable é uma aplicação distribuída que opera sobre o Google File System (GFS) e implementa tabelas 3D genéricas, cujos vetores são linha, coluna e tempo. Todo o mapeamento é feito String para String, ou seja, as chaves linha, coluna e tempo são string e o condeúdo dos campos são também strings.
As tabelas são obrigadoriamente ordenadas por linha, dentro da linha por coluna, e então por tempo, e são quebradas em unidades menores de tamanhos típicos de 200MB chamadas "tablets" para mapear melhor com o GFS. As "tablets" sempre contém linhas inteiras, ou seja, a fronteira da linha é usada para quebrar os "tablets".
Então os "tablets" ficam sendo os motores de armazenamento de dados e alterações, onde um "log" em disco e uma versão em memória das alterações do "log" são usadas para registrar e preservar as alterações recentes, e tabelas chamadas "SSTables" contém mapas mais antigos de <linha,coluna,tempo> para <dado>.
Uma aplicação em batch faz compilações dos "logs" para novas "SSTables" constantemente, e outra mais esporádica agrupa as "SSTables" em uma única "SSTable" para reclamar o espaço em disco dos elementos que foram retirados ("Garbage Collection").
Para quem tiver interesse, existe uma apresentação sobre o BigTable feita pelo Jeff Dean da Google na Universidade de Washington no Google Video.
O BigTable não possui interface SQL, não é uma base relacional e nem transacional, implementando apenas garantias de alterações atômicas ao nível de linha. Entretanto, com os devidos cuidados, esta é a base para aplicações gigantescas oferecidas pelo Google, como o Google Earth (70TB de dados), Google Analytics (200TB de dados) e a base de buscas do Google (800TB de dados).
Já a Amazon não fala muito como implementa suas aplicações, apenas que utiliza exatamente a mesma infraestrutura de serviços web sendo oferecida hoje (S3, EC2 e SQS).
Existe um artigo bastante interessante de Pat Helland (ex-funcionário da Amazon) onde ele comenta sobre como implementar aplicações massivas e distribuídas em centenas de computadores.
Ele argumenta que para distribuir aplicações, é necessário separar os "estados" em entidades ("entities"). Entidades seriam uma coleção de dados com uma única chave para sua localização. Exemplos: uma Ordem de Compra (chave OrderId) , um Ítem em Estoque (ItemId), etc.
Então para considerar uma aplicação "escalável", você não pode assumir que transações atômicas sejam possíveis envolvendo mais de uma entidade. O artigo apresenta o conceito de operações canceláveis (tentativas de operações) como a única forma de manter consistência em ambientes distribuídos.
O interessante é que de certa forma tanto a Amazon como a Google chegaram em conceitos semelhantes, o que a Google chama de "linha" numa tabela BigTable acaba sendo uma entidade da Amazon.
No caso do Google, a principal ferramenta hoje é o BigTable. O BigTable é uma aplicação distribuída que opera sobre o Google File System (GFS) e implementa tabelas 3D genéricas, cujos vetores são linha, coluna e tempo. Todo o mapeamento é feito String para String, ou seja, as chaves linha, coluna e tempo são string e o condeúdo dos campos são também strings.
As tabelas são obrigadoriamente ordenadas por linha, dentro da linha por coluna, e então por tempo, e são quebradas em unidades menores de tamanhos típicos de 200MB chamadas "tablets" para mapear melhor com o GFS. As "tablets" sempre contém linhas inteiras, ou seja, a fronteira da linha é usada para quebrar os "tablets".
Então os "tablets" ficam sendo os motores de armazenamento de dados e alterações, onde um "log" em disco e uma versão em memória das alterações do "log" são usadas para registrar e preservar as alterações recentes, e tabelas chamadas "SSTables" contém mapas mais antigos de <linha,coluna,tempo> para <dado>.
Uma aplicação em batch faz compilações dos "logs" para novas "SSTables" constantemente, e outra mais esporádica agrupa as "SSTables" em uma única "SSTable" para reclamar o espaço em disco dos elementos que foram retirados ("Garbage Collection").
Para quem tiver interesse, existe uma apresentação sobre o BigTable feita pelo Jeff Dean da Google na Universidade de Washington no Google Video.
O BigTable não possui interface SQL, não é uma base relacional e nem transacional, implementando apenas garantias de alterações atômicas ao nível de linha. Entretanto, com os devidos cuidados, esta é a base para aplicações gigantescas oferecidas pelo Google, como o Google Earth (70TB de dados), Google Analytics (200TB de dados) e a base de buscas do Google (800TB de dados).
Já a Amazon não fala muito como implementa suas aplicações, apenas que utiliza exatamente a mesma infraestrutura de serviços web sendo oferecida hoje (S3, EC2 e SQS).
Existe um artigo bastante interessante de Pat Helland (ex-funcionário da Amazon) onde ele comenta sobre como implementar aplicações massivas e distribuídas em centenas de computadores.
Ele argumenta que para distribuir aplicações, é necessário separar os "estados" em entidades ("entities"). Entidades seriam uma coleção de dados com uma única chave para sua localização. Exemplos: uma Ordem de Compra (chave OrderId) , um Ítem em Estoque (ItemId), etc.
Então para considerar uma aplicação "escalável", você não pode assumir que transações atômicas sejam possíveis envolvendo mais de uma entidade. O artigo apresenta o conceito de operações canceláveis (tentativas de operações) como a única forma de manter consistência em ambientes distribuídos.
O interessante é que de certa forma tanto a Amazon como a Google chegaram em conceitos semelhantes, o que a Google chama de "linha" numa tabela BigTable acaba sendo uma entidade da Amazon.
09 junho 2008
Processamento seguro dos dados na Amazon e na Google
Já comentei sobre como grandes volumes de dados são armazenados de forma segura pela Amazon e pela Google. Também comentei como o processamento ocorre nos servidores destas empresas.
Agora temos que analisar como as interações com os sistemas são robustas a ponto de que nenhuma transação seja perdida mesmo com falhas nos servidores dos respectivos datacenters.
Os serviços S3 da Amazon e o GFS da Google são mecanismos para preservação de estado robustas, mas que não oferecem meios para alteração dos dados armazenados. Então como as transações são armazenadas de forma segura?
No caso da Google a solução é bastante interessante: utilizar do mecanismo de append em fim de arquivo como uma forma de implementar uma fila FIFO de transações. Ou seja, um "change log".
Como isto funcionaria?
Por exemplo, digamos que tenhamos um arquivo com uma base de informações grandes. Então uma transação é efetuada provocando a alteração lógica de algum elemento. Esta transação é então armazenada como uma alteração no final de um arquivo separado de "log de alteração".
Logicamente isto implica que toda consulta agora precisaria consultar a base original e consultar os "logs de alteração" para verificar o valor correto, mas se o "log" não for muito grande não há grandes problemas.
Para o "log" não crescer sem parar, uma operação em background pode construir num novo arquivo uma segunda base atual com as alterações do "log", ou um novo arquivo com a base original completa contendo também os dados não alterados. O paper do GFS comenta sobre este mecanismo.
Já a Amazon disponibilizou um outro serviço web chamado Amazon Simple Queue Service (Amazon SQS) que implementa filas robustas específicas para o fim de registrar ações, com custos de $0,10 centavos de dólar por 1.000 mensagens para quem desejar desenvolver aplicações sobre este serviço.
O modo de uso acaba sendo semelhante ao implementado pelo Google, onde algum processo em background gerencia estas alterações armazenadas nas filas para construções de novas bases atualizadas.
A solução SQS da Amazon acaba sendo uma abstração mais avançada e específica para o registro de eventos e ações.
Agora temos que analisar como as interações com os sistemas são robustas a ponto de que nenhuma transação seja perdida mesmo com falhas nos servidores dos respectivos datacenters.
Os serviços S3 da Amazon e o GFS da Google são mecanismos para preservação de estado robustas, mas que não oferecem meios para alteração dos dados armazenados. Então como as transações são armazenadas de forma segura?
No caso da Google a solução é bastante interessante: utilizar do mecanismo de append em fim de arquivo como uma forma de implementar uma fila FIFO de transações. Ou seja, um "change log".
Como isto funcionaria?
Por exemplo, digamos que tenhamos um arquivo com uma base de informações grandes. Então uma transação é efetuada provocando a alteração lógica de algum elemento. Esta transação é então armazenada como uma alteração no final de um arquivo separado de "log de alteração".
Logicamente isto implica que toda consulta agora precisaria consultar a base original e consultar os "logs de alteração" para verificar o valor correto, mas se o "log" não for muito grande não há grandes problemas.
Para o "log" não crescer sem parar, uma operação em background pode construir num novo arquivo uma segunda base atual com as alterações do "log", ou um novo arquivo com a base original completa contendo também os dados não alterados. O paper do GFS comenta sobre este mecanismo.
Já a Amazon disponibilizou um outro serviço web chamado Amazon Simple Queue Service (Amazon SQS) que implementa filas robustas específicas para o fim de registrar ações, com custos de $0,10 centavos de dólar por 1.000 mensagens para quem desejar desenvolver aplicações sobre este serviço.
O modo de uso acaba sendo semelhante ao implementado pelo Google, onde algum processo em background gerencia estas alterações armazenadas nas filas para construções de novas bases atualizadas.
A solução SQS da Amazon acaba sendo uma abstração mais avançada e específica para o registro de eventos e ações.
03 junho 2008
Storage na Amazon e na Google
Como é que a Amazon e a Google armazenam suas absurdas demandas de persistência de informação?
Se você acha que é com grandes storages fiberchannel em RAID5, RAID6 ou RAID10 e instalações gigantescas de bancos de dados comerciais você estaria completamente enganado.
Tanto uma como a outra desenvolveu seus próprios mecanismos de armazenamento de informação em servidores convencionais usando simples discos ATAs.
A idéia é utilizar muitas máquinas com dados espalhados e com cópias redundandes em vários lugares, normalmente 3 cópias independentes.
A Amazon utiliza do serviço S3 internamente para implementar seus mecanismos de redundância. Este serviço permite o armazenamento e a recuperação de arquivos de até 2GB em uma estrutura de diretório, a remoção dos mesmos e a listagem destes diretórios.
Internamente o S3 implementa tudo o que é necessário para garantir a preservação dos dados e a acessibilidade dos mesmos. Os arquivos são copiados automaticamente para vários datacenters da Amazon.
O interessante deste serviço S3 é que a Amazon oferece este serviço para qualquer pessoa que tenha interesse de desenvolver aplicações com dados seguros por preços muito baixos: $0,15 centavos de dólar por GB armazenado, $0,10 por GB enviado à Amazon, até $0,18 por GB recebido da Amazon, e mais $0,01 por 1.000 envios ou listagens e $0,01 por 10.000 recebimentos.
Este é o caso da SmugMug, que se utiliza da estrutura da S3 para armazenar mais de 100 TB de fotos dos clientes deles.
Já a Google se utiliza da tecnologia do Google File System, que implementa de forma semelhante um mecanismo robusto de armazenamento dos dados.
A Google não oferece acesso por terceiros a este sistema, mas seu funcionamento é documentado neste paper.
O Google File System (GFS) implementa um mecanismo de quebrar os arquivos a serem preservados em chunks de 64MB por default, chunks estes que são replicados em 3 servidores ou mais.
As leituras são distribuidas entre as cópias permitindo multiplicar o throughput, já as escritas são feitas em seqüência entre os servidores e sempre na mesma ordem para que situações de corrida não façam as cópias ficarem diferentes. As escritas só são confirmadas para a aplicação se todas as cópias estão com o dado gravado corretamente.
Tanto a solução da Google como da Amazon não implementam mecanismos esperados em sistemas de arquivos convencionais, como a alteração no meio de um arquivo já gravado. A solução da Google entretanto permite a leitura a partir de um endereço aleatório e pelo menos anexar dados no final de arquivos previamente guardados.
E como é possível usar isso para substituir um banco de dados convencional?
Não é simples, mas com esta base funcional as duas empresas implementaram abstrações, tipo o BigTable (paper) do Google, que permitem hoje fazer ambas as empresas operar os seus negócios em escalas impensáveis para bancos convencionais.
Se você acha que é com grandes storages fiberchannel em RAID5, RAID6 ou RAID10 e instalações gigantescas de bancos de dados comerciais você estaria completamente enganado.
Tanto uma como a outra desenvolveu seus próprios mecanismos de armazenamento de informação em servidores convencionais usando simples discos ATAs.
A idéia é utilizar muitas máquinas com dados espalhados e com cópias redundandes em vários lugares, normalmente 3 cópias independentes.
A Amazon utiliza do serviço S3 internamente para implementar seus mecanismos de redundância. Este serviço permite o armazenamento e a recuperação de arquivos de até 2GB em uma estrutura de diretório, a remoção dos mesmos e a listagem destes diretórios.
Internamente o S3 implementa tudo o que é necessário para garantir a preservação dos dados e a acessibilidade dos mesmos. Os arquivos são copiados automaticamente para vários datacenters da Amazon.
O interessante deste serviço S3 é que a Amazon oferece este serviço para qualquer pessoa que tenha interesse de desenvolver aplicações com dados seguros por preços muito baixos: $0,15 centavos de dólar por GB armazenado, $0,10 por GB enviado à Amazon, até $0,18 por GB recebido da Amazon, e mais $0,01 por 1.000 envios ou listagens e $0,01 por 10.000 recebimentos.
Este é o caso da SmugMug, que se utiliza da estrutura da S3 para armazenar mais de 100 TB de fotos dos clientes deles.
Já a Google se utiliza da tecnologia do Google File System, que implementa de forma semelhante um mecanismo robusto de armazenamento dos dados.
A Google não oferece acesso por terceiros a este sistema, mas seu funcionamento é documentado neste paper.
O Google File System (GFS) implementa um mecanismo de quebrar os arquivos a serem preservados em chunks de 64MB por default, chunks estes que são replicados em 3 servidores ou mais.
As leituras são distribuidas entre as cópias permitindo multiplicar o throughput, já as escritas são feitas em seqüência entre os servidores e sempre na mesma ordem para que situações de corrida não façam as cópias ficarem diferentes. As escritas só são confirmadas para a aplicação se todas as cópias estão com o dado gravado corretamente.
Tanto a solução da Google como da Amazon não implementam mecanismos esperados em sistemas de arquivos convencionais, como a alteração no meio de um arquivo já gravado. A solução da Google entretanto permite a leitura a partir de um endereço aleatório e pelo menos anexar dados no final de arquivos previamente guardados.
E como é possível usar isso para substituir um banco de dados convencional?
Não é simples, mas com esta base funcional as duas empresas implementaram abstrações, tipo o BigTable (paper) do Google, que permitem hoje fazer ambas as empresas operar os seus negócios em escalas impensáveis para bancos convencionais.
31 julho 2007
Conectividade aberta no atacado sugerida pela Google não foi aprovada
A FCC foi realmente conservadora e não aceitou as principais provisões sugeridas pelo Google para a licitação das freqüências de 700MHz.
As obrigações sugeridas de aceitar qualquer uso e por qualquer dispositivo terminal foram aceitas, o que defendem pelo menos o conceito de Net Neutrality, só que a obrigação que acabaria por criar um mercado competitivo de conectividade sem fio através da obrigação de oferecer o serviço no atacado a empresas terceiras foram vistas como um favorecimento direto ao Google.
Parece que nos EUA ainda não foi desta vez que o duopólio será combatido.
As obrigações sugeridas de aceitar qualquer uso e por qualquer dispositivo terminal foram aceitas, o que defendem pelo menos o conceito de Net Neutrality, só que a obrigação que acabaria por criar um mercado competitivo de conectividade sem fio através da obrigação de oferecer o serviço no atacado a empresas terceiras foram vistas como um favorecimento direto ao Google.
Parece que nos EUA ainda não foi desta vez que o duopólio será combatido.
23 julho 2007
Google quebrará o duopólio das comunicações nos EUA?
Já comentei várias vezes que a maneira mais certa de conseguir aumentar a competição nos serviços de comunicação móveis ou fixas de voz ou de dados é a separação dos negócios de comunicação no atacado e do varejo.
Esta foi a técnica adotada pelos reguladores com a British Telecom, onde a empresa foi obrigada a ser dividida exatamente nestes termos.
Também foi o caso na França, onde os reguladores obrigaram a France Telecom vender o uso do par de fios e de espaço em suas centrais para prestadores de serviços no varejo, como a Free.
Nos EUA, o duopólio da AT&T e da Verizon come solto, com o pessoal da FCC claramente trabalhando para defender os interesses destas incumbents.
Agora aparece o espectro de 700MHz que hoje é utilizado para TV analógica e que deverá ter este uso descontinuado em 2009 para dar espaço para outras aplicações. A grande vantagem desta freqüência é o fato de ter longo alcance e ser uma faixa que atravessa muito bem obstáculos como paredes.
A FCC deseja fazer uma licitação convencional, oferecendo as tradicionais empresas de telefonia o seu uso. Já a Google está fazendo lobby para conseguir que a freqüência seja utilizada de forma não discriminatória e aberta para competição.
As operadoras convencionais provavelmente desejarão ganhar a licitação para evitar que apareçam competidores e que possa preservar a rentabilidade do duopólio estabelecido.
A idéia da Google é exatamente conseguir que a FCC adote uma metodologia que está dando certo em alguns lugares do mundo, a separação do negócio de comunicação no atacado do negócio do varejo. A empresa que ganhar a licitação seria impedida de oferecer serviços a clientes finais e seria obrigada a oferecer conectividade no atacado para outras prestadoras de serviços especializadas no varejo.
A FCC está argumentando que a adoção de regras restritivas na licitação, reduzirá a atratividade do negócio para as operadoras, e que por isso seria contrário ao interesse da sociedade de viabilizar e rentabilizar o Estado com a licitação.
Agora o Chairman da Google Eric Schmidt fez uma oferta para a FCC que não pode recusar: a Google oferecerá no mínimo $4,6 bilhões de dólares para participar desta licitação, desde que as exigências de abertura da rede sejam definidos pela FCC para qualquer dos ganhadores da licitação.
Isto destrói o argumento de que não haveria interessados na licitação caso a FCC definisse regras restritivas sobre o ganhador da licitação, colocando a FCC numa situação difícil de ter que escolher o melhor para sociedade em vez de defender os interesses dos lobbistas.
Os EUA caminham para uma situação inusitada: interesses corporativos de uma empresa (a Google) estão tentando forçar o governo a caminhar para uma situação de maior competição.
Esta foi a técnica adotada pelos reguladores com a British Telecom, onde a empresa foi obrigada a ser dividida exatamente nestes termos.
Também foi o caso na França, onde os reguladores obrigaram a France Telecom vender o uso do par de fios e de espaço em suas centrais para prestadores de serviços no varejo, como a Free.
Nos EUA, o duopólio da AT&T e da Verizon come solto, com o pessoal da FCC claramente trabalhando para defender os interesses destas incumbents.
Agora aparece o espectro de 700MHz que hoje é utilizado para TV analógica e que deverá ter este uso descontinuado em 2009 para dar espaço para outras aplicações. A grande vantagem desta freqüência é o fato de ter longo alcance e ser uma faixa que atravessa muito bem obstáculos como paredes.
A FCC deseja fazer uma licitação convencional, oferecendo as tradicionais empresas de telefonia o seu uso. Já a Google está fazendo lobby para conseguir que a freqüência seja utilizada de forma não discriminatória e aberta para competição.
As operadoras convencionais provavelmente desejarão ganhar a licitação para evitar que apareçam competidores e que possa preservar a rentabilidade do duopólio estabelecido.
A idéia da Google é exatamente conseguir que a FCC adote uma metodologia que está dando certo em alguns lugares do mundo, a separação do negócio de comunicação no atacado do negócio do varejo. A empresa que ganhar a licitação seria impedida de oferecer serviços a clientes finais e seria obrigada a oferecer conectividade no atacado para outras prestadoras de serviços especializadas no varejo.
A FCC está argumentando que a adoção de regras restritivas na licitação, reduzirá a atratividade do negócio para as operadoras, e que por isso seria contrário ao interesse da sociedade de viabilizar e rentabilizar o Estado com a licitação.
Agora o Chairman da Google Eric Schmidt fez uma oferta para a FCC que não pode recusar: a Google oferecerá no mínimo $4,6 bilhões de dólares para participar desta licitação, desde que as exigências de abertura da rede sejam definidos pela FCC para qualquer dos ganhadores da licitação.
Isto destrói o argumento de que não haveria interessados na licitação caso a FCC definisse regras restritivas sobre o ganhador da licitação, colocando a FCC numa situação difícil de ter que escolher o melhor para sociedade em vez de defender os interesses dos lobbistas.
Os EUA caminham para uma situação inusitada: interesses corporativos de uma empresa (a Google) estão tentando forçar o governo a caminhar para uma situação de maior competição.
Assinar:
Postagens (Atom)