Repository: bmatsuo/lmdb-go (c)

Issue:
lmdbsync: default MapResizeHandler strategy should have exponential backoff
Right now there is a constant delay. This is doesn't seem terrible for the default (low) number of retries. But increasing the number of retries is not as effective as it should be.

Also, it seems a little weird that the delay function only gets called after one immediate attempt. It seems more flexible and consistent to always call the delay function.

Pull request description:
lmdbsync: changes to MapResizedHandler delays and defaults
Fixes #54 

A DelayFunc type is defined to describe the interface for
MapResizedHandler.  The delay function is called before each call to
Env.SetMapSize including the first, when its argument is zero.  This is
an incompatible change for lmdbsync.

Additionally, the default values for MapResizedHandler arguments have
been renamed so that they more clearly reflect their purpose.  Their
previous names made no sense to users as they corresponded to field
names for unexported structs.

Patch:
diff --git a/exp/lmdbsync/handler.go b/exp/lmdbsync/handler.go
index 9841190..abd1b95 100644
--- a/exp/lmdbsync/handler.go
+++ b/exp/lmdbsync/handler.go
@@ -2,6 +2,8 @@ package lmdbsync
 
 import (
 	"errors"
+	"math"
+	"math/rand"
 	"time"
 
 	"golang.org/x/net/context"
@@ -45,19 +47,48 @@ func (c HandlerChain) Append(h ...Handler) HandlerChain {
 //
 // If the database is growing too rapidly and maxRetry consecutive transactions
 // fail due to lmdb.MapResized then the Handler returned by MapResizedHandler
-// gives up and returns the lmdb.MapResized error to the caller.  When
-// repeatDelay is not nil it will be called to insert a delay between attempts
-// to adopt the new map size.
+// gives up and returns the lmdb.MapResized error to the caller.  Delay will be
+// called before each call to Env.SetMapSize to insert an optional delay.
 //
 // Open transactions must not directly create new (non-child) transactions when
 // using MapResizedHandler or the environment will deadlock.
-func MapResizedHandler(maxRetry int, repeatDelay func(retry int) time.Duration) Handler {
+func MapResizedHandler(maxRetry int, delay DelayFunc) Handler {
+	if maxRetry == 0 {
+		maxRetry = MapResizedDefaultRetry
+	}
+	if delay == nil {
+		delay = MapResizedDefaultDelay
+	}
 	return &resizedHandler{
-		RetryResize:       maxRetry,
-		DelayRepeatResize: repeatDelay,
+		MaxRetry: maxRetry,
+		Delay:    delay,
+	}
+}
+
+// MapResizedDefaultRetry is the default number of attempts MapResizedHandler
+// will make adopt a new map size when lmdb.MapResized is encountered
+// repeatedly.
+var MapResizedDefaultRetry = 2
+
+// DelayFunc takes as input the number of previous attempts and returns the
+// delay before making another attempt.
+type DelayFunc func(attempt int) time.Duration
+
+// ExponentialBackoff returns a function that delays each attempt by random
+// number between 0 and the minimum of max and base*factor^attempt.
+func ExponentialBackoff(base time.Duration, max time.Duration, factor float64) DelayFunc {
+	return func(attempt int) time.Duration {
+		_max := float64(base) * math.Pow(factor, float64(attempt))
+		_max = math.Min(_max, float64(max))
+		n := rand.Int63n(int64(_max))
+		return time.Duration(n)
 	}
 }
 
+// MapResizedDefaultDelay is the default DelayFunc when MapResizedHandler is
+// passed a nil value.
+var MapResizedDefaultDelay = ExponentialBackoff(time.Millisecond, 5*time.Millisecond, 2)
+
 // MapFullFunc is a function for resizing a memory map after it has become
 // full.  The function receives the current map size as its argument and
 // returns a new map size.  The new size will only be applied if the second
@@ -79,18 +110,6 @@ func MapFullHandler(fn MapFullFunc) Handler {
 	return &mapFullHandler{fn}
 }
 
-// DefaultRetryResize is the default number of times to retry a transaction
-// that is returning repeatedly MapResized. This signifies rapid database
-// growth from another process or some bug/corruption in memory.
-//
-// If DefaultRetryResize is less than zero the transaction will be retried
-// indefinitely.
-var DefaultRetryResize = 2
-
-// DefaultDelayRepeatResize is the default delay between encountering
-// lmdb.MapResized and calling Env.MapSize to adopt the latest size.
-var DefaultDelayRepeatResize = time.Millisecond
-
 // ErrTxnRetry is returned by a Handler to have the Env retry the transaction.
 var ErrTxnRetry = errors.New("lmdbsync: retry failed txn")
 
@@ -195,24 +214,8 @@ func withResizedRetryCount(ctx context.Context, count *resizeRetryCount) context
 }
 
 type resizedHandler struct {
-	// RetryResize overrides DefaultRetryResize for the Env.
-	RetryResize int
-	// DelayRepeateResize overrides DefaultDelayRetryResize for the Env.
-	DelayRepeatResize func(retry int) time.Duration
-}
-
-func (h *resizedHandler) getRetryResize() int {
-	if h.RetryResize != 0 {
-		return h.RetryResize
-	}
-	return DefaultRetryResize
-}
-
-func (h *resizedHandler) getDelayRepeatResize(i int) time.Duration {
-	if h.DelayRepeatResize != nil {
-		return h.DelayRepeatResize(i)
-	}
-	return DefaultDelayRepeatResize
+	MaxRetry int
+	Delay    DelayFunc
 }
 
 func (h *resizedHandler) HandleTxnErr(ctx context.Context, env *Env, err error) (context.Context, error) {
@@ -226,11 +229,7 @@ func (h *resizedHandler) HandleTxnErr(ctx context.Context, env *Env, err error)
 
 	// fail the transaction with MapResized error when too many attempts have
 	// been made.
-	maxRetry := h.getRetryResize()
-	if maxRetry == 0 {
-		ctx := withResizedRetryCount(ctx, nil)
-		return ctx, err
-	}
+	maxRetry := h.MaxRetry
 	if maxRetry > 0 && numRetry >= maxRetry {
 		ctx := withResizedRetryCount(ctx, nil)
 		return ctx, err
@@ -238,11 +237,7 @@ func (h *resizedHandler) HandleTxnErr(ctx context.Context, env *Env, err error)
 
 	ctx = withResizedRetryCount(ctx, count.Add(1))
 
-	var delay time.Duration
-	if numRetry > 0 {
-		delay = h.getDelayRepeatResize(numRetry)
-	}
-
+	delay := h.Delay(numRetry)
 	err = env.setMapSize(0, delay)
 	if err != nil {
 		return ctx, err


Test patch:
diff --git a/exp/lmdbsync/handler_test.go b/exp/lmdbsync/handler_test.go
index d0bb8d2..a784267 100644
--- a/exp/lmdbsync/handler_test.go
+++ b/exp/lmdbsync/handler_test.go
@@ -169,3 +169,30 @@ func TestMapResizedHandler(t *testing.T) {
 		t.Errorf("unexpected error: %v", err)
 	}
 }
+
+func TestExponentialBackoff(t *testing.T) {
+	base := time.Millisecond
+	max := 3 * time.Millisecond
+	factor := 2.0
+	backoff := ExponentialBackoff(base, max, factor)
+
+	const numtest = 100
+	for i := 0; i < numtest; i++ {
+		n := backoff(0)
+		if n < 0 || n > base {
+			t.Errorf("unexpected backoff: %v", n)
+		}
+	}
+	for i := 0; i < numtest; i++ {
+		n := backoff(1)
+		if n < 0 || n > 2*base {
+			t.Errorf("unexpected backoff: %v", n)
+		}
+	}
+	for i := 0; i < numtest; i++ {
+		n := backoff(2)
+		if n < 0 || n > max {
+			t.Errorf("unexpected backoff: %v", n)
+		}
+	}
+}
diff --git a/exp/lmdbsync/testresize_test.go b/exp/lmdbsync/testresize_test.go
index 26fb2e1..21007a2 100644
--- a/exp/lmdbsync/testresize_test.go
+++ b/exp/lmdbsync/testresize_test.go
@@ -141,7 +141,9 @@ func TestResize(t *testing.T) {
 	runner := env.WithHandler(HandlerChain{
 		trace,
 		MapResizedHandler(2, func(retry int) time.Duration {
-			t.Error("unable to reopen")
+			if retry > 0 {
+				t.Errorf("failed to reopen at %d times", retry)
+			}
 			return time.Millisecond
 		}),
 	})