Palestra Windows Internals

Enquanto não sai o próximo post da série Inside the Machine, fiz uma apresentação sobre fundamentos de Windows Internals para alguns DBAs SQL Server.

Nessa palestra falei, entre outras coisas, sobre um pequeno segredo para gerar dumps “full” do SQL Server sem que se tenha que suspender o processo original do mesmo. Isso é bastante interessante em cenários onde você tem uma instância com um Buffer Pool relativamente grande (30 GB+) e não pode manter o processo parado enquanto gera um dump.

Pretendo (um dia haha) postar sobre isso, mas por enquanto veja nos slides para maiores informações. Vale ressaltar que essa funcionalidade não é documentada, não é suportada pela Microsoft e pode destruir o processo da sua instância SQL, corromper os bancos de dados, explodir o seu data center e ainda por cima matar alguns gatinhos! Não use em produção.

Segue o link para download do pdf: http://bit.ly/1KgXElG

Se você quer se aprofundar mais nos assuntos, recomendo dar uma olhadinha nas referências ao fim da apresentação e também o meu treinamento on-demand de Windows Internals na Sr. Nimbus.

No mais, fique à vontade para deixar seus comentários sobre o material!

Pin It

Inside the Machine Parte 2 – Processadores

Introdução

Continuando nossa série de artigos sobre hardware, vamos falar um pouco sobre microprocessadores. Se você não viu a primeira parte da série,  sugiro que leia antes de continuar, pois nessa parte vamos seguir a linha de pensamento apresentado anteriormente.

Processadores

Já que vamos falar sobre mecanismos internos das CPUs precisamos escolher alguma implementação, ou microarquitetura específica como ponto de partida.

Escolhi a microarquitetura Nehalem [1] pelo simples fato de que tenho processadores baseados nessa microarquitetura tanto nos servidores do ambiente onde trabalho quanto no meu notebook. :)

Segundo a Intel, o desenvolvimento dessa microarquitetura custou aproximadamente 12 bilhões de dólares, incluindo US$ 9 bilhões na construção das fábricas (fabs), US$ 1 bilhão para o design do processo de fabricação de 45 nanômetros em material dielétrico “High-k” [11], e US$ 2 bilhões no design da microarquitetura em si [3].

Outra microarquitetura, chamada Westmere é a versão reduzida (shrink) da microarquitetura Nehalem, seguindo o padrão tick-tock de fabricação da Intel [2]. Esse tem um processo de fabricação de 32nm. A atualização das fabs para esse shrink custou à Intel mais US$ 7 bilhões [10].

Apesar da Intel já ter lançado novas microarquiteturas desde então – Sandy Bridge, Ivy Bridge e o recém-anunciado Haswell – as microarquiteturas Nehalem e Westmere são bastante comuns nos servidores que se encontram em produção hoje. Além do mais, pretendo cobrir as microarquiteturas mais novas ao longo do tempo.

Overview da Microarquitetura

Nehalem foi uma microarquitetura particularmente importante em relação a tecnologias Intel. Foi nessa microarquitetura que a Intel reintroduziu o hyper-threading ao seus processadores, após remover a funcionalidade nos processadores baseados na microarquitetura Core. Outra tecnologia importante introduzida pelo Nehalem foi o uso de um interconnect entre os processadores, similar ao que a AMD já vinha oferecendo, para remover o gargalo do acesso à memória com o Front-Side Bus (FSB). Chamado de QuickPath Interconnect (QPI), a Intel criou a tecnologia visando recuperar o mercado perdido para a AMD durante o período.

Falaremos sobre o QPI no futuro, quando entrarmos no assunto de Non-Uniform Memory Access, ou NUMA.

Primeiro chip Nehalem, Cortesia Intel

Primeiro chip Nehalem, Cortesia Intel

Core e Uncore

Na terminologia dos designers e engenheiros de processadores, os processadores são divididos entre Cores e Uncore.

Cores são desenhados como blocos reutilizáveis de lógica e hardware e não mudam entre um modelo e outro.

Os cores Nehalem e Westmere possuem 64 KB de cache L1 e 256 KB de cache L2 cada. O cache L3 é compartilhado entre todos os caches do chip, e o seu tamanho é dependente dos modelos.

O Uncore, por outro lado, são os componentes que não fazem parte do Core. Dependendo da literatura que você ler isso inclui L3, I/O, IMC e QPI. Outros separam os componentes, portanto teríamos Uncore, QPI, IMC, etc.

O Uncore pode mudar (e efetivamente muda) de um modelo para outro, mesmo entre modelos da mesma microarquitetura.

Planta

