Switch random ID generation to normal (not crypto) random

[anuraaga]

I randomly noticed that trace and span IDs in this SDK use crypto, so they are secure random numbers. I quickly checked other languages, Java, Go, and Python, and they all seem to use normal random numbers. I know in Java the cost of secure random is very high and could easily impose a significant CPU cost on an app. I'm not sure about JS, but for consistency anyways, does it make sense to switch to normal random numbers here?

[dyladan]

Do you have a suggested "normal" method? I assume you are talking about using Math.random() multiple times to generate the required key length?

[anuraaga]

Yeah I think it's calling it twice for 8 bytes for span id, four times for 16 bytes for trace id and concatenating the hex encode. It's not as simple as calling crypto but will make it consistent with the other SDKs.

[dyladan]

Did some quick benchmarks:

const Benchmark = require('benchmark');
const benchmarks = require('beautify-benchmark');
const suite = new Benchmark.Suite();

const crypto = require("crypto");

const SHARED_BUFFER = Buffer.allocUnsafe(16);

suite
  .add('crypto', function () {
    crypto.randomBytes(16).toString('hex')
  })
  .add('math concatenation', function () {
    Math.random().toString(16).substr(2, 10) + Math.random().toString(16).substr(2, 10) + Math.random().toString(16).substr(2, 10) + Math.random().toString(16).substr(2, 10);
  })
  .add('buffer math inline', function () {
    Buffer.from([
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
      Math.floor(Math.random() * 256),
    ]).toString('hex')
  })
  .add('buffer math map', function () {
    Buffer.from(Array(16).fill(0).map(_ => Math.floor(Math.random() * 256)).toString('hex'));
  })
  .add('buffer math loop', function () {
    const arr = [];
    
    for (let i = 0; i < 16; i++) {
      arr[i] = Math.floor(Math.random() * 256);
    }
    Buffer.from(arr).toString('hex');
  })
  .add('buffer math loop no arr', function () {
    const buf = Buffer.allocUnsafe(16);
    
    for (let i = 0; i < 16; i++) {
      buf[i] = Math.floor(Math.random() * 256);
    }
    buf.toString('hex');
  })
  .add('buffer math loop no arr no alloc', function () {    
    for (let i = 0; i < 16; i++) {
      SHARED_BUFFER[i] = Math.floor(Math.random() * 256);
    }
    SHARED_BUFFER.slice(0, 16).toString('hex');
  })
  .add('direct string gen', function () {
    const charCodes = Array(32);
    
    for (let i = 0; i < 32; i++) {
      charCodes[i] = (Math.floor(Math.random() * 16)) + 48;
      // if out of 0-9 range, add 49 to get into lowercase alpha range
      if (charCodes[i] >= 58) { 
        charCodes[i] += 39;
      }
    }
    String.fromCharCode.apply(null, charCodes)
  })
  // add listeners
  .on('cycle', function (event) {
    benchmarks.add(event.target);
  })
  .on('complete', function () {
    benchmarks.log();
    console.log('Fastest is ' + this.filter('fastest').map('name'));
  })
  .run();

output:

  crypto                           x   423,835 ops/sec ±1.09% (90 runs sampled)
  math concatenation               x   952,891 ops/sec ±0.87% (92 runs sampled)
  buffer math inline               x 2,247,226 ops/sec ±0.79% (90 runs sampled)
  buffer math map                  x   771,429 ops/sec ±0.70% (91 runs sampled)
  buffer math loop                 x 2,118,362 ops/sec ±0.90% (93 runs sampled)
  buffer math loop no arr          x 2,512,774 ops/sec ±0.81% (93 runs sampled)
  buffer math loop no arr no alloc x 2,813,994 ops/sec ±0.68% (91 runs sampled)
  direct string gen                x 1,540,517 ops/sec ±0.85% (88 runs sampled)
Fastest is buffer math loop no arr no alloc

edit: added case: buffer math loop
edit: added case: buffer math loop no arr
edit: added case: direct string gen
edit: formatting
edit: added case: buffer math loop no arr no alloc

[dyladan]

Based on this, I would say the cost comes first from the use of cryptographic randomness, second from toString. The "buffer math inline" case seems to be faster than the "math" case simply because it only calls toString once. Attempting to use array methods to make the code terser seems to have a nontrivial performance penalty which nearly nullifies the benefit of using the Math module.

[anuraaga]

Thanks for the benches! One last point to check might be manually hex encoding instead of using a built in one. We have it in browser, and it wouldn't be that hard to adapt to operate on ints returned by Random instead of a byte array

opentelemetry-js/packages/opentelemetry-core/src/platform/browser/id.ts

Line 43 in e9b2cf9

const chars: number[] = new Array(byteArray.length * 2);

[anuraaga]

Also for reference is the Java code which may be relatively simple to port to js

https://github.com/open-telemetry/opentelemetry-java/blob/6ca3d1deaf9687e08bad9969fa779b0cb92fb235/api/src/main/java/io/opentelemetry/trace/BigendianEncoding.java#L120

[dyladan]

Thanks for the benches! One last point to check might be manually hex encoding instead of using a built in one. We have it in browser, and it wouldn't be that hard to adapt to operate on ints returned by Random instead of a byte array

opentelemetry-js/packages/opentelemetry-core/src/platform/browser/id.ts

Line 43 in e9b2cf9

const chars: number[] = new Array(byteArray.length * 2);

In my experience, nothing is ever faster than the built in buffer hex encoding in node, which is implemented in native code. Even if we skip the byte array step and jump straight to string conversion (see case "direct string gen"), it is still slower than the built in hex encoding.

[dyladan]

Based on this research, I would suggest we do "buffer math loop no arr no alloc" for nodejs, and "direct string gen" for web.