htrace-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From cmcc...@apache.org
Subject incubator-htrace git commit: HTRACE-304. htraced: fix bug with GREATER_THAN queries (cmccabe)
Date Tue, 24 Nov 2015 20:14:31 GMT
Repository: incubator-htrace
Updated Branches:
  refs/heads/master 5f87495ab -> df684e2cf


HTRACE-304. htraced: fix bug with GREATER_THAN queries (cmccabe)


Project: http://git-wip-us.apache.org/repos/asf/incubator-htrace/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-htrace/commit/df684e2c
Tree: http://git-wip-us.apache.org/repos/asf/incubator-htrace/tree/df684e2c
Diff: http://git-wip-us.apache.org/repos/asf/incubator-htrace/diff/df684e2c

Branch: refs/heads/master
Commit: df684e2cfc6cfa3a6c162ecc9fc743be6196ec5c
Parents: 5f87495
Author: Colin P. Mccabe <cmccabe@apache.org>
Authored: Tue Nov 24 12:07:50 2015 -0800
Committer: Colin P. Mccabe <cmccabe@apache.org>
Committed: Tue Nov 24 12:07:50 2015 -0800

----------------------------------------------------------------------
 .../src/org/apache/htrace/htraced/datastore.go  | 88 +++++++++++---------
 .../org/apache/htrace/htraced/datastore_test.go | 62 ++++++++++++++
 2 files changed, 111 insertions(+), 39 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/df684e2c/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go
----------------------------------------------------------------------
diff --git a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go
index 816123a..3f17a61 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go
@@ -1013,20 +1013,51 @@ func (pred *predicateData) spanPtrIsBefore(a *common.Span, b *common.Span)
bool
 	}
 }
 