Além disso, os Cores rodam em frequências e voltagens independentes entre si. O Uncore também roda em uma frequência independente do restante dos cores. Nos slides da Intel, eles se referem ao Uncore e outros componentes de forma distinta, mas ao se referirem à frequência e voltagem, chamam todos de Uncore também.

Particionamento de voltagem e frequência do Nehalem, Cortesia Intel

Particionamento de voltagem e frequência do Nehalem, Cortesia Intel

A diferença na frequência entre Cores e Uncore tem impacto direto no desempenho da máquina. Falaremos disso tudo quando chegarmos aos assuntos de Turbo Boost e SpeedStep.

Quando estiver abordando um assunto específico de cada modelo (uncore) darei preferência ao Xeon E7-8870, o modelo com qual trabalho. Conhecido como Westmere-EX, este é o absoluto top de linha da Intel em arquitetura x86 nesse ciclo de lançamentos.

Xeon E7

Processador Intel Xeon E7, Cortesia Intel

Processador Intel Xeon E7, Cortesia Intel

O Xeon E7-8870 possui aproximadamente 2.6 bilhões (!) de transístores em uma pastilha de 513 mm²; quatro portas QuickPath Interconnect (full-width)  em 3.2 GHz rodando a 25.6 GB/s full-duplex; 2 controladoras de memória DDR3 on-chip dual-channel de 10.83 GB/s cada, totalizando 4 canais e 43.3 GB/s; 10 cores – 20 threads em com hyper-threading – por socket rodando a uma frequência base de 2.4 GHz. As 4 portas QPI permitem escalar até 8 sockets em um único sistema e chegar até 2 TB de memória com DIMMs de até 32 GB.

Chip Westmere, Cortesia Intel

Chip Westmere, Cortesia Intel

Note o aumento de cores na imagem do chip Westmere em relação ao Nehalem apresentado no início do post. Se olhar atentamente, poderá perceber que se tratam dos mesmos cores, apenas replicados mais 2 vezes. É possível perceber também o aumento nos bancos de cache, abaixo dos cores.

Core i5 460M

Já o meu notebook tem uma configuração bem mais modesta e é organizado de uma forma um pouco diferente, apesar de ser baseado na mesma microarquitetura.

É um Intel Core i5 460M, codinome Arrendale, rodando a 2.53 GHz. Possui aproximadamente 382 milhões de transístores divididos entre 2 cores e o LLC (aka L3) de 4 MB, porém somente 3 MB são habilitados para esse modelo. A controladora de memória (IMC) e o gráfico ficam em outro chip no mesmo package, interligados com o chip do processador através de uma interface QuickPath Interconnect. A controladora de memória possui 2 canais DDR3 de 1.333 MHz e suportam DIMMs de até 8 GB.

Na imagem abaixo podemos visualizar o chip do processador (88mm²) e o chip “Northbridge” de aprox. 177 milhões de transístores (114mm²) no mesmo package.

Intel's Core i5 Arrandale CPU, Cortesia Intel

Intel’s Core i5 Arrandale CPU, Cortesia Intel

No diagrama de blocos podemos ver claramente a topologia entre o processador e o GPU, conectados por uma interface QPI:

Diagrama de blocos dos Clarkdale/Arrandale, Cortesia Arstechnica

Diagrama de blocos dos Clarkdale/Arrandale, Cortesia Arstechnica

Moore’s Law

Como eu falei no post anterior, o clock dos processadores parou de subir, mas o desempenho dos cores continua subindo, embora não no mesmo ritmo que subia anteriormente. Como isso é possível? Através da lei de Moore.

Gordon Moore [4] é co-fundador da Intel, e a lei leva o seu nome pois ele foi o autor da frase que dizia que o número de transistors em cada processador dobraria a cada 2 anos. Existem diversas versões e interpretações das palavras ditas por Moore. Segue a frase original [5]:

“The complexity for minimum component costs has increased at a rate of roughly a factor of two per year. Certainly over the short term this rate can be expected to continue, if not to increase. Over the longer term, the rate of increase is a bit more uncertain, although there is no reason to believe it will not remain nearly constant for at least 10 years.”

A frase pode se encontrada no artigo escrito por Moore [14], mas sem entender a relação entre defeitos, custo e integração na fabricação de chips a frase é difícil de ser digerida. Uma versão que gosto e que modifica ao mínimo a frase foi publicada no Arstechnica, em 2008 [13]:

“The number of transistors per chip that yields the minimum cost per transistor has increased at a rate of roughly a factor of two per year.”

Esse é o sentido original da frase, e a percepção do mercado de chips em geral nas últimas décadas. A frase foi dita em 1965, e apesar de Moore ter previsto a continuidade por 10 anos, a lei continua em vigor até hoje.

A frase foi dita em 1965, e apesar de Moore ter previsto a continuidade por 10 anos, a lei continua em vigor até hoje.

