| Message ID | 146907709719.25461.3104352212846077948.stgit@birch.djwong.org (mailing list archive) |
|---|---|
| State | Accepted |
| Headers | show |
On Wed, Jul 20, 2016 at 09:58:17PM -0700, Darrick J. Wong wrote: > By my calculations, a 1,073,741,824 block AG with a 1k block size > can attain a maximum height of 9. Assuming a record size of 24 > bytes, a key/ptr size of 44 bytes, and half-full btree nodes, > we'd need 53,687,092 blocks for the records and ~6 million blocks > for the keys. That requires a btree of height 9. > > Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com> > --- I believe you.. :) but could you add a bit more detail to the commit log just to describe the calculations (e.g., how many records per leaf block, keys per node block) so 1.) I don't have to try and figure it out ;) (and probably get it wrong) and 2.) so we have a reference in the git repo going forward? Brian > fs/xfs/libxfs/xfs_btree.h | 2 +- > 1 file changed, 1 insertion(+), 1 deletion(-) > > > diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h > index b8bbb21..629ef4f 100644 > --- a/fs/xfs/libxfs/xfs_btree.h > +++ b/fs/xfs/libxfs/xfs_btree.h > @@ -133,7 +133,7 @@ do { \ > } \ > } while (0) > > -#define XFS_BTREE_MAXLEVELS 8 /* max of all btrees */ > +#define XFS_BTREE_MAXLEVELS 9 /* max of all btrees */ > > struct xfs_btree_ops { > /* size of the key and record structures */ > > _______________________________________________ > xfs mailing list > xfs@oss.sgi.com > http://oss.sgi.com/mailman/listinfo/xfs
On Tue, Aug 02, 2016 at 02:48:46PM -0400, Brian Foster wrote: > On Wed, Jul 20, 2016 at 09:58:17PM -0700, Darrick J. Wong wrote: > > By my calculations, a 1,073,741,824 block AG with a 1k block size > > can attain a maximum height of 9. Assuming a record size of 24 > > bytes, a key/ptr size of 44 bytes, and half-full btree nodes, > > we'd need 53,687,092 blocks for the records and ~6 million blocks > > for the keys. That requires a btree of height 9. > > > > Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com> > > --- > > I believe you.. :) but could you add a bit more detail to the commit log > just to describe the calculations (e.g., how many records per leaf > block, keys per node block) so 1.) I don't have to try and figure it out > ;) (and probably get it wrong) and 2.) so we have a reference in the git > repo going forward? Block size = 1024b sblock CRC header = 56b == 1024-56 = 968 bytes for tree data rmapbt record = 24b == 40 records per leaf block rmapbt ptr/key = 44b == 22 ptr/keys per block Worst case, each block is half full, so 20 records and 11 ptrs per block. 1073741824 rmap records / 20 records per block == 53687092 leaf blocks 53687092 leaves / 11 ptrs per block == 4880645 level 1 blocks == 443695 level 2 blocks == 40336 level 3 blocks == 3667 level 4 blocks == 334 level 5 blocks == 31 level 6 blocks == 3 level 7 blocks == 1 level 8 block Yay latency.... (Hey, at least this isn't ext4 which has no lower bound on block fill...) --D > > Brian > > > fs/xfs/libxfs/xfs_btree.h | 2 +- > > 1 file changed, 1 insertion(+), 1 deletion(-) > > > > > > diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h > > index b8bbb21..629ef4f 100644 > > --- a/fs/xfs/libxfs/xfs_btree.h > > +++ b/fs/xfs/libxfs/xfs_btree.h > > @@ -133,7 +133,7 @@ do { \ > > } \ > > } while (0) > > > > -#define XFS_BTREE_MAXLEVELS 8 /* max of all btrees */ > > +#define XFS_BTREE_MAXLEVELS 9 /* max of all btrees */ > > > > struct xfs_btree_ops { > > /* size of the key and record structures */ > > > > _______________________________________________ > > xfs mailing list > > xfs@oss.sgi.com > > http://oss.sgi.com/mailman/listinfo/xfs
On Tue, Aug 02, 2016 at 01:06:35PM -0700, Darrick J. Wong wrote: > On Tue, Aug 02, 2016 at 02:48:46PM -0400, Brian Foster wrote: > > On Wed, Jul 20, 2016 at 09:58:17PM -0700, Darrick J. Wong wrote: > > > By my calculations, a 1,073,741,824 block AG with a 1k block size > > > can attain a maximum height of 9. Assuming a record size of 24 > > > bytes, a key/ptr size of 44 bytes, and half-full btree nodes, > > > we'd need 53,687,092 blocks for the records and ~6 million blocks > > > for the keys. That requires a btree of height 9. > > > > > > Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com> > > > --- > > > > I believe you.. :) but could you add a bit more detail to the commit log > > just to describe the calculations (e.g., how many records per leaf > > block, keys per node block) so 1.) I don't have to try and figure it out > > ;) (and probably get it wrong) and 2.) so we have a reference in the git > > repo going forward? > > Block size = 1024b > sblock CRC header = 56b > == 1024-56 = 968 bytes for tree data > > rmapbt record = 24b > == 40 records per leaf block > > rmapbt ptr/key = 44b > == 22 ptr/keys per block > > Worst case, each block is half full, so 20 records and 11 ptrs per block. > > 1073741824 rmap records / 20 records per block > == 53687092 leaf blocks > > 53687092 leaves / 11 ptrs per block > == 4880645 level 1 blocks > == 443695 level 2 blocks > == 40336 level 3 blocks > == 3667 level 4 blocks > == 334 level 5 blocks > == 31 level 6 blocks > == 3 level 7 blocks > == 1 level 8 block > Thanks! Seems Ok to me.. with that in the commit log: Reviewed-by: Brian Foster <bfoster@redhat.com> > Yay latency.... > > (Hey, at least this isn't ext4 which has no lower bound on block fill...) > > --D > > > > > Brian > > > > > fs/xfs/libxfs/xfs_btree.h | 2 +- > > > 1 file changed, 1 insertion(+), 1 deletion(-) > > > > > > > > > diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h > > > index b8bbb21..629ef4f 100644 > > > --- a/fs/xfs/libxfs/xfs_btree.h > > > +++ b/fs/xfs/libxfs/xfs_btree.h > > > @@ -133,7 +133,7 @@ do { \ > > > } \ > > > } while (0) > > > > > > -#define XFS_BTREE_MAXLEVELS 8 /* max of all btrees */ > > > +#define XFS_BTREE_MAXLEVELS 9 /* max of all btrees */ > > > > > > struct xfs_btree_ops { > > > /* size of the key and record structures */ > > > > > > _______________________________________________ > > > xfs mailing list > > > xfs@oss.sgi.com > > > http://oss.sgi.com/mailman/listinfo/xfs
diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h index b8bbb21..629ef4f 100644 --- a/fs/xfs/libxfs/xfs_btree.h +++ b/fs/xfs/libxfs/xfs_btree.h @@ -133,7 +133,7 @@ do { \ } \ } while (0) -#define XFS_BTREE_MAXLEVELS 8 /* max of all btrees */ +#define XFS_BTREE_MAXLEVELS 9 /* max of all btrees */ struct xfs_btree_ops { /* size of the key and record structures */
By my calculations, a 1,073,741,824 block AG with a 1k block size can attain a maximum height of 9. Assuming a record size of 24 bytes, a key/ptr size of 44 bytes, and half-full btree nodes, we'd need 53,687,092 blocks for the records and ~6 million blocks for the keys. That requires a btree of height 9. Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com> --- fs/xfs/libxfs/xfs_btree.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)