Repository: buchgr/bazel-remote (go)

Issue:
use block-based disk usage accounting
We currently use a simple sum of the file sizes of each blob in the cache to estimate the total disk usage. This underestimates the actual disk usage, since most filesystems use 4Kb blocks. We can get a better estimate from the `syscall.Stat_t` struct's `Blocks` field, which is a count of the number of 512 byte blocks used by the file.

Pull request:
[disk] improve disk usage estimates by rounding file sizes up to 4kb blocks
Before this change, we approximated disk usage by keeping a running total of the file lengths of every blob in the index. But most filesystems store files in sequences of fixed size blocks, typically with size 4kb, so our estimate of filesystem space usage has been significantly lower than the actual usage.

It we round file sizes up to the nearest 4kb boundary for the disk usage accounting, then we would have a better estimate. An even better estimate would check the number of 512 byte blocks reported by stat(2), but that would require an extra syscall after writing every file- so let's try this simple approximation first.

Resolves #397.

Patch:
diff --git a/cache/disk/lru.go b/cache/disk/lru.go
index f8984be..5788543 100644
--- a/cache/disk/lru.go
+++ b/cache/disk/lru.go
@@ -55,7 +55,7 @@ type SizedLRU struct {
 	// Map to access the items in O(1) time
 	cache map[interface{}]*list.Element
 
-	// Total cache size including reserved bytes.
+	// Total cache size including reserved bytes and estimated filesystem overhead.
 	currentSize int64
 
 	// Total size of all blobs in uncompressed form.
@@ -77,6 +77,10 @@ type entry struct {
 	value lruItem
 }
 
+// Actual disk usage will be estimated by rounding file sizes up to the
+// nearest multiple of this number.
+const BlockSize = 4096
+
 // NewSizedLRU returns a new SizedLRU cache
 func NewSizedLRU(maxSize int64, onEvict EvictCallback) SizedLRU {
 	return SizedLRU{
@@ -87,21 +91,29 @@ func NewSizedLRU(maxSize int64, onEvict EvictCallback) SizedLRU {
 	}
 }
 
-// Add adds a (key, value) to the cache, evicting items as necessary. Add returns false (
-// and does not add the item) if the item size is larger than the maximum size of the cache,
-// or it cannot be added to the cache because too much space is reserved.
+// Add adds a (key, value) to the cache, evicting items as necessary.
+// Add returns false and does not add the item if the item size is
+// larger than the maximum size of the cache, or if the item cannot
+// be added to the cache because too much space is reserved.
+//
+// Note that this function rounds file sizes up to the nearest
+// BlockSize (4096) bytes, as an estimate of actual disk usage since
+// most linux filesystems default to 4kb blocks.
 func (c *SizedLRU) Add(key Key, value lruItem) (ok bool) {
-	if value.sizeOnDisk > c.maxSize {
+
+	roundedUpSizeOnDisk := roundUp4k(value.sizeOnDisk)
+
+	if roundedUpSizeOnDisk > c.maxSize {
 		return false
 	}
 
 	var sizeDelta, uncompressedSizeDelta int64
 	if ee, ok := c.cache[key]; ok {
-		sizeDelta = value.sizeOnDisk - ee.Value.(*entry).value.sizeOnDisk
+		sizeDelta = roundedUpSizeOnDisk - roundUp4k(ee.Value.(*entry).value.sizeOnDisk)
 		if c.reservedSize+sizeDelta > c.maxSize {
 			return false
 		}
-		uncompressedSizeDelta = value.size - ee.Value.(*entry).value.size
+		uncompressedSizeDelta = roundUp4k(value.size) - roundUp4k(ee.Value.(*entry).value.size)
 		c.ll.MoveToFront(ee)
 		counterOverwrittenBytes.Add(float64(ee.Value.(*entry).value.sizeOnDisk))
 
@@ -112,11 +124,11 @@ func (c *SizedLRU) Add(key Key, value lruItem) (ok bool) {
 
 		ee.Value.(*entry).value = value
 	} else {
-		sizeDelta = value.sizeOnDisk
+		sizeDelta = roundedUpSizeOnDisk
 		if c.reservedSize+sizeDelta > c.maxSize {
 			return false
 		}
-		uncompressedSizeDelta = value.size
+		uncompressedSizeDelta = roundUp4k(value.size)
 		ele := c.ll.PushFront(&entry{key, value})
 		c.cache[key] = ele
 	}
@@ -253,11 +265,16 @@ func (c *SizedLRU) removeElement(e *list.Element) {
 	c.ll.Remove(e)
 	kv := e.Value.(*entry)
 	delete(c.cache, kv.key)
-	c.currentSize -= kv.value.sizeOnDisk
-	c.uncompressedSize -= kv.value.size
+	c.currentSize -= roundUp4k(kv.value.sizeOnDisk)
+	c.uncompressedSize -= roundUp4k(kv.value.size)
 	counterEvictedBytes.Add(float64(kv.value.sizeOnDisk))
 
 	if c.onEvict != nil {
 		c.onEvict(kv.key, kv.value)
 	}
 }
+
+// Round n up to the nearest multiple of BlockSize (4096).
+func roundUp4k(n int64) int64 {
+	return (n + BlockSize - 1) & -BlockSize
+}


Test patch:
diff --git a/cache/disk/disk_test.go b/cache/disk/disk_test.go
index 9fb1b4a..3d43f85 100644
--- a/cache/disk/disk_test.go
+++ b/cache/disk/disk_test.go
@@ -46,7 +46,7 @@ func TestCacheBasics(t *testing.T) {
 	itemSize := int64(256)
 
 	// Add some overhead for likely CAS blob storage expansion.
-	cacheSize := int64(itemSize * 2)
+	cacheSize := int64(itemSize*2 + BlockSize)
 
 	testCache, err := New(cacheDir, cacheSize, "zstd", nil)
 	if err != nil {
@@ -91,7 +91,7 @@ func TestCacheBasics(t *testing.T) {
 func TestCachePutWrongSize(t *testing.T) {
 	cacheDir := tempDir(t)
 	defer os.RemoveAll(cacheDir)
-	testCache, err := New(cacheDir, 100, "zstd", nil)
+	testCache, err := New(cacheDir, BlockSize, "zstd", nil)
 	if err != nil {
 		t.Fatal(err)
 	}
@@ -118,7 +118,7 @@ func TestCacheGetContainsWrongSize(t *testing.T) {
 
 	cacheDir := tempDir(t)
 	defer os.RemoveAll(cacheDir)
-	testCache, err := New(cacheDir, 100, "zstd", nil)
+	testCache, err := New(cacheDir, BlockSize, "zstd", nil)
 	if err != nil {
 		t.Fatal(err)
 	}
@@ -156,7 +156,7 @@ func TestCacheGetContainsWrongSizeWithProxy(t *testing.T) {
 
 	cacheDir := tempDir(t)
 	defer os.RemoveAll(cacheDir)
-	testCache, err := New(cacheDir, 100, "zstd", new(proxyStub))
+	testCache, err := New(cacheDir, BlockSize, "zstd", new(proxyStub))
 	if err != nil {
 		t.Fatal(err)
 	}
@@ -296,7 +296,7 @@ func TestOverwrite(t *testing.T) {
 	cacheDir := tempDir(t)
 	defer os.RemoveAll(cacheDir)
 
-	testCache, err := New(cacheDir, 100, "zstd", nil)
+	testCache, err := New(cacheDir, BlockSize, "zstd", nil)
 	if err != nil {
 		t.Fatal(err)
 	}
@@ -391,7 +391,7 @@ func TestCacheExistingFiles(t *testing.T) {
 	}
 
 	// Add some overhead for likely CAS blob storage expansion.
-	const cacheSize = 1024
+	const cacheSize = BlockSize * 5
 
 	testCache, err := New(cacheDir, cacheSize, "zstd", nil)
 	if err != nil {
@@ -448,7 +448,7 @@ func TestCacheExistingFiles(t *testing.T) {
 func TestCacheBlobTooLarge(t *testing.T) {
 	cacheDir := tempDir(t)
 	defer os.RemoveAll(cacheDir)
-	testCache, err := New(cacheDir, 100, "zstd", nil)
+	testCache, err := New(cacheDir, BlockSize, "zstd", nil)
 	if err != nil {
 		t.Fatal(err)
 	}
@@ -474,7 +474,7 @@ func TestCacheBlobTooLarge(t *testing.T) {
 func TestCacheCorruptedCASBlob(t *testing.T) {
 	cacheDir := tempDir(t)
 	defer os.RemoveAll(cacheDir)
-	testCache, err := New(cacheDir, 1000, "zstd", nil)
+	testCache, err := New(cacheDir, BlockSize, "zstd", nil)
 	if err != nil {
 		t.Fatal(err)
 	}
@@ -556,7 +556,7 @@ func TestMigrateFromOldDirectoryStructure(t *testing.T) {
 	}
 
 	// Add some overhead for likely CAS blob storage expansion.
-	const cacheSize = 2560 * 2
+	const cacheSize = 2560*2 + BlockSize*2
 
 	testCache, err := New(cacheDir, cacheSize, "zstd", nil)
 	if err != nil {
@@ -626,7 +626,7 @@ func TestLoadExistingEntries(t *testing.T) {
 	}
 
 	// Add some overhead for likely CAS blob storage expansion.
-	cacheSize := int64(blobSize * numBlobs * 2)
+	cacheSize := int64((blobSize + BlockSize) * numBlobs * 2)
 
 	testCache, err := New(cacheDir, cacheSize, "zstd", nil)
 	if err != nil {
@@ -664,7 +664,7 @@ func TestDistinctKeyspaces(t *testing.T) {
 	blobSize := 1024
 
 	// Add some overhead for likely CAS blob storage expansion.
-	cacheSize := int64(blobSize*3) * 2
+	cacheSize := int64((blobSize+BlockSize)*3) * 2
 
 	testCache, err := New(cacheDir, cacheSize, "zstd", nil)
 	if err != nil {
diff --git a/cache/disk/lru_test.go b/cache/disk/lru_test.go
index bb48c9a..819379e 100644
--- a/cache/disk/lru_test.go
+++ b/cache/disk/lru_test.go
@@ -19,7 +19,7 @@ func checkSizeAndNumItems(t *testing.T, lru SizedLRU, expSize int64, expNum int)
 }
 
 func TestBasics(t *testing.T) {
-	maxSize := int64(10)
+	maxSize := int64(BlockSize)
 	lru := NewSizedLRU(maxSize, nil)
 
 	// Empty cache
@@ -50,7 +50,7 @@ func TestBasics(t *testing.T) {
 		t.Fatalf("Get: got a different item back")
 	}
 
-	checkSizeAndNumItems(t, lru, 5, 1)
+	checkSizeAndNumItems(t, lru, BlockSize, 1)
 
 	// Remove the item
 	lru.Remove(aKey)
@@ -64,10 +64,10 @@ func TestEviction(t *testing.T) {
 		evictions = append(evictions, key.(int))
 	}
 
-	lru := NewSizedLRU(10, onEvict)
+	lru := NewSizedLRU(10*BlockSize, onEvict)
 
 	expectedSizesNumItems := []struct {
-		expSize     int64
+		expBlocks   int64
 		expNumItems int
 		expEvicted  []int
 	}{
@@ -79,19 +79,18 @@ func TestEviction(t *testing.T) {
 		{9, 2, []int{0, 1, 2, 3}}, // 4, 5
 		{6, 1, []int{4, 5}},       // 6
 		{7, 1, []int{6}},          // 7
-
 	}
 
 	var expectedEvictions []int
 
 	for i, thisExpected := range expectedSizesNumItems {
-		item := lruItem{size: int64(i), sizeOnDisk: int64(i)}
+		item := lruItem{size: int64(i) * BlockSize, sizeOnDisk: int64(i) * BlockSize}
 		ok := lru.Add(i, item)
 		if !ok {
 			t.Fatalf("Add: failed adding %d", i)
 		}
 
-		checkSizeAndNumItems(t, lru, thisExpected.expSize, thisExpected.expNumItems)
+		checkSizeAndNumItems(t, lru, thisExpected.expBlocks*BlockSize, thisExpected.expNumItems)
 
 		expectedEvictions = append(expectedEvictions, thisExpected.expEvicted...)
 		if !reflect.DeepEqual(expectedEvictions, evictions) {
@@ -246,7 +245,7 @@ func TestUnreserve(t *testing.T) {
 }
 
 func TestAddWithSpaceReserved(t *testing.T) {
-	lru := NewSizedLRU(2, nil)
+	lru := NewSizedLRU(roundUp4k(2), nil)
 
 	ok, err := lru.Reserve(1)
 	if err != nil {
diff --git a/cache/httpproxy/httpproxy_test.go b/cache/httpproxy/httpproxy_test.go
index 49ec6a8..202db2a 100644
--- a/cache/httpproxy/httpproxy_test.go
+++ b/cache/httpproxy/httpproxy_test.go
@@ -113,7 +113,7 @@ func TestEverything(t *testing.T) {
 		t.Fatal(err)
 	}
 
-	diskCacheSize := int64(len(casData) + 2048)
+	diskCacheSize := int64(len(casData) + disk.BlockSize)
 	diskCache, err := disk.New(cacheDir, diskCacheSize, "zstd", proxyCache)
 	if err != nil {
 		t.Fatal(err)
diff --git a/server/http_test.go b/server/http_test.go
index 85a47b3..23df1b2 100644
--- a/server/http_test.go
+++ b/server/http_test.go
@@ -32,7 +32,7 @@ func TestDownloadFile(t *testing.T) {
 	data, hash := testutils.RandomDataAndHash(blobSize)
 
 	// Add some overhead for likely CAS blob storage expansion.
-	cacheSize := blobSize * 2
+	cacheSize := blobSize*2 + disk.BlockSize
 
 	c, err := disk.New(cacheDir, cacheSize, "zstd", nil)
 	if err != nil {
@@ -244,7 +244,7 @@ func TestUploadEmptyActionResult(t *testing.T) {
 
 	r := httptest.NewRequest("PUT", "/ac/"+hash, bytes.NewReader(data))
 
-	c, err := disk.New(cacheDir, 2048, "zstd", nil)
+	c, err := disk.New(cacheDir, disk.BlockSize, "zstd", nil)
 	if err != nil {
 		t.Fatal(err)
 	}