Gráfico do número de transístores ao longo da história, Cortesia Wikipedia

Gráfico do número de transístores ao longo da história, Cortesia Wikipedia

Essa quantidade extra de transístores é utilizada pelos engenheiros para aumentar a eficiência dos processadores. Com cada ciclo de lançamentos, os processadores ficam mais e mais complexos.

Em alguns modelos Nehalem, por exemplo, quase 60% desses transístores são dedicados aos caches, principalmente no cache L3 [12]. O restante é utilizado para adicionar mais lógica e mais funcionalidades, aumentando assim a complexidade dos chips.

Complexidade

Vista aérea de Shangai, China

Vista aérea de Shangai, China

Para se ter uma ideia da complexidade desses processadores, basta imaginar que a cidade mais populosa da China, Shangai, possui aproximadamente 16 milhões de habitantes, enquanto o processador Xeon E7-8870, como dito anteriormente, possui aproximadamente 2.6 bilhões de transístores. Ou seja, se cada morador correspondesse a um transístor, precisaríamos de 162 Shangais e meia. Isso é o dobro de toda a população da própria China, o país mais populoso do mundo.

GPGPU

Uma forma alternativa de utilizar esses transístores seria a criação de núcleos pouco complexos, porém em quantidades muito maiores do que vistos hoje, como por exemplo um processador com dezenas ou centenas de cores.

Na verdade esse tipo de arquitetura existe e é muito utilizada. É encontrada em GPUs, que possuem centenas de núcleos simples (em relação aos núcleos de uma CPU). Em geral, esses núcleos não servem para fazer o processamento de qualquer tipo de código e operação e portanto não substituem os processadores comuns, mas podem ser úteis para algoritmos onde é possível fazer paralelismo massivo do processamento. Existem várias vertentes de desenvolvimento de dispositivos, linguagens e ferramentas para aproveitar melhor esses recursos como o NVIDIA CUDA, OpenCL e mais recentemente o C++AMP da Microsoft, do qual já falei por aqui.

Esse tipo de processamento, chamado de General-purpose computing on graphics processing units, ou GPGPU, ainda não é utilizado pelos SGBDs, mas já existem pesquisas nesse sentido, como pode ser visto em [8] e [9].

Cache

Agora que já fizemos uma introdução básica às CPUs, no próximo artigo vamos nos aprofundar um pouco no assunto dos caches.

Até a próxima. ;)

Referências

[1] http://en.wikipedia.org/wiki/Nehalem_(microarchitecture)
[2] http://en.wikipedia.org/wiki/Intel_Tick-Tock
[3] http://forwardthinking.pcmag.com/pc-hardware/283044-intel-looks-ahead-nehalem-larrabee-and-atom
[4] http://en.wikipedia.org/wiki/Gordon_Moore
[5] http://en.wikipedia.org/wiki/Moore’s_Law
[6] http://www.xbitlabs.com/articles/cpu/display/core-i7-920-overclocking_3.html
[7] http://www.extremetech.com/extreme/133541-intels-64-core-champion-in-depth-on-xeon-phi
[8] http://sacan.biomed.drexel.edu/vldb2012/program/?volno=vol5no13&pid=1004&downloadpaper=1
[9] http://wiki.postgresql.org/images/6/65/Pgopencl.pdf
[10] http://asia.cnet.com/blogs/intel-invests-us7-billion-in-32nm-westmere-cpu-manufacturing-62114335.htm
[11] http://www.intel.com/pressroom/kits/advancedtech/doodle/ref_HiK-MG/high-k.htm
[12] http://upcommons.upc.edu/e-prints/bitstream/2117/13932/1/hybrid_NUCA-hipc11.pdf
[13] http://arstechnica.com/gadgets/2008/09/moore/
[14] http://www.computerhistory.org/semiconductor/assets/media/classic-papers-pdfs/Moore_1965_Article.pdf

Pin It

Série – Inside The Machine – Introdução

Quando você pensa na memória do seu servidor, qual é a primeira coisa que te vem à cabeça? Gigabytes? Terabytes? Enfim, espaço? E quando você pensa em desempenho, a primeira coisa que você pensa são os Gigahertz da CPU?

Nessa série de artigos quero explorar o subsistema de memória de um ponto de vista um pouco diferente: o foco será a interação entre ele e a CPU. Falaremos do desempenho da memória e como ela pode afetar – e afeta! – o desempenho como um todo do seu servidor, e o que você pode – e não pode – fazer a respeito em relação ao seu banco de dados (ou qualquer outra aplicação).

Confesso que essa série estava parada no meu OneNote há algum tempo. Conversando com o meu amigo Luan Moreno recentemente cheguei a conclusão que era hora de tirar a poeira e postá-los. :)

