Com o que você está brincando hoje?

Introdução

Um colega meu recentemente me perguntou como eu faço pesquisa, e de onde as ideias vêm. A conversa foi algo deste tipo:

NN: Tá, mas como você aprende todas essas coisas?
EU: É um efeito colateral, realmente. Deixa eu explicar: quando é que você aprende mais na vida?
NN: Deve ser na infância…
EU: Sim, e por que isso?
NN: O cérebro é mais flexível quando se é jovem…
EU: Sim, isso ajuda bastante, mas essa não é a resposta completa. A coisa que principalmente ajuda é que você estava brincando.
NN: Então, você está me dizendo que eu deveria brincar mais?
EU: Sim, mas para se dar bem com isso, você chama de pesquisa.

Atualmente, estou fazendo pesquisas (brincando) sobre estruturas de dados persistentes. A literatura utiliza uma série de nomes diferentes (CoW, append-only, log-structured, persistent, …), onde as atualizações (pelo menos conceitualmente) nunca alteram nada, o que significa que você tem acesso a todas as versões anteriores. Isso é associado a série de novidades de palavras como instant snapshotting, cheap transactions, ssd optimized, hot copy, …

Append-only de árvore binária

Para ilustrar o conceito, mostrarei como brincar com uma append-only de árvore binária (uma B-tree significaria apenas mais trabalho, sem diversão adicional).

variação de árvore binária

Vamos começar com algumas imagens da estrutura de dados que queremos implementar. A representação de append-only será mostrada na próxima seção.

Inicialmente, a árvore está vazia e não há nada para mostrar, mas depois de adicionar o primeiro par de chave de valor (“f”, “F”), que significa apenas que “f” é mapeado para “F”, a árvore se parece com isso:

Uma tecla nó (mostrada como uma forma oval, e chamada de leaf) apenas aponta para um nó de valor (mostrado como uma caixa).

Esta é a árvore depois de inserir um segundo mapeamento (“D” mapeia para “D”):

Um branch node  (mostrado como um trapézio) divide a tecla espaço chave em 2 partes e tudo menor ou igual ao seu separador (“d”) oscila para a esquerda; todo o resto oscila para a direita.

Depois de adicionar os mapeamentos (“h”, “H”) (“a”, “A”) e (z “,” Z “), temos a seguinte árvore:

representação append-only

O nome append-only deriva (eu acho) do ponto de vista baseado em arquivo, onde escreve somente no final do arquivo (append).
É também chamado de um registro.
Para a árvore de um elemento, isso é simples, uma vez que você percebe que uma vez que “f” aponta para “F”, você precisa escrever primeiro valor “F” antes de escrever a leaf “f”:

O número à esquerda de uma entrada denota a sua posição no log, para que os nós mais recentes possam consultá-la (o 0 na leaf “f” aponta para o valor na posição 0).
A adição de coisas só pode ser feita no lado direito, e as coisas só podem apontar para as que já foram escritas.
Inserir (“d”, “D”) significa primeiro escrever o valor “D”, em seguida escrever a leaf “d”, e finalmente o branch node.
O resultado é mostrado abaixo:

Ok, acrescentar (“h”, “H”), (“a”, “A”) e (“z”, “Z”) produz o seguinte:

Você vê imediatamente que o espaço elevado pode ser considerado.
Em algum ponto, você não se importa mais com snapshots antigos e você vai querer ter a possibilidade de recuperar esse espaço.

implementação mínima

Nós ainda não temos nada com o que brincar. Vamos fazer uma implementação mínima.
Primeiro comece com um log.

type v = string
type k = string
type pos = int

type entry =
  | NIL
  | V of v
  | L of k * pos
  | N of pos * k * pos

type log = {es:entry array;  mutable next : int;}

As entradas são nil, values, leafs ou nodes. A propósito, este é ocaml.
Um log é um array, combinado com um atributo next que lhe diz onde ‘escrever’.
Algumas funções auxiliares são necessárias.

let make cap = {es = Array.make cap NIL; next = 0;}
let root_pos log = log.next -1
let get_entry log pos = if pos = -1 then NIL else log.es.(pos)
let get_length log = Array.length log.es
let free log = get_length log - log.next

let write log es =
  let do_one e =
    if free log = 0 then failwith "full";
    let p = log.next in
    log.es.(p) <- e;
    log.next <- p + 1
  in
  List.iter do_one es

Recuperar um valor é simples, só descende a partir da raiz.

let get log k =
  let rec find_pos pos =
    match get_entry log pos with
      | V v -> v
      | L (k0,p0) when k = k0 -> find_pos p0
      | N (l,k0,r) -> let p' = if k <= k0 then l else r  in
              find_pos p'          
      | _ -> failwith "Not_found"
  in
  find_pos (root_pos log)

Adicionar um mapeamento não é tão difícil. O truque é registrar os lugares que você visitou no caminho; estas são exatamente as entradas que precisarão ser reescritas.

type dir = Hit | Left | Right
type trail = (dir * entry * pos) list

exception Todo of trail * string
let todo v msg = raise (Todo (v,msg))

Depois de introduzir a direção e o trail, acrescentei uma exceção para os casos não lidados.
O esqueleto para o ‘set’ é bastante simples:

let set log k v =
  let rec descend trail pos =
    match get_entry log pos with
      | NIL -> trail
      | V v -> failwith "corrupt"
      | L (k0,p0) as e -> let dir =
                if k = k0
                then Hit else if k < k0
                  then Left
                  else Right
              in
              (dir , e, pos) :: trail
      | N (l,k0,r) as e when k <= k0 -> descend ((Left,e, pos) :: trail) l
      | N (l,k0,r) as e              -> descend ((Right,e,pos) :: trail) r
  in
  let trail = descend [] (root_pos log) in
  let update = build_set k v log.next trail in
  write log update

