Change sampling to use knuth algorithm
MODIFY
dd-trace-ot/src/main/java/datadog/trace/common/sampling/AbstractSampler.java
dd-trace-ot/src/main/java/datadog/trace/common/sampling/AbstractSampler.java
@@ -6,6 +6,7 @@ import java.util.Map;
import java.util.Map.Entry;
import java.util.regex.Pattern;
+@Deprecated
public abstract class AbstractSampler implements Sampler {
/** Sample tags */
@@ -35,6 +36,7 @@ public abstract class AbstractSampler implements Sampler {
* @param tag
* @param skipPattern
*/
+ @Deprecated
public void addSkipTagPattern(final String tag, final Pattern skipPattern) {
skipTagsPatterns.put(tag, skipPattern);
}

ADD
dd-trace-ot/src/main/java/datadog/trace/common/sampling/KnuthSampler.java
+package datadog.trace.common.sampling;
+
+import datadog.opentracing.DDSpan;
+import datadog.opentracing.DDTracer;
+import java.math.BigDecimal;
+import java.math.BigInteger;
+import lombok.extern.slf4j.Slf4j;
+
+@Slf4j
+public class KnuthSampler implements RateSampler {
+ private static final BigInteger KNUTH_FACTOR = new BigInteger("1111111111111111111");
+ private static final BigDecimal TRACE_ID_MAX_AS_BIG_DECIMAL =
+ new BigDecimal(DDTracer.TRACE_ID_MAX);
+ private static final BigInteger MODULUS = new BigInteger("2").pow(64);
+
+ private final BigInteger cutoff;
+ private final double rate;
+
+ public KnuthSampler(final double rate) {
+ this.rate = rate;
+ cutoff = new BigDecimal(rate).multiply(TRACE_ID_MAX_AS_BIG_DECIMAL).toBigInteger();
+
+ log.debug("Initializing the RateSampler, sampleRate: {} %", rate * 100);
+ }
+
+ @Override
+ public boolean sample(final DDSpan span) {
+ final boolean sampled;
+ if (rate == 1) {
+ sampled = true;
+ } else if (rate == 0) {
+ sampled = false;
+ } else {
+ sampled = span.getTraceId().multiply(KNUTH_FACTOR).mod(MODULUS).compareTo(cutoff) < 0;
+ }
+
+ log.debug("{} - Span is sampled: {}", span, sampled);
+
+ return sampled;
+ }
+
+ @Override
+ public double getSampleRate() {
+ return rate;
+ }
+}

MODIFY
dd-trace-ot/src/main/java/datadog/trace/common/sampling/RateByServiceSampler.java
dd-trace-ot/src/main/java/datadog/trace/common/sampling/RateByServiceSampler.java
@@ -11,7 +11,6 @@ import datadog.trace.common.writer.DDApi.ResponseListener;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
-import java.util.concurrent.ThreadLocalRandom;
import lombok.extern.slf4j.Slf4j;
/**
@@ -27,7 +26,7 @@ public class RateByServiceSampler implements Sampler, ResponseListener {
private static final double DEFAULT_RATE = 1.0;
private volatile Map<String, RateSampler> serviceRates =
- unmodifiableMap(singletonMap(DEFAULT_KEY, new RateSampler(DEFAULT_RATE)));
+ unmodifiableMap(singletonMap(DEFAULT_KEY, createRateSampler(DEFAULT_RATE)));
@Override
public boolean sample(final DDSpan span) {
@@ -82,7 +81,7 @@ public class RateByServiceSampler implements Sampler, ResponseListener {
final JsonNode value = newServiceRates.get(key);
try {
if (value instanceof NumericNode) {
- updatedServiceRates.put(key, new RateSampler(value.doubleValue()));
+ updatedServiceRates.put(key, createRateSampler(value.doubleValue()));
} else {
log.debug("Unable to parse new service rate {} -> {}", key, value);
}
@@ -91,55 +90,23 @@ public class RateByServiceSampler implements Sampler, ResponseListener {
}
}
if (!updatedServiceRates.containsKey(DEFAULT_KEY)) {
- updatedServiceRates.put(DEFAULT_KEY, new RateSampler(DEFAULT_RATE));
+ updatedServiceRates.put(DEFAULT_KEY, createRateSampler(DEFAULT_RATE));
}
serviceRates = unmodifiableMap(updatedServiceRates);
}
}
- /**
- * This sampler sample the traces at a predefined rate.
- *
- * <p>Keep (100 * `sample_rate`)% of the traces. It samples randomly, its main purpose is to
- * reduce the integration footprint.
- */
- private static class RateSampler extends AbstractSampler {
-
- /** The sample rate used */
- private final double sampleRate;
-
- /**
- * Build an instance of the sampler. The Sample rate is fixed for each instance.
- *
- * @param sampleRate a number [0,1] representing the rate ratio.
- */
- private RateSampler(double sampleRate) {
-
+ private RateSampler createRateSampler(final double sampleRate) {
+ final double sanitizedRate;
if (sampleRate < 0) {
- sampleRate = 1;
log.error("SampleRate is negative or null, disabling the sampler");
+ sanitizedRate = 1;
} else if (sampleRate > 1) {
- sampleRate = 1;
- }
-
- this.sampleRate = sampleRate;
- log.debug("Initializing the RateSampler, sampleRate: {} %", this.sampleRate * 100);
- }
-
- @Override
- public boolean doSample(final DDSpan span) {
- final boolean sample = ThreadLocalRandom.current().nextFloat() <= sampleRate;
- log.debug("{} - Span is sampled: {}", span, sample);
- return sample;
- }
-
- public double getSampleRate() {
- return sampleRate;
+ sanitizedRate = 1;
+ } else {
+ sanitizedRate = sampleRate;
}
- @Override
- public String toString() {
- return "RateSampler { sampleRate=" + sampleRate + " }";
- }
+ return new KnuthSampler(sanitizedRate);
}
}

ADD
dd-trace-ot/src/main/java/datadog/trace/common/sampling/RateSampler.java
+package datadog.trace.common.sampling;
+
+public interface RateSampler extends Sampler {
+ double getSampleRate();
+}

ADD
dd-trace-ot/src/test/groovy/datadog/trace/api/sampling/KnuthSamplerTest.groovy
+package datadog.trace.api.sampling
+
+import datadog.opentracing.DDSpan
+import datadog.trace.common.sampling.KnuthSampler
+import datadog.trace.util.test.DDSpecification
+
+class KnuthSamplerTest extends DDSpecification {
+
+ def "test known values: #traceId"() {
+ given:
+ KnuthSampler sampler = new KnuthSampler(0.5)
+ DDSpan span = Mock(DDSpan) {
+ getTraceId() >> traceId
+ }
+
+ when:
+ def sampled = sampler.sample(span)
+
+ then:
+ sampled == expected
+
+ where:
+ expected | traceId
+ false | 10428415896243638596G
+ false | 11199607447739267382G
+ false | 11273630029763932141G
+ false | 11407674492757219439G
+ false | 11792151447964398879G
+ false | 12432680895096110463G
+ false | 13126262220165910460G
+ false | 13174268766980400525G
+ false | 15505210698284655633G
+ false | 15649472107743074779G
+ false | 17204678798284737396G
+ false | 17344948852394588913G
+ false | 17496662575514578077G
+ false | 18252401681137062077G
+ false | 18317291550776694829G
+ false | 1874068156324778273G
+ false | 1905388747193831650G
+ false | 2202916659517317514G
+ false | 2227583514184312746G
+ false | 2338498362660772719G
+ false | 2781055864473387780G
+ false | 3328451335138149956G
+ false | 3337066551442961397G
+ false | 3409814636252858217G
+ false | 3510942875414458836G
+ false | 3784560248718450071G
+ false | 4751997750760398084G
+ false | 4831389563158288344G
+ false | 4990765271833742716G
+ false | 5089134323978233018G
+ false | 5199948958991797301G
+ false | 5577006791947779410G
+ false | 5600924393587988459G
+ false | 5793183108815074904G
+ false | 6263450610539110790G
+ false | 6382800227808658932G
+ false | 6651414131918424343G
+ false | 6842348953158377901G
+ false | 6941261091797652072G
+ false | 7273596521315663110G
+ false | 7504504064263669287G
+ false | 788787457839692041G
+ false | 7955079406183515637G
+ false | 8549944162621642512G
+ false | 8603989663476771718G
+ false | 8807817071862113702G
+ false | 9010467728050264449G
+ true | 10667007354186551956G
+ true | 10683692646452562431G
+ true | 10821471013040158923G
+ true | 10950412492527322440G
+ true | 11239168150708129139G
+ true | 1169089424364679180G
+ true | 11818186001859264308G
+ true | 11833901312327420776G
+ true | 11926759511765359899G
+ true | 11926873763676642186G
+ true | 11963748953446345529G
+ true | 11998794077335055257G
+ true | 12096659438561119542G
+ true | 12156940908066221323G
+ true | 12947799971452915849G
+ true | 13260572831089785859G
+ true | 13771804148684671731G
+ true | 14117161486975057715G
+ true | 14242321332569825828G
+ true | 14486903973548550719G
+ true | 14967026985784794439G
+ true | 15213854965919594827G
+ true | 15352856648520921629G
+ true | 15399114114227588261G
+ true | 15595235597337683065G
+ true | 16194613440650274502G
+ true | 1687184559264975024G
+ true | 17490665426807838719G
+ true | 18218388313430417611G
+ true | 2601737961087659062G
+ true | 261049867304784443G
+ true | 2740103009342231109G
+ true | 2970700287221458280G
+ true | 3916589616287113937G
+ true | 4324745483838182873G
+ true | 4937104021912138218G
+ true | 5486140987150761883G
+ true | 5944830206637008055G
+ true | 6296367092202729479G
+ true | 6334824724549167320G
+ true | 6556961545928831643G
+ true | 6735196588112087610G
+ true | 7388428680384065704G
+ true | 8249030965139585917G
+ true | 837825985403119657G
+ true | 8505906760983331750G
+ true | 8674665223082153551G
+ true | 894385949183117216G
+ true | 898860202204764712G
+ true | 9768663798983814715G
+ true | 9828766684487745566G
+ true | 9908585559158765387G
+ true | 9956202364908137547G
+ }
+
+ def "test sampling none: #traceId"() {
+ given:
+ KnuthSampler sampler = new KnuthSampler(0)
+ DDSpan span = Mock(DDSpan) {
+ getTraceId() >> traceId
+ }
+
+ when:
+ def sampled = sampler.sample(span)
+
+ then:
+ sampled == expected
+
+ // These values are repeated from the "known values test"
+ // It is an arbitrary subset of all possible traceIds
+ where:
+ expected | traceId
+ false | 10428415896243638596G
+ false | 11199607447739267382G
+ false | 11273630029763932141G
+ false | 11407674492757219439G
+ false | 11792151447964398879G
+ false | 12432680895096110463G
+ false | 13126262220165910460G
+ false | 13174268766980400525G
+ false | 15505210698284655633G
+ false | 15649472107743074779G
+ false | 17204678798284737396G
+ false | 17344948852394588913G
+ false | 17496662575514578077G
+ false | 18252401681137062077G
+ false | 18317291550776694829G
+ false | 1874068156324778273G
+ false | 1905388747193831650G
+ false | 2202916659517317514G
+ false | 2227583514184312746G
+ false | 2338498362660772719G
+ false | 2781055864473387780G
+ false | 3328451335138149956G
+ false | 3337066551442961397G
+ false | 3409814636252858217G
+ false | 3510942875414458836G
+ false | 3784560248718450071G
+ false | 4751997750760398084G
+ false | 4831389563158288344G
+ false | 4990765271833742716G
+ false | 5089134323978233018G
+ false | 5199948958991797301G
+ false | 5577006791947779410G
+ false | 5600924393587988459G
+ false | 5793183108815074904G
+ false | 6263450610539110790G
+ false | 6382800227808658932G
+ false | 6651414131918424343G
+ false | 6842348953158377901G
+ false | 6941261091797652072G
+ false | 7273596521315663110G
+ false | 7504504064263669287G
+ false | 788787457839692041G
+ false | 7955079406183515637G
+ false | 8549944162621642512G
+ false | 8603989663476771718G
+ false | 8807817071862113702G
+ false | 9010467728050264449G
+ false | 10667007354186551956G
+ false | 10683692646452562431G
+ false | 10821471013040158923G
+ false | 10950412492527322440G
+ false | 11239168150708129139G
+ false | 1169089424364679180G
+ false | 11818186001859264308G
+ false | 11833901312327420776G
+ false | 11926759511765359899G
+ false | 11926873763676642186G
+ false | 11963748953446345529G
+ false | 11998794077335055257G
+ false | 12096659438561119542G
+ false | 12156940908066221323G
+ false | 12947799971452915849G
+ false | 13260572831089785859G
+ false | 13771804148684671731G
+ false | 14117161486975057715G
+ false | 14242321332569825828G
+ false | 14486903973548550719G
+ false | 14967026985784794439G
+ false | 15213854965919594827G
+ false | 15352856648520921629G
+ false | 15399114114227588261G
+ false | 15595235597337683065G
+ false | 16194613440650274502G
+ false | 1687184559264975024G
+ false | 17490665426807838719G
+ false | 18218388313430417611G
+ false | 2601737961087659062G
+ false | 261049867304784443G
+ false | 2740103009342231109G
+ false | 2970700287221458280G
+ false | 3916589616287113937G
+ false | 4324745483838182873G
+ false | 4937104021912138218G
+ false | 5486140987150761883G
+ false | 5944830206637008055G
+ false | 6296367092202729479G
+ false | 6334824724549167320G
+ false | 6556961545928831643G
+ false | 6735196588112087610G
+ false | 7388428680384065704G
+ false | 8249030965139585917G
+ false | 837825985403119657G
+ false | 8505906760983331750G
+ false | 8674665223082153551G
+ false | 894385949183117216G
+ false | 898860202204764712G
+ false | 9768663798983814715G
+ false | 9828766684487745566G
+ false | 9908585559158765387G
+ false | 9956202364908137547G
+ }
+
+ def "test sampling all: #traceId"() {
+ given:
+ KnuthSampler sampler = new KnuthSampler(1)
+ DDSpan span = Mock(DDSpan) {
+ getTraceId() >> traceId
+ }
+
+ when:
+ def sampled = sampler.sample(span)
+
+ then:
+ sampled == expected
+
+ // These values are repeated from the "known values test"
+ // It is an arbitrary subset of all possible traceIds
+ where:
+ expected | traceId
+ true | 10428415896243638596G
+ true | 11199607447739267382G
+ true | 11273630029763932141G
+ true | 11407674492757219439G
+ true | 11792151447964398879G
+ true | 12432680895096110463G
+ true | 13126262220165910460G
+ true | 13174268766980400525G
+ true | 15505210698284655633G
+ true | 15649472107743074779G
+ true | 17204678798284737396G
+ true | 17344948852394588913G
+ true | 17496662575514578077G
+ true | 18252401681137062077G
+ true | 18317291550776694829G
+ true | 1874068156324778273G
+ true | 1905388747193831650G
+ true | 2202916659517317514G
+ true | 2227583514184312746G
+ true | 2338498362660772719G
+ true | 2781055864473387780G
+ true | 3328451335138149956G
+ true | 3337066551442961397G
+ true | 3409814636252858217G
+ true | 3510942875414458836G
+ true | 3784560248718450071G
+ true | 4751997750760398084G
+ true | 4831389563158288344G
+ true | 4990765271833742716G
+ true | 5089134323978233018G
+ true | 5199948958991797301G
+ true | 5577006791947779410G
+ true | 5600924393587988459G
+ true | 5793183108815074904G
+ true | 6263450610539110790G
+ true | 6382800227808658932G
+ true | 6651414131918424343G
+ true | 6842348953158377901G
+ true | 6941261091797652072G
+ true | 7273596521315663110G
+ true | 7504504064263669287G
+ true | 788787457839692041G
+ true | 7955079406183515637G
+ true | 8549944162621642512G
+ true | 8603989663476771718G
+ true | 8807817071862113702G
+ true | 9010467728050264449G
+ true | 10667007354186551956G
+ true | 10683692646452562431G
+ true | 10821471013040158923G
+ true | 10950412492527322440G
+ true | 11239168150708129139G
+ true | 1169089424364679180G
+ true | 11818186001859264308G
+ true | 11833901312327420776G
+ true | 11926759511765359899G
+ true | 11926873763676642186G
+ true | 11963748953446345529G
+ true | 11998794077335055257G
+ true | 12096659438561119542G
+ true | 12156940908066221323G
+ true | 12947799971452915849G
+ true | 13260572831089785859G
+ true | 13771804148684671731G
+ true | 14117161486975057715G
+ true | 14242321332569825828G
+ true | 14486903973548550719G
+ true | 14967026985784794439G
+ true | 15213854965919594827G
+ true | 15352856648520921629G
+ true | 15399114114227588261G
+ true | 15595235597337683065G
+ true | 16194613440650274502G
+ true | 1687184559264975024G
+ true | 17490665426807838719G
+ true | 18218388313430417611G
+ true | 2601737961087659062G
+ true | 261049867304784443G
+ true | 2740103009342231109G
+ true | 2970700287221458280G
+ true | 3916589616287113937G
+ true | 4324745483838182873G
+ true | 4937104021912138218G
+ true | 5486140987150761883G
+ true | 5944830206637008055G
+ true | 6296367092202729479G
+ true | 6334824724549167320G
+ true | 6556961545928831643G
+ true | 6735196588112087610G
+ true | 7388428680384065704G
+ true | 8249030965139585917G
+ true | 837825985403119657G
+ true | 8505906760983331750G
+ true | 8674665223082153551G
+ true | 894385949183117216G
+ true | 898860202204764712G
+ true | 9768663798983814715G
+ true | 9828766684487745566G
+ true | 9908585559158765387G
+ true | 9956202364908137547G
+ }
+}

Change sampling to use knuth algorithm