Velocidade do processador é tudo?

Se você não conhece Martin Thompson, recomendo adicionar o blog ao seu leitor de RSS favorito e acompanhar o que ele escreve e palestra. Ele é definitivamente uma das grandes referências no assunto de HPC (High Performance Computing) e baixa latência e vamos utilizar alguns testes escritos por ele (e alguns meus) durante essa série, então nada mais justo do que começar fazendo referência a uma frase sua: “The real design action is nn the memory sub-systems.” [2]

Você já percebeu que ultimamente têm sido bastante falado sobre a velocidade dos processadores e como seu desempenho parou de evoluir nos últimos anos em favor do aumento da quantidade de cores? Quem desenvolve software com certeza já ouviu que deve aprender desenvolvimento de software com paralelismo para não arriscar ficar sem emprego no futuro. A famosa frase “the free lunch is over” tem sido repetida diversas vezes nas últimas conferências mundo à fora desde que o guru de C++ Herb Sutter escreveu o seu artigo homônimo em 2005 para o respeitado journal Dr. Bobb’s [1].

De fato a frequência dos processadores parou de subir, principalmente devido às questões de economia de energia e dissipação de calor, como é possível observar claramente no gráfico abaixo tirado do artigo de Sutter:

Intel CPU Trends Chart

Intel CPU Trends 1970-2010. Fonte: The Free Lunch Is Over, Herb Sutter

Mas olhar apenas para os GHz não conta toda a história.

Linha Modelo Ops/Sec Ano de Lançamento
Core 2 Duo  P8600 @ 2.40GHz 1434 2008
Xeon  E5620 @ 2.40GHz 1768 2010
Core i7  i7-2677M @ 1.80GHz 2202 2011
Core i7  i7-2720QM @ 2.20GHz 2674 2011

Podemos observar na tabela acima que o desempenho geral do CPU continua subindo, mesmo que a frequência esteja, de certa forma, estagnada. Medimos esse desempenho através de IPCs, ou Instructions per Cycle.

Ou seja, em um processador de 2 GHz capaz de fazer o retirement de até 4 instruções por ciclo (IPC), como é o caso da microarquitetura Nehalem, no caso ideal o seu desempenho pode chegar a 8 bilhões de instruções por segundo! Nada mal.

Single Threaded Performance Trends Chart

Single Threaded Performance Trends 1995-2011 [3]

Então se o desempenho das CPUs efetivamente continua subindo (apesar de claramente em um ritmo menor) mesmo que os clocks se mantenham estáveis, quem é o responsável por segurar o desempenho geral dos sistemas?

Refazendo a pergunta anterior de outra forma… Em um workload onde o gargalo não se encontra nem em I/O nem na CPU, o que impede o seu processador de realizar o trabalho mais rapidamente?

Você provavelmente já deve ter matado a charada: no acesso à memória, ou o que chamamos de latência. Mas esse fato não parece ser muito óbvio à primeira vista: memória não é só uma questão de quantidade.

Latência? E acesso à memória lá tem custo?!

Em relação ao custo de acesso ao disco, a latência do acesso à memória é irrisório.

A memória, porém, é o que previne que o seu sistema rode em seu desempenho máximo. Isso ocorre pois o acesso à memória é significativamente inferior à velocidade do processador, e essa diferença só cresceu ainda mais nas últimas décadas. Esse fenômeno é chamado de “Memory Wall“, termo cunhado no paper [4].

Se pudéssemos trabalhar com dados apenas nos registradores, a “memória” com a menor latência no CPU, o nosso processador poderia utilizar todo o seu potencial computacional. Infelizmente, principalmente em servidores de bancos de dados, isso está muito longe da realidade. É comum trabalharmos com working sets de dezenas ou centenas de GB. E por isso pagamos o custo de acesso à memória o tempo todo. Enquanto esse acesso ocorre, o processador precisa ficar esperando pelos dados até que ele possa voltar a trabalhar, efetivamente gastando ciclos de clock à toa. Um cache miss pode custar centenas de ciclos de clock do processador, tempo que ele poderia gastar realizando operações ao invés de esperar por dados para serem processados.

Com o fim da era de crescimento contínuo dos clocks dos processadores os engenheiros têm evoluído as microarquiteturas a fim de amenizar o impacto da latência do acesso à memória principal do sistema. Os processadores se utilizam de diversos artifícios para esconder essa latência, e assim diminuir a penalidade causada pela disparidade entre o desempenho entre eles. Já falei sobre um deles aqui, o Hyper-Threading (SMT). Ao longo da série, são esses mecanismos, artifícios e otimizações que vamos tratar, além de outros assuntos que estejam relacionados.

