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 <[email protected]> Authored: Tue Nov 24 12:07:50 2015 -0800 Committer: Colin P. Mccabe <[email protected]> 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{
