act-act about projects rss

CouchDB Source Code Reading part3

couch_db_updater:init_db/6の以下の部分を掘り下げてみたいと思います。

couch_db_updater.erl

1
2
3
4
5
6
7
8
9
10
11
12
    {ok, IdBtree} = couch_btree:open(Header#db_header.fulldocinfo_by_id_btree_state, Fd,
        [{split, fun(X) -> btree_by_id_split(X) end},
        {join, fun(X,Y) -> btree_by_id_join(X,Y) end},
        {reduce, fun(X,Y) -> btree_by_id_reduce(X,Y) end},
        {compression, Compression}]),
    {ok, SeqBtree} = couch_btree:open(Header#db_header.docinfo_by_seq_btree_state, Fd,
            [{split, fun(X) -> btree_by_seq_split(X) end},
            {join, fun(X,Y) -> btree_by_seq_join(X,Y) end},
            {reduce, fun(X,Y) -> btree_by_seq_reduce(X,Y) end},
            {compression, Compression}]),
    {ok, LocalDocsBtree} = couch_btree:open(Header#db_header.local_docs_btree_state, Fd,
        [{compression, Compression}]),

couch_db_updater:btree_by_id_split/1

IdBtreeSeqBtreeLocalDocsBtreeの3つのtreeの用意が行われています。まずはIdBtreeの初期化の部分。splitには以下の関数が設定されています。

couch_db_updater.erl

1
2
3
btree_by_id_split(#full_doc_info{id=Id, update_seq=Seq,
        deleted=Deleted, rev_tree=Tree}) ->
(...snip...)

full_doc_infoというドキュメントを扱っています。レコードの定義は以下のようになっています。

couch_db.hrl

1
2
3
4
5
6
7
record(full_doc_info,
    {id = <<"">>,
    update_seq = 0,
    deleted = false,
    rev_tree = [],
    leafs_size = 0
    }).

idはドキュメントのID、update_seqは文字通り更新毎にインクリメントされていくシーケンスですかね。rev_treeはこのドキュメントの履歴を管理するリストかな。couch_key_tree:map/2を見てみます。

couch_key_tree.erl

1
2
3
4
5
6
7
8
9
10
11
map(_Fun, []) ->
    [];
map(Fun, [{Pos, Tree}|Rest]) ->
    case erlang:fun_info(Fun, arity) of
    {arity, 2} ->
        [NewTree] = map_simple(fun(A,B,_C) -> Fun(A,B) end, Pos, [Tree]),
        [{Pos, NewTree} | map(Fun, Rest)];
    {arity, 3} ->
        [NewTree] = map_simple(Fun, Pos, [Tree]),
        [{Pos, NewTree} | map(Fun, Rest)]
    end.

erlang:fun_info/2で関数のメタ情報が取れるようです。couch_key_tree:map_simple/3の第一引数のFunのarityの数を見て呼び出し方を調整しています。couch_db_updater:btree_by_id_split/1の中でこの関数を呼び出す際に渡している無名関数の引数の数は2なので、{arity, 2} の方にマッチすることになります。そうなると、couch_key_tree:simple_map/3の第一引数Funの_Cは何か気になります。

couch_key_tree.erl

1
2
3
4
5
6
map_simple(_Fun, _Pos, []) ->
    [];
map_simple(Fun, Pos, [{Key, Value, SubTree} | RestTree]) ->
    Value2 = Fun({Pos, Key}, Value,
            if SubTree == [] -> leaf; true -> branch end),
    [{Key, Value2, map_simple(Fun, Pos + 1, SubTree)} | map_simple(Fun, Pos, RestTree)].

_Cの部分はif SubTree == [] -> leaf; true -> branch endなので、_Cにはleafもしくはbranchが指定されることになり、couch_db_updater:btree_by_id_split/1からの呼び出しシーケンスではこの値は参照しなくても処理できる、というなのでしょう。

