[tahoe-lafs-trac-stream] [Tahoe-LAFS] #1906: constant-time directory lookup

[Tahoe-LAFS]

#1906: constant-time directory lookup
-------------------------+-------------------------------------------------
     Reporter:           |      Owner:  davidsarah
  davidsarah             |     Status:  new
         Type:           |  Milestone:  undecided
  enhancement            |    Version:  1.9.2
     Priority:  normal   |   Keywords:  performance directory database
    Component:  code-    |  newcaps research
  dirnodes               |
   Resolution:           |
Launchpad Bug:           |
-------------------------+-------------------------------------------------

Old description:

> Currently to look up an entry in a directory, it is necessary to download
> the whole file backing the directory, then decode it to find the correct
> child. This takes linear time in the number of entries.
>
> Suppose that the secret cryptovalue of each child were derived from the
> cap of the parent directory and the child name. Then, provided that the
> metadata is not needed, it is possible to obtain the child directly
> rather than via the parent. (If that child does not exist, we can't
> distinguish that from missing shares, but that isn't necessarily a
> problem.)
>
> Note that this makes directories more useful for some database-like
> applications, rather than just as filesystem directories per-se.

New description:

 Currently to look up an entry in a directory, it is necessary to download
 the whole file backing the directory, then decode it to find the correct
 child. This takes linear time in the number of entries.

 Suppose that the secret cryptovalue of each child were derived from the
 cap of the parent directory and the child name. Then, provided that the
 metadata is not needed, it is possible to obtain the child directly rather
 than via the parent. (If that child does not exist, we can't distinguish
 that from missing shares, but that isn't necessarily a problem.)

 Note that this makes directories more useful for some database-like
 applications, rather than just as filesystem directories per-se.

--

Comment (by daira):

 Reminder to self: try a pairing-based drop cryptosystem.

--
Ticket URL: <https://tahoe-lafs.org/trac/tahoe-lafs/ticket/1906#comment:5>
Tahoe-LAFS <https://Tahoe-LAFS.org>
secure decentralized storage