Fora do Quadrado com Java NIO e Binary Search

Primeiramente, boas vindas pessoal !!      

Este é o meu primeiro post… primeiro de muitos. Obrigado aos meus colegas de trabalho @rafanoronha e @alnascimento por me incentivarem constantemente na criação do meu blog.      

 Neste primeiro assunto vou mostrar um caso real de software que ocorreu em um projeto do nosso time no Software Delivery Center na Stefanini, onde tive o prazer de dar alguns pitacos técnicos. Tinhamos uma funcionalidade em que precisávamos localizar uma determinada lista de palavras dentro de um dicionário de aproximadamente 70 mil palavras (não podíamos utilizar Lucene e o sistema era intranet).      

Primeira solução imaginada… no quadrado… vamos subir estas palavras no nosso poderoso Oracle, criar um mega índice na palavra, que a busca será super rápida. E realmente era rápida… eh… para até umas 10 palavras. Quando testávamos um texto razoável de 200 palavras, o tempo de busca já ia pra ordem de minutos, o que ra inviável em produção. Aí já viu… faz mais índice, segmenta em tabelas separadas, enche de if, parseia via procedure, diversas tentativas e nada.      

Foi quando percebi que precisava encontrar uma solução fora do quadrado… deitado na minha cama, pensei… Oracle ? Pra que ?! Quem precisa de Oracle ? Por acaso o Google indexa sua base de sites no Oracle ?! Acho que não ! Logo me veio em mente, vamos indexar isso em arquivo texto! Todos sabem que IO no disco é muito mais rápido que ir no banco, não tem controles de conexão, sessões, camadas de rede no meio… é tudo alí, na lata.       

Solução: Java NIO + Binary Search  … vamos entender porque.       

Java NIO      

Muitas pessoas não sabem que este recurso existe, muito menos conhecem seu poder. A maioria dos desenvolvedores utilizam o velho IO, baseado em Streams (xxxInputStream, xxxOutputStream)… o problemas dos Streams é que eles são baseados em bytes de forma unitária. Um Stream comum faz operações de IO byte-a-byte, e são unidirecionais (ou é input, ou é output).      

A partir do JDK 1.4, foi introduzida a API Java New IO (NIO), que trouxe o poder do IO de baixo nível para o java. Alguns autores brincam que ela deveria se chamar de LLIO (Low-Level IO) ao invés de NIO. O principal diferencial desta nova API é que ela trabalha com blocos de bytes (buffers) e canais (channels). Fazer operações de IO com blocos de bytes é muito mais rápido que fazer byte-a-byte… os channels são bidirecionais, o que é muito mais natural pois é como o Sistema Operacional trabalha. Sem contar da capacidade de implementar non-blocking-io e utilizar recursos a nível de SO, como as Mapped Files, que são a base da nossa solução desenvolvida.       

Problema 1: como gerar o arquivo texto ?       

Ora… esta é fácil… fazemos um batch que roda 1 vez por dia, de madrugada. Tudo que ele tem de fazer é um “SELECT *” na tabela de palavras e gravar num arquivo texto, com um número fixo de bytes por registro (palavra), para podermos encontrá-los facilmente no arquivo. E o mais importante…. o “ORDER BY” ! Um dos truques sa solução é gerar o arquivo de palavras ordenado em ordem alfabética, para podermos aplicar o famoso algoritmo da Busca Binária (ou Binary Search).      

Problema 2: como garantir acesso rápido do IO ao arquivo ?       

Aqui utilizamos o poder do NIO, através das Mapped Files. Este é um recurso poderosíssimo, talvez este post não seja o suficiente para entender a fundo… requer um pouco de conhecimento sobre SO. Mas em resumo, consiste no seguinte… quando fazemos um IO comum para ler um arquivo, os bytes do arquivo são trazidos para um buffer intermediário na memória, e este buffer é lido na aplicação. Ou seja, em um Random Access File, para se posicionar no meio do arquivo por exemplo, este buffer precisa ser percorrido até chegar no ponto desejado.      

O recurso das Mapped Files consiste em utilizar o próprio mapeamento do arquivo no FileSystem para identificar os bytes do arquivo, ou seja, não são criados buffers intermediários. É criado um mapeamento do arquivo na memória virtual que fica sincronizado com o mapeamento do arquivo no FileSystem:      

Mapped Buffer
Mapped Buffer

