toolkit/components/utils/Sampling.sys.mjs

   1 /* This Source Code Form is subject to the terms of the Mozilla Public
   2  * License, v. 2.0. If a copy of the MPL was not distributed with this
   3  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   4
   5 const hashBits = 48;
   6 const hashLength = hashBits / 4; // each hexadecimal digit represents 4 bits
   7 const hashMultiplier = Math.pow(2, hashBits) - 1;
   8
   9 export var Sampling = {
  10   /**
  11    * Map from the range [0, 1] to [0, 2^48].
  12    * @param  {number} frac A float from 0.0 to 1.0.
  13    * @return {string} A 48 bit number represented in hex, padded to 12 characters.
  14    */
  15   fractionToKey(frac) {
  16     if (frac < 0 || frac > 1) {
  17       throw new Error(`frac must be between 0 and 1 inclusive (got ${frac})`);
  18     }
  19
  20     return Math.floor(frac * hashMultiplier)
  21       .toString(16)
  22       .padStart(hashLength, "0");
  23   },
  24
  25   /**
  26    * @param {ArrayBuffer} buffer Data to convert
  27    * @returns {String}    `buffer`'s content, converted to a hexadecimal string.
  28    */
  29   bufferToHex(buffer) {
  30     const hexCodes = [];
  31     const view = new DataView(buffer);
  32     for (let i = 0; i < view.byteLength; i += 4) {
  33       // Using getUint32 reduces the number of iterations needed (we process 4 bytes each time)
  34       const value = view.getUint32(i);
  35       // toString(16) will give the hex representation of the number without padding
  36       hexCodes.push(value.toString(16).padStart(8, "0"));
  37     }
  38
  39     // Join all the hex strings into one
  40     return hexCodes.join("");
  41   },
  42
  43   /**
  44    * Check if an input hash is contained in a bucket range.
  45    *
  46    * isHashInBucket(fractionToKey(0.5), 3, 6, 10) -> returns true
  47    *
  48    *              minBucket
  49    *              |     hash
  50    *              v     v
  51    *    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  52    *                       ^
  53    *                       maxBucket
  54    *
  55    * @param inputHash {String}
  56    * @param minBucket {int} The lower boundary, inclusive, of the range to check.
  57    * @param maxBucket {int} The upper boundary, exclusive, of the range to check.
  58    * @param bucketCount {int} The total number of buckets. Should be greater than
  59    *                          or equal to maxBucket.
  60    */
  61   isHashInBucket(inputHash, minBucket, maxBucket, bucketCount) {
  62     const minHash = Sampling.fractionToKey(minBucket / bucketCount);
  63     const maxHash = Sampling.fractionToKey(maxBucket / bucketCount);
  64     return minHash <= inputHash && inputHash < maxHash;
  65   },
  66
  67   /**
  68    * @promise A hash of `data`, truncated to the 12 most significant characters.
  69    */
  70   async truncatedHash(data) {
  71     const hasher = crypto.subtle;
  72     const input = new TextEncoder().encode(JSON.stringify(data));
  73     const hash = await hasher.digest("SHA-256", input);
  74     // truncate hash to 12 characters (2^48), because the full hash is larger
  75     // than JS can meaningfully represent as a number.
  76     return Sampling.bufferToHex(hash).slice(0, 12);
  77   },
  78
  79   /**
  80    * Sample by splitting the input into two buckets, one with a size (rate) and
  81    * another with a size (1.0 - rate), and then check if the input's hash falls
  82    * into the first bucket.
  83    *
  84    * @param    {object}  input Input to hash to determine the sample.
  85    * @param    {Number}  rate  Number between 0.0 and 1.0 to sample at. A value of
  86    *                           0.25 returns true 25% of the time.
  87    * @promises {boolean} True if the input is in the sample.
  88    */
  89   async stableSample(input, rate) {
  90     const inputHash = await Sampling.truncatedHash(input);
  91     const samplePoint = Sampling.fractionToKey(rate);
  92
  93     return inputHash < samplePoint;
  94   },
  95
  96   /**
  97    * Sample by splitting the input space into a series of buckets, and checking
  98    * if the given input is in a range of buckets.
  99    *
 100    * The range to check is defined by a start point and length, and can wrap
 101    * around the input space. For example, if there are 100 buckets, and we ask to
 102    * check 50 buckets starting from bucket 70, then buckets 70-99 and 0-19 will
 103    * be checked.
 104    *
 105    * @param {object}     input Input to hash to determine the matching bucket.
 106    * @param {integer}    start Index of the bucket to start checking.
 107    * @param {integer}    count Number of buckets to check.
 108    * @param {integer}    total Total number of buckets to group inputs into.
 109    * @promises {boolean} True if the given input is within the range of buckets
 110    *                     we're checking. */
 111   async bucketSample(input, start, count, total) {
 112     const inputHash = await Sampling.truncatedHash(input);
 113     const wrappedStart = start % total;
 114     const end = wrappedStart + count;
 115
 116     // If the range we're testing wraps, we have to check two ranges: from start
 117     // to max, and from min to end.
 118     if (end > total) {
 119       return (
 120         Sampling.isHashInBucket(inputHash, 0, end % total, total) ||
 121         Sampling.isHashInBucket(inputHash, wrappedStart, total, total)
 122       );
 123     }
 124
 125     return Sampling.isHashInBucket(inputHash, wrappedStart, end, total);
 126   },
 127
 128   /**
 129    * Sample over a list of ratios such that, over the input space, each ratio
 130    * has a number of matches in correct proportion to the other ratios.
 131    *
 132    * For example, given the ratios:
 133    *
 134    * [1, 2, 3, 4]
 135    *
 136    * 10% of all inputs will return 0, 20% of all inputs will return 1, 30% will
 137    * return 2, and 40% will return 3. You can determine the percent of inputs
 138    * that will return an index by dividing the ratio by the sum of all ratios
 139    * passed in. In the case above, 4 / (1 + 2 + 3 + 4) == 0.4, or 40% of the
 140    * inputs.
 141    *
 142    * @param {object} input
 143    * @param {Array<integer>} ratios
 144    * @promises {integer}
 145    *   Index of the ratio that matched the input
 146    * @rejects {Error}
 147    *   If the list of ratios doesn't have at least one element
 148    */
 149   async ratioSample(input, ratios) {
 150     if (ratios.length < 1) {
 151       throw new Error(
 152         `ratios must be at least 1 element long (got length: ${ratios.length})`
 153       );
 154     }
 155
 156     const inputHash = await Sampling.truncatedHash(input);
 157     const ratioTotal = ratios.reduce((acc, ratio) => acc + ratio);
 158
 159     let samplePoint = 0;
 160     for (let k = 0; k < ratios.length - 1; k++) {
 161       samplePoint += ratios[k];
 162       if (inputHash <= Sampling.fractionToKey(samplePoint / ratioTotal)) {
 163         return k;
 164       }
 165     }
 166
 167     // No need to check the last bucket if the others didn't match.
 168     return ratios.length - 1;
 169   },
 170 };