New cache implementation and prefetch handing in mw/cache (#731)

* cache: add sharded cache implementation

Add Cache impl and a few tests. This cache is 256-way sharded, mainly
so each shard has it's own lock. The main cache structure is a readonly
jump plane into the right shard.

This should remove the single lock contention on the main lock and
provide more concurrent throughput - Obviously this hasn't been tested
or measured.

The key into the cache was made a uint32 (hash.fnv) and the hashing op
is not using strings.ToLower anymore remove any GC in that code path.

* here too

* Minimum shard size

* typos

* blurp

* small cleanups no defer

* typo

* Add freq based on Johns idea

* cherry-pick conflict resolv

* typo

* update from early code review from john

* add prefetch to the cache

* mw/cache: add prefetch

* remove println

* remove comment

* Fix tests

* Test prefetch in setup

* Add start of cache

* try add diff cache options

* Add hacky testcase

* not needed

* allow the use of a percentage for prefetch

If the TTL falls below xx% do a prefetch, if the record was popular.
Some other fixes and correctly prefetch only popular records.

1 files changed, 32 insertions, 18 deletions

diff --git a/middleware/cache/setup_test.go b/middleware/cache/setup_test.go
index f46a93b76..afc2ecc13 100644
--- a/middleware/cache/setup_test.go
+++ b/middleware/cache/setup_test.go
@@ -9,46 +9,57 @@ import (
 
 func TestSetup(t *testing.T) {
 	tests := []struct {
-		input        string
-		shouldErr    bool
-		expectedNcap int
-		expectedPcap int
-		expectedNttl time.Duration
-		expectedPttl time.Duration
+		input            string
+		shouldErr        bool
+		expectedNcap     int
+		expectedPcap     int
+		expectedNttl     time.Duration
+		expectedPttl     time.Duration
+		expectedPrefetch int
 	}{
-		{`cache`, false, defaultCap, defaultCap, maxNTTL, maxTTL},
-		{`cache {}`, false, defaultCap, defaultCap, maxNTTL, maxTTL},
+		{`cache`, false, defaultCap, defaultCap, maxNTTL, maxTTL, 0},
+		{`cache {}`, false, defaultCap, defaultCap, maxNTTL, maxTTL, 0},
 		{`cache example.nl {
 			success 10
-		}`, false, defaultCap, 10, maxNTTL, maxTTL},
+		}`, false, defaultCap, 10, maxNTTL, maxTTL, 0},
 		{`cache example.nl {
 			success 10
 			denial 10 15
-		}`, false, 10, 10, 15 * time.Second, maxTTL},
+		}`, false, 10, 10, 15 * time.Second, maxTTL, 0},
 		{`cache 25 example.nl {
 			success 10
 			denial 10 15
-		}`, false, 10, 10, 15 * time.Second, 25 * time.Second},
-		{`cache aaa example.nl`, false, defaultCap, defaultCap, maxNTTL, maxTTL},
+		}`, false, 10, 10, 15 * time.Second, 25 * time.Second, 0},
+		{`cache aaa example.nl`, false, defaultCap, defaultCap, maxNTTL, maxTTL, 0},
+		{`cache	{
+			prefetch 10
+		}`, false, defaultCap, defaultCap, maxNTTL, maxTTL, 10},
 
 		// fails
 		{`cache example.nl {
 			success
 			denial 10 15
-		}`, true, defaultCap, defaultCap, maxTTL, maxTTL},
+		}`, true, defaultCap, defaultCap, maxTTL, maxTTL, 0},
 		{`cache example.nl {
 			success 15
 			denial aaa
-		}`, true, defaultCap, defaultCap, maxTTL, maxTTL},
+		}`, true, defaultCap, defaultCap, maxTTL, maxTTL, 0},
 		{`cache example.nl {
 			positive 15
 			negative aaa
-		}`, true, defaultCap, defaultCap, maxTTL, maxTTL},
-		{`cache 0 example.nl`, true, defaultCap, defaultCap, maxTTL, maxTTL},
-		{`cache -1 example.nl`, true, defaultCap, defaultCap, maxTTL, maxTTL},
+		}`, true, defaultCap, defaultCap, maxTTL, maxTTL, 0},
+		{`cache 0 example.nl`, true, defaultCap, defaultCap, maxTTL, maxTTL, 0},
+		{`cache -1 example.nl`, true, defaultCap, defaultCap, maxTTL, maxTTL, 0},
 		{`cache 1 example.nl {
 			positive 0
-		}`, true, defaultCap, defaultCap, maxTTL, maxTTL},
+		}`, true, defaultCap, defaultCap, maxTTL, maxTTL, 0},
+		{`cache 1 example.nl {
+			positive 0
+			prefetch -1
+		}`, true, defaultCap, defaultCap, maxTTL, maxTTL, 0},
+		{`cache 1 example.nl {
+			prefetch 0 blurp
+		}`, true, defaultCap, defaultCap, maxTTL, maxTTL, 0},
 	}
 	for i, test := range tests {
 		c := caddy.NewTestController("dns", test.input)
@@ -76,5 +87,8 @@ func TestSetup(t *testing.T) {
 		if ca.pttl != test.expectedPttl {
 			t.Errorf("Test %v: Expected pttl %v but found: %v", i, test.expectedPttl, ca.pttl)
 		}
+		if ca.prefetch != test.expectedPrefetch {
+			t.Errorf("Test %v: Expected prefetch %v but found: %v", i, test.expectedPrefetch, ca.prefetch)
+		}
 	}
 }