ちょっと戻り値が分かりにくくなったので整理すると、引数と戻り値の関係は以下のようになっています。

couch_key_tree:map/2

Fun, [{Pos, Tree}, ...] => [{Pos, NewTree}, ...]

couch_key_tree:map_simple/2

Fun, Pos, [{Key, Value, SubTree}, ...] => [{Key, Value2, [{SubKey, SubValue2, [...]}]}, ...]

ここでcouch_db_updater:btree_by_id_split/1戻ります。

couch_db_updater.erl

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
btree_by_id_split(#full_doc_info{id=Id, update_seq=Seq,
        deleted=Deleted, rev_tree=Tree}) ->
    DiskTree =
    couch_key_tree:map(
        fun(_RevId, ?REV_MISSING) ->
            ?REV_MISSING;
        (_RevId, RevValue) ->
            IsDeleted = element(1, RevValue),
            BodyPointer = element(2, RevValue),
            UpdateSeq = element(3, RevValue),
            Size = case tuple_size(RevValue) of
            4 ->
                element(4, RevValue);
            3 ->
                % pre 1.2 format, will be upgraded on compaction
                nil
            end,
            {if IsDeleted -> 1; true -> 0 end, BodyPointer, UpdateSeq, Size}
        end, Tree),
    {Id, {Seq, if Deleted -> 1; true -> 0 end, DiskTree}}.

rev_treeに保存された{Key, Value}が(_RevId, RevValue)に対応することになります。_RevIdは無視されます。

RevValueは{IsDeleted, BodyPointer, UpdateSeq, Size}で、{Deleted, BodyPointer, UpdateSeq, Size}に変換されます。この変換を図にすると、以下のようになります。

btree_by_id_split

シンボルと変数名がごちゃ混ぜですが、単なる備忘録なのでご容赦を。leaf_sizeが無くなっており、Deletedtrue/falseから1/0に変わっているところが違いになります。現時点ではこの変換が何を意味するのか分かってませんが、splitに設定された関数を呼び出すと、#full_doc_infoが上記図の一番下部のタプルに変換されることになります。

couch_db_updater:btree_by_id_join/2

次にjoinに設定されているbtree_by_id_join/2ですが、これはパッと見でbtree_by_id_split/1の逆を行うことが分かるので細かく読まないことにしますが、#full_doc_info.leaf_sizeはこの契機で計算しなおしてます。

couch_db_updater.erl

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
btree_by_id_join(Id, {HighSeq, Deleted, DiskTree}) ->
    {Tree, LeafsSize} =
    couch_key_tree:mapfold(
        fun(_RevId, {IsDeleted, BodyPointer, UpdateSeq}, leaf, _Acc) ->
            % pre 1.2 format, will be upgraded on compaction
            {{IsDeleted == 1, BodyPointer, UpdateSeq, nil}, nil};
        (_RevId, {IsDeleted, BodyPointer, UpdateSeq}, branch, Acc) ->
            {{IsDeleted == 1, BodyPointer, UpdateSeq, nil}, Acc};
        (_RevId, {IsDeleted, BodyPointer, UpdateSeq, Size}, leaf, Acc) ->
            Acc2 = sum_leaf_sizes(Acc, Size),
            {{IsDeleted == 1, BodyPointer, UpdateSeq, Size}, Acc2};
        (_RevId, {IsDeleted, BodyPointer, UpdateSeq, Size}, branch, Acc) ->
            {{IsDeleted == 1, BodyPointer, UpdateSeq, Size}, Acc};
        (_RevId, ?REV_MISSING, _Type, Acc) ->
            {?REV_MISSING, Acc}
        end, 0, DiskTree),
    #full_doc_info{
        id = Id,
        update_seq = HighSeq,
        deleted = (Deleted == 1),
        rev_tree = Tree,
        leafs_size = LeafsSize
    }.

couch_db_updater:btree_by_id_reduce/2

