Hi,
On Tue, Apr 18, 2000 at 09:44:28AM -0400, Alexander Viro wrote:
>
> On Tue, 18 Apr 2000, Stephen C. Tweedie wrote:
> > On Tue, Apr 18, 2000 at 09:12:47AM -0400, Alexander Viro wrote:
> > >
> > Yes, but if you are talking about storing extents rather than individual
> > block mappings, then the amount of data in the tree will be a _tiny_
> > fraction of the amount needed in the current scheme.
>
> Yes. And what will it do to journalling/soft-updates/whatever equivalent
> you prefer? At least with the normal scheme the amount of requests per
> transaction is limited and we know the limit...
For static (non-btree, append-only) extent map trees, the complexity
doesn't change. For the btree case it's more of a problem, but still
quite tractable. The amount of data you can potentially touch is still
bounded by an upper limit of one rotate per depth of the tree or one split
per tree depth. Maybe 3 or 4 blocks per tree depth.
The current ext3 journaling infrastructure has to be _very_ pessimistic
about block usage anyway, and has a reservation mechanism to make quite
sure that you can always complete a transaction. That mechanism will
cope with btrees just fine.
Also, note that if you do get short on space, a tree rebalancing operation
can be broken into multiple transactions without losing tree balance in
many of the common types of btree. In particular, if you have a scheme
where you split blocks pessimistically on the way down the tree for an
insert, then it's easy to make each descent through the tree into a
separate transaction. (The advantage of that mechanism is locking: it
means that you never have to rebalance the tree on the way up, so that
you _always_ lock from the top of the tree down, and so it is much easier
to stay deadlock-free while at the same time minimising locking.)
--Stephen
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Sun Apr 23 2000 - 21:00:13 EST