couchdb-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Paul Davis <paul.joseph.da...@gmail.com>
Subject Re: How does the B-tree for view indexes behave?
Date Sat, 08 Oct 2011 06:42:34 GMT
On Fri, Oct 7, 2011 at 8:59 PM, Pulkit Singhal <pulkitsinghal@gmail.com> wrote:
> If this is not an inappropriate place to ask these questions, then please
> point me in the right direction :)
>
> 1) Does CouchDB mark existing rows in a view index as "invalid" for ALL of
> the following operations: add,delete, edit?

Rows are dropped when they're removed from the index. This could be
due to a document being deleted or due to a document being updated and
the map function emit'ing new rows.

> 2) For deletes: Is the info not added at the end of the B-tree for the view
> index?

As Jens says, there are two layers (at least) here. In regards to the
btree, its not really important. Things that are deleted are deleted.
In terms of the file storage, this means that information about the
delete (rather, new parts of the btree that have removed information
about the data that was deleted) are appended to the end of the file.

> 3) Does CouchDB break out of its "append-only-model" if a document gets
> updated for a view index? Are the resulting new lines really inserted into
> the B-tree? Why the change in behavior?
>

It's quite impossible for CouchDB to break out of an append only mode.
If you read couch_file.erl you'll see that there are basically only
two functions: pread (read data at offset/positional read) and append.
Our file abstraction literally has no concept or ability to write data
other than at the end of the file.

The O'Reilly book is a bit misleading here. The idea is close, but in
terms of internals its missing the point a bit. First, when it refers
to lines, it should've said rows. There's no '\n' character
specifically stored in the btree itself. The lines in the view output
are just a formatting applied to the internal structure.

The "marked as invalid" is also misleading because it suggests that
things are modified through non tail-append means which is also wrong.
But the copy-on-write semantics are a bit subtle to describe in a
single paragraph so the transgressions are quite forgivable.

Its harder to say something like, "all modifications to the btree
write new versions of the btree to disk. An "update" is merely a
change in where the root of the tree points. Without compaction, each
file would contain all information on every version of the btree.
Compaction exists to remove the portions of the tree that are no
longer needed. This is a fairly standard approach to enforcing
consistency when its valued over raw performance."

Or something because that still fails to catch all the important
details while the book version seems much more informative if you're
not worried about the exact implementation.

> I am basing my questions on the following excerpt @
> http://guide.couchdb.org/draft/views.html#lookups
> "What happens, though, when you change a document, add a new one, or delete
> one? Easy: CouchDB is smart enough to find the rows in the view result that
> were created by a specific document. It marks them invalid so that they no
> longer show up in view results. If the document was deleted, we’re good—the
> resulting B-tree reflects the state of the database. If a document got
> updated, the new document is run through the map function and the resulting
> new lines are inserted into the B-tree at the correct spots. New documents
> are handled in the same way. Appendix F, The Power of B-trees demonstrates
> that a B-tree is a very efficient data structure for our needs, and the
> crash-only design of CouchDB databases is carried over to the view indexes
> as well. "
>

Mime
View raw message