そしてreduceに設定されているbtree_by_id_redulce/2ですが、これは第一引数がreducerereduceかで処理が分かれています。まずはreduceから。

couch_db_updater.erl

1
2
3
4
5
6
7
8
9
10
11
12
btree_by_id_reduce(reduce, FullDocInfos) ->
    lists:foldl(
        fun(Info, {NotDeleted, Deleted, Size}) ->
            Size2 = sum_leaf_sizes(Size, Info#full_doc_info.leafs_size),
            case Info#full_doc_info.deleted of
            true ->
                {NotDeleted, Deleted + 1, Size2};
            false ->
                {NotDeleted + 1, Deleted, Size2}
            end
        end,
        {0, 0, 0}, FullDocInfos);

引数に指定された#full_doc_infoのリストをまわし、削除済みドキュメントの数、未削除のドキュメントの数、#full_doc_info.leafs_sizeの総数を算出して返します。#full_doc_info.leafs_sizeの総数を求める際、couch_db_updater:sum_leaf_size/2を呼び出しているのが気になったのでコードを見てみました。

couch_db_updater.erl

1
2
3
4
5
6
sum_leaf_sizes(nil, _) ->
    nil;
sum_leaf_sizes(_, nil) ->
    nil;
sum_leaf_sizes(Size1, Size2) ->
    Size1 + Size2.

思ったよりも普通でした。次にrereduceを指定している方を読んでみます。

couch_db_updater.erl

1
2
3
4
5
6
7
8
9
10
btree_by_id_reduce(rereduce, Reds) ->
    lists:foldl(
        fun({NotDeleted, Deleted}, {AccNotDeleted, AccDeleted, _AccSize}) ->
            % pre 1.2 format, will be upgraded on compaction
            {AccNotDeleted + NotDeleted, AccDeleted + Deleted, nil};
        ({NotDeleted, Deleted, Size}, {AccNotDeleted, AccDeleted, AccSize}) ->
            AccSize2 = sum_leaf_sizes(AccSize, Size),
            {AccNotDeleted + NotDeleted, AccDeleted + Deleted, AccSize2}
        end,
        {0, 0, 0}, Reds).

reduceと異なるのは、第二引数で指定されているのが#full_doc_infoのリストではなく、{NotDeleted, Deleted}{NotDeleted, Deleted, Size}のリストであること。処理内容はreduceと同じです。

couch_db_updater:btree_by_seq_split/1

次にSeqBtreeの方を。現時点でIdBtreeとの役割の違いが分かっていないので、推測できる部分が少ないのがツラいところです。

couch_db_updater.erl

1
2
3
4
5
6
7
8
9
btree_by_seq_split(#doc_info{id=Id, high_seq=KeySeq, revs=Revs}) ->
    {RevInfos, DeletedRevInfos} = lists:foldl(
        fun(#rev_info{deleted = false, seq = Seq} = Ri, {Acc, AccDel}) ->
                {[{Ri#rev_info.rev, Seq, Ri#rev_info.body_sp} | Acc], AccDel};
            (#rev_info{deleted = true, seq = Seq} = Ri, {Acc, AccDel}) ->
                {Acc, [{Ri#rev_info.rev, Seq, Ri#rev_info.body_sp} | AccDel]}
        end,
        {[], []}, Revs),
    {KeySeq, {Id, lists:reverse(RevInfos), lists:reverse(DeletedRevInfos)}}.

今度は#doc_infoというレコードを使っています。レコードの定義は以下のとおりです。

couch_db.hrl

1
2
3
4
5
6
-record(doc_info,
    {
    id = <<"">>,
    high_seq = 0,
    revs = [] % rev_info
    }).

#full_doc_infoと照らし合わせて推測すると、id#full_doc_info.idと同じで、high_seq#full_doc_info.update_seqの最も高い値、revs#full_doc_info.rev_treeに対応しているように見えます。また、revsには#ref_infoレコードのリストが設定されるようになっているので、このレコードの定義も確認します。

couch_db.hrl

1
2
3
4
5
6
7
-record(rev_info,
    {
    rev,
    seq = 0,
    deleted = false,
    body_sp = nil % stream pointer
    }).

個々のリビジョンの情報なのかな。body_sp#full_doc_info.rev_treeValueにあったBodyPointerと違うものなのかが気になります。

btree_by_seq_split/1に戻ると、#doc_info.revsをまわして、未削除の#rev_infoと削除済みの#rev_infoに分けています。最終的に{high_seq, {id, RevInfos, DeletedRevInfos}}として返します。

couch_db_updater:btree_by_seq_join/2

次にjoinに設定されているbtree_by_seq_join/2ですが、やはりbtree_by_seq_split/1の逆の処理を行う関数なのでパっと見るだけで。

couch_db_updater.erl

1
2
3
4
5
6
7
8
9
btree_by_seq_join(KeySeq, {Id, RevInfos, DeletedRevInfos}) ->
    #doc_info{
        id = Id,
        high_seq=KeySeq,
        revs =
            [#rev_info{rev=Rev,seq=Seq,deleted=false,body_sp = Bp} ||
                {Rev, Seq, Bp} <- RevInfos] ++
            [#rev_info{rev=Rev,seq=Seq,deleted=true,body_sp = Bp} ||
                {Rev, Seq, Bp} <- DeletedRevInfos]}.

couch_db_updater:btree_by_seq_reduce/2

そしてreduceに設定されているbtree_by_seq_reduce/2reduceが指定された場合は#doc_infoのリストの要素数を返しているだけ。rereducelists:sum/1を呼び出しているので、Reds[number()]かな。

couch_db_updater.erl

1
2
3
4
5
btree_by_seq_reduce(reduce, DocInfos) ->
    % count the number of documents
    length(DocInfos);
btree_by_seq_reduce(rereduce, Reds) ->
    lists:sum(Reds).

couch_btree:open/3

IdBtreeSeqBtreeと読んできたのでLocalDocsBtreeの番ですが、これはsplitjoinreduceといった関数が設定されていないので、couch_btree:open/3を読んでみようと思います。

couch_btree.erl

1
2
open(State, Fd, Options) ->
    {ok, set_options(#btree{root=State, fd=Fd}, Options)}.

StateIdBtreeSeqBtreeLocalDocsBtree毎に異なる値が設定されています。set_options/2も見てみます。

couch_btree.erl

1
2
3
4
5
6
7
8
9
10
11
12
set_options(Bt, []) ->
    Bt;
set_options(Bt, [{split, Extract}|Rest]) ->
    set_options(Bt#btree{extract_kv=Extract}, Rest);
set_options(Bt, [{join, Assemble}|Rest]) ->
    set_options(Bt#btree{assemble_kv=Assemble}, Rest);
set_options(Bt, [{less, Less}|Rest]) ->
    set_options(Bt#btree{less=Less}, Rest);
set_options(Bt, [{reduce, Reduce}|Rest]) ->
    set_options(Bt#btree{reduce=Reduce}, Rest);
set_options(Bt, [{compression, Comp}|Rest]) ->
    set_options(Bt#btree{compression=Comp}, Rest).

splitjoinreduceに設定された各関数がそれぞれ、extract_kvassemble_kvreduceという名前で#btreeに設定されています。compressionも同様です。lessはまだ出てきてませんが、どういう役割なのか気になります。

Conclusion

各Btreeの初期化処理を見てきました。ここまで見てきた限りでは、IdBtreeはドキュメントそのもの、SeqBtreeは各ドキュメントの最新Seqの管理を行っているように見受けられます。LocalDocsBtreeはまだ分かりません。このBtreeに関してはもう少し読み進めていく中で役割を確認しようと思います。