Mailing-List: contact dev-help@couchdb.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@couchdb.apache.org
Received-SPF: pass (nike.apache.org: domain of randall.leeds@gmail.com
 designates 209.85.210.180 as permitted sender)
MIME-Version: 1.0
In-Reply-To: 
 <CABn9xAH1g9nHt2FUxnU+Dy5X2E_8+J1PVAfO4bODAYFWkCf0Hw@mail.gmail.com>
References: 
 <CABn9xAEqet5BFjHz3m+OsT8+HMc4v3PSuqBT-GiF9OwP=ssjrQ@mail.gmail.com>
	<CAL3q7H5Jto+vvbPkzba4y1h1o12qJVOQfd583mZD_vxMpB1GzA@mail.gmail.com>
	<CABn9xAHeJw8Mu=hzQCTo4dRz2ZcohfdZKCS4h9yQqp35JMvkWQ@mail.gmail.com>
	<4BB9B050-6977-446E-8844-C6FE83DBDDA4@dionne-associates.com>
	<CABn9xAHyV4Rhp4NjvrGJU_89CzNMbyX+yt0VEM7ev4CwipNOSA@mail.gmail.com>
	<CABn9xAFSDo_BK-xvnfPrCEHd1OD9PMXEiDbwUK40yxpdKVFm9w@mail.gmail.com>
	<EA9D823D-B8BF-4043-BC29-D5B7DB89DEAF@dionne-associates.com>
	<CABn9xAG=msumMrxw_QOXEeeVdB9=ow-JtTHpeeNzP_OqrTZvLA@mail.gmail.com>
	<73943F19-3FBE-43D7-A97B-E012A391BFED@apache.org>
	<CABn9xAHpcNLNsZFWkwCNFHUE1Oyx1G=wC-h-WY_d2gK45xUs=A@mail.gmail.com>
	<CABvT1DFZqxdfkkUdwGmKuEiaw6wuWBrstf+21wkssT=L1jg3kg@mail.gmail.com>
	<CABn9xAH1g9nHt2FUxnU+Dy5X2E_8+J1PVAfO4bODAYFWkCf0Hw@mail.gmail.com>
Date: Thu, 22 Dec 2011 17:10:34 -0800
Message-ID: 
 <CAAL6JQhQim_v6nS66BENLrWSB5NMpyxsMMa4zfT=bMVsGm=JvA@mail.gmail.com>
Subject: Re: Understanding the CouchDB file format
From: Randall Leeds <randall.leeds@gmail.com>
To: dev@couchdb.apache.org
Content-Type: text/plain; charset=UTF-8

On Thu, Dec 22, 2011 at 12:11, Riyad Kalla <rkalla@gmail.com> wrote:
> On Thu, Dec 22, 2011 at 12:38 PM, Robert Newson <rnewson@apache.org> wrote:
>
>> There are a
>> few parts of the article that are inaccurate (like the assertion we
>> have good locality for the id and seq trees. If this were true we
>> wouldn't have seen such a huge improvement in compaction by
>> temporarily separating them).
>
>
> I'd look forward to more detail on this... it was my understanding the
> updates were appended out in the [doc rev][_id idx diff][_seq idx diff]
> format at the end of the data file. Sounds like I may have misunderstood
> that?
>

Riyad, as you pointed out earlier, all the inner nodes are rewritten
up to the root. The two btrees are not written in parallel, though,
which means that for deep trees all the updated nodes are written
before the other tree's nodes are written. Also remember that the
trees themselves end up pretty fragmented since older nodes that
haven't changed are back toward the beginning of the file. In general,
I'm not sure there's much that's useful to mention about locality in
the trees. Also, updating these trees requires reading the old values,
so there is still seeking that occurs (if the pages aren't cached by
the OS).

>
>> The 'COMPETE recreation' paragraph also
>> strikes me as factually awry.
>>
>
> I'd appreciate a detailed correction on this if it is wrong; all the
> digging I've done (in this thread and other partial resources) suggests
> that the path from the changed doc ref back to the root (including a copy
> of all internal nodes and all of their child references) is written so as
> being able to read-back into the index from the tail of the data file
> quickly... specifically slides 17, 18 and 19 from this slidedeck (
> http://www.slideshare.net/jchrisa/btree-nosql-oak?from=embed) -- note that
> the interim nodes [A..M] and [A..Z] are rewritten (including any and all
> child pointers they contained).
>
> This is what I was referring to; I should either clean up my wording
> (confusing) or I got it wrong in which case I'd appreciate any and all
> corrections.

Right. It mostly seems a bit confusing to me.
"it DOES NOT just rewrite the nodes pathing from the leaf to the node
and ONLY the connections for that single document"
That doesn't sound quite right, but I can tell what you're trying to
say is accurate. If I'm right, you mean that every changed inner node
is rewritten in its entirety rather than having a single pointer to
the new child updated in place.

Cheers. Thanks for taking the time to write this up.

-Randall