Então, primeiro vamos para baixo na árvore acumulando um trail, o qual usamos para construir a atualização que foi gravada no lo.
Vamos construir a atualização:

let rec build_set k v start (visited:trail)  = V v :: do_start start k visited
and do_start start k visited = match visited with
  | [] -> [L (k, start) ]
  | (dir , L(k0,p0),pe) :: rest ->
    begin
      let e = L(k,start) in
      match dir with
    | Hit   -> e :: do_rest (start + 1) rest
    | Left  -> e :: N(start + 1, k, pe) :: do_rest (start + 2) rest
    | Right -> e :: N(pe, k0, start +1) :: do_rest (start + 2) rest
    end
  | _ -> todo visited (Printf.sprintf "do_start %i '%s'" start k)
and do_rest start visited =
  match visited with
    | [] -> []
    | h :: t ->
      let e =
    match h with
      | (Left , N(pl,k0,pr),pe)  ->  N(start,k0,pr)
      | (Right, N(pl,k0,pr),pe)  ->  N(pl,k0,start)
      | _ -> todo visited (Printf.sprintf "do_rest %i" start)
      in
      e :: do_rest (start + 1) t

A criação da atualização é feita em três etapas, onde do_rest é a mais difícil.
O key insight é que, se no meio do caminho você pegou o branch esquerdo, aquela parte do nó precisa mudar, a outra pode ser copiada.

interatividade, por favor

A parte de código abaixo permite você dispensar um log.

let dump log =
  Array.iteri (fun i e->
    let () = Printf.printf "%2i: " i in
    match e with
      | NIL        -> print_newline()
      | V v        -> Printf.printf "V \"%s\"\n" v
      | L (k,p)    -> Printf.printf "L(\"%s\",%i)\n" k p
      | N (l,k0,r) -> Printf.printf "N(%i,\"%s\",%i)\n" l k0 r
  ) log.es

um exemplo dump:

0: V "F"
1: L("f",0)
2: V "D"
3: L("d",2)
4: N(3,"d",1)
5: V "H"
6: L("h",5)
7: N(1,"f",6)
8: N(3,"d",7)
9: V "A"
10: L("a",9)
11: N(10,"a",3)
12: N(11,"d",7)
13: V "Z"
14: L("z",13)
15: N(6,"h",14)
16: N(1,"f",15)
17: N(11,"d",16)
18:

Mas analisar isso para ver se todas as referências estão corretas é um pouco entediante.
Com algumas linhas de código você pode gerar a saída que pode ser processada por graphviz para gerar imagens que permitem a inspeção visual.

let dot_log ?(f = stdout) log =
  Printf.fprintf f "digraph Log{\n";
  Printf.fprintf f "\trankdir=\"RL\";\n";
  Printf.fprintf f "\tnode [shape=record];\n";
  let () = Array.iteri (fun i e ->
    let () = match e with
      | NIL -> ()
      | V v     ->
    Printf.fprintf f "\tnode%i [label = \"{%i|%s}\"];\n" i i v
      | L (k,p) ->
    Printf.fprintf f
      "\tnode%i [label = \"{%i | { %s | <f1> %i} }\"];\n"
      i i k p;
    Printf.fprintf f "\tnode%i:<f1> -> node%i;\n" i p
      | N(l,k0,r)  -> Printf.fprintf f "\tnode%i [label = \"{%i| { <f1> %i | %s | <f2> %i}}\"];\n" i i l k0 r;
    Printf.fprintf f "\tnode%i:<f1> -> node%i;\n" i l;
    Printf.fprintf f "\tnode%i:<f2> -> node%i;\n" i r;
    in
    if e <> NIL && i > 0 then Printf.fprintf f "\tnode%i -> node%i [style = invis];\n" i (i-1)
  ) log.es in
  Printf.fprintf f "}"

Isso precisava de um pouco de experimentação, mas a feature record ajuda muito.

Para assegurar que as coisas são renderizadas na ordem correta da esquerda para a direita, cada entrada tem uma seta invisível para seu antecessor.

O último fragmento gruda graphviz e evince juntos para ter o tipo de visualização interativa que você aprecia de mathlab ou scipy.

let view ?(v=dot_log) log =
  let root = "test" in
  let dot = Filename.temp_file root ".dot" in
  let png = Filename.temp_file root ".png" in
  let oc = open_out dot in
  let () = v ~f:oc log in
  close_out oc;
  let convert_cmd = Printf.sprintf "dot -Tpng -o %s %s" png dot in
  let _ = Sys.command convert_cmd in
  let cmd = Printf.sprintf "evince %s" png in
  Sys.command cmd

let view_log  log = view ~v:dot_log log

Ok, isso exige um screenshot:

Observações finais

A essência é que construí para mim um brinquedo interessante para ganhar percepção em estruturas de dados persistentes em menos de 150 linhas de código, que é um tributo ao poder de ocaml.

Tudo isso pode ser verdade, mas o código não é assim tão mínimo e não muito bonito:

• build_set pode ser feito com tail recursivo e mais curto também.
• As funções mútuas recursivas não são necessárias mesmo se definidas na ordem correta.
• leaf nodes podem ser suprimidos.
• dot_log parece hackish.

A maior parte do tempo, na escrita do código, foi gasta tentando seduzir graphviz ao fazer o que eu queria.

Divirta-se!

***

Texto original disponível em http://blog.incubaid.com/2011/10/03/what-are-you-playing-with-today/