Seguem alguns dos tópicos que tenho planejado para essa série:

  • Microprocessadores
  • Latência
  • Caches e Hierarquia da memória
  • Intel SpeedStep e Turbo Boost
  • Hyper-Threading (SMT)
  • FSB e NUMA
  • Superscalar
  • Pipelining
  • Spinlocks & Latches
  • Algoritmos e Otimizações no SQL Server 2014

Tentarei seguir a lista acima, mas vou manter a possibilidade de inserir, mesclar ou remover tópicos conforme a série se desenvolve. Manterei a lista atualizada de acordo, incluindo atualizações (adição de tópicos, etc.) e links para os artigos conforme vão sendo lançados. Portanto se quiser acompanhar você pode marcar essa página nos seus favoritos, ou adicionar o feed do blog ao seu leitor RSS favorito, como preferir.

Referências:

[1] Sutter – The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software
[2] Thompson – Mythbusting modern hardware to gain “Mechanical Sympathy”
[3] Moore – Data Processing in Exascale-class Computing Systems
[4] Wulf, McKee – Hitting the Memory Wall: Implications of the Obvious

Pin It

Hyper-Threading (SMT) e SQL Server

Semana passada postaram uma pergunta muito interessante na lista de SQL Server Nimbus Advanced, que participo. Pela própria natureza do assunto que o torna interessante para um grupo de pessoas além dos que participam da lista, e o fato de que a resposta que eu estava escrevendo acabou crescendo um pouco, acabei decidindo transformá-lo em um post. :)

Hyper-Threading (SMT) e SQL Server

Muito interessante o asssunto. Vamos por partes…

O principal fator que vai definir o impacto do HT no seu ambiente é o seu workload – tanto positivamente quanto negativamente.

Intel Core i7 logoA própria Intel limita o ganho teórico do HT a 30% [1]. Isso é, no melhor do melhor dos casos, o máximo de desempenho que você vai “ganhar” com HT é 30%. É pouco? Não acho. Mas o que eu acho é que HT é muitas vezes confundido como uma funcionalidade de desempenho quando na realidade é uma funcionalidade que visa melhorar a eficiência do seu processador. Ele vai utilizar alguns ciclos a mais que teriam sido perdidos caso não houvesse um “pipeline” substituto pronto para entrar em cena. Não há ganho, e sim “controle de perda”. :)

HT nada mais é do que a duplicação de alguns componentes do pipeline do núcleo, permitindo que esse, no melhor caso, não pare totalmente de trabalhar quando houver uma dependência ainda não disponível durante a execução, como um acesso de memória que resultou em cache miss, por exemplo.

Pipeline wih and w/o SMT

Pipeline (SMT)

Teoria e prática

Ok, mas saindo um pouco da teoria e indo para a parte prática, muitas coisas começam a influenciar na brincadeira.

O próprio escalonamento do Windows (e de tabela o do SQL Server) afeta o desempenho do sistema com o HT habilitado ou não. Por exemplo, se o algoritmo do scheduler não levar em conta o fato de dois “núcleos lógicos” (por falta de nome melhor) compartilharem os mesmos ALUs o seu desempenho vai piorar sensivelmente quando o scheduler escalonar duas threads no mesmo núcleo físico ao invés de núcleos físicos distintos.

Esse cenário era muito comum nos primórdios do Windows Server [2], quando este não fazia distinção entre núcleos físicos e lógicos. Ainda vemos algo parecido hoje nos processadores oriundos da microarquitetura Bulldozer da AMD, que utiliza uma tecnologia que também afeta o comportamento do pipeline, mas não é exatamente uma implementação do SMT. Os schedulers não estavam preparados para lidar com isso durante o lançamento dos processadores dessa microarquitetura, fazendo a AMD sofrer em alguns benchmarks [3].

Trocando em miúdos, existem muitos fatores e o impacto no desempenho final pode ser bem maior do que os 30% teóricos, tanto positivamente quanto negativamente.

Mito

Existe um mito que o Hyper-Threading é o mal encarnado para o SQL Server, devido a diversos fatores, incluindo os citados acima. Um dos causadores (não intencional) desse rumor foi o Slava Oks [4] (ex-time de produto, SQLOS), e se você quiser ver um ótimo exemplo de como fazer o HT não funcionar, sugiro que leia o seu post e execute os testes você mesmo.

Processadores

Agora vamos para a questão de desempenho de processadores…

Observando o processo do SQL Server (sqlservr.exe) podemos notar que ele possui callstacks bastante profundas, de pelo menos uns 8 níveis desde o início do processamento de uma consulta, e muitos branches ao longo da execução dessa consulta, mesmo simples. Servidores OLTP, em geral, costumam ter um working set de GBs de dados em memória e processar pequenas partes dessa massa à cada segundo, de forma “aleatória”. Na teoria [5], esses tipos de cenários são excelentes candidatos a fazer um bom uso do SMT e também são bastante influenciados pelo tamanho dos caches do processador, a latência de acesso da sua memória RAM e a eficiência do branch predictor. Esses fatores podem até mesmo influenciar mais que o próprio clock do seu processador… Nada de comprar processadores olhando apenas os GHz!

