Re: Redirects and Revocation in a Capability Filesystem

On Sat, Nov 8, 2014 at 5:18 AM, Rob Meijer <rmeijer-qWit8jRvyhVmR6Xm/[email protected]> wrote:

>
> How much are you willing to pay in performance and storage? And how does
> your solution scale in these respect?
>

For transitive revocability and flexible mount points with compositional
behavior, I'm willing to pay a lot more than my solution asks.

In the current design, the effective storage hit is negligible: one object
is added to the system for each revocation point, but that's essential. One
byte is added to a capability for each revocation point, but in practice I
can expect this to no more than double or triple the capability size (e.g.
it's extremely rare to have filesystem paths that are fifty links deep,
which would be necessary to triple the cap size); the outliers would mostly
exist to prove they can exist, and would not be the bulk of the cost.

The performance hit is searching an index or graph for a viable path. This
is a O(N) linear search in the base case. Fortunately, it's also highly
cacheable. So the common case cost, for using a resource many times or many
related resources, is much smaller.



If you are willing to take the (O(N)) performance (with N being the number
> of revocation points in a path) and (O(NlogN)) storage hit (with N being
> the upper bound of covered by a revocation point), you could use
> Rumpelstiltskin hash trees with extended attributes as I described.


I don't understand all of your solution at the moment. Was eliminating
potentially cyclic redirects essential to these performance numbers? Or was
it just a choice you made?



these scaling specs are not particularly appealing, especially as apart
> from the big O scaling issues, for small files and directories even a
> single revocation point already adds up to almost 400% of disk IO
> overhead.  What kind of price can be expected from your solution in this
> respect? Is it better than my O(N) performance and O(NlogN) state?
>

I do think my approach will offer better performance. The state overhead
barely even registers (O(1) per redirect), and the space overhead including
non-state elements is only slightly higher (one or two extra bytes on every
revocable capability), and the worst-case validation is O(N), but is highly
cacheable.

My solution also seems more expressive, allowing for redirects to form
ad-hoc cyclic graphs (which happen to overlay a tree structure, in my use
case). And I intend to make heavy use of it - e.g. every user directory is
revocable, and users may have revocable sessions, and applications will
typically be given revocable spaces. The 'revocation' in my model has some
useful stability properties, i.e. you can just as easily un-revoke by
adding the redirect back to the graph, thus treat revoke as 'disable'.

OTOH, we aren't comparing apples to apples, here. My design doesn't require
encrypting data on disk, so I'm not including keys in each ID. I'm most
likely going to implement it above Berkeley DB rather than directly on a
filesystem (I want my ACID and log files and smart memcache). Having
fixed-size capabilities isn't essential for my use cases.


>

_______________________________________________
cap-talk mailing list
[email protected]
http://www.eros-os.org/mailman/listinfo/cap-talk