tahoe-lafs/trac

repairer service #483

New issue

Closed

opened 2008-07-01 23:44:29 +00:00 by warner · 8 comments

warner commented

2008-07-01 23:44:29 +00:00

It is time to build a Repairer service. This should accept a storage index, or a verifier cap, and:

locate all existing shares
read all existing shares, checking hashes, report bad ones
generate+upload new shares as necessary

There should be a work queue, a directory of SI or verifier-cap (or repair-caps, once we define them). The files in the work queue directory should have one file per line, and the file will be deleted once all its files have been repaired.

Eventually we will make a foolscap inlet port for the work queue.

The Repairer service should be another twisted.application.service.MultiService, like uploaders and downloaders and helpers.

It is time to build a Repairer service. This should accept a storage index, or a verifier cap, and: * locate all existing shares * read all existing shares, checking hashes, report bad ones * generate+upload new shares as necessary There should be a work queue, a directory of SI or verifier-cap (or repair-caps, once we define them). The files in the work queue directory should have one file per line, and the file will be deleted once all its files have been repaired. Eventually we will make a foolscap inlet port for the work queue. The Repairer service should be another twisted.application.service.MultiService, like uploaders and downloaders and helpers.

warner added the

labels 2008-07-01 23:44:29 +00:00

warner added this to the undecided milestone 2008-07-01 23:44:29 +00:00

warner self-assigned this 2008-07-01 23:44:29 +00:00

warner commented

2008-07-17 19:51:52 +00:00

Author

The problem is both more and less deep than you might think. At first glance, the idea of allowing a reader (or someone with even less authority) to create new shares would sound like a capability violation: they don't have write authority, why should they get to write anything?. But the key is that the write-authority is about creating new versions of the file. Repair is about creating new shares for an existing version.

The mutable file uses a signature to express write authority: only the holders of the write-cap will be able to generate new valid signatures. This signature covers the root of the merkle tree that has shares as its leaves. The signature can be verified by anybody: it covers the ciphertext, not the plaintext, so a read-cap is not necessary to verify it.

So the repairer can use the remaining shares to reconstruct the ciphertext, then generate new shares (using the same encoding parameters, i.e. 'k' and 'N') which should exactly match the old ones. These shares should already fit into the existing hash tree, so the repairer can create perfectly valid new shares.

The stumbling block is in how the storage server knows that it ought to accept those new shares. Let's call this "publish authority" to distinguish it from the nominally-identical "write authority".

The current RSA-based scheme uses "write-enablers", a shared secret that is used to prove posession of the write-cap that does not involve signatures. The write-cap is hashed with each server's nodeid, and the result is the "write-enabler". When the share is first created, the original publisher provides the write-enabler, and it is stored next to the share (in a region that readers cannot access). When later publishers want to update the share, they must provide the same write-enabler. The write-enabler is different for each server, so server1 cannot get modification authority on server2. Everybody with the write-cap will be able to compute the write-enabler.

So in the RSA scheme, in fact anybody can perform the initial publish of a new mutable file, even

I realized this morning that we can't currently repair mutable files without the write-cap. (We'd like to be able to repair them with merely the storage index, so that nodes which are not given read- or write- access could do repair work, allowing us to distribute the workload out to untrusted machines). The problem is both more and less deep than you might think. At first glance, the idea of allowing a reader (or someone with even less authority) to create new shares would sound like a capability violation: they don't have write authority, why should they get to write anything?. But the key is that the write-authority is about creating new versions of the file. Repair is about creating new shares for an existing version. The mutable file uses a signature to express write authority: only the holders of the write-cap will be able to generate new valid signatures. This signature covers the root of the merkle tree that has shares as its leaves. The signature can be verified by anybody: it covers the ciphertext, not the plaintext, so a read-cap is not necessary to verify it. So the repairer can use the remaining shares to reconstruct the ciphertext, then generate new shares (using the same encoding parameters, i.e. 'k' and 'N') which should exactly match the old ones. These shares should already fit into the existing hash tree, so the repairer can create perfectly valid new shares. The stumbling block is in how the storage server knows that it ought to accept those new shares. Let's call this "publish authority" to distinguish it from the nominally-identical "write authority". The current RSA-based scheme uses "write-enablers", a shared secret that is used to prove posession of the write-cap that does not involve signatures. The write-cap is hashed with each server's nodeid, and the result is the "write-enabler". When the share is first created, the original publisher provides the write-enabler, and it is stored next to the share (in a region that readers cannot access). When later publishers want to update the share, they must provide the same write-enabler. The write-enabler is different for each server, so server1 cannot get modification authority on server2. Everybody with the write-cap will be able to compute the write-enabler. So in the RSA scheme, in fact anybody can perform the initial publish of a new mutable file, even