Workloads de OLAP e aplicações científicas , por outro lado, tendem a ser mais sensíveis à “força bruta” do processador.

Enfim… No final das contas, a única coisa que vai te dizer se o HT pode ou não beneficiar o seu ambiente é o teste. São fatores demais que influenciam no resultado final para fazer uma previsão para qualquer direção. Se você tiver um processador com HT, teste seu workload com e sem o HT habilitado e colete métricas que te dirão qual é preferível.

No caso do seu processador não possuir a funcionalidade, só posso dizer que não se preocupe com isso. Há formas mais práticas e diretas de influenciar o desempenho do seu ambiente.

Referências:

[1] http://en.wikipedia.org/wiki/Simultaneous_multithreading#Modern_commercial_implementations
[2] http://www.hardwaresecrets.com/article/Activating-the-Hyper-Threading/20
[3] http://www.hardwarecanucks.com/news/cpu/microsoft-tries-again-second-win-7-bulldozer-hotfix-now-available/
[4] http://blogs.msdn.com/b/slavao/archive/2005/11/12/492119.aspx
[5] http://www.cs.washington.edu/research/smt/papers/smtdatabase.pdf

Pin It

Está chegando! SQLSaturday #253 Brasília

Como alguns já sabem, esse ano teremos o evento PASS SQLSaturday de número 253, aqui em Brasília!

PASS SQLSaturday #253 - Brasília Logo

PASS SQLSaturday #253 – Brasília

Organizado por um dos regional mentors do PASS no Brasil, Luciano Moreira, o evento contará com  a participação de diversos palestrantes de renome e algumas novas caras que são muito bem vindas à nossa comunidade.

Tive a honra de participar da organização do evento e montamos a agenda da melhor forma possível para que os participantes pudessem aproveitar ao máximo o conteúdo de alto nível digno de um evento desse calibre.

Teremos, além das tradicionais trilhas de Desenvolvimento (Dev), Administração (DBA) e Business Intelligence (BI), uma trilha especial Acadêmica para quem está iniciando no mundo de SQL Server e Bancos de Dados em geral:

Agenda SQLSat #253

Agenda provisória do evento

O evento ocorrerá no dia 28 de Setembro de 2013 e já possui mais de 400 inscritos. Portanto  se você tem interesse em participar, não deixe de fazer sua inscrição o mais rápido possível!

Para mais informações, acesso o blog do Luti e o site do evento.

Te espero lá!

Pin It

SQL Server XTP (Hekaton) – Hash Indexes

Recentemente no TechEd 2013 a Microsoft anunciou o SQL Server 2014, e a funcionalidade do momento com certeza é o Extreme Transaction Processing (conhecido anteriormente pelo codinome Hekaton).

Eu gostaria de tomar esse momento e falar um pouco sobre uma característica da implementação do XTP em particular que me chamou a atenção: é o primeiro mecanismo do SQL Server que permite trabalharmos com índices hash (mas não apenas hash! Mais sobre isso adiante.)

Um ponto interessante em relação aos indexes hash é que, em geral, os DBAs SQL Server não estão muito acostumados com eles, justamente por ser uma “novidade” no produto.

Novidade?

Apesar de no SQL Server não termos índices Hash para dados (apenas B+Trees), a hash table é uma estrutura de dados bastante comum na ciência da computação. A própria engine do SQL Server utiliza hash tables (internamente) para diversas tarefas de gerenciamento. Alguns exemplos que me vêm a mente são a manutenção de lista de estruturas BUF (que apontam para as páginas do Data Cache) e também o Plan Cache, mas com certeza existem (diversos) outros.

E não sou nenhum especialista no assunto, mas acredito que no Oracle é possível criar índices tanto B+Tree como Hash há algum tempo.

Mas o que vem a ser uma estrutura de Hash table e como ela se compara com estruturas B+Tree?

Hash tables – Conceitos gerais

Primeiramente, e diferentemente das B+Trees, as hash tables são estruturas que se encaixam na definição de vetores associativos. Isto é, elas armazenam dados de forma não ordenada e no formato de pares de Key-Value: chaves e valores.

Hash Table - Collision Chain

Hash Table - Cadeia de Colisão

Alguns desses pontos são bastante importantes, portanto vamos discutir um pouco mais sobre eles e diferenciá-los da B+Tree.

