// Test that we fetch as little nodes as needed to reach the HAMTShardingSize
// during the sizeBelowThreshold computation.
Test that we fetch as little nodes as needed to reach the HAMTShardingSize
during the sizeBelowThreshold computation.
// Test that we fetch as little nodes as needed to reach the HAMTShardingSize // during the sizeBelowThreshold computation .
func TestHAMTEnumerationWhenComputingSize(t *testing.T) {
	linksize.LinkSizeFunction = mockLinkSizeFunc(1)
	defer func() { linksize.LinkSizeFunction = productionLinkSize }()
	oldHashFunc := internal.HAMTHashFunction
	defer func() { internal.HAMTHashFunction = oldHashFunc }()
	internal.HAMTHashFunction = idHash
	oldHamtOption := HAMTShardingSize
	defer func() { HAMTShardingSize = oldHamtOption }()
	treeHeight := 4
	thresholdToWidthRatio := 4
	shardWidth := 16
	HAMTShardingSize = shardWidth * thresholdToWidthRatio
	bstore := blockstore.NewBlockstore(dssync.MutexWrap(ds.NewMapDatastore()))
	countGetsDS := newCountGetsDS(bstore)
	dsrv := mdag.NewDAGService(bsrv.New(countGetsDS, offline.Exchange(countGetsDS)))
	completeHAMTRoot, err := CreateCompleteHAMT(dsrv, treeHeight, shardWidth)
	assert.NoError(t, err)
	optimalNodesToFetch := 0
	nodesToProcess := HAMTShardingSize
	for i := 0; i < treeHeight-1; i++ {
		parentNodes := int(math.Ceil(float64(nodesToProcess) / float64(shardWidth)))
		optimalNodesToFetch += parentNodes
		nodesToProcess = parentNodes
	}
	nodesToFetch := 0
	for i := 0; i < treeHeight-1; i++ {
		nodesToFetch += int(math.Pow(float64(shardWidth), float64(i)))
	}
	nodesToFetch += thresholdToWidthRatio
	hamtDir, err := newHAMTDirectoryFromNode(dsrv, completeHAMTRoot)
	assert.NoError(t, err)
	countGetsDS.resetCounter()
	countGetsDS.setRequestDelay(10 * time.Millisecond)
	below, err := hamtDir.sizeBelowThreshold(context.TODO(), 0)
	assert.NoError(t, err)
	assert.False(t, below)
	t.Logf("fetched %d nodes (predicted range: %d-%d)",
		countGetsDS.uniqueCidsFetched(), optimalNodesToFetch, nodesToFetch+defaultConcurrentFetch)
	assert.True(t, countGetsDS.uniqueCidsFetched() <= nodesToFetch+defaultConcurrentFetch)
	assert.True(t, countGetsDS.uniqueCidsFetched() >= optimalNodesToFetch)
}
func TestHAMTEnumerationWhenComputingSize ( t * testing . T ) { linksize . LinkSizeFunction = mockLinkSizeFunc ( 1 ) defer func ( ) { linksize . LinkSizeFunction = productionLinkSize } ( ) oldHashFunc := internal . HAMTHashFunction defer func ( ) { internal . HAMTHashFunction = oldHashFunc } ( ) internal . HAMTHashFunction = idHash oldHamtOption := HAMTShardingSize defer func ( ) { HAMTShardingSize = oldHamtOption } ( ) treeHeight := 4 thresholdToWidthRatio := 4 shardWidth := 16 HAMTShardingSize = shardWidth * thresholdToWidthRatio bstore := blockstore . NewBlockstore ( dssync . MutexWrap ( ds . NewMapDatastore ( ) ) ) countGetsDS := newCountGetsDS ( bstore ) dsrv := mdag . NewDAGService ( bsrv . New ( countGetsDS , offline . Exchange ( countGetsDS ) ) ) completeHAMTRoot , err := CreateCompleteHAMT ( dsrv , treeHeight , shardWidth ) assert . NoError ( t , err ) optimalNodesToFetch := 0 nodesToProcess := HAMTShardingSize for i := 0 ; i < treeHeight - 1 ; i ++ { parentNodes := int ( math . Ceil ( float64 ( nodesToProcess ) / float64 ( shardWidth ) ) ) optimalNodesToFetch += parentNodes nodesToProcess = parentNodes } nodesToFetch := 0 for i := 0 ; i < treeHeight - 1 ; i ++ { nodesToFetch += int ( math . Pow ( float64 ( shardWidth ) , float64 ( i ) ) ) } nodesToFetch += thresholdToWidthRatio hamtDir , err := newHAMTDirectoryFromNode ( dsrv , completeHAMTRoot ) assert . NoError ( t , err ) countGetsDS . resetCounter ( ) countGetsDS . setRequestDelay ( 10 * time . Millisecond ) below , err := hamtDir . sizeBelowThreshold ( context . TODO ( ) , 0 ) assert . NoError ( t , err ) assert . False ( t , below ) t . Logf ( " " , countGetsDS . uniqueCidsFetched ( ) , optimalNodesToFetch , nodesToFetch + defaultConcurrentFetch ) assert . True ( t , countGetsDS . uniqueCidsFetched ( ) <= nodesToFetch + defaultConcurrentFetch ) assert . True ( t , countGetsDS . uniqueCidsFetched ( ) >= optimalNodesToFetch ) }
Test that we fetch as little nodes as needed to reach the HAMTShardingSize
during the sizeBelowThreshold computation.
Test that we fetch as little nodes as needed to reach the HAMTShardingSize during the sizeBelowThreshold computation .
// Adjust HAMT global/static options for the test to simplify its logic. // FIXME: These variables weren't designed to be modified and we should //  review in depth side effects. // Set all link sizes to a uniform 1 so the estimated directory size // is just the count of its entry links (in HAMT/Shard terminology these // are the "value" links pointing to anything that is *not* another Shard). // Use an identity hash function to ease the construction of "complete" HAMTs // (see CreateCompleteHAMT below for more details). (Ideally this should be // a parameter we pass and not a global option we modify in the caller.) // --- End of test static configuration adjustments. --- // Some arbitrary values below that make this test not that expensive. // How many leaf shards nodes (with value links, // i.e., directory entries) do we need to reach the threshold. // Departing from DefaultShardWidth of 256 to reduce HAMT size in // CreateCompleteHAMT. // We create a "complete" HAMT (see CreateCompleteHAMT for more details) // with a regular structure to be able to predict how many Shard nodes we // will need to fetch in order to reach the HAMTShardingSize threshold in // sizeBelowThreshold (assuming a sequential DAG walk function). // Calculate the optimal number of nodes to traverse // divide by the shard width to get the parents and continue up the tree // With this structure and a BFS traversal (from `parallelWalkDepth`) then // we would roughly fetch the following nodes: // * all layers up to (but not including) the last one with leaf nodes //   (because it's a BFS) // * `thresholdToWidthRatio` leaf Shards with enough value links to reach //    the HAMTShardingSize threshold. // (Without the `setRequestDelay` above the number of nodes fetched //  drops dramatically and unpredictably as the BFS starts to behave //  more like a DFS because some search paths are fetched faster than //  others.) // Check that the actual number of nodes fetched is within the margin of the // estimated `nodesToFetch` plus an extra of `defaultConcurrentFetch` since // we are fetching in parallel.