Repository: google/certificate-transparency-go
Pull request #639 (2020-01-13 12:32:12)

Attempt to coerce get-entries ranges into alignment
This PR attempts to truncate incoming `get-entries` requests into order to coerce these requests into alignment on multiples of the maximum permitted block size.  This should result in subsequent requests/responses being more cache friendly.

### Checklist

- [X] I have updated the [CHANGELOG](CHANGELOG.md).
  - Adjust the draft version number according to [semantic versioning](https://semver.org/) rules.
- [ ] I have updated [documentation](docs/) accordingly.


codecov[bot]: # [Codecov](https://codecov.io/gh/google/certificate-transparency-go/pull/639?src=pr&el=h1) Report
> Merging [#639](https://codecov.io/gh/google/certificate-transparency-go/pull/639?src=pr&el=desc) into [master](https://codecov.io/gh/google/certificate-transparency-go/commit/c673245cdce131a7c02976894f4b6ac87bdc9bd7?src=pr&el=desc) will **increase** coverage by `<.01%`.
> The diff coverage is `81.81%`.

[![Impacted file tree graph](https://codecov.io/gh/google/certificate-transparency-go/pull/639/graphs/tree.svg?width=650&token=kYPnjCLppA&height=150&src=pr)](https://codecov.io/gh/google/certificate-transparency-go/pull/639?src=pr&el=tree)

```diff
@@            Coverage Diff             @@
##           master     #639      +/-   ##
==========================================
+ Coverage   71.75%   71.76%   +<.01%     
==========================================
  Files          90       90              
  Lines        9854     9864      +10     
==========================================
+ Hits         7071     7079       +8     
- Misses       2286     2287       +1     
- Partials      497      498       +1
```


| [Impacted Files](https://codecov.io/gh/google/certificate-transparency-go/pull/639?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [trillian/ctfe/handlers.go](https://codecov.io/gh/google/certificate-transparency-go/pull/639/diff?src=pr&el=tree#diff-dHJpbGxpYW4vY3RmZS9oYW5kbGVycy5nbw==) | `80.93% <81.81%> (-0.02%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/google/certificate-transparency-go/pull/639?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/google/certificate-transparency-go/pull/639?src=pr&el=footer). Last update [c673245...3637f9d](https://codecov.io/gh/google/certificate-transparency-go/pull/639?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

AlCutter: PTAL

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 45c016ff..6fa44259 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -12,12 +12,49 @@ The CTFE now includes a Cache-Control header in responses containing purely
 immutable data, e.g. those for get-entries and get-proof-by-hash. This allows
 clients and proxies to cache these responses for up to 24 hours.
 
+#### GetEntries
+Calls to `get-entries` which are at (or above) the maximum permitted number of
+entries whose `start` parameter does not fall on a multiple of the maximum
+permitted number of entries, will have their responses truncated such that
+subsequent requests will align with this boundary.
+This is intended to coerce callers of `get-entries` into all using the same
+`start` and `end` parameters and thereby increase the cachability of
+these requests.
+
+e.g.:
+
+<pre>
+Old behaviour:
+             1         2         3
+             0         0         0
+Entries>-----|---------|---------|----...
+Client A -------|---------|----------|...
+Client B --|--------|---------|-------...
+           ^        ^         ^
+           `--------`---------`---- requests
+
+With coercion (max batch = 10 entries):
+             1         2         3
+             0         0         0
+Entries>-----|---------|---------|----...
+Client A ----X---------|---------|...
+Client B --|-X---------|---------|-------...
+             ^
+             `-- Requests truncated
+</pre>
+
+This behaviour can be disabled by setting the `--align_getentries`
+flag to false.
+
 #### Flags
 
 The `ct_server` binary changed the default of these flags:
 
 -   `by_range` - Now defaults to `true`
 
+The `ct_server` binary added the following flags:
+-   `align_getentries` - See GetEntries section above for details
+
 ### Libraries
 
 #### x509 fork
diff --git a/trillian/ctfe/handlers.go b/trillian/ctfe/handlers.go
index 6889ee9c..9c5f62e2 100644
--- a/trillian/ctfe/handlers.go
+++ b/trillian/ctfe/handlers.go
@@ -45,8 +45,11 @@ import (
 	ct "github.com/google/certificate-transparency-go"
 )
 
-// TODO(drysdale): remove this flag once everything has migrated to ByRange
-var getByRange = flag.Bool("by_range", true, "Use trillian.GetEntriesByRange for get-entries processing")
+var (
+	// TODO(drysdale): remove this flag once everything has migrated to ByRange
+	getByRange      = flag.Bool("by_range", true, "Use trillian.GetEntriesByRange for get-entries processing")
+	alignGetEntries = flag.Bool("align_getentries", true, "Enable get-entries request alignment")
+)
 
 const (
 	// HTTP Cache-Control header
@@ -116,6 +119,7 @@ var (
 	reqsCounter        monitoring.Counter   // logid, ep => value
 	rspsCounter        monitoring.Counter   // logid, ep, rc => value
 	rspLatency         monitoring.Histogram // logid, ep, rc => value
+	alignedGetEntries  monitoring.Counter   // logid, aligned => count
 )
 
 // setupMetrics initializes all the exported metrics.
@@ -131,6 +135,7 @@ func setupMetrics(mf monitoring.MetricFactory) {
 	reqsCounter = mf.NewCounter("http_reqs", "Number of requests", "logid", "ep")
 	rspsCounter = mf.NewCounter("http_rsps", "Number of responses", "logid", "ep", "rc")
 	rspLatency = mf.NewHistogram("http_latency", "Latency of responses in seconds", "logid", "ep", "rc")
+	alignedGetEntries = mf.NewCounter("aligned_get_entries", "Number of get-entries requests which were aligned to size limit boundaries", "logid", "aligned")
 }
 
 // Entrypoints is a list of entrypoint names as exposed in statistics/logging.
@@ -717,7 +722,7 @@ func getEntries(ctx context.Context, li *logInfo, w http.ResponseWriter, r *http
 	// The first job is to parse the params and make sure they're sensible. We just make
 	// sure the range is valid. We don't do an extra roundtrip to get the current tree
 	// size and prefer to let the backend handle this case
-	start, end, err := parseGetEntriesRange(r, MaxGetEntriesAllowed)
+	start, end, err := parseGetEntriesRange(r, MaxGetEntriesAllowed, li.logID)
 	if err != nil {
 		return http.StatusBadRequest, fmt.Errorf("bad range on get-entries request: %s", err)
 	}
@@ -981,7 +986,7 @@ func marshalAndWriteAddChainResponse(sct *ct.SignedCertificateTimestamp, signer
 	return nil
 }
 
-func parseGetEntriesRange(r *http.Request, maxRange int64) (int64, int64, error) {
+func parseGetEntriesRange(r *http.Request, maxRange, logID int64) (int64, int64, error) {
 	start, err := strconv.ParseInt(r.FormValue(getEntriesParamStart), 10, 64)
 	if err != nil {
 		return 0, 0, err
@@ -1003,6 +1008,16 @@ func parseGetEntriesRange(r *http.Request, maxRange int64) (int64, int64, error)
 	if count > maxRange {
 		end = start + maxRange - 1
 	}
+	if *alignGetEntries && count >= maxRange {
+		// Truncate a "maximally sized" get-entries request at the next multiple
+		// of MaxGetEntriesAllowed.
+		// This is intended to coerce large runs of get-entries requests (e.g. by
+		// monitors/mirrors) into all requesting the same start/end ranges,
+		// thereby making the responses more readily cachable.
+		d := (end + 1) % maxRange
+		end = end - d
+		alignedGetEntries.Inc(strconv.FormatInt(logID, 10), strconv.FormatBool(d == 0))
+	}
 
 	return start, end, nil
 }


Test patch:
diff --git a/trillian/ctfe/handlers_test.go b/trillian/ctfe/handlers_test.go
index 62ab4b42..19ecb92c 100644
--- a/trillian/ctfe/handlers_test.go
+++ b/trillian/ctfe/handlers_test.go
@@ -1164,56 +1164,73 @@ func runTestGetEntriesRanges(t *testing.T) {
 			want:  http.StatusBadRequest,
 		},
 		{
-			desc:   "range too large, truncated",
-			start:  1000,
+			desc:   "range too large, coerced into alignment",
+			start:  14,
 			end:    50000,
-			rpcEnd: 1000 + MaxGetEntriesAllowed - 1,
 			want:   http.StatusInternalServerError,
+			rpcEnd: MaxGetEntriesAllowed - 1,
+			rpc:    true,
+		},
+		{
+			desc:   "range too large, already in alignment",
+			start:  MaxGetEntriesAllowed,
+			end:    5000,
+			want:   http.StatusInternalServerError,
+			rpcEnd: MaxGetEntriesAllowed + MaxGetEntriesAllowed - 1,
+			rpc:    true,
+		},
+		{
+			desc:   "small range straddling boundary, not coerced",
+			start:  MaxGetEntriesAllowed - 2,
+			end:    MaxGetEntriesAllowed + 2,
+			want:   http.StatusInternalServerError,
+			rpcEnd: MaxGetEntriesAllowed + 2,
 			rpc:    true,
 		},
 	}
 
-	info := setupTest(t, nil, nil)
-	defer info.mockCtrl.Finish()
-	handler := AppHandler{Info: info.li, Handler: getEntries, Name: "GetEntries", Method: http.MethodGet}
-
 	// This tests that only valid ranges make it to the backend for get-entries.
 	// We're testing request handling up to the point where we make the RPC so arrange for
 	// it to fail with a specific error.
 	for _, test := range tests {
-		info.setRemoteQuotaUser(test.wantQuotaUser)
-		if test.rpc {
-			end := test.rpcEnd
-			if end == 0 {
-				end = test.end
-			}
-			var chargeTo *trillian.ChargeTo
-			if len(test.wantQuotaUser) != 0 {
-				chargeTo = &trillian.ChargeTo{User: []string{test.wantQuotaUser}}
-			}
-			if *getByRange {
-				info.client.EXPECT().GetLeavesByRange(deadlineMatcher(), cmpMatcher{&trillian.GetLeavesByRangeRequest{LogId: 0x42, StartIndex: test.start, Count: end + 1 - test.start, ChargeTo: chargeTo}}).Return(nil, errors.New("RPCMADE"))
-			} else {
-				info.client.EXPECT().GetLeavesByIndex(deadlineMatcher(), cmpMatcher{&trillian.GetLeavesByIndexRequest{LogId: 0x42, LeafIndex: buildIndicesForRange(test.start, end), ChargeTo: chargeTo}}).Return(nil, errors.New("RPCMADE"))
+		t.Run(test.desc, func(t *testing.T) {
+			info := setupTest(t, nil, nil)
+			defer info.mockCtrl.Finish()
+			handler := AppHandler{Info: info.li, Handler: getEntries, Name: "GetEntries", Method: http.MethodGet}
+
+			info.setRemoteQuotaUser(test.wantQuotaUser)
+			if test.rpc {
+				end := test.rpcEnd
+				if end == 0 {
+					end = test.end
+				}
+				var chargeTo *trillian.ChargeTo
+				if len(test.wantQuotaUser) != 0 {
+					chargeTo = &trillian.ChargeTo{User: []string{test.wantQuotaUser}}
+				}
+				if *getByRange {
+					info.client.EXPECT().GetLeavesByRange(deadlineMatcher(), cmpMatcher{&trillian.GetLeavesByRangeRequest{LogId: 0x42, StartIndex: test.start, Count: end + 1 - test.start, ChargeTo: chargeTo}}).Return(nil, errors.New("RPCMADE"))
+				} else {
+					info.client.EXPECT().GetLeavesByIndex(deadlineMatcher(), cmpMatcher{&trillian.GetLeavesByIndexRequest{LogId: 0x42, LeafIndex: buildIndicesForRange(test.start, end), ChargeTo: chargeTo}}).Return(nil, errors.New("RPCMADE"))
+				}
 			}
-		}
 
-		path := fmt.Sprintf("/ct/v1/get-entries?start=%d&end=%d", test.start, test.end)
-		req, err := http.NewRequest("GET", path, nil)
-		if err != nil {
-			t.Errorf("Failed to create request: %v", err)
-			continue
-		}
-		w := httptest.NewRecorder()
-		handler.ServeHTTP(w, req)
+			path := fmt.Sprintf("/ct/v1/get-entries?start=%d&end=%d", test.start, test.end)
+			req, err := http.NewRequest("GET", path, nil)
+			if err != nil {
+				t.Fatalf("Failed to create request: %v", err)
+			}
+			w := httptest.NewRecorder()
+			handler.ServeHTTP(w, req)
 
-		if got := w.Code; got != test.want {
-			t.Errorf("getEntries(%d, %d)=%d; want %d for test %s", test.start, test.end, got, test.want, test.desc)
-		}
-		if test.rpc && !strings.Contains(w.Body.String(), "RPCMADE") {
-			// If an RPC was emitted, it should have received and propagated an error.
-			t.Errorf("getEntries(%d, %d)=%q; expect RPCMADE for test %s", test.start, test.end, w.Body, test.desc)
-		}
+			if got := w.Code; got != test.want {
+				t.Errorf("getEntries(%d, %d)=%d; want %d for test %s", test.start, test.end, got, test.want, test.desc)
+			}
+			if test.rpc && !strings.Contains(w.Body.String(), "RPCMADE") {
+				// If an RPC was emitted, it should have received and propagated an error.
+				t.Errorf("getEntries(%d, %d)=%q; expect RPCMADE for test %s", test.start, test.end, w.Body, test.desc)
+			}
+		})
 	}
 }