docs/garbage-collection.rst

   1 ===========================
   2 Garbage Collection in Tahoe
   3 ===========================
   4
   5 1. `Overview`_
   6 2. `Client-side Renewal`_
   7 3. `Server Side Expiration`_
   8 4. `Expiration Progress`_
   9 5. `Future Directions`_
  10
  11 Overview
  12 ========
  13
  14 When a file or directory in the virtual filesystem is no longer referenced,
  15 the space that its shares occupied on each storage server can be freed,
  16 making room for other shares. Tahoe currently uses a garbage collection
  17 ("GC") mechanism to implement this space-reclamation process. Each share has
  18 one or more "leases", which are managed by clients who want the
  19 file/directory to be retained. The storage server accepts each share for a
  20 pre-defined period of time, and is allowed to delete the share if all of the
  21 leases are cancelled or allowed to expire.
  22
  23 Garbage collection is not enabled by default: storage servers will not delete
  24 shares without being explicitly configured to do so. When GC is enabled,
  25 clients are responsible for renewing their leases on a periodic basis at
  26 least frequently enough to prevent any of the leases from expiring before the
  27 next renewal pass.
  28
  29 There are several tradeoffs to be considered when choosing the renewal timer
  30 and the lease duration, and there is no single optimal pair of values. See
  31 the "lease-tradeoffs.svg" diagram to get an idea for the tradeoffs involved.
  32 If lease renewal occurs quickly and with 100% reliability, than any renewal
  33 time that is shorter than the lease duration will suffice, but a larger ratio
  34 of duration-over-renewal-time will be more robust in the face of occasional
  35 delays or failures.
  36
  37 The current recommended values for a small Tahoe grid are to renew the leases
  38 once a week, and to give each lease a duration of 31 days. Renewing leases
  39 can be expected to take about one second per file/directory, depending upon
  40 the number of servers and the network speeds involved. Note that in the
  41 current release, the server code enforces a 31 day lease duration: there is
  42 not yet a way for the client to request a different duration (however the
  43 server can use the "expire.override_lease_duration" configuration setting to
  44 increase or decrease the effective duration to something other than 31 days).
  45
  46 Client-side Renewal
  47 ===================
  48
  49 If all of the files and directories which you care about are reachable from a
  50 single starting point (usually referred to as a "rootcap"), and you store
  51 that rootcap as an alias (via "tahoe create-alias"), then the simplest way to
  52 renew these leases is with the following CLI command:
  53
  54   tahoe deep-check --add-lease ALIAS:
  55
  56 This will recursively walk every directory under the given alias and renew
  57 the leases on all files and directories. (You may want to add a --repair flag
  58 to perform repair at the same time). Simply run this command once a week (or
  59 whatever other renewal period your grid recommends) and make sure it
  60 completes successfully. As a side effect, a manifest of all unique files and
  61 directories will be emitted to stdout, as well as a summary of file sizes and
  62 counts. It may be useful to track these statistics over time.
  63
  64 Note that newly uploaded files (and newly created directories) get an initial
  65 lease too: the --add-lease process is only needed to ensure that all older
  66 objects have up-to-date leases on them.
  67
  68 For larger systems (such as a commercial grid), a separate "maintenance
  69 daemon" is under development. This daemon will acquire manifests from
  70 rootcaps on a periodic basis, keep track of checker results, manage
  71 lease-addition, and prioritize repair needs, using multiple worker nodes to
  72 perform these jobs in parallel. Eventually, this daemon will be made
  73 appropriate for use by individual users as well, and may be incorporated
  74 directly into the client node.
  75
  76 Server Side Expiration
  77 ======================
  78
  79 Expiration must be explicitly enabled on each storage server, since the
  80 default behavior is to never expire shares. Expiration is enabled by adding
  81 config keys to the "[storage]" section of the tahoe.cfg file (as described
  82 below) and restarting the server node.
  83
  84 Each lease has two parameters: a create/renew timestamp and a duration. The
  85 timestamp is updated when the share is first uploaded (i.e. the file or
  86 directory is created), and updated again each time the lease is renewed (i.e.
  87 "tahoe check --add-lease" is performed). The duration is currently fixed at
  88 31 days, and the "nominal lease expiration time" is simply $duration seconds
  89 after the $create_renew timestamp. (In a future release of Tahoe, the client
  90 will get to request a specific duration, and the server will accept or reject
  91 the request depending upon its local configuration, so that servers can
  92 achieve better control over their storage obligations).
  93
  94 The lease-expiration code has two modes of operation. The first is age-based:
  95 leases are expired when their age is greater than their duration. This is the
  96 preferred mode: as long as clients consistently update their leases on a
  97 periodic basis, and that period is shorter than the lease duration, then all
  98 active files and directories will be preserved, and the garbage will
  99 collected in a timely fashion.
 100
 101 Since there is not yet a way for clients to request a lease duration of other
 102 than 31 days, there is a tahoe.cfg setting to override the duration of all
 103 leases. If, for example, this alternative duration is set to 60 days, then
 104 clients could safely renew their leases with an add-lease operation perhaps
 105 once every 50 days: even though nominally their leases would expire 31 days
 106 after the renewal, the server would not actually expire the leases until 60
 107 days after renewal.
 108
 109 The other mode is an absolute-date-cutoff: it compares the create/renew
 110 timestamp against some absolute date, and expires any lease which was not
 111 created or renewed since the cutoff date. If all clients have performed an
 112 add-lease some time after March 20th, you could tell the storage server to
 113 expire all leases that were created or last renewed on March 19th or earlier.
 114 This is most useful if you have a manual (non-periodic) add-lease process.
 115 Note that there is not much point to running a storage server in this mode
 116 for a long period of time: once the lease-checker has examined all shares and
 117 expired whatever it is going to expire, the second and subsequent passes are
 118 not going to find any new leases to remove.
 119
 120 The tahoe.cfg file uses the following keys to control lease expiration::
 121
 122   [storage]
 123
 124   expire.enabled = (boolean, optional)
 125
 126     If this is True, the storage server will delete shares on which all leases
 127     have expired. Other controls dictate when leases are considered to have
 128     expired. The default is False.
 129
 130   expire.mode = (string, "age" or "cutoff-date", required if expiration enabled)
 131
 132         If this string is "age", the age-based expiration scheme is used, and the
 133         "expire.override_lease_duration" setting can be provided to influence the
 134         lease ages. If it is "cutoff-date", the absolute-date-cutoff mode is used,
 135         and the "expire.cutoff_date" setting must be provided to specify the cutoff
 136         date. The mode setting currently has no default: you must provide a value.
 137
 138         In a future release, this setting is likely to default to "age", but in this
 139         release it was deemed safer to require an explicit mode specification.
 140
 141   expire.override_lease_duration = (duration string, optional)
 142
 143         When age-based expiration is in use, a lease will be expired if its
 144         "lease.create_renew" timestamp plus its "lease.duration" time is
 145         earlier/older than the current time. This key, if present, overrides the
 146         duration value for all leases, changing the algorithm from:
 147
 148     if (lease.create_renew_timestamp + lease.duration) < now:
 149         expire_lease()
 150
 151     to:
 152
 153     if (lease.create_renew_timestamp + override_lease_duration) < now:
 154         expire_lease()
 155
 156         The value of this setting is a "duration string", which is a number of days,
 157         months, or years, followed by a units suffix, and optionally separated by a
 158         space, such as one of the following:
 159
 160           7days
 161           31day
 162           60 days
 163           2mo
 164           3 month
 165           12 months
 166           2years
 167
 168         This key is meant to compensate for the fact that clients do not yet have
 169         the ability to ask for leases that last longer than 31 days. A grid which
 170         wants to use faster or slower GC than a 31-day lease timer permits can use
 171         this parameter to implement it. The current fixed 31-day lease duration
 172         makes the server behave as if "lease.override_lease_duration = 31days" had
 173         been passed.
 174
 175         This key is only valid when age-based expiration is in use (i.e. when
 176         "expire.mode = age" is used). It will be rejected if cutoff-date expiration
 177         is in use.
 178
 179   expire.cutoff_date = (date string, required if mode=cutoff-date)
 180
 181         When cutoff-date expiration is in use, a lease will be expired if its
 182         create/renew timestamp is older than the cutoff date. This string will be a
 183         date in the following format:
 184
 185           2009-01-16   (January 16th, 2009)
 186           2008-02-02
 187           2007-12-25
 188
 189         The actual cutoff time shall be midnight UTC at the beginning of the given
 190         day. Lease timers should naturally be generous enough to not depend upon
 191         differences in timezone: there should be at least a few days between the
 192         last renewal time and the cutoff date.
 193
 194         This key is only valid when cutoff-based expiration is in use (i.e. when
 195         "expire.mode = cutoff-date"). It will be rejected if age-based expiration is
 196         in use.
 197
 198   expire.immutable = (boolean, optional)
 199
 200         If this is False, then immutable shares will never be deleted, even if their
 201         leases have expired. This can be used in special situations to perform GC on
 202         mutable files but not immutable ones. The default is True.
 203
 204   expire.mutable = (boolean, optional)
 205
 206         If this is False, then mutable shares will never be deleted, even if their
 207         leases have expired. This can be used in special situations to perform GC on
 208         immutable files but not mutable ones. The default is True.
 209
 210 Expiration Progress
 211 ===================
 212
 213 In the current release, leases are stored as metadata in each share file, and
 214 no separate database is maintained. As a result, checking and expiring leases
 215 on a large server may require multiple reads from each of several million
 216 share files. This process can take a long time and be very disk-intensive, so
 217 a "share crawler" is used. The crawler limits the amount of time looking at
 218 shares to a reasonable percentage of the storage server's overall usage: by
 219 default it uses no more than 10% CPU, and yields to other code after 100ms. A
 220 typical server with 1.1M shares was observed to take 3.5 days to perform this
 221 rate-limited crawl through the whole set of shares, with expiration disabled.
 222 It is expected to take perhaps 4 or 5 days to do the crawl with expiration
 223 turned on.
 224
 225 The crawler's status is displayed on the "Storage Server Status Page", a web
 226 page dedicated to the storage server. This page resides at $NODEURL/storage,
 227 and there is a link to it from the front "welcome" page. The "Lease
 228 Expiration crawler" section of the status page shows the progress of the
 229 current crawler cycle, expected completion time, amount of space recovered,
 230 and details of how many shares have been examined.
 231
 232 The crawler's state is persistent: restarting the node will not cause it to
 233 lose significant progress. The state file is located in two files
 234 ($BASEDIR/storage/lease_checker.state and lease_checker.history), and the
 235 crawler can be forcibly reset by stopping the node, deleting these two files,
 236 then restarting the node.
 237
 238 Future Directions
 239 =================
 240
 241 Tahoe's GC mechanism is undergoing significant changes. The global
 242 mark-and-sweep garbage-collection scheme can require considerable network
 243 traffic for large grids, interfering with the bandwidth available for regular
 244 uploads and downloads (and for non-Tahoe users of the network).
 245
 246 A preferable method might be to have a timer-per-client instead of a
 247 timer-per-lease: the leases would not be expired until/unless the client had
 248 not checked in with the server for a pre-determined duration. This would
 249 reduce the network traffic considerably (one message per week instead of
 250 thousands), but retain the same general failure characteristics.
 251
 252 In addition, using timers is not fail-safe (from the client's point of view),
 253 in that a client which leaves the network for an extended period of time may
 254 return to discover that all of their files have been garbage-collected. (It
 255 *is* fail-safe from the server's point of view, in that a server is not
 256 obligated to provide disk space in perpetuity to an unresponsive client). It
 257 may be useful to create a "renewal agent" to which a client can pass a list
 258 of renewal-caps: the agent then takes the responsibility for keeping these
 259 leases renewed, so the client can go offline safely. Of course, this requires
 260 a certain amount of coordination: the renewal agent should not be keeping
 261 files alive that the client has actually deleted. The client can send the
 262 renewal-agent a manifest of renewal caps, and each new manifest should
 263 replace the previous set.
 264
 265 The GC mechanism is also not immediate: a client which deletes a file will
 266 nevertheless be consuming extra disk space (and might be charged or otherwise
 267 held accountable for it) until the ex-file's leases finally expire on their
 268 own. If the client is certain that they've removed their last reference to
 269 the file, they could accelerate the GC process by cancelling their lease. The
 270 current storage server API provides a method to cancel a lease, but the
 271 client must be careful to coordinate with anyone else who might be
 272 referencing the same lease (perhaps a second directory in the same virtual
 273 drive), otherwise they might accidentally remove a lease that should have
 274 been retained.
 275
 276 In the current release, these leases are each associated with a single "node
 277 secret" (stored in $BASEDIR/private/secret), which is used to generate
 278 renewal- and cancel- secrets for each lease. Two nodes with different secrets
 279 will produce separate leases, and will not be able to renew or cancel each
 280 others' leases.
 281
 282 Once the Accounting project is in place, leases will be scoped by a
 283 sub-delegatable "account id" instead of a node secret, so clients will be able
 284 to manage multiple leases per file. In addition, servers will be able to
 285 identify which shares are leased by which clients, so that clients can safely
 286 reconcile their idea of which files/directories are active against the
 287 server's list, and explicitly cancel leases on objects that aren't on the
 288 active list.
 289
 290 By reducing the size of the "lease scope", the coordination problem is made
 291 easier. In general, mark-and-sweep is easier to implement (it requires mere
 292 vigilance, rather than coordination), so unless the space used by deleted
 293 files is not expiring fast enough, the renew/expire timed lease approach is
 294 recommended.
 295