-// Returns true if the predicate is satisfied by the given span.
-func (pred *predicateData) satisfiedBy(span *common.Span) bool {
+type satisfiedByReturn int
+
+const (
+	NOT_SATISFIED satisfiedByReturn = iota
+	NOT_YET_SATISFIED = iota
+	SATISFIED = iota
+)
+
+// Determine whether the predicate is satisfied by the given span.
+func (pred *predicateData) satisfiedBy(span *common.Span) satisfiedByReturn {
 	val := pred.extractRelevantSpanData(span)
 	switch pred.Op {
 	case common.CONTAINS:
-		return bytes.Contains(val, pred.key)
+		if bytes.Contains(val, pred.key) {
+			return SATISFIED
+		} else {
+			return NOT_SATISFIED
+		}
 	case common.EQUALS:
-		return bytes.Equal(val, pred.key)
+		if bytes.Equal(val, pred.key) {
+			return SATISFIED
+		} else {
+			return NOT_SATISFIED
+		}
 	case common.LESS_THAN_OR_EQUALS:
-		return bytes.Compare(val, pred.key) <= 0
+		if bytes.Compare(val, pred.key) <= 0 {
+			return SATISFIED
+		} else {
+			return NOT_SATISFIED
+		}
 	case common.GREATER_THAN_OR_EQUALS:
-		return bytes.Compare(val, pred.key) >= 0
+		if bytes.Compare(val, pred.key) >= 0 {
+			return SATISFIED
+		} else {
+			return NOT_SATISFIED
+		}
 	case common.GREATER_THAN:
-		return bytes.Compare(val, pred.key) > 0
+		cmp := bytes.Compare(val, pred.key)
+		if cmp < 0 {
+			return NOT_SATISFIED
+		} else if cmp == 0 {
+			return NOT_YET_SATISFIED
+		} else {
+			return SATISFIED
+		}
 	default:
 		panic(fmt.Sprintf("unknown Op type %s should have been caught "+
 			"during normalization", pred.Op))
@@ -1176,25 +1207,6 @@ func CreateReaperSource(shd *shard) (*source, error) {
 	return src, nil
 }
 
-// Return true if this operation may require skipping the first result we get back from leveldb.
-func mayRequireOneSkip(op common.Op) bool {
-	switch op {
-	// When dealing with descending predicates, the first span we read might not satisfy
-	// the predicate, even though subsequent ones will.  This is because the iter.Seek()
-	// function "moves the iterator the position of the key given or, if the key doesn't
-	// exist, the next key that does exist in the database."  So if we're on that "next
-	// key" it will not satisfy the predicate, but the keys previous to it might.
-	case common.LESS_THAN_OR_EQUALS:
-		return true
-	// iter.Seek basically takes us to the key which is "greater than or equal to" some
-	// value.  Since we want greater than (not greater than or equal to) we may have to
-	// skip the first key.
-	case common.GREATER_THAN:
-		return true
-	}
-	return false
-}
-
 // Fill in the entry in the 'next' array for a specific shard.
 func (src *source) populateNextFromShard(shardIdx int) {
 	lg := src.store.lg
@@ -1253,20 +1265,18 @@ func (src *source) populateNextFromShard(shardIdx int) {
 		} else {
 			iter.Next()
 		}
-		if src.pred.satisfiedBy(span) {
-			lg.Debugf("Populated valid span %v from shard %s.\n", sid, shdPath)
-			src.nexts[shardIdx] = span // Found valid entry
-			return
-		} else {
+		ret := src.pred.satisfiedBy(span)
+		switch ret {
+		case NOT_SATISFIED:
+			break // This and subsequent entries don't satisfy predicate
+		case SATISFIED:
 			if lg.DebugEnabled() {
-				lg.Debugf("Span %s from shard %s does not satisfy the predicate.\n",
-					sid.String(), shdPath)
-			}
-			if src.numRead[shardIdx] <= 1 && mayRequireOneSkip(src.pred.Op) {
-				continue
+				lg.Debugf("Populated valid span %v from shard %s.\n", sid, shdPath)
 			}
-			// This and subsequent entries don't satisfy predicate
-			break
+			src.nexts[shardIdx] = span // Found valid entry
+			return
+		case NOT_YET_SATISFIED:
+			continue // try again
 		}
 	}
 	lg.Debugf("Closing iterator for shard %s.\n", shdPath)
@@ -1361,7 +1371,7 @@ func (store *dataStore) HandleQuery(query *common.Query) ([]*common.Span,
error)
 		}
 		satisfied := true
 		for predIdx := range preds {
-			if !preds[predIdx].satisfiedBy(span) {
+			if preds[predIdx].satisfiedBy(span) != SATISFIED {
 				satisfied = false
 				break
 			}

http://git-wip-us.apache.org/repos/asf/incubator-htrace/blob/df684e2c/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go
----------------------------------------------------------------------
diff --git a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go
index b13112b..05fabfd 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go
@@ -330,6 +330,68 @@ func TestQueries4(t *testing.T) {
 	}, []common.Span{SIMPLE_TEST_SPANS[2]})
 }
 
+var TEST_QUERIES5_SPANS []common.Span = []common.Span{
+	common.Span{Id: common.TestId("10000000000000000000000000000001"),
+		SpanData: common.SpanData{
+			Begin:       123,
+			End:         456,
+			Description: "span1",
+			Parents:     []common.SpanId{},
+			TracerId:    "myTracer",
+		}},
+	common.Span{Id: common.TestId("10000000000000000000000000000002"),
+		SpanData: common.SpanData{
+			Begin:       123,
+			End:         200,
+			Description: "span2",
+			Parents:     []common.SpanId{common.TestId("10000000000000000000000000000001")},
+			TracerId:    "myTracer",
+		}},
+	common.Span{Id: common.TestId("10000000000000000000000000000003"),
+		SpanData: common.SpanData{
+			Begin:       124,
+			End:         457,
+			Description: "span3",
+			Parents:     []common.SpanId{common.TestId("10000000000000000000000000000001")},
+			TracerId:    "myTracer",
+		}},
+}
+
+func TestQueries5(t *testing.T) {
+	t.Parallel()
+	htraceBld := &MiniHTracedBuilder{Name: "TestQueries5",
+		WrittenSpans: common.NewSemaphore(0),
+		DataDirs: make([]string, 1),
+	}
+	ht, err := htraceBld.Build()
+	if err != nil {
+		panic(err)
+	}
+	defer ht.Close()
+	createSpans(TEST_QUERIES5_SPANS, ht.Store)
+
+	testQuery(t, ht, &common.Query{
+		Predicates: []common.Predicate{
+			common.Predicate{
+				Op:    common.GREATER_THAN,
+				Field: common.BEGIN_TIME,
+				Val:   "123",
+			},
+		},
+		Lim: 5,
+	}, []common.Span{TEST_QUERIES5_SPANS[2]})
+	testQuery(t, ht, &common.Query{
+		Predicates: []common.Predicate{
+			common.Predicate{
+				Op:    common.GREATER_THAN,
+				Field: common.END_TIME,
+				Val:   "200",
+			},
+		},
+		Lim: 500,
+	}, []common.Span{TEST_QUERIES5_SPANS[0], TEST_QUERIES5_SPANS[2]})
+}
+
 func BenchmarkDatastoreWrites(b *testing.B) {
 	htraceBld := &MiniHTracedBuilder{Name: "BenchmarkDatastoreWrites",
 		Cnf: map[string]string{


Mime
View raw message