O Baardskeerder é um banco de dados simples incorporado em torno de uma estrutura de dados b-tree de inclusão apenas. É um dicionário que também suporta consultas de intervalo e transações.
Ele é implementado em ocaml, e a ideia principal é que ele substituirá o Tokyo Gabinet em nossa loja de chave-valor Arakoon.
Este artigo vai tentar explicar a nossa abordagem sobre as transações.
Preliminares
O Baardskeerder anexa slabs em um log. Slags são lista de entradas, e elas podem ser valores, espaços em branco, índices ou commits. Suponha que comecemos com um log vazio, e adicionemos uma primeira atualização.
O Baardskeerder constrói um slab mais ou menos assim:
Value "F" Leaf ["f", Inner 0] Commit (Inner 1)
Este slab fica serializado, e é adicionado a um log, o que resulta em algo assim:
Value "F" Leaf ["f", Outer 0] Commit (Outer 1)
Observe que existem referências externas e internas. As externas referem-se a posições no Log, enquanto que as internas referem-se ao slab atual. Durante a serialização, cada posição interna precisa ser traduzida em uma externa, enquanto que as posições externas só podem ser copiadas. (Na realidade, as posições externas são um pouco mais complexas para calcular, já que o tamanho das entradas após a serialização as influencia, mas eu abstraí esse problema aqui).
Quando um slab está pronto para ser serializado e adicionado, ele acaba sempre com um node Commit. Esse node commit é necessário porque pode haver um desastre ao escrever o slab serializado, e ele pode não acabar inteiramente no log. Então, depois de uma atualização bem-sucedida, a última entrada no log é um Commit apontando para o node na raiz atual.
Para podermos apreciar plenamente a diferença entre slab e referências de log,vamos adicionar outra atualização.
O novo slab se parece com isto:
Value "D" Leaf ["d", Inner 0; "f", Outer 0] Commit (Inner 1)
O novo espaço no slab refere-se tanto ao valor na posição 0 no log (Value “F”) e ao valor na posição 0 em (Value “D”) do slab.
Após a serialização do slab, e de escrever no log, ele fica assim:
Value "F" Leaf ["f", Outer 0] Commit (Outer 1) Value "D" Leaf ["d", Outer 3; "f", Outer 0] Commit (Outer 4)
Para termos um log mais interessante, vamos adicionar mais algumas atualizações:
set "h" "H"; set "a" "A"; set "z" "Z"
Após isso, o log fica assim:
Value "F" Leaf ["f", Outer 0] Commit (Outer 1) Value "D" Leaf ["d", Outer 3; "f", Outer 0] Commit (Outer 4) Value "H" Leaf ["d", Outer 3; "f", Outer 0; "h", Outer 6] Commit (Outer 7) Value "A" Leaf ["a", Outer 9; "d", Outer 3] Leaf ["f", Outer 0; "h", Outer 6] Index Outer 10, ["d", Outer 11] Commit (Outer 12) Value "Z" Leaf ["f", Outer 0; "h", Outer 6; "z", Outer 14] Index Outer 10, ["d", Outer 15] Commit (Outer 16)
Isso corresponde à seguinte árvore:
Existem várias pequenas coisas para serem notadas aqui. Primeiro, os espaços que sobram (size = 4) são divididos em novos espaços com uma entrada no índice para se referir a ambos. Além disso, as entradas no log apenas se referem a entradas anteriores e, o mais importante, nada muda dentro do log.
Transações
Suponha que por algum acidente o processo morra enquanto se escrevia o slab, o último slab não chega por completo até o log. No exemplo acima, o log pode terminar apenas após o valor “Z” (ou um pouco mais com um meio espaço escrito).
Na próxima abertura do log, vamos procurar o último commit, e o log fica truncado apenas após a posição 13. Como tal, a presença de commits que fazem atualizações atômicas.
Eles também fornecem meios para implementar transações não-simultâneas. Na verdade, se só tivermos uma entrada de commit no final de um slab, o slab será literalmente a transação. No início da transação, criamos um slab, e o passamos adiante para todas as atualizações. Uma entrada de commit está escrita no fim do slab, quando terminamos. A única complexidade adicionada vem da tree descendente: devemos começar na raiz do slab (ou log, se estiver vazio) e se tivermos que saltar para uma entrada, temos que olhar para a sua posição e saltar para o slab se for uma posição interna, e no log se for uma uma externa.
O fragmento de código a seguir ilustra nossa API de transação:
module DBX : sig type tx val get : tx -> k -> v val set : tx -> k -> v -> unit val delete : tx -> k -> unit ... val with_tx : log -> (tx -> unit) -> unit end
O fragmento de código a seguir ilustra a nossa API de transação:
let xs = ["f","F";
"d","D";
"h","H";
"a","A";
"z","Z";
]
in
DBX.with_tx log
(fun tx ->
List.iter (fun (k,v) ->
DBX.set tx k v) xs
)
e suponha que aplicamos essa transação para um log vazio. O nosso resultado é:
Value "F" Leaf ["f", Outer 0] Value "D" Leaf ["d", Outer 2; "f", Outer 0] Value "H" Leaf ["d", Outer 2; "f", Outer 0; "h", Outer 4] Value "A" Leaf ["a", Outer 6; "d", Outer 2] Leaf ["f", Outer 0; "h", Outer 4] Index Outer 7, ["d", Outer 8] Value "Z" Leaf ["f", Outer 0; "h", Outer 4; "z", Outer 10] Index Outer 7, ["d", Outer 11] Commit (Outer 12)
Resumo do desempenho: cada transação se resume a um slab, e cada um, por sua vez, é escrito usando uma chamada de sistema (write).
A compactação Slab
As atualizações em transações feitas em série usam menos espaço em comparação com as atualizações individuais, mas continuaríamos tendo um monte de entradas inválidas. Vamos pegar o log acima de exemplo. As entradas 1,3, 5,8, e 9 não são úteis em qualquer forma. Portanto, seria desejável podá-las do slab antes mesmo de atingir o log.
Isso acaba sendo surpreendentemente fácil.
Primeiro, temos que encontrar as entradas inválidas, o que podemos fazer com uma iteração simples por meio do slab, a partir da raiz, e marcando cada posição interna como conhecida. Quando você terminar, as posições que você não marcou serão lixo.
type t = { mutable es: entry array; mutable nes: int}
let mark slab =
let r = Array.make (slab.nes) false in
let maybe_mark = function
| Outer _ -> ()
| Inner x -> r.(x) <- true
in
let maybe_mark2 (_,p) = maybe_mark p in
let mark _ e =
match e with
| NIL | Value _ -> ()
| Commit p -> maybe_mark p
| Leaf l -> List.iter maybe_mark2 l
| Index (p0,kps) -> let () = maybe_mark p0 in List.iter maybe_mark2 kps
in
let () = iteri_rev slab mark in
let () = r.(slab.nes -1) <- true in
r
Depois de marcamos as entradas inválidas, nós iteramos por meio do slab de novo, a partir da posição 0 para o final, e construímos um mapeamento que indica como traduzir uma antiga posição interna para uma nova posição.
let mapping mark =
let s = Array.length mark in
let h = Hashtbl.create s in
let rec loop i o =
if i = s then h
else
let v = mark.(i) in
let i' = i + 1 in
let () = Hashtbl.add h i o in
let o' = if v then o + 1 else o in
loop i' o'
in
loop 0 0
A última fase é a reescrita real do slab, sem as entradas inválidas. Esta é, de novo, uma iteração simples.
let rewrite s s_mark s_map =
let lookup_pos = function
| Outer x -> Outer x
| Inner x -> Inner (Hashtbl.find s_map x)
in
let rewrite_leaf kps = List.map (fun (k,p) -> (k,lookup_pos p)) kps in
let rewrite_index (p0,kps) = (lookup_pos p0 , rewrite_leaf kps) in
let rewrite_commit p = lookup_pos p in
let esa = s.es in
let size = s.nes in
let r = Array.create size NIL in
let rec loop c i =
if i = size
then { es = r; nes = c}
else
begin
let i' = i + 1 in
let a = s_mark.(i) in
if a then
let e = esa.(i) in
let e' = match e with
| Leaf l -> Leaf (rewrite_leaf l)
| Index i -> Index (rewrite_index i)
| Commit p -> Commit (rewrite_commit p)
| Value _
| NIL -> e
in
let () = r.(c) <- e' in
let c' = c + 1 in
loop c' i'
else
loop c i'
end
in
loop 0 0
Juntando tudo:
let compact s = let s_mark = mark s in let s_map = mapping s_mark in rewrite s s_mark s_map
Se a gente der uma olhada no slab para o nosso exemplo de transação de 5 conjuntos antes da compactação:
Value "F" Leaf ["f", Inner 0] Value "D" Leaf ["d", Inner 2; "f", Inner 0] Value "H" Leaf ["d", Inner 2; "f", Inner 0; "h", Inner 4] Value "A" Leaf ["a", Inner 6; "d", Inner 2] Leaf ["f", Inner 0; "h", Inner 4] Index Inner 7, ["d", Inner 8] Value "Z" Leaf ["f", Inner 0; "h", Inner 4; "z", Inner 10] Index Inner 7, ["d", Inner 11] Commit (Inner 12)
E depois da compactação:
Value "F" Value "D" Value "H" Value "A" Leaf ["a", Inner 3; "d", Inner 1] Leaf ["f", Inner 0; "h", Inner 2] Value "Z" Leaf ["f", Inner 0; "h", Inner 2; "z", Inner 6] Index Inner 4, ["d", Inner 7] Commit (Inner 8)
Podemos ver que vale a pena o esforço.
É claro que, quanto maior for a transação, maior será o benefício de compactação.
Compactação de log offline
Dado que o Baardskeerder possui operações com compactação de slab, podemos construir um algoritmo de compactação offline simples e eficiente para arquivos de log. Comece a partir da raiz, passe pela tree enquanto estiver construindo grandes transações (tão grandes quanto você desejar, ou quanto puder pagar), e adicione-as a um novo arquivo de log. Quando estiver pronto, você terá seu registro compactado.
Compactação de log online
Logs de Baardskeerder também podem retornar lixo para o sistema de arquivos enquanto eles estão em uso, mas isso será guardado para um artigo próximo.
Se divirta!
***
Texto original disponível em http://blog.incubaid.com/2011/11/28/baardskeerders-transaction-strategy/
De 0 a 10, o quanto você recomendaria este artigo para um amigo?