docs/performance.rst

   1 .. -*- coding: utf-8-with-signature -*-
   2
   3 ============================================
   4 Performance costs for some common operations
   5 ============================================
   6
   7 1.  `Publishing an A-byte immutable file`_
   8 2.  `Publishing an A-byte mutable file`_
   9 3.  `Downloading B bytes of an A-byte immutable file`_
  10 4.  `Downloading B bytes of an A-byte mutable file`_
  11 5.  `Modifying B bytes of an A-byte mutable file`_
  12 6.  `Inserting/Removing B bytes in an A-byte mutable file`_
  13 7.  `Adding an entry to an A-entry directory`_
  14 8.  `Listing an A entry directory`_
  15 9.  `Checking an A-byte file`_
  16 10. `Verifying an A-byte file (immutable)`_
  17 11. `Repairing an A-byte file (mutable or immutable)`_
  18
  19 ``K`` indicates the number of shares required to reconstruct the file
  20 (default: 3)
  21
  22 ``N`` indicates the total number of shares produced (default: 10)
  23
  24 ``S`` indicates the segment size (default: 128 KiB)
  25
  26 ``A`` indicates the number of bytes in a file
  27
  28 ``B`` indicates the number of bytes of a file that are being read or
  29 written
  30
  31 ``G`` indicates the number of storage servers on your grid
  32
  33 Most of these cost estimates may have a further constant multiplier: when a
  34 formula says ``N/K*S``, the cost may actually be ``2*N/K*S`` or ``3*N/K*S``.
  35 Also note that all references to mutable files are for SDMF-formatted files;
  36 this document has not yet been updated to describe the MDMF format.
  37
  38 Publishing an ``A``-byte immutable file
  39 =======================================
  40
  41 when the file is already uploaded
  42 ---------------------------------
  43
  44 If the file is already uploaded with the exact same contents, same
  45 erasure coding parameters (K, N), and same added convergence secret,
  46 then it reads the whole file from disk one time while hashing it to
  47 compute the storage index, then contacts about N servers to ask each
  48 one to store a share. All of the servers reply that they already have
  49 a copy of that share, and the upload is done.
  50
  51 disk: A
  52
  53 cpu: ~A
  54
  55 network: ~N
  56
  57 memory footprint: S
  58
  59 when the file is not already uploaded
  60 -------------------------------------
  61
  62 If the file is not already uploaded with the exact same contents, same
  63 erasure coding parameters (K, N), and same added convergence secret,
  64 then it reads the whole file from disk one time while hashing it to
  65 compute the storage index, then contacts about N servers to ask each
  66 one to store a share. Then it uploads each share to a storage server.
  67
  68 disk: 2*A
  69
  70 cpu: 2*~A
  71
  72 network: N/K*A
  73
  74 memory footprint: N/K*S
  75
  76 Publishing an ``A``-byte mutable file
  77 =====================================
  78
  79 cpu: ~A + a large constant for RSA keypair generation
  80
  81 network: A
  82
  83 memory footprint: N/K*A
  84
  85 notes: Tahoe-LAFS generates a new RSA keypair for each mutable file that it
  86 publishes to a grid. This takes up to 1 or 2 seconds on a typical desktop PC.
  87
  88 Part of the process of encrypting, encoding, and uploading a mutable file to a
  89 Tahoe-LAFS grid requires that the entire file be in memory at once. For larger
  90 files, this may cause Tahoe-LAFS to have an unacceptably large memory footprint
  91 (at least when uploading a mutable file).
  92
  93 Downloading ``B`` bytes of an ``A``-byte immutable file
  94 =======================================================
  95
  96 cpu: ~B
  97
  98 network: B
  99
 100 notes: When Tahoe-LAFS 1.8.0 or later is asked to read an arbitrary
 101 range of an immutable file, only the S-byte segments that overlap the
 102 requested range will be downloaded.
 103
 104 (Earlier versions would download from the beginning of the file up
 105 until the end of the requested range, and then continue to download
 106 the rest of the file even after the request was satisfied.)
 107
 108 Downloading ``B`` bytes of an ``A``-byte mutable file
 109 =====================================================
 110
 111 cpu: ~A
 112
 113 network: A
 114
 115 memory footprint: A
 116
 117 notes: As currently implemented, mutable files must be downloaded in
 118 their entirety before any part of them can be read. We are
 119 exploring fixes for this; see ticket #393 for more information.
 120
 121 Modifying ``B`` bytes of an ``A``-byte mutable file
 122 ===================================================
 123
 124 cpu: ~A
 125
 126 network: A
 127
 128 memory footprint: N/K*A
 129
 130 notes: If you upload a changed version of a mutable file that you
 131 earlier put onto your grid with, say, 'tahoe put --mutable',
 132 Tahoe-LAFS will replace the old file with the new file on the
 133 grid, rather than attempting to modify only those portions of the
 134 file that have changed. Modifying a file in this manner is
 135 essentially uploading the file over again, except that it re-uses
 136 the existing RSA keypair instead of generating a new one.
 137
 138 Inserting/Removing ``B`` bytes in an ``A``-byte mutable file
 139 ============================================================
 140
 141 cpu: ~A
 142
 143 network: A
 144
 145 memory footprint: N/K*A
 146
 147 notes: Modifying any part of a mutable file in Tahoe-LAFS requires that
 148 the entire file be downloaded, modified, held in memory while it is
 149 encrypted and encoded, and then re-uploaded. A future version of the
 150 mutable file layout ("LDMF") may provide efficient inserts and
 151 deletes. Note that this sort of modification is mostly used internally
 152 for directories, and isn't something that the WUI, CLI, or other
 153 interfaces will do -- instead, they will simply overwrite the file to
 154 be modified, as described in "Modifying B bytes of an A-byte mutable
 155 file".
 156
 157 Adding an entry to an ``A``-entry directory
 158 ===========================================
 159
 160 cpu: ~A
 161
 162 network: ~A
 163
 164 memory footprint: N/K*~A
 165
 166 notes: In Tahoe-LAFS, directories are implemented as specialized mutable
 167 files. So adding an entry to a directory is essentially adding B
 168 (actually, 300-330) bytes somewhere in an existing mutable file.
 169
 170 Listing an ``A`` entry directory
 171 ================================
 172
 173 cpu: ~A
 174
 175 network: ~A
 176
 177 memory footprint: N/K*~A
 178
 179 notes: Listing a directory requires that the mutable file storing the
 180 directory be downloaded from the grid. So listing an A entry
 181 directory requires downloading a (roughly) 330 * A byte mutable
 182 file, since each directory entry is about 300-330 bytes in size.
 183
 184 Checking an ``A``-byte file
 185 ===========================
 186
 187 cpu: ~G
 188
 189 network: ~G
 190
 191 memory footprint: negligible
 192
 193 notes: To check a file, Tahoe-LAFS queries all the servers that it knows
 194 about. Note that neither of these values directly depend on the size
 195 of the file. This is relatively inexpensive, compared to the verify
 196 and repair operations.
 197
 198 Verifying an A-byte file (immutable)
 199 ====================================
 200
 201 cpu: ~N/K*A
 202
 203 network: N/K*A
 204
 205 memory footprint: N/K*S
 206
 207 notes: To verify a file, Tahoe-LAFS downloads all of the ciphertext
 208 shares that were originally uploaded to the grid and integrity checks
 209 them. This is (for grids with good redundancy) more expensive than
 210 downloading an A-byte file, since only a fraction of these shares would
 211 be necessary to recover the file.
 212
 213 Verifying an A-byte file (mutable)
 214 ==================================
 215
 216 cpu: ~N/K*A
 217
 218 network: N/K*A
 219
 220 memory footprint: N/K*A
 221
 222 notes: To verify a file, Tahoe-LAFS downloads all of the ciphertext
 223 shares that were originally uploaded to the grid and integrity checks
 224 them. This is (for grids with good redundancy) more expensive than
 225 downloading an A-byte file, since only a fraction of these shares would
 226 be necessary to recover the file.
 227
 228 Repairing an ``A``-byte file (mutable or immutable)
 229 ===================================================
 230
 231 cpu: variable, between ~A and ~N/K*A
 232
 233 network: variable; between A and N/K*A
 234
 235 memory footprint (immutable): (1+N/K)*S
 236               (SDMF mutable): (1+N/K)*A
 237
 238 notes: To repair a file, Tahoe-LAFS downloads the file, and
 239 generates/uploads missing shares in the same way as when it initially
 240 uploads the file.  So, depending on how many shares are missing, this
 241 can cost as little as a download or as much as a download followed by
 242 a full upload.
 243
 244 Since SDMF files have only one segment, which must be processed in its
 245 entirety, repair requires a full-file download followed by a full-file
 246 upload.