O que acontece de engraçado:    

  • Qualquer alteração no objeto de buffer reflete diretamente no arquivo no disco (você está trabalhando no filesystem, oras !) 
  • Mesmo para mapear um arquivo de vários gigas é consumida pouquíssima memória, pois são utilizados os recursos de cache e paginação comuns do filesystem. Na hora da leitura efetiva do arquivo, ela é feita sobre demanda.
  •  Sua paginação é sincronizada, ou seja, não são criados buffers intermediários.
  • Se o arquivo for modificado após ter sido mapeado, irão ocorrer exceptions ao fazer a leitura. Portanto, ou fazemos o lock via código, ou garantimos que o arquivo não será modificado durante a leitura. Se for modificado, temos que mapeá-lo novamente antes de ler.
  • Não ocupa quase nada do Heap da JVM para mapear o arquivo. É tudo feito a nível de SO e memória virtual.
  • O mapeamento é liberado quando o objeto do buffer é recolhido pelo Garbage Colector (e não quando fechamos o channel).

  

Problema 3: como localizar a palavra rapidamente ?       

Em uma busca convencional, teriamos que ler palavra por palavra, e comparar cada uma com a palavra que buscamos, até encontrá-la (ou não). Absurdo ! Ordenamos justamente para utilizar um modo mais performático… a Busca Binária. Com este algorítimo, descartamos as palavras de metade em metade, conseguindo um match com pouquíssimas comparações. O NIO garantirá acesso rápido a qualquer posição de byte dentro do arquivo (pois sabemos quantos bytes cada palavra ocupa). Conseguimos encontrar uma palvravra em 70 mil com algo em torno de apenas 17 comparações.      

Produto Final: GibaBizarreSearch.class  

  

public class GibaBizarreSearch {
 private final int tamanhoRegistroInBytes;
 private final int tamanhoPagina;
 private final File file;
 private final String charset; 

 private List<MappedByteBuffer> buffers; 

 public GibaBizarreSearch(File file, String charset, int tamanhoRegistroInBytes) throws IOException {
  if (tamanhoRegistroInBytes <= 0) {
   throw new IllegalArgumentException("O tamanho do registro em bytes deve ser maior que zero.");
  } else if (file == null) {
   throw new IllegalArgumentException("O objeto file não pode ser nulo.");
  }
  this.tamanhoRegistroInBytes = tamanhoRegistroInBytes;
  this.tamanhoPagina = (Integer.MAX_VALUE / tamanhoRegistroInBytes) * tamanhoRegistroInBytes;
  this.file = file;
  this.charset = charset;
 }
 
 public void mapear() throws IOException {
  if (!file.exists()) {
   throw new IllegalStateException("O arquivo indicado para leitura não existe.");
  } else if (!file.isFile()) {
   throw new IllegalStateException("O arquivo indicado para leitura não é um arquivo.");
  } else if (!file.canRead()) {
   throw new IllegalStateException("O arquivo indicado para leitura não pode ser lido, verifique as permissões no SO.");
  }
  
  this.buffers = new ArrayList<MappedByteBuffer>();
  FileChannel channel = (new RandomAccessFile(file, "r")).getChannel();
  
  long channelSize = channel.size();
  long inicio = 0;
  int tamanho = 0;
  for (long i = 0; inicio + tamanho < channelSize; i++) {
   if ((channelSize / tamanhoPagina) == i) {
    tamanho = (int)(channelSize - i * tamanhoPagina);
   } else {
    tamanho = tamanhoPagina;
   }
   inicio = i * tamanhoPagina;
   MappedByteBuffer pagina = channel.map(FileChannel.MapMode.READ_ONLY, inicio, tamanho);
   buffers.add(pagina);
  }
  
  channel.close();
 }
 
 public void desalocar() {
  if (buffers != null && !buffers.isEmpty()) {
   buffers.clear();
   buffers = null;
  }
 }
 
 public long buscar(String texto) throws UnsupportedEncodingException {
  if (buffers == null) {
   throw new IllegalStateException("O arquivo não foi mapeado.");
  }
  
  long posicaoAchou = 0;
  for (int i = 0; i < buffers.size(); i++) {  
   MappedByteBuffer buf = buffers.get(i); 

   int qtdRegistros = buf.limit() / tamanhoRegistroInBytes;
   
   byte[] registro = new byte[tamanhoRegistroInBytes];
   int inf = 0;
   int sup = qtdRegistros - 1;
   int meio = -1; 

   posicaoAchou = 0;
   while(inf <= sup && posicaoAchou == 0) {
    meio = (int)(inf + sup) / 2;
    buf.position(meio * tamanhoRegistroInBytes);
    buf.get(registro, 0, tamanhoRegistroInBytes);
    String valor = new String(registro, charset).trim();
    if (texto.compareTo(valor) > 0) {
     inf = meio + 1;
    } else if (texto.compareTo(valor) < 0) {
     sup = meio - 1;
    } else {
     posicaoAchou = meio + 1;
    }
   } 

   if (posicaoAchou > 0 || meio != qtdRegistros - 1) {
    if (posicaoAchou > 0) {
     posicaoAchou += i * (tamanhoPagina / tamanhoRegistroInBytes);
    }
    break;
   }
  } 

  return posicaoAchou;
 } 

}  

 