warner commented

2008-07-17 19:56:51 +00:00

Author

Hrm, that comment got cut off and lost about half of what I wrote. Pity.

The summary is that we need a way to update the write-enablers when a repairer or share-migration tool causes a valid share to be put on a server. This operation will probably require a signed message, so the server will both need to know about the layout of the share (which is a version-coupling problem that I'd prefer to avoid) and will need to do pubkey verification (which is relatively expensive, but I'm ok with doing it just for repair operations, since they shouldn't happen very frequently).

Ticket #489 tracks a potential problem with the non-pubkey-based update-write-enablers approach that I've been considering so far. This problem and that one will probably be solved together.

Hrm, that comment got cut off and lost about half of what I wrote. Pity. The summary is that we need a way to update the write-enablers when a repairer or share-migration tool causes a valid share to be put on a server. This operation will probably require a signed message, so the server will both need to know about the layout of the share (which is a version-coupling problem that I'd prefer to avoid) and will need to do pubkey verification (which is relatively expensive, but I'm ok with doing it just for repair operations, since they shouldn't happen very frequently). Ticket #489 tracks a potential problem with the non-pubkey-based update-write-enablers approach that I've been considering so far. This problem and that one will probably be solved together.

warner commented

2008-09-03 01:35:06 +00:00

Author

The 1.3.0 release is all about checker/repairer. We're implementing it differently that this ticket originally described.

warner modified the milestone from undecided to 1.3.0

2008-09-03 01:35:06 +00:00

warner was unassigned by zooko

2008-09-24 13:29:33 +00:00

zooko self-assigned this 2008-09-24 13:29:33 +00:00

zooko changed title from ~~build the repairer~~ to repairer service

2008-09-24 13:29:53 +00:00

zooko added

p/critical

and removed

p/major

labels 2008-09-24 13:50:27 +00:00

zooko was unassigned by warner

2009-02-04 00:11:19 +00:00

warner self-assigned this 2009-02-04 00:11:19 +00:00

warner commented

2009-02-04 00:46:22 +00:00

Author

Then, as we drifted away from the idea of clients maintaining manifest lists,
we started thinking about clients performing periodic deep-check and
deep-check-and-repair operations instead.

Now, as we're writing tools to maintain the allmydata.com production grid,
we're drifting back towards the standalone process idea. The current
direction my tools are headed is towards a daemon which holds on to customer
rootcaps (which some day can be replaced by mere traversal-caps),
periodically scans them to develop a manifest, then checks and repairs the
results. In practice, it would look a lot like the original idea, but it
would generate the manifests by itself. For customers who don't share a
rootcap with us, they could generate their manifest themselves and hand us
the verifycaps, perhaps in some automated way. In addition, since we don't
have Accounting yet, this daemon is also responsible for examining the
manifest to compute total-space-used for each account. It is also used to
create a list of active files, so GC can be performed.

So the new daemon design is also obligated to help fill in the gaps (for
Accounting and GC).

At the moment, I'm performing these tasks with a bunch of manual scripts. In
the near future, I plan to combine these scripts into a daemon that will
fulfill the goals of this ticket. In the further future (when GC and
Accounting are handled by more appropriate mechanisms), this daemon can be
broken back down into something resembling the original concept: check+repair
only.

I'm moving this ticket out of the tahoe-1.3.0 release, because the real
consumer of this daemon is the allmydata.com production grid. I intend to
commit the code (to the misc/ subdirectory), so other folks can take
advantage of it, but we hope to make it unnecessary in the long run, so it
doesn't quite fit into src/allmydata yet.

I'm also reducing its priority level. The original reason we raised its
priority to critical was that we needed the Repairer itself (the ability to
do POST t=check&repair=true), and that has been implemented and committed
under the auspices of a different ticket. The "repairer service" (which
decides what should be repaired) is at the next layer up, and is the subject
of this ticket.

Ok, so the original concept for this ticket was a standalone process, a daemon somewhere, which was given lists of repaircaps/verifycaps by clients (who maintain manifest lists somehow), and spends its time crawling over these verifycaps, checking and repairing. Then, as we drifted away from the idea of clients maintaining manifest lists, we started thinking about clients performing periodic deep-check and deep-check-and-repair operations instead. Now, as we're writing tools to maintain the allmydata.com production grid, we're drifting back towards the standalone process idea. The current direction my tools are headed is towards a daemon which holds on to customer rootcaps (which some day can be replaced by mere traversal-caps), periodically scans them to develop a manifest, then checks and repairs the results. In practice, it would look a lot like the original idea, but it would generate the manifests by itself. For customers who don't share a rootcap with us, they could generate their manifest themselves and hand us the verifycaps, perhaps in some automated way. In addition, since we don't have Accounting yet, this daemon is also responsible for examining the manifest to compute total-space-used for each account. It is also used to create a list of active files, so GC can be performed. So the new daemon design is also obligated to help fill in the gaps (for Accounting and GC). At the moment, I'm performing these tasks with a bunch of manual scripts. In the near future, I plan to combine these scripts into a daemon that will fulfill the goals of this ticket. In the further future (when GC and Accounting are handled by more appropriate mechanisms), this daemon can be broken back down into something resembling the original concept: check+repair only. I'm moving this ticket out of the tahoe-1.3.0 release, because the real consumer of this daemon is the allmydata.com production grid. I intend to commit the code (to the misc/ subdirectory), so other folks can take advantage of it, but we hope to make it unnecessary in the long run, so it doesn't quite fit into src/allmydata yet. I'm also reducing its priority level. The original reason we raised its priority to critical was that we needed the Repairer itself (the ability to do POST t=check&repair=true), and that has been implemented and committed under the auspices of a different ticket. The "repairer service" (which decides what should be repaired) is at the next layer up, and is the subject of this ticket.

warner added

p/major

and removed

p/critical

labels 2009-02-04 00:46:22 +00:00

zooko commented

2009-06-30 12:40:30 +00:00

Brian: is this done?

zooko modified the milestone from 1.5.0 to eventually

2009-06-30 12:40:30 +00:00

daira commented

2009-12-29 19:34:11 +00:00

Automatically scheduling repair is #643. The inability to repair given only a read cap is #625. Maybe some of the comments here should be copied to those tickets, but I think this is now a duplicate.

daira commented

2010-12-12 23:27:24 +00:00

(These are not to be confused with #643, which is a less ambitious ticket about scheduling the existing deep-checker/repairer using a cron job or the Windows scheduler.)

#450 was a duplicate of this ticket. If a repair operation were to also rebalance shares (as of v1.8.1 it does not), then this would be a duplicate of #543 ('rebalancing manager'). So we should close this ticket as a duplicate iff we decide that repair should rebalance. (These are not to be confused with #643, which is a less ambitious ticket about scheduling the existing deep-checker/repairer using a cron job or the Windows scheduler.)

Rows
Columns