From commits-return-8078-apmail-couchdb-commits-archive=couchdb.apache.org@couchdb.apache.org Sun Feb 26 22:08:02 2012 Return-Path: X-Original-To: apmail-couchdb-commits-archive@www.apache.org Delivered-To: apmail-couchdb-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id A22FA9DDD for ; Sun, 26 Feb 2012 22:08:02 +0000 (UTC) Received: (qmail 11603 invoked by uid 500); 26 Feb 2012 22:08:02 -0000 Delivered-To: apmail-couchdb-commits-archive@couchdb.apache.org Received: (qmail 11554 invoked by uid 500); 26 Feb 2012 22:08:02 -0000 Mailing-List: contact commits-help@couchdb.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@couchdb.apache.org Delivered-To: mailing list commits@couchdb.apache.org Received: (qmail 11546 invoked by uid 500); 26 Feb 2012 22:08:02 -0000 Delivered-To: apmail-incubator-couchdb-commits@incubator.apache.org Received: (qmail 11542 invoked by uid 99); 26 Feb 2012 22:08:02 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 26 Feb 2012 22:08:02 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.131] (HELO eos.apache.org) (140.211.11.131) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 26 Feb 2012 22:08:01 +0000 Received: from eos.apache.org (localhost [127.0.0.1]) by eos.apache.org (Postfix) with ESMTP id 5E140F39; Sun, 26 Feb 2012 22:07:41 +0000 (UTC) MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable From: Apache Wiki To: Apache Wiki Date: Sun, 26 Feb 2012 22:07:41 -0000 Message-ID: <20120226220741.69149.48421@eos.apache.org> Subject: =?utf-8?q?=5BCouchdb_Wiki=5D_Update_of_=22ReleaseNotice1=2E0=2E0RepairToo?= =?utf-8?q?l=22_by_JanLehnardt?= Auto-Submitted: auto-generated Dear Wiki user, You have subscribed to a wiki page or wiki category on "Couchdb Wiki" for c= hange notification. The "ReleaseNotice1.0.0RepairTool" page has been changed by JanLehnardt: http://wiki.apache.org/couchdb/ReleaseNotice1.0.0RepairTool?action=3Ddiff&r= ev1=3D1&rev2=3D2 Comment: add repair tool page 5. Start CouchDB 1.0.1. 6. Wait until CouchDB says "Time to Relax.". 6.1. CouchDB will have switched te config to `recovery =3D false`. - 6.2. CouchDB will = + 6.2. CouchDB will have created `/lost\_and\_found\_$dbname\_$timestamp= ` for every db that has orphaned data. + 7. Go to `/lost\_and\_found\_$dbname\_$timestamp` and see if any lost da= ta is found. + 8. Replicate `/lost\_and\_found\_$dbname\_$timestamp` to `/$dbname` to r= estore all data. = + = + = + =3D A generalized repair algorithm =3D + = + = + =3D=3D the basic repair algorithm: =3D=3D + = + for Node in BTreeNodes + run the compactor to create a lost and found database file that tre= ats Node as a root + use the replicator to merge all the lost and found database files int= o one database + Done! + = + It is an optimization to prune the Nodes in BTreeNodes so that there is t= he minumum number of them without losing any data. If we did this for every= single node in the original file, we'd end up with the same final result a= s if we did it optimally. the difference is that we'd use exponentially mor= e disk space in the process. + = + [Another space saving optimization would be to only keep one resident los= t+found db around and have one active l+f db one per compaction and replica= te the current one into the resident one after each compaction. I don't kno= w how hard it'd be to find the minimal set of node to apply the other optim= ization, so this might be a reasonable alternative to keep disk-usage in bo= unds, although not as optimal -- Jan] + = + =3D=3D Finding only the btree nodes we need: =3D=3D + = + It is hard to tell roots apart from other nodes. The way to do that is wo= rk backwards through the file keeping track of pointers in nodes. if a node= matches a pointer you've seen, you don't need to capture it. if a node has= not been pointed to, capture it. This gives you all the roots. + = + = + This means we can also keep track of the pointers that headers point to, = and a root is pointed to by any header, we can assume any other roots later= in the file from that header, take that state into account. therefore any = root pointed to be a header can be disregarded. + = + when we are done, we will have a list of roots that are not reflected by = the last valid header in the file (some of these may be after the last vali= d header), **nor are they reflected by later roots in the same "lineage"**.= this is the set of nodes that we need to use as the starting point for com= pactions. + = + **the part in bold is false and means we will collect unneeded roots** I'= m currently looking into a way to distinguish superceded roots from final r= oots. + = + we will end up with as many "lost and found" database files as we have ro= ots here. once we have them, we can begin the compact and replicate routine. +=20