[20/47] xfs: increase XFS_BTREE_MAXLEVELS to fit the rmapbt
diff mbox

Message ID 146907709719.25461.3104352212846077948.stgit@birch.djwong.org
State Accepted
Headers show

Commit Message

Darrick J. Wong July 21, 2016, 4:58 a.m. UTC
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(-)

Comments

Brian Foster Aug. 2, 2016, 6:48 p.m. UTC | #1
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
Darrick J. Wong Aug. 2, 2016, 8:06 p.m. UTC | #2
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
Brian Foster Aug. 2, 2016, 9:38 p.m. UTC | #3
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

Patch
diff mbox

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 */