t-percentile

    1.0.0 • Public • Published

    Percentile

    Build Status Coverage Status

    Percentile is a frequently-used metrics in cases like analyzing service response time, where we are specifically interested in those edge cases that response in a significant time. In the real world, there are always tremendous data/logs/files to be analyzed which makes it impossible to load the whole data into system to process and calculate percentile in the [traditional way](Percentile - Wikipedia). Instead, we need an algorithm that can calculate percentile on stream data with limited CPU and RAM consuming, but also trade the accuracy and get an approximate result with an acceptable deviation. There are already many algorithm to handle percentile calculation on stream data, e.g. HdrHistogram , GK, CKMS, T-Digest.

    With the inspiration of the [Prometheus node client](GitHub - siimon/prom-client: Prometheus client for node.js) I have implemented the percentile library based on T-Digest algorithm which also support window buckets, that in most cases we are not only interested in the percentile of overall data but the most recent ones. In the worst case, T-Digest would have a time complexity at O(nlogn) while the memory usage is related to the compression which by default is 100, the number of nodes in T-Digest is limited within 20 * compression, giving that one node is occupying approximate 32 byte, in theory the worst case would need 64KB.

    References:

    How to use

    const { Percentile } = require('t-percentile');
     
    // Init single bucket instance
    const p = new Percentile();
     
    // Init multi bucket instance with parameters:
    // windowLiveTimeMS - the TTL of data in a window bucket, in milliSecond
    // bucketsNum - number of window buckets
    const wp = new Percentile(1000, 10);
     
    // Push data
    for (let i = 0; i < 10000; i++) {
      p.push(i);
      wp.push(i);
    }
    p.compress();
    wp.compress();
     
    console.log(p.percentile(0.9));
    console.log(wp.percentile(0.9));

    How to test

    yarn
    yarn test
    

    License

    Install

    npm i t-percentile

    DownloadsWeekly Downloads

    2

    Version

    1.0.0

    License

    MIT

    Unpacked Size

    9.39 kB

    Total Files

    8

    Last publish

    Collaborators

    • ccharlieli