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/