Explicação:  

  • Construtor: inicializa as variáveis e define o tamanho máximo da página que seja divisível pelo tamanho do registro. O tamanho máximo que podemos mapear num buffer é o range do int (Integer.MAX_VALUE). Portanto, caso o nosso arquivo tenha um tamanho em bytes que exceda este valor (tipo alguns gigas), precisamos dividi-lo em mais buffers. Porém, não podemos cortar um registro no meio e deixar uma parte em cada página, por isso esta divisão.
  • mapear(): verifica quantas páginas (buffers) são necessárias para mapear o arquivo. A chamada channel.size() retorna o tamanho total do arquivo em bytes. Este método apenas decide quantas páginas serão necessárias para mapear o arquivo inteiro, de acordo com o tamanho máximo da página que definimos no construtor. Ele realiza então os mapeamentos, e guarda cada página em um buffer da lista. Apenas arquivo muito grandes precisarão de mais de um buffer.
  • desalocar(): remove o mapeamento. Vimos que fechar o channel não influencia em nada no mapeamento. Se quisermos desfazer o mapeamento, temos que deixar os buffers elegíveis ao Garbage Collector.
  • buscar(String): efetua a busca binária e retorna a posição em que o registro (ou neste caso palavra) foi encontrada, e caso não encontre, retorna zero 0. Note que existe ao final uma consistência para verificar se existe a necessidade de abrir o próximo buffer, pois como está ordenado, se a palavra não foi encontrada em um buffer e for menor que as palavras do próximo buffer, nem precisa verificá-los pois é fato que ela não existe. Ao final existe um pequeno ajuste para adequar a posição do registro de acordo com o número do buffer atual (ex.: se é o registro de posição 5 do segundo buffer, e cada buffer tem 10 registros, então na verdade é o registro de posição 15).

Fica aqui um incentivo ! Vamos pensar fora do quadrado !

Advertisements

11 thoughts on “Fora do Quadrado com Java NIO e Binary Search

  1. William M. 03/25/2010 / 8:50 AM

    Sem comentários, para falar a verdade o Giba dispensa comentários …rsrs
    O nome da classe diz tudo GibaBizarreSearch

  2. Leonardo Neves 03/25/2010 / 1:47 PM

    Fazia tempo que eu não lia um artigo tecnico “desse nivel” Giba, hehehe… Só vindo de vc mesmo!

    Parabéns pelo blog. Sucesso nessa nova empreitada.

    Abraços!

  3. Jonas 03/25/2010 / 3:37 PM

    ADO AADO cada um no seu quadrado !

    Muito bom, sucesso no blog !

    Não nos deixe ficar sem esse tipo de “bizarrice” search ou não, poste sempre, assuntos interessantes como este são muito bem vindos.

    Abraço.

  4. André Nascimento 03/25/2010 / 4:11 PM

    Grande Giba !!!! Meus parabéns pelo blog, você tinha que começar destruindo né? auhauahu.

    Muito sucesso pra você rapaz… e vê se coloca um post de “inauguração” agora, vai…

    Abs

    André Nascimento

  5. Rafael Noronha 03/25/2010 / 10:17 PM

    Isso é o que eu chamo de escovar os bits.

    Excelente inauguração, já mostrou a que veio. 🙂

  6. Felipe Rojas 03/27/2010 / 1:20 AM

    Boa iniciativa do blog giba! Arrebentou no post!

    Abraço rapaz.

  7. Gisele 03/28/2010 / 10:43 PM

    Mor não entendi nada do que vc falou, mas sei que deve estar muito bom!!!

    Bjuuu!!!! Te amo!!!!

  8. Felipe 04/09/2010 / 4:12 PM

    É… vou imprimir, mostrar pra minha mãe e dizer que fui eu quem fiz!!! rsrsrs….
    Decididamente… o cara não sabe brincar!!!

  9. Alexandre 07/15/2010 / 3:16 PM

    Idéia muito interessante cara!! Estudarei ela mais um pouco e tentarei implementar!!!
    Parabéns!!! Show!!!

  10. Daniel 09/10/2013 / 6:20 PM

    E ae cara, meu amigo recomendou a sua solução e achei fantástica, mas vc acha que dária para “adaptá-la” para uma busca fonética? Abraços e Excelente blog.

    • gibaholms 09/11/2013 / 8:03 AM

      Oi Daniel, acho que dá sim cara, é só usar o algoritmo que vai retornar a lista de palavras possiveis, como por exemplo o algoritmo de Levenshtein, e depois “caçar” elas na lista.
      Abraços !

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s