Os valores em vetores associativos, em particular as hash tables, são divididos em slots chamados de Buckets. Cada bucket corresponde a um valor de hash único: a chave. Cada Bucket pode conter diversas entradas. Se duas linhas geram valores de hash iguais (e portanto apontam para o mesmo Bucket) nós temos o que chamamos de colisão.

Se houver uma colisão a implementação da hash table deve realizar algum tipo de esforço adicional para garantir a integridade dos dados (eg. não sobreescrever o valor já contido no bucket). No paper [1] a Microsoft fornece alguns detalhes sobre a implementação do mecanismo de gerenciamento de colisão do XTP. Se você tiver interesse em saber mais sobre o assunto em particular e a implementação do mecanismo de MVCC, dê uma olhada nesse paper.

Função de Hash

A escolha de uma função de hash adequada é de suma importância para uma implementação efetiva de uma hash table. Uma função muito forte pode gerar hashes muito grandes e consumir muito espaço, além de maior utilização da CPU para aplicá-la. Já uma função hash muito fraca pode salvar espaço e CPU, mas fará com que exista um número muito grande de conflitos, causando o que chamamos de clustering, onde grande quantidade de dados é mapeada para poucos Buckets, o que também não é desejável.

Função de Hash

Função de Hash

Como são os valores dos hashes que determinam a posição na tabela onde o valor será armazenado, é através desse hash que a estrutura é “fisicamente ordenada”, e não através do valor em si. Na teoria, é possível construir uma função de hash que preserve a ordem das suas chaves, mas na prática isso geralmente é inviável. Para todos os efeitos, assuma que hash tables não mantém chaves de forma ordenada. Portanto temos uma tabela onde a chave “1” pode estar armazenada no meio da estrutura, enquanto a chave “8192032” poderia estar armazenada no primeiro Bucket.

A escolha de uma função de hash adequada é de suma importância para uma implementação efetiva de uma hash table.

Pela sua própria estrutura as hash tables são ótimas candidatas para realizar buscas de igualdade.

SELECT * FROM table WHERE key = 8192032

No geral a complexidade de uma busca de igualdade em uma hash table é O(1), ou seja, é constante¹. Basta que a função de hash seja aplicada ao valor de search argument (SARG), nesse caso 8192032, para gerar o endereço do Bucket e então recuperar o valor do mesmo.

Em comparação à B+Tree, não existe navegação entre diversos níveis da estrutura², uma vez que a mesma não é uma árvore e sim um vetor, como dito no início do artigo.

Existe porém a navegação entre a cadeia de colisão, já que há a possibilidade de que existam vários valores para o mesmo hash (Bucket), ou ainda vários valores repetidos para a mesma chave (caso a coluna não seja chave primária).

Para buscas de desigualdade (ex.: maior que, menor que, !=, NOT IN, etc.), porém, as hash tables não trabalham bem.

SELECT * FROM table WHERE key > 10

Se você não sabe exatamente qual é o valor que está procurando, não é possível calcular o hash desse valor (uma vez que é desconhecido) e portanto não é possível encontrar o valor desejado a menos que se percorra toda a estrutura do índice, ie. realize um scan. Isso é o que chamamos de complexidade linear: O(n) onde n é o número de linhas (pares key-value) armazenados nessa hash table. Para encontrar um valor desconhecido X é necessário percorrer todas as n linhas da tabela.

Esse ponto é importante pois esclarece a principal fraqueza das hash tables em cenários de bancos de dados: não é possível realizar buscas por ranges de forma eficiente em hash tables!

O que isso quer dizer, afinal? Quer dizer que um banco de dados implementado apenas com hash tables não seria um banco de dados eficiente³. E é por isso que a Microsoft introduz também no XTP (Hekaton) uma nova estrutura de índice chamada de Bw-Trees[2].

Mas vamos deixar as Bw-Trees para outro post… Nesse momento quero entrar na parte prática das hash tables como implementadas no SQL Server 2014.

Implementação no SQL Server 2014

Aproveitei os testes que estive realizando no Windows Azure esse mês e hoje configurei uma nova máquina virtual com o SQL Server 2014 CTP1 pré-instalado.

Aqui estão alguns itens interessantes que verifiquei nesse primeiro momento. De forma alguma essa lista é exaustiva, e tenha em mente que pelo fato dos testes terem sido realizados em uma versão pré-release do SQL Server, algumas coisas  podem mudar até a release final.

Algumas limitações que notei na implementação atual:

  • Colunas Nullable não são suportadas com índices
  • Nada de default constraints para tabelas XTP
  • Identity também ainda não é suportado, mas pela mensagem de erro deve ser implementado em breve.
  • STATISTICS IO é ignorado em tabelas XTP
  • Não consegui criar índices hash em campos char e varchar
  • Hash indexes são permitidos apenas em tabelas XTP (o que era de se esperar, mas nunca se sabe… ;))

