docs/performance.txt

   1 = Performance costs for some common operations =
   2
   3 === Publishing an A-byte immutable file ===
   4
   5 cost:  O(A)
   6
   7 notes: An immutable file uploaded using convergent encryption will
   8        require an additional I/O pass over the entire source file before
   9        the upload process can start, since convergent encryption derives
  10        the encryption key in part from the contents of the source file.
  11
  12 === Publishing an A-byte mutable file ===
  13
  14 cost:  O(A) + a large constant for RSA + memory usage.
  15
  16 notes: Tahoe-LAFS generates a new RSA keypair for each mutable file that
  17        it publishes to a grid. This takes up to 1 or 2 seconds on a
  18        typical desktop PC.
  19
  20        Part of the process of encrypting, encoding, and uploading a
  21        mutable file to a Tahoe-LAFS grid requires that the entire file
  22        be in memory at once. For larger files, this may cause
  23        Tahoe-LAFS to have an unacceptably large memory footprint (at
  24        least when uploading a mutable file).
  25
  26 === Downloading B bytes of an A-byte immutable file ===
  27
  28 time/cost until the read is satisfied: variable; up to O(A).
  29 cost of the entire operation:          O(A) if the file isn't cached.
  30
  31 notes: When asked to read an arbitrary range of an immutable file,
  32        Tahoe-LAFS will download from the beginning of the file up until
  33        it has enough of the file to satisfy the requested read.
  34        Depending on where in the file the requested range is, this can
  35        mean that the entire file is downloaded before the request is
  36        satisfied. Tahoe-LAFS will continue to download the rest of the
  37        file even after the request is satisfied, so in any case where the
  38        file actually has to downloaded from the grid, reading part of an
  39        immutable file will result in downloading all of the immutable
  40        file. Ticket #798 is a proposal to change this behavior.
  41
  42        Tahoe-LAFS will cache files that are read in this manner for a
  43        short while, so subsequent reads of the same file may be served
  44        entirely from cache, depending on what part of the file they need
  45        to read, what part of the file was read by previous reads, and
  46        how much time has elapsed since the last read.
  47
  48 === Downloading B bytes of an A-byte mutable file ===
  49
  50 cost:  O(A)
  51
  52 notes: As currently implemented, mutable files must be downloaded in
  53        their entirety before any part of them can be read. We are
  54        exploring fixes for this; see ticket #393 for more information.
  55
  56 === Modifying B bytes of an A-byte mutable file ===
  57
  58 cost:  O(A)
  59
  60 notes: If you upload a changed version of a mutable file that you
  61        earlier put onto your grid with, say, 'tahoe put --mutable',
  62        Tahoe-LAFS will replace the old file with the new file on the
  63        grid, rather than attempting to modify only those portions of the
  64        file that have changed. Modifying a file in this manner is
  65        essentially uploading the file over again, except that it re-uses
  66        the existing RSA keypair instead of generating a new one.
  67
  68 === Adding/Removing B bytes in an A-byte mutable file ===
  69
  70 cost:  O(A)
  71
  72 notes: Modifying any part of a mutable file in Tahoe-LAFS requires that
  73        the entire file be downloaded, modified, held in memory while it
  74        is encrypted and encoded, and then re-uploaded. Note that this
  75        sort of modification is mostly used internally for directories,
  76        and isn't something that the WUI, CLI, or other interfaces will
  77        do -- instead, they will simply overwrite the file to be
  78        modified, as described in "Modifying B bytes of an A-byte mutable
  79        file".
  80
  81 === Adding an entry to an A-entry directory ===
  82
  83 cost:  O(A) (roughly)
  84 notes: In Tahoe-LAFS, directories are implemented as specialized mutable
  85        files. So adding an entry to a directory is essentially adding B
  86        (actually, 300-330) bytes somewhere in an existing mutable file.
  87
  88 === Listing an A entry directory ===
  89
  90 cost:  O(A)
  91
  92 notes: Listing a directory requires that the mutable file storing the
  93        directory be downloaded from the grid. So listing an A entry
  94        directory requires downloading a (roughly) 330 * A byte mutable
  95        file, since each directory entry is about 300-330 bytes in size.
  96
  97 === Checking an A-byte file ===
  98
  99 cost:  variable; between O(N) and O(S), where N is the number of shares
 100        generated when the file was initially uploaded, and S is the
 101        number of servers on your grid.
 102
 103 notes: To check a file, Tahoe-LAFS queries the servers that it knows
 104        about until it either runs out of servers, or finds all of the
 105        shares that were originally uploaded. Note that neither of these
 106        values directly depend on the size of the file. This is
 107        relatively inexpensive, compared to the verify and repair
 108        operations.
 109
 110 === Verifying an A-byte file ===
 111
 112 cost: O(A)
 113
 114 notes: To verify a file, Tahoe-LAFS downloads all of the ciphertext
 115        shares that were originally uploaded to the grid and integrity
 116        checks them. This is, for well-behaved grids, likely to be more
 117        expensive than downloading an A-byte file, since only a fraction
 118        of these shares are necessary to recover the file.
 119
 120 === Repairing an A-byte file (mutable or immutable) ===
 121
 122 cost:  variable; up to around O(A)
 123
 124 notes: To repair a file, Tahoe-LAFS generates and uploads missing shares
 125        in the same way as when it initially uploads the file. So,
 126        depending on how many shares are missing, this can be about as
 127        expensive as initially uploading the file in the first place.