aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGravatar Miek Gieben <miek@miek.nl> 2017-06-13 12:39:10 -0700
committerGravatar GitHub <noreply@github.com> 2017-06-13 12:39:10 -0700
commite9eda7e7c8ed75d62b02f23c62e8e318ea1685ae (patch)
tree152a04673698e1a39caa751c02612d4e21315662
parentb1efd3736e6e68ab01baf54f83071c62690899b2 (diff)
downloadcoredns-e9eda7e7c8ed75d62b02f23c62e8e318ea1685ae.tar.gz
coredns-e9eda7e7c8ed75d62b02f23c62e8e318ea1685ae.tar.zst
coredns-e9eda7e7c8ed75d62b02f23c62e8e318ea1685ae.zip
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.
-rw-r--r--middleware/cache/README.md16
-rw-r--r--middleware/cache/cache.go93
-rw-r--r--middleware/cache/cache_test.go11
-rw-r--r--middleware/cache/freq/freq.go54
-rw-r--r--middleware/cache/freq/freq_test.go36
-rw-r--r--middleware/cache/handler.go36
-rw-r--r--middleware/cache/item.go11
-rw-r--r--middleware/cache/item_test.go20
-rw-r--r--middleware/cache/prefech_test.go54
-rw-r--r--middleware/cache/setup.go55
-rw-r--r--middleware/cache/setup_test.go50
-rw-r--r--middleware/dnssec/cache.go11
-rw-r--r--middleware/dnssec/cache_test.go9
-rw-r--r--middleware/dnssec/dnssec.go14
-rw-r--r--middleware/dnssec/dnssec_test.go10
-rw-r--r--middleware/dnssec/handler_test.go10
-rw-r--r--middleware/dnssec/setup.go9
-rw-r--r--middleware/etcd/etcd.go6
-rw-r--r--middleware/pkg/cache/cache.go129
-rw-r--r--middleware/pkg/cache/cache_test.go31
-rw-r--r--middleware/pkg/cache/shard_test.go60
-rw-r--r--middleware/pkg/singleflight/singleflight.go6
-rw-r--r--middleware/pkg/singleflight/singleflight_test.go6
23 files changed, 595 insertions, 142 deletions
diff --git a/middleware/cache/README.md b/middleware/cache/README.md
index 145ce2fdf..6477fe891 100644
--- a/middleware/cache/README.md
+++ b/middleware/cache/README.md
@@ -10,13 +10,12 @@ cache [TTL] [ZONES...]
* **TTL** max TTL in seconds. If not specified, the maximum TTL will be used which is 3600 for
noerror responses and 1800 for denial of existence ones.
- A set TTL of 300 *cache 300* would cache the record up to 300 seconds.
- Smaller record provided TTLs will take precedence.
+ Setting a TTL of 300 *cache 300* would cache the record up to 300 seconds.
* **ZONES** zones it should cache for. If empty, the zones from the configuration block are used.
Each element in the cache is cached according to its TTL (with **TTL** as the max).
For the negative cache, the SOA's MinTTL value is used. A cache can contain up to 10,000 items by
-default. A TTL of zero is not allowed. No cache invalidation triggered by other middlewares is available. Therefore even reloaded items might still be cached for the duration of the TTL.
+default. A TTL of zero is not allowed.
If you want more control:
@@ -24,16 +23,21 @@ If you want more control:
cache [TTL] [ZONES...] {
success CAPACITY [TTL]
denial CAPACITY [TTL]
+ prefetch AMOUNT [[DURATION] [PERCENTAGE%]]
}
~~~
* **TTL** and **ZONES** as above.
* `success`, override the settings for caching successful responses, **CAPACITY** indicates the maximum
- number of packets we cache before we start evicting (LRU). **TTL** overrides the cache maximum TTL.
+ number of packets we cache before we start evicting (*randomly*). **TTL** overrides the cache maximum TTL.
* `denial`, override the settings for caching denial of existence responses, **CAPACITY** indicates the maximum
number of packets we cache before we start evicting (LRU). **TTL** overrides the cache maximum TTL.
-
-There is a third category (`error`) but those responses are never cached.
+ There is a third category (`error`) but those responses are never cached.
+* `prefetch`, will prefetch popular items when they are about to be expunged from the cache.
+ Popular means **AMOUNT** queries have been seen no gaps of **DURATION** or more between them.
+ **DURATION** defaults to 1m. Prefetching will happen when the TTL drops below **PERCENTAGE**,
+ which defaults to `10%`. Values should be in the range `[10%, 90%]`. Note the percent sign is
+ mandatory. **PERCENTAGE** is treated as an `int`.
The minimum TTL allowed on resource records is 5 seconds.
diff --git a/middleware/cache/cache.go b/middleware/cache/cache.go
index e2a669723..30775c598 100644
--- a/middleware/cache/cache.go
+++ b/middleware/cache/cache.go
@@ -2,15 +2,15 @@
package cache
import (
+ "encoding/binary"
+ "hash/fnv"
"log"
- "strconv"
- "strings"
"time"
"github.com/coredns/coredns/middleware"
+ "github.com/coredns/coredns/middleware/pkg/cache"
"github.com/coredns/coredns/middleware/pkg/response"
- "github.com/hashicorp/golang-lru"
"github.com/miekg/dns"
)
@@ -20,48 +20,73 @@ type Cache struct {
Next middleware.Handler
Zones []string
- ncache *lru.Cache
+ ncache *cache.Cache
ncap int
nttl time.Duration
- pcache *lru.Cache
+ pcache *cache.Cache
pcap int
pttl time.Duration
+
+ // Prefetch.
+ prefetch int
+ duration time.Duration
+ percentage int
}
-// Return key under which we store the item. The empty string is returned
-// when we don't want to cache the message. Currently we do not cache Truncated, errors
-// zone transfers or dynamic update messages.
-func key(m *dns.Msg, t response.Type, do bool) string {
+// Return key under which we store the item, -1 will be returned if we don't store the
+// message.
+// Currently we do not cache Truncated, errors zone transfers or dynamic update messages.
+func key(m *dns.Msg, t response.Type, do bool) int {
// We don't store truncated responses.
if m.Truncated {
- return ""
+ return -1
}
// Nor errors or Meta or Update
if t == response.OtherError || t == response.Meta || t == response.Update {
- return ""
+ return -1
}
- qtype := m.Question[0].Qtype
- qname := strings.ToLower(m.Question[0].Name)
- return rawKey(qname, qtype, do)
+ return int(hash(m.Question[0].Name, m.Question[0].Qtype, do))
}
-func rawKey(qname string, qtype uint16, do bool) string {
+var one = []byte("1")
+var zero = []byte("0")
+
+func hash(qname string, qtype uint16, do bool) uint32 {
+ h := fnv.New32()
+
if do {
- return "1" + qname + "." + strconv.Itoa(int(qtype))
+ h.Write(one)
+ } else {
+ h.Write(zero)
+ }
+
+ b := make([]byte, 2)
+ binary.BigEndian.PutUint16(b, qtype)
+ h.Write(b)
+
+ for i := range qname {
+ c := qname[i]
+ if c >= 'A' && c <= 'Z' {
+ c += 'a' - 'A'
+ }
+ h.Write([]byte{c})
}
- return "0" + qname + "." + strconv.Itoa(int(qtype))
+
+ return h.Sum32()
}
// ResponseWriter is a response writer that caches the reply message.
type ResponseWriter struct {
dns.ResponseWriter
*Cache
+
+ prefetch bool // When true write nothing back to the client.
}
// WriteMsg implements the dns.ResponseWriter interface.
-func (c *ResponseWriter) WriteMsg(res *dns.Msg) error {
+func (w *ResponseWriter) WriteMsg(res *dns.Msg) error {
do := false
mt, opt := response.Typify(res, time.Now().UTC())
if opt != nil {
@@ -71,9 +96,9 @@ func (c *ResponseWriter) WriteMsg(res *dns.Msg) error {
// key returns empty string for anything we don't want to cache.
key := key(res, mt, do)
- duration := c.pttl
+ duration := w.pttl
if mt == response.NameError || mt == response.NoData {
- duration = c.nttl
+ duration = w.nttl
}
msgTTL := minMsgTTL(res, mt)
@@ -81,20 +106,23 @@ func (c *ResponseWriter) WriteMsg(res *dns.Msg) error {
duration = msgTTL
}
- if key != "" {
- c.set(res, key, mt, duration)
+ if key != -1 {
+ w.set(res, key, mt, duration)
- cacheSize.WithLabelValues(Success).Set(float64(c.pcache.Len()))
- cacheSize.WithLabelValues(Denial).Set(float64(c.ncache.Len()))
+ cacheSize.WithLabelValues(Success).Set(float64(w.pcache.Len()))
+ cacheSize.WithLabelValues(Denial).Set(float64(w.ncache.Len()))
}
setMsgTTL(res, uint32(duration.Seconds()))
+ if w.prefetch {
+ return nil
+ }
- return c.ResponseWriter.WriteMsg(res)
+ return w.ResponseWriter.WriteMsg(res)
}
-func (c *ResponseWriter) set(m *dns.Msg, key string, mt response.Type, duration time.Duration) {
- if key == "" {
+func (w *ResponseWriter) set(m *dns.Msg, key int, mt response.Type, duration time.Duration) {
+ if key == -1 {
log.Printf("[ERROR] Caching called with empty cache key")
return
}
@@ -102,11 +130,11 @@ func (c *ResponseWriter) set(m *dns.Msg, key string, mt response.Type, duration
switch mt {
case response.NoError, response.Delegation:
i := newItem(m, duration)
- c.pcache.Add(key, i)
+ w.pcache.Add(uint32(key), i)
case response.NameError, response.NoData:
i := newItem(m, duration)
- c.ncache.Add(key, i)
+ w.ncache.Add(uint32(key), i)
case response.OtherError:
// don't cache these
@@ -116,9 +144,12 @@ func (c *ResponseWriter) set(m *dns.Msg, key string, mt response.Type, duration
}
// Write implements the dns.ResponseWriter interface.
-func (c *ResponseWriter) Write(buf []byte) (int, error) {
+func (w *ResponseWriter) Write(buf []byte) (int, error) {
log.Printf("[WARNING] Caching called with Write: not caching reply")
- n, err := c.ResponseWriter.Write(buf)
+ if w.prefetch {
+ return 0, nil
+ }
+ n, err := w.ResponseWriter.Write(buf)
return n, err
}
diff --git a/middleware/cache/cache_test.go b/middleware/cache/cache_test.go
index 18aa05fe5..adac7d67b 100644
--- a/middleware/cache/cache_test.go
+++ b/middleware/cache/cache_test.go
@@ -7,10 +7,10 @@ import (
"time"
"github.com/coredns/coredns/middleware"
+ "github.com/coredns/coredns/middleware/pkg/cache"
"github.com/coredns/coredns/middleware/pkg/response"
"github.com/coredns/coredns/middleware/test"
- lru "github.com/hashicorp/golang-lru"
"github.com/miekg/dns"
)
@@ -148,10 +148,10 @@ func cacheMsg(m *dns.Msg, tc cacheTestCase) *dns.Msg {
func newTestCache(ttl time.Duration) (*Cache, *ResponseWriter) {
c := &Cache{Zones: []string{"."}, pcap: defaultCap, ncap: defaultCap, pttl: ttl, nttl: ttl}
- c.pcache, _ = lru.New(c.pcap)
- c.ncache, _ = lru.New(c.ncap)
+ c.pcache = cache.New(c.pcap)
+ c.ncache = cache.New(c.ncap)
- crr := &ResponseWriter{nil, c}
+ crr := &ResponseWriter{ResponseWriter: nil, Cache: c}
return c, crr
}
@@ -176,7 +176,8 @@ func TestCache(t *testing.T) {
name := middleware.Name(m.Question[0].Name).Normalize()
qtype := m.Question[0].Qtype
- i, ok, _ := c.get(name, qtype, do)
+ i, _ := c.get(time.Now().UTC(), name, qtype, do)
+ ok := i != nil
if ok != tc.shouldCache {
t.Errorf("cached message that should not have been cached: %s", name)
diff --git a/middleware/cache/freq/freq.go b/middleware/cache/freq/freq.go
new file mode 100644
index 000000000..528eedc1c
--- /dev/null
+++ b/middleware/cache/freq/freq.go
@@ -0,0 +1,54 @@
+// Package freq keeps track of last X seen events. The events themselves are not stored
+// here. So the Freq type should be added next to the thing it is tracking.
+package freq
+
+import (
+ "sync"
+ "time"
+)
+
+type Freq struct {
+ // Last time we saw a query for this element.
+ last time.Time
+ // Number of this in the last time slice.
+ hits int
+
+ sync.RWMutex
+}
+
+// New returns a new initialized Freq.
+func New(t time.Time) *Freq {
+ return &Freq{last: t, hits: 0}
+}
+
+// Updates updates the number of hits. Last time seen will be set to now.
+// If the last time we've seen this entity is within now - d, we increment hits, otherwise
+// we reset hits to 1. It returns the number of hits.
+func (f *Freq) Update(d time.Duration, now time.Time) int {
+ earliest := now.Add(-1 * d)
+ f.Lock()
+ defer f.Unlock()
+ if f.last.Before(earliest) {
+ f.last = now
+ f.hits = 1
+ return f.hits
+ }
+ f.last = now
+ f.hits++
+ return f.hits
+}
+
+// Hits returns the number of hits that we have seen, according to the updates we have done to f.
+func (f *Freq) Hits() int {
+ f.RLock()
+ defer f.RUnlock()
+ return f.hits
+}
+
+// Reset resets f to time t and hits to hits.
+func (f *Freq) Reset(t time.Time, hits int) {
+ f.Lock()
+ defer f.Unlock()
+ f.last = t
+ f.hits = hits
+}
diff --git a/middleware/cache/freq/freq_test.go b/middleware/cache/freq/freq_test.go
new file mode 100644
index 000000000..740194c86
--- /dev/null
+++ b/middleware/cache/freq/freq_test.go
@@ -0,0 +1,36 @@
+package freq
+
+import (
+ "testing"
+ "time"
+)
+
+func TestFreqUpdate(t *testing.T) {
+ now := time.Now().UTC()
+ f := New(now)
+ window := 1 * time.Minute
+
+ f.Update(window, time.Now().UTC())
+ f.Update(window, time.Now().UTC())
+ f.Update(window, time.Now().UTC())
+ hitsCheck(t, f, 3)
+
+ f.Reset(now, 0)
+ history := time.Now().UTC().Add(-3 * time.Minute)
+ f.Update(window, history)
+ hitsCheck(t, f, 1)
+}
+
+func TestReset(t *testing.T) {
+ f := New(time.Now().UTC())
+ f.Update(1*time.Minute, time.Now().UTC())
+ hitsCheck(t, f, 1)
+ f.Reset(time.Now().UTC(), 0)
+ hitsCheck(t, f, 0)
+}
+
+func hitsCheck(t *testing.T, f *Freq, expected int) {
+ if x := f.Hits(); x != expected {
+ t.Fatalf("Expected hits to be %d, got %d", expected, x)
+ }
+}
diff --git a/middleware/cache/handler.go b/middleware/cache/handler.go
index 195322e31..520b23767 100644
--- a/middleware/cache/handler.go
+++ b/middleware/cache/handler.go
@@ -24,36 +24,58 @@ func (c *Cache) ServeDNS(ctx context.Context, w dns.ResponseWriter, r *dns.Msg)
do := state.Do() // TODO(): might need more from OPT record? Like the actual bufsize?
- if i, ok, expired := c.get(qname, qtype, do); ok && !expired {
+ now := time.Now().UTC()
+
+ i, ttl := c.get(now, qname, qtype, do)
+ if i != nil && ttl > 0 {
resp := i.toMsg(r)
state.SizeAndDo(resp)
resp, _ = state.Scrub(resp)
w.WriteMsg(resp)
+ i.Freq.Update(c.duration, now)
+
+ pct := 100
+ if i.origTTL != 0 { // you'll never know
+ pct = int(float64(ttl) / float64(i.origTTL) * 100)
+ }
+
+ if c.prefetch > 0 && i.Freq.Hits() > c.prefetch && pct < c.percentage {
+ // When prefetching we loose the item i, and with it the frequency
+ // that we've gathered sofar. See we copy the frequence info back
+ // into the new item that was stored in the cache.
+ prr := &ResponseWriter{ResponseWriter: w, Cache: c, prefetch: true}
+ middleware.NextOrFailure(c.Name(), c.Next, ctx, prr, r)
+
+ if i1, _ := c.get(now, qname, qtype, do); i1 != nil {
+ i1.Freq.Reset(now, i.Freq.Hits())
+ }
+ }
+
return dns.RcodeSuccess, nil
}
- crr := &ResponseWriter{w, c}
+ crr := &ResponseWriter{ResponseWriter: w, Cache: c}
return middleware.NextOrFailure(c.Name(), c.Next, ctx, crr, r)
}
// Name implements the Handler interface.
func (c *Cache) Name() string { return "cache" }
-func (c *Cache) get(qname string, qtype uint16, do bool) (*item, bool, bool) {
- k := rawKey(qname, qtype, do)
+func (c *Cache) get(now time.Time, qname string, qtype uint16, do bool) (*item, int) {
+ k := hash(qname, qtype, do)
if i, ok := c.ncache.Get(k); ok {
cacheHits.WithLabelValues(Denial).Inc()
- return i.(*item), ok, i.(*item).expired(time.Now())
+ return i.(*item), i.(*item).ttl(now)
}
if i, ok := c.pcache.Get(k); ok {
cacheHits.WithLabelValues(Success).Inc()
- return i.(*item), ok, i.(*item).expired(time.Now())
+ return i.(*item), i.(*item).ttl(now)
}
cacheMisses.Inc()
- return nil, false, false
+ return nil, 0
}
var (
diff --git a/middleware/cache/item.go b/middleware/cache/item.go
index 6a75afdf9..5084bcf1c 100644
--- a/middleware/cache/item.go
+++ b/middleware/cache/item.go
@@ -3,6 +3,7 @@ package cache
import (
"time"
+ "github.com/coredns/coredns/middleware/cache/freq"
"github.com/coredns/coredns/middleware/pkg/response"
"github.com/miekg/dns"
)
@@ -18,6 +19,8 @@ type item struct {
origTTL uint32
stored time.Time
+
+ *freq.Freq
}
func newItem(m *dns.Msg, d time.Duration) *item {
@@ -43,10 +46,12 @@ func newItem(m *dns.Msg, d time.Duration) *item {
i.origTTL = uint32(d.Seconds())
i.stored = time.Now().UTC()
+ i.Freq = new(freq.Freq)
+
return i
}
-// toMsg turns i into a message, it tailers the reply to m.
+// toMsg turns i into a message, it tailors the reply to m.
// The Authoritative bit is always set to 0, because the answer is from the cache.
func (i *item) toMsg(m *dns.Msg) *dns.Msg {
m1 := new(dns.Msg)
@@ -67,9 +72,9 @@ func (i *item) toMsg(m *dns.Msg) *dns.Msg {
return m1
}
-func (i *item) expired(now time.Time) bool {
+func (i *item) ttl(now time.Time) int {
ttl := int(i.origTTL) - int(now.UTC().Sub(i.stored).Seconds())
- return ttl < 0
+ return ttl
}
// setMsgTTL sets the ttl on all RRs in all sections. If ttl is smaller than minTTL
diff --git a/middleware/cache/item_test.go b/middleware/cache/item_test.go
deleted file mode 100644
index b338d02bd..000000000
--- a/middleware/cache/item_test.go
+++ /dev/null
@@ -1,20 +0,0 @@
-package cache
-
-import (
- "testing"
-
- "github.com/miekg/dns"
-)
-
-func TestKey(t *testing.T) {
- if x := rawKey("miek.nl.", dns.TypeMX, false); x != "0miek.nl..15" {
- t.Errorf("failed to create correct key, got %s", x)
- }
- if x := rawKey("miek.nl.", dns.TypeMX, true); x != "1miek.nl..15" {
- t.Errorf("failed to create correct key, got %s", x)
- }
- // rawKey does not lowercase.
- if x := rawKey("miEK.nL.", dns.TypeMX, true); x != "1miEK.nL..15" {
- t.Errorf("failed to create correct key, got %s", x)
- }
-}
diff --git a/middleware/cache/prefech_test.go b/middleware/cache/prefech_test.go
new file mode 100644
index 000000000..69ad5f92a
--- /dev/null
+++ b/middleware/cache/prefech_test.go
@@ -0,0 +1,54 @@
+package cache
+
+import (
+ "fmt"
+ "testing"
+ "time"
+
+ "github.com/coredns/coredns/middleware"
+ "github.com/coredns/coredns/middleware/pkg/cache"
+ "github.com/coredns/coredns/middleware/pkg/dnsrecorder"
+
+ "github.com/coredns/coredns/middleware/test"
+ "github.com/miekg/dns"
+ "golang.org/x/net/context"
+)
+
+var p = false
+
+func TestPrefetch(t *testing.T) {
+ c := &Cache{Zones: []string{"."}, pcap: defaultCap, ncap: defaultCap, pttl: maxTTL, nttl: maxTTL}
+ c.pcache = cache.New(c.pcap)
+ c.ncache = cache.New(c.ncap)
+ c.prefetch = 1
+ c.duration = 1 * time.Second
+ c.Next = PrefetchHandler(t, dns.RcodeSuccess, nil)
+
+ ctx := context.TODO()
+
+ req := new(dns.Msg)
+ req.SetQuestion("lowttl.example.org.", dns.TypeA)
+
+ rec := dnsrecorder.New(&test.ResponseWriter{})
+
+ c.ServeDNS(ctx, rec, req)
+ p = true // prefetch should be true for the 2nd fetch
+ c.ServeDNS(ctx, rec, req)
+}
+
+func PrefetchHandler(t *testing.T, rcode int, err error) middleware.Handler {
+ return middleware.HandlerFunc(func(ctx context.Context, w dns.ResponseWriter, r *dns.Msg) (int, error) {
+ m := new(dns.Msg)
+ m.SetQuestion("lowttl.example.org.", dns.TypeA)
+ m.Response = true
+ m.RecursionAvailable = true
+ m.Answer = append(m.Answer, test.A("lowttl.example.org. 80 IN A 127.0.0.53"))
+ if p != w.(*ResponseWriter).prefetch {
+ err = fmt.Errorf("cache prefetch not equal to p: got %t, want %t", p, w.(*ResponseWriter).prefetch)
+ t.Fatal(err)
+ }
+
+ w.WriteMsg(m)
+ return rcode, err
+ })
+}
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
}
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)
+ }
}
}
diff --git a/middleware/dnssec/cache.go b/middleware/dnssec/cache.go
index 2153c84cb..ea95b73b4 100644
--- a/middleware/dnssec/cache.go
+++ b/middleware/dnssec/cache.go
@@ -2,14 +2,13 @@ package dnssec
import (
"hash/fnv"
- "strconv"
"github.com/miekg/dns"
)
-// Key serializes the RRset and return a signature cache key.
-func key(rrs []dns.RR) string {
- h := fnv.New64()
+// hash serializes the RRset and return a signature cache key.
+func hash(rrs []dns.RR) uint32 {
+ h := fnv.New32()
buf := make([]byte, 256)
for _, r := range rrs {
off, err := dns.PackRR(r, buf, 0, nil, false)
@@ -18,6 +17,6 @@ func key(rrs []dns.RR) string {
}
}
- i := h.Sum64()
- return strconv.FormatUint(i, 10)
+ i := h.Sum32()
+ return i
}
diff --git a/middleware/dnssec/cache_test.go b/middleware/dnssec/cache_test.go
index c88e310e3..b9434fcbe 100644
--- a/middleware/dnssec/cache_test.go
+++ b/middleware/dnssec/cache_test.go
@@ -4,10 +4,9 @@ import (
"testing"
"time"
+ "github.com/coredns/coredns/middleware/pkg/cache"
"github.com/coredns/coredns/middleware/test"
"github.com/coredns/coredns/request"
-
- "github.com/hashicorp/golang-lru"
)
func TestCacheSet(t *testing.T) {
@@ -21,11 +20,11 @@ func TestCacheSet(t *testing.T) {
t.Fatalf("failed to parse key: %v\n", err)
}
- cache, _ := lru.New(defaultCap)
+ c := cache.New(defaultCap)
m := testMsg()
state := request.Request{Req: m}
- k := key(m.Answer) // calculate *before* we add the sig
- d := New([]string{"miek.nl."}, []*DNSKEY{dnskey}, nil, cache)
+ k := hash(m.Answer) // calculate *before* we add the sig
+ d := New([]string{"miek.nl."}, []*DNSKEY{dnskey}, nil, c)
m = d.Sign(state, "miek.nl.", time.Now().UTC())
_, ok := d.get(k)
diff --git a/middleware/dnssec/dnssec.go b/middleware/dnssec/dnssec.go
index 7ad5f2bf7..4e1e70217 100644
--- a/middleware/dnssec/dnssec.go
+++ b/middleware/dnssec/dnssec.go
@@ -6,11 +6,11 @@ import (
"time"
"github.com/coredns/coredns/middleware"
+ "github.com/coredns/coredns/middleware/pkg/cache"
"github.com/coredns/coredns/middleware/pkg/response"
"github.com/coredns/coredns/middleware/pkg/singleflight"
"github.com/coredns/coredns/request"
- "github.com/hashicorp/golang-lru"
"github.com/miekg/dns"
)
@@ -21,15 +21,15 @@ type Dnssec struct {
zones []string
keys []*DNSKEY
inflight *singleflight.Group
- cache *lru.Cache
+ cache *cache.Cache
}
// New returns a new Dnssec.
-func New(zones []string, keys []*DNSKEY, next middleware.Handler, cache *lru.Cache) Dnssec {
+func New(zones []string, keys []*DNSKEY, next middleware.Handler, c *cache.Cache) Dnssec {
return Dnssec{Next: next,
zones: zones,
keys: keys,
- cache: cache,
+ cache: c,
inflight: new(singleflight.Group),
}
}
@@ -90,7 +90,7 @@ func (d Dnssec) Sign(state request.Request, zone string, now time.Time) *dns.Msg
}
func (d Dnssec) sign(rrs []dns.RR, signerName string, ttl, incep, expir uint32) ([]dns.RR, error) {
- k := key(rrs)
+ k := hash(rrs)
sgs, ok := d.get(k)
if ok {
return sgs, nil
@@ -110,11 +110,11 @@ func (d Dnssec) sign(rrs []dns.RR, signerName string, ttl, incep, expir uint32)
return sigs.([]dns.RR), err
}
-func (d Dnssec) set(key string, sigs []dns.RR) {
+func (d Dnssec) set(key uint32, sigs []dns.RR) {
d.cache.Add(key, sigs)
}
-func (d Dnssec) get(key string) ([]dns.RR, bool) {
+func (d Dnssec) get(key uint32) ([]dns.RR, bool) {
if s, ok := d.cache.Get(key); ok {
cacheHits.Inc()
return s.([]dns.RR), true
diff --git a/middleware/dnssec/dnssec_test.go b/middleware/dnssec/dnssec_test.go
index 1c9c9a545..3549a7c8f 100644
--- a/middleware/dnssec/dnssec_test.go
+++ b/middleware/dnssec/dnssec_test.go
@@ -4,10 +4,10 @@ import (
"testing"
"time"
+ "github.com/coredns/coredns/middleware/pkg/cache"
"github.com/coredns/coredns/middleware/test"
"github.com/coredns/coredns/request"
- "github.com/hashicorp/golang-lru"
"github.com/miekg/dns"
)
@@ -69,8 +69,8 @@ func TestSigningDifferentZone(t *testing.T) {
m := testMsgEx()
state := request.Request{Req: m}
- cache, _ := lru.New(defaultCap)
- d := New([]string{"example.org."}, []*DNSKEY{key}, nil, cache)
+ c := cache.New(defaultCap)
+ d := New([]string{"example.org."}, []*DNSKEY{key}, nil, c)
m = d.Sign(state, "example.org.", time.Now().UTC())
if !section(m.Answer, 1) {
t.Errorf("answer section should have 1 sig")
@@ -183,8 +183,8 @@ func testMsgDname() *dns.Msg {
func newDnssec(t *testing.T, zones []string) (Dnssec, func(), func()) {
k, rm1, rm2 := newKey(t)
- cache, _ := lru.New(defaultCap)
- d := New(zones, []*DNSKEY{k}, nil, cache)
+ c := cache.New(defaultCap)
+ d := New(zones, []*DNSKEY{k}, nil, c)
return d, rm1, rm2
}
diff --git a/middleware/dnssec/handler_test.go b/middleware/dnssec/handler_test.go
index 37a92935a..60847d17b 100644
--- a/middleware/dnssec/handler_test.go
+++ b/middleware/dnssec/handler_test.go
@@ -6,10 +6,10 @@ import (
"testing"
"github.com/coredns/coredns/middleware/file"
+ "github.com/coredns/coredns/middleware/pkg/cache"
"github.com/coredns/coredns/middleware/pkg/dnsrecorder"
"github.com/coredns/coredns/middleware/test"
- "github.com/hashicorp/golang-lru"
"github.com/miekg/dns"
"golang.org/x/net/context"
)
@@ -89,8 +89,8 @@ func TestLookupZone(t *testing.T) {
dnskey, rm1, rm2 := newKey(t)
defer rm1()
defer rm2()
- cache, _ := lru.New(defaultCap)
- dh := New([]string{"miek.nl."}, []*DNSKEY{dnskey}, fm, cache)
+ c := cache.New(defaultCap)
+ dh := New([]string{"miek.nl."}, []*DNSKEY{dnskey}, fm, c)
ctx := context.TODO()
for _, tc := range dnsTestCases {
@@ -128,8 +128,8 @@ func TestLookupDNSKEY(t *testing.T) {
dnskey, rm1, rm2 := newKey(t)
defer rm1()
defer rm2()
- cache, _ := lru.New(defaultCap)
- dh := New([]string{"miek.nl."}, []*DNSKEY{dnskey}, test.ErrorHandler(), cache)
+ c := cache.New(defaultCap)
+ dh := New([]string{"miek.nl."}, []*DNSKEY{dnskey}, test.ErrorHandler(), c)
ctx := context.TODO()
for _, tc := range dnssecTestCases {
diff --git a/middleware/dnssec/setup.go b/middleware/dnssec/setup.go
index 1b1fb6393..6935c4aaa 100644
--- a/middleware/dnssec/setup.go
+++ b/middleware/dnssec/setup.go
@@ -6,8 +6,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"
)
@@ -24,12 +24,9 @@ func setup(c *caddy.Controller) error {
return middleware.Error("dnssec", err)
}
- cache, err := lru.New(capacity)
- if err != nil {
- return err
- }
+ ca := cache.New(capacity)
dnsserver.GetConfig(c).AddMiddleware(func(next middleware.Handler) middleware.Handler {
- return New(zones, keys, next, cache)
+ return New(zones, keys, next, ca)
})
// Export the capacity for the metrics. This only happens once, because this is a re-load change only.
diff --git a/middleware/etcd/etcd.go b/middleware/etcd/etcd.go
index f701785f3..b438b794d 100644
--- a/middleware/etcd/etcd.go
+++ b/middleware/etcd/etcd.go
@@ -9,6 +9,7 @@ import (
"github.com/coredns/coredns/middleware"
"github.com/coredns/coredns/middleware/etcd/msg"
+ "github.com/coredns/coredns/middleware/pkg/cache"
"github.com/coredns/coredns/middleware/pkg/singleflight"
"github.com/coredns/coredns/middleware/proxy"
"github.com/coredns/coredns/request"
@@ -90,7 +91,10 @@ func (e *Etcd) Records(name string, exact bool) ([]msg.Service, error) {
// get is a wrapper for client.Get that uses SingleInflight to suppress multiple outstanding queries.
func (e *Etcd) get(path string, recursive bool) (*etcdc.Response, error) {
- resp, err := e.Inflight.Do(path, func() (interface{}, error) {
+
+ hash := cache.Hash([]byte(path))
+
+ resp, err := e.Inflight.Do(hash, func() (interface{}, error) {
ctx, cancel := context.WithTimeout(e.Ctx, etcdTimeout)
defer cancel()
r, e := e.Client.Get(ctx, path, &etcdc.GetOptions{Sort: false, Recursive: recursive})
diff --git a/middleware/pkg/cache/cache.go b/middleware/pkg/cache/cache.go
new file mode 100644
index 000000000..56cae2180
--- /dev/null
+++ b/middleware/pkg/cache/cache.go
@@ -0,0 +1,129 @@
+// Package cache implements a cache. The cache hold 256 shards, each shard
+// holds a cache: a map with a mutex. There is no fancy expunge algorithm, it
+// just randomly evicts elements when it gets full.
+package cache
+
+import (
+ "hash/fnv"
+ "sync"
+)
+
+// Hash returns the FNV hash of what.
+func Hash(what []byte) uint32 {
+ h := fnv.New32()
+ h.Write(what)
+ return h.Sum32()
+}
+
+// Cache is cache.
+type Cache struct {
+ shards [shardSize]*shard
+}
+
+// shard is a cache with random eviction.
+type shard struct {
+ items map[uint32]interface{}
+ size int
+
+ sync.RWMutex
+}
+
+// New returns a new cache.
+func New(size int) *Cache {
+ ssize := size / shardSize
+ if ssize < 512 {
+ ssize = 512
+ }
+
+ c := &Cache{}
+
+ // Initialize all the shards
+ for i := 0; i < shardSize; i++ {
+ c.shards[i] = newShard(ssize)
+ }
+ return c
+}
+
+// Add adds a new element to the cache. If the element already exists it is overwritten.
+func (c *Cache) Add(key uint32, el interface{}) {
+ shard := key & (shardSize - 1)
+ c.shards[shard].Add(key, el)
+}
+
+// Get looks up element index under key.
+func (c *Cache) Get(key uint32) (interface{}, bool) {
+ shard := key & (shardSize - 1)
+ return c.shards[shard].Get(key)
+}
+
+// Remove removes the element indexed with key.
+func (c *Cache) Remove(key uint32) {
+ shard := key & (shardSize - 1)
+ c.shards[shard].Remove(key)
+}
+
+// Len returns the number of elements in the cache.
+func (c *Cache) Len() int {
+ l := 0
+ for _, s := range c.shards {
+ l += s.Len()
+ }
+ return l
+}
+
+// newShard returns a new shard with size.
+func newShard(size int) *shard { return &shard{items: make(map[uint32]interface{}), size: size} }
+
+// Add adds element indexed by key into the cache. Any existing element is overwritten
+func (s *shard) Add(key uint32, el interface{}) {
+ l := s.Len()
+ if l+1 > s.size {
+ s.Evict()
+ }
+
+ s.Lock()
+ s.items[key] = el
+ s.Unlock()
+}
+
+// Remove removes the element indexed by key from the cache.
+func (s *shard) Remove(key uint32) {
+ s.Lock()
+ delete(s.items, key)
+ s.Unlock()
+}
+
+// Evict removes a random element from the cache.
+func (s *shard) Evict() {
+ s.Lock()
+ defer s.Unlock()
+
+ key := -1
+ for k := range s.items {
+ key = int(k)
+ break
+ }
+ if key == -1 {
+ // empty cache
+ return
+ }
+ delete(s.items, uint32(key))
+}
+
+// Get looks up the element indexed under key.
+func (s *shard) Get(key uint32) (interface{}, bool) {
+ s.RLock()
+ el, found := s.items[key]
+ s.RUnlock()
+ return el, found
+}
+
+// Len returns the current length of the cache.
+func (s *shard) Len() int {
+ s.RLock()
+ l := len(s.items)
+ s.RUnlock()
+ return l
+}
+
+const shardSize = 256
diff --git a/middleware/pkg/cache/cache_test.go b/middleware/pkg/cache/cache_test.go
new file mode 100644
index 000000000..2c92bf438
--- /dev/null
+++ b/middleware/pkg/cache/cache_test.go
@@ -0,0 +1,31 @@
+package cache
+
+import "testing"
+
+func TestCacheAddAndGet(t *testing.T) {
+ c := New(4)
+ c.Add(1, 1)
+
+ if _, found := c.Get(1); !found {
+ t.Fatal("Failed to find inserted record")
+ }
+}
+
+func TestCacheLen(t *testing.T) {
+ c := New(4)
+
+ c.Add(1, 1)
+ if l := c.Len(); l != 1 {
+ t.Fatalf("Cache size should %d, got %d", 1, l)
+ }
+
+ c.Add(1, 1)
+ if l := c.Len(); l != 1 {
+ t.Fatalf("Cache size should %d, got %d", 1, l)
+ }
+
+ c.Add(2, 2)
+ if l := c.Len(); l != 2 {
+ t.Fatalf("Cache size should %d, got %d", 2, l)
+ }
+}
diff --git a/middleware/pkg/cache/shard_test.go b/middleware/pkg/cache/shard_test.go
new file mode 100644
index 000000000..26675cee1
--- /dev/null
+++ b/middleware/pkg/cache/shard_test.go
@@ -0,0 +1,60 @@
+package cache
+
+import "testing"
+
+func TestShardAddAndGet(t *testing.T) {
+ s := newShard(4)
+ s.Add(1, 1)
+
+ if _, found := s.Get(1); !found {
+ t.Fatal("Failed to find inserted record")
+ }
+}
+
+func TestShardLen(t *testing.T) {
+ s := newShard(4)
+
+ s.Add(1, 1)
+ if l := s.Len(); l != 1 {
+ t.Fatalf("Shard size should %d, got %d", 1, l)
+ }
+
+ s.Add(1, 1)
+ if l := s.Len(); l != 1 {
+ t.Fatalf("Shard size should %d, got %d", 1, l)
+ }
+
+ s.Add(2, 2)
+ if l := s.Len(); l != 2 {
+ t.Fatalf("Shard size should %d, got %d", 2, l)
+ }
+}
+
+func TestShardEvict(t *testing.T) {
+ s := newShard(1)
+ s.Add(1, 1)
+ s.Add(2, 2)
+ // 1 should be gone
+
+ if _, found := s.Get(1); found {
+ t.Fatal("Found item that should have been evicted")
+ }
+}
+
+func TestShardLenEvict(t *testing.T) {
+ s := newShard(4)
+ s.Add(1, 1)
+ s.Add(2, 1)
+ s.Add(3, 1)
+ s.Add(4, 1)
+
+ if l := s.Len(); l != 4 {
+ t.Fatalf("Shard size should %d, got %d", 4, l)
+ }
+
+ // This should evict one element
+ s.Add(5, 1)
+ if l := s.Len(); l != 4 {
+ t.Fatalf("Shard size should %d, got %d", 4, l)
+ }
+}
diff --git a/middleware/pkg/singleflight/singleflight.go b/middleware/pkg/singleflight/singleflight.go
index ff2c2ee4f..365e3ef58 100644
--- a/middleware/pkg/singleflight/singleflight.go
+++ b/middleware/pkg/singleflight/singleflight.go
@@ -31,17 +31,17 @@ type call struct {
// units of work can be executed with duplicate suppression.
type Group struct {
mu sync.Mutex // protects m
- m map[string]*call // lazily initialized
+ m map[uint32]*call // lazily initialized
}
// Do executes and returns the results of the given function, making
// sure that only one execution is in-flight for a given key at a
// time. If a duplicate comes in, the duplicate caller waits for the
// original to complete and receives the same results.
-func (g *Group) Do(key string, fn func() (interface{}, error)) (interface{}, error) {
+func (g *Group) Do(key uint32, fn func() (interface{}, error)) (interface{}, error) {
g.mu.Lock()
if g.m == nil {
- g.m = make(map[string]*call)
+ g.m = make(map[uint32]*call)
}
if c, ok := g.m[key]; ok {
g.mu.Unlock()
diff --git a/middleware/pkg/singleflight/singleflight_test.go b/middleware/pkg/singleflight/singleflight_test.go
index 47b4d3dc0..d1d406e0b 100644
--- a/middleware/pkg/singleflight/singleflight_test.go
+++ b/middleware/pkg/singleflight/singleflight_test.go
@@ -27,7 +27,7 @@ import (
func TestDo(t *testing.T) {
var g Group
- v, err := g.Do("key", func() (interface{}, error) {
+ v, err := g.Do(1, func() (interface{}, error) {
return "bar", nil
})
if got, want := fmt.Sprintf("%v (%T)", v, v), "bar (string)"; got != want {
@@ -41,7 +41,7 @@ func TestDo(t *testing.T) {
func TestDoErr(t *testing.T) {
var g Group
someErr := errors.New("Some error")
- v, err := g.Do("key", func() (interface{}, error) {
+ v, err := g.Do(1, func() (interface{}, error) {
return nil, someErr
})
if err != someErr {
@@ -66,7 +66,7 @@ func TestDoDupSuppress(t *testing.T) {
for i := 0; i < n; i++ {
wg.Add(1)
go func() {
- v, err := g.Do("key", fn)
+ v, err := g.Do(1, fn)
if err != nil {
t.Errorf("Do error: %v", err)
}