Na criação da tabela a sintaxe permite configurar um valor qualquer para a quantidade de Buckets de um determinado índice hash, mas efetivamente o SQL Server sempre vai criar com 16 ou mais Buckets.

CREATE TABLE TabelaXTP (
 C1 INT NOT NULL,
 C2 CHAR(100) NOT NULL,
 C3 VARCHAR(100) NOT NULL
 CONSTRAINT PK_TabelaXTP PRIMARY KEY HASH (C1)
  WITH (BUCKET_COUNT = 16)
) WITH (MEMORY_OPTIMIZED = ON);
GO

A quantidade de Buckets por hash table cresce de forma exponencial com base 2, começando pelo valor mínimo de 16. Ou seja, podemos ter hash tables com um número de Buckets de 16, 32, 64, 128, 256, etc.

O número de buckets sempre arredonda para cima. Se você tentar criar um hash index com 17 buckets, o SQL Server irá criá-lo com 32, sem exibir nenhuma mensagem de alerta ou erro.

A maior hash table que consegui criar hoje tinha um total de 1.073.740.000 buckets. Na prática não acredito que eu vá usar essa quantidade de buckets tão cedo. Haha :)

O operador de Index Scan (NonClusteredHash) permite observar a quantidade de Buckets em um índice hash através do campo TableCardinality. Ou seja, a cardinalidade da hash table.

TableCardinality - Execution Plan Property

Cardinalidade da hash table

A utilização de memória por parte dos índices do Extreme Transaction Processing pode ser monitorada através dos novos Memory Objects MEMOBJ_XTPDB e MEMOBJ_XTPBLOCKALLOC e no Clerk MEMORYCLERK_XTP.

New SQL Server 2014 Memory Clerks

Novo Memory Clerk de XTP

Os índices hash utilizam espaço do Buffer Pool mesmo que vazios, por conta dos buckets. Por isso tome muito cuidado ao criar índices hash com um número excessivo de buckets! Nesse meu teste acima o índice consumiu sozinho mais de 10 GB de memória.Lembrando: ele estava vazio!

New SQL Server 2014 XTP Memory Objects

Novos Memory Objects do SQL Server 2014 - XTP

Se você tem interesse em se aprofundar mais em hash tables, em particular em relação à implementação da Microsoft de lock-free hash tables, recomendo o paper [3] além dos outros dois já referenciados nesse post.

Benchmarks

Infelizmente não é possível utilizar o STATISTICS IO para visualizar as leituras lógicas do acesso a um índice hash, mas já realizei alguns testes através dos Extended Events e assim que tiver resultados conclusivos pretendo compartilhá-los por aqui. Quem sabe aproveito e falo um pouco sobre os novos objetos de Extended Events do XTP também, se entender como funcionam até lá… Hahaha :)

¹ No geral, porque em alguns casos onde há conflito excessivo de chaves a complexidade será maior;
² Raiz, níveis intermediários e folhas;
³ Salvo cenários onde é desejável a realização de 100% scans no lugar de seeks por questões de eficiência de I/O sequencial;

[1]: http://research.microsoft.com/apps/pubs/default.aspx?id=193594
[2]: http://research.microsoft.com/apps/pubs/default.aspx?id=178758
[3]: http://www.research.ibm.com/people/m/michael/spaa-2002.pdf

 

Pin It

Está chegando: 24 Horas de PASS Português!

Pessoal, esse mês teremos o primeiro evento 24 Hours de PASS em Português em conjunto com os nossos amigos de Portugal!

Logo - 24 Hours de PASS

24 Horas de PASS - Português

Para quem não conhece, o 24HOP é um evento gratuito e você pode acompanhar tudo on-line. Com duas rodadas de 12h non-stop de SQL Server entre os dias 27 e 28 desse mês, tendo início às 11h de Brasília (ou 13h de Portugal, se você estiver do lado de lá do Atlântico.)

As comunidades Brasileira e Portuguesa prepararam diversas apresentações, e como sempre a Sr. Nimbus não poderia deixar de participar. Nós vamos marcar presença com algumas palestras, sendo que a primeiríssima palestra do evento será nossa! Mais precisamente dos nossos amigos e colegas Fabiano Amorim (Twitter | Blog) e Gilberto Uchôa (Blog):

Sessão 01 – 11:00 (13:00 GMT)
"T-SQL Expert – Escrevendo códigos “like a Boss”"
Fabiano Amorim & Gilberto Uchôa

A agenda com todas as palestras pode ser encontrada no site do PASS. Dá só uma olhada no pessoal que estará apresentando!

Então não deixe de assistir e aproveite pra aprender bastante SQL Server com os melhores profissionais da área! :)

Pin It