Repository: gocql/gocql
Pull request #1405 (2020-02-17 15:16:34)

Fix selection of host by token
We've seen increased per-query latency after upgrading to latest gocql.
This commit fixes the latency issue for us.

This partially reverts 7b17705d75148afe48e336a49743178a201cdda3. There
were multiple unrelated changes in that commit. The relevant part of
that commit's description is:

    Fix finding the correct token in the token ring for host selection.

Unfortunately that description does not contain the details of the issue
it was aimed to fix.

The change in 7b17705d75148afe48e336a49743178a201cdda3 also made the two
binary search implementations (tokenRingReplicas.replicasFor and
tokenRing.GetHostForToken) inconsistent, reverting the change fixed this
discrepancy as well.

The token values returned in system.peers and system.local tables are
ends of ranges that the nodes are responsible for[1], so we never need
to rollunder.

When searching for a node responsible for token X (computed from
partition key), we need to find hostTokens with end token Y with the
lowest value such that Y >= X. In case X is larger than the largest
end token value in tokenRingReplicas, we wrap the ring and the node with
the lowest token is responsible (i.e. the hostTokens at index 0).

[1] https://docs.datastax.com/en/dse/6.7/dse-arch/datastax_enterprise/dbArch/archAboutDataDistribute.html

martin-sucha: Hi @Zariel I'm not sure whether it's the correct fix since I couldn't find good documentation on how the token ranges in Cassandra work exactly (if you happen to have a link to a good documentation that describes the edge cases, please let me know), but this change fixed a latency regression here. What was the reason for the rollunder change in https://github.com/gocql/gocql/commit/7b17705d75148afe48e336a49743178a201cdda3 ?
martin-sucha: Okay I finally found a piece of official documentation I was looking for that describes the edge cases: https://docs.datastax.com/en/dse/6.7/dse-arch/datastax_enterprise/dbArch/archAboutDataDistribute.html

(I found some other contradicting pieces of information on the internet)

The docs confirm that the tokens returned from `system.peers` and `system.local` are end of the range (the end is included in the range).

I'm going to update the commit message to include the explanation of why this fixes the issue including a link to the documentation.

Patch:
diff --git a/README.md b/README.md
index a35d9f3..ccb4803 100644
--- a/README.md
+++ b/README.md
@@ -166,6 +166,22 @@ func main() {
 }
 ```
 
+
+Authentication 
+-------
+
+```go
+cluster := gocql.NewCluster("192.168.1.1", "192.168.1.2", "192.168.1.3")
+cluster.Authenticator = gocql.PasswordAuthenticator{
+	Username: "user",
+	Password: "password"
+}
+cluster.Keyspace = "example"
+cluster.Consistency = gocql.Quorum
+session, _ := cluster.CreateSession()
+defer session.Close()
+```
+
 Data Binding
 ------------
 
diff --git a/policies.go b/policies.go
index a93bd66..83c9bca 100644
--- a/policies.go
+++ b/policies.go
@@ -953,10 +953,15 @@ func (c *ConstantReconnectionPolicy) GetMaxRetries() int {
 type ExponentialReconnectionPolicy struct {
 	MaxRetries      int
 	InitialInterval time.Duration
+	MaxInterval     time.Duration
 }
 
 func (e *ExponentialReconnectionPolicy) GetInterval(currentRetry int) time.Duration {
-	return getExponentialTime(e.InitialInterval, math.MaxInt16*time.Second, currentRetry)
+	max := e.MaxInterval
+	if max < e.InitialInterval {
+		max = math.MaxInt16 * time.Second
+	}
+	return getExponentialTime(e.InitialInterval, max, currentRetry)
 }
 
 func (e *ExponentialReconnectionPolicy) GetMaxRetries() int {
diff --git a/token.go b/token.go
index 8ab7b85..51d2b71 100644
--- a/token.go
+++ b/token.go
@@ -130,8 +130,15 @@ func (ht hostToken) String() string {
 // a data structure for organizing the relationship between tokens and hosts
 type tokenRing struct {
 	partitioner partitioner
-	tokens      []hostToken
-	hosts       []*HostInfo
+
+	// tokens map token range to primary replica.
+	// The elements in tokens are sorted by token ascending.
+	// The range for a given item in tokens starts after preceding range and ends with the token specified in
+	// token. The end token is part of the range.
+	// The lowest (i.e. index 0) range wraps around the ring (its preceding range is the one with largest index).
+	tokens []hostToken
+
+	hosts []*HostInfo
 }
 
 func newTokenRing(partitioner string, hosts []*HostInfo) (*tokenRing, error) {
diff --git a/topology.go b/topology.go
index 008f4a7..5ff7fd2 100644
--- a/topology.go
+++ b/topology.go
@@ -8,10 +8,16 @@ import (
 )
 
 type hostTokens struct {
+	// token is end (inclusive) of token range these hosts belong to
 	token token
 	hosts []*HostInfo
 }
 
+// tokenRingReplicas maps token ranges to list of replicas.
+// The elements in tokenRingReplicas are sorted by token ascending.
+// The range for a given item in tokenRingReplicas starts after preceding range and ends with the token specified in
+// token. The end token is part of the range.
+// The lowest (i.e. index 0) range wraps around the ring (its preceding range is the one with largest index).
 type tokenRingReplicas []hostTokens
 
 func (h tokenRingReplicas) Less(i, j int) bool { return h[i].token.Less(h[j].token) }
@@ -27,19 +33,9 @@ func (h tokenRingReplicas) replicasFor(t token) *hostTokens {
 		return !h[i].token.Less(t)
 	})
 
-	// TODO: simplify this
-	if p < len(h) && h[p].token == t {
-		return &h[p]
-	}
-
-	p--
-
 	if p >= len(h) {
 		// rollover
 		p = 0
-	} else if p < 0 {
-		// rollunder
-		p = len(h) - 1
 	}
 
 	return &h[p]


Test patch:
diff --git a/policies_test.go b/policies_test.go
index e65a11f..826b2cd 100644
--- a/policies_test.go
+++ b/policies_test.go
@@ -106,8 +106,8 @@ func TestHostPolicy_TokenAware_SimpleStrategy(t *testing.T) {
 	// now the token ring is configured
 	query.RoutingKey([]byte("20"))
 	iter = policy.Pick(query)
-	iterCheck(t, iter, "0")
 	iterCheck(t, iter, "1")
+	iterCheck(t, iter, "2")
 }
 
 // Tests of the host pool host selection policy implementation
@@ -608,7 +608,7 @@ func TestHostPolicy_TokenAware_NetworkStrategy(t *testing.T) {
 	}, policyInternal.getMetadataReadOnly().replicas)
 
 	// now the token ring is configured
-	query.RoutingKey([]byte("23"))
+	query.RoutingKey([]byte("18"))
 	iter = policy.Pick(query)
 	// first should be hosts with matching token from the local DC
 	iterCheck(t, iter, "4")