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, 44 insertions, 11 deletions

diff --git a/middleware/cache/setup.go b/middleware/cache/setup.go
index eb835ba4e..65cfb70d1 100644
--- a/middleware/cache/setup.go
+++ b/middleware/cache/setup.go
@@ -7,8 +7,8 @@ import (
 
 	"github.com/coredns/coredns/core/dnsserver"
 	"github.com/coredns/coredns/middleware"
+	"github.com/coredns/coredns/middleware/pkg/cache"
 
-	"github.com/hashicorp/golang-lru"
 	"github.com/mholt/caddy"
 )
 
@@ -38,7 +38,7 @@ func setup(c *caddy.Controller) error {
 
 func cacheParse(c *caddy.Controller) (*Cache, error) {
 
-	ca := &Cache{pcap: defaultCap, ncap: defaultCap, pttl: maxTTL, nttl: maxNTTL}
+	ca := &Cache{pcap: defaultCap, ncap: defaultCap, pttl: maxTTL, nttl: maxNTTL, prefetch: 0, duration: 1 * time.Minute}
 
 	for c.Next() {
 		// cache [ttl] [zones..]
@@ -109,6 +109,46 @@ func cacheParse(c *caddy.Controller) (*Cache, error) {
 					}
 					ca.nttl = time.Duration(nttl) * time.Second
 				}
+			case "prefetch":
+				args := c.RemainingArgs()
+				if len(args) == 0 || len(args) > 3 {
+					return nil, c.ArgErr()
+				}
+				amount, err := strconv.Atoi(args[0])
+				if err != nil {
+					return nil, err
+				}
+				if amount < 0 {
+					return nil, fmt.Errorf("prefetch amount should be positive: %d", amount)
+				}
+				ca.prefetch = amount
+
+				ca.duration = 1 * time.Minute
+				ca.percentage = 10
+				if len(args) > 1 {
+					dur, err := time.ParseDuration(args[1])
+					if err != nil {
+						return nil, err
+					}
+					ca.duration = dur
+				}
+				if len(args) > 2 {
+					pct := args[2]
+					if x := pct[len(pct)-1]; x != '%' {
+						return nil, fmt.Errorf("last character of percentage should be `%%`, but is: %q", x)
+					}
+					pct = pct[:len(pct)-1]
+
+					num, err := strconv.Atoi(pct)
+					if err != nil {
+						return nil, err
+					}
+					if num < 10 || num > 90 {
+						return nil, fmt.Errorf("percentage should fall in range [10, 90]: %d", num)
+					}
+					ca.percentage = num
+				}
+
 			default:
 				return nil, c.ArgErr()
 			}
@@ -118,17 +158,10 @@ func cacheParse(c *caddy.Controller) (*Cache, error) {
 			origins[i] = middleware.Host(origins[i]).Normalize()
 		}
 
-		var err error
 		ca.Zones = origins
 
-		ca.pcache, err = lru.New(ca.pcap)
-		if err != nil {
-			return nil, err
-		}
-		ca.ncache, err = lru.New(ca.ncap)
-		if err != nil {
-			return nil, err
-		}
+		ca.pcache = cache.New(ca.pcap)
+		ca.ncache = cache.New(ca.ncap)
 
 		return ca, nil
 	}