2012-05-18 19:08, Edward Ned Harvey wrote:
From: zfs-discuss-boun...@opensolaris.org [mailto:zfs-discuss-
boun...@opensolaris.org] On Behalf Of Jim Klimov

I'm reading the ZFS on-disk spec, and I get the idea that there's an
uberblock pointing to a self-balancing tree (some say b-tree, some say
avl-tree, some say nv-tree), where data is only contained in the nodes.  But
I haven't found one particular important detail yet:

On which values does the balancing tree balance?  Is it balancing on the
logical block address?  This would make sense, as an application requests to
read/write some logical block, making it easy and fast to find the
corresponding physical blocks...

My memory fails me here for a precise answer... I think that
the on-disk data within a raidzN top-level VDEV (mirrors are
trivial) is laid out as follows, for an arbitrary 6-disk set
of raidz2 TLVDEV:

D1   D2   D3   D4   D5   D6
Ar1  Ar2  Ad1  Ad2  Ad3  Ad4
Br1  Br2  Bd1  Cr1  Cr2  Cd1
Cd2  Cd3  Cd4  Cr3  Cr4  Cd5
Cd6  Dr1  Dr2  Dd1  ...

In these examples above, several blocks are laid out in sectors
of different disks, including the redundancy blocks. Sequential
accesses on one disk progress in a column from top to bottom.
Accesses in a row are parallelized between many disks.

The "A" block userdata is 4 sectors long, with 2 redundancy blocks.
The "B" block has just one userdata sector, and the "C" block has
6 userdata sectors with a redundancy started for each 4 sectors.

AFAIK each ZFS block fully resides within one TLVDEV (and ditto
copies have their own separate life in another TLVDEV if available),
and striping over several TLVDEVs occurs at a whole-block level.
This, in particular, allows disbalanced pools with TLVDEVs of
different size and layout.

IF this picture is correct (confirmation or the reverse is
kindly requested), then:

1) DVA to LBA translation should be somewhat trivial, since
   the DVA is defined as "ID(tlvdev):offset:length" in 512-byte
   units (regardless of ashift value on the pool). I did not
   test this in practice or incur from the code though.

   I don't know if there are any gaps to take into account
   (i.e. maybe between "metaslabs", which are supposed to be
   about 200 of which per vdev (or tlvdev, or pool?) in order to
   limit seeking between data written at roughly the same time.
   Even if there are gaps (i.e. to round allocations to on-disk
   tracks or offsets at multiples of a given number), I'd not
   complicate things and just leave the gaps as addressable but
   unreferenced free spaces.

   A poster on the list recently referenced "slabs", I don't
   think I saw this term - but I guess it stands for the total
   allocation needed for a userdata block?

2) Addressing of blocks (or reverse - saying that these sectors
   belong to a particular block or are available) is impossible
   without knowing the (generally whole) blockpointer tree, and
   depending on (re-)written object sizes, the same sector can
   at different times in its life belong to blocks (slabs?) of
   different lengths and starting at different DVA offsets...

   Indeed, we also can not assume that sectors read-in from the
   disks contain a valid part of the blockpointer tree (despite
   even matching some magic number), not until we find a path
   through the known tree that leads to this block (I discussed
   this in my other post regarding vdev prefetch and defrag).
   However since reads are free as long as the HDD head is in
   the right location, and if blkptr_t's leading one to another
   are colocated on the disk, clever use of the prefetch and
   timely inspection of the prefetch cache can hopefully boost
   the BPtree walking speed.

   MAYBE I am wrong in this and there is also an allocation map
   in the large metaslabs or something? (I know there is some
   cleverness about finding available locations to write into,
   but I'm not ready to speak about it off the top of my head).

   I am not sure if this gives a clue to whether it's "balancing
   on the logical block address?" though :) AFAIK the balancing
   tries to keep the maximum tree depth shortest, yet there is
   one root block and no rewriting of existing unchanged stale
   blocks (tree nodes). I am puzzled too :)

3) The layout is fixed at tlvdev creation time by its total
   number of disks since that directly affects the calculation
   "on which disk does an offset'ed sector belong" - it would
   be offset modulo number of disks for raidzN regardless of N
   (because of not-full stripes), and just 0 for single drives
   and mirrors. This is why resizing a raidz set is indeed hard,
   while conversion of single disks to mirrors and back is easy.

   To a lesser extent the layout is limited by vdev size (which
   can be increased easily, but can not be decreased without
   reallocation and BP rewrite [*1]), and somewhat by the number
   of redundancy disks which influences individual blocks' on-disk
   representation and required length [*2].

[*1]: This might be doable relatively easily by limiting the top
   writeable address, and executing a routine similar to zfs-send
   and zfs-recv to relocate all blocks with a larger DVA offset
   on this TLVDEV to any accessible location on the pool. When
   no more referenced blocks remain above the watermark, the
   TLVDEV can be shrunk. This may involve some magic with TXG
   "birth" and "alloc" fields in blkptr's as well.

[*2]: As we know, in Oracle ZFS there is hybrid allocation,
   which in particular allows mirrored writes for metadata
   and raidz writes for userdata to coexist on a pool.
   I can only guess there is some new bit-flag in the blkptr_t
   for that? Anyhow, the number of redundancy disks and the
   layout algorithm for a particular block can be variable,
   so it seems...

//Jim Klimov
zfs-discuss mailing list

Reply via email to