docs/garbage-collection.rst

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