Dynamically convert the positive/negative stores to use dense/sparse encoding

[srikanthccv]

It's waste space and slow to always use dense encoding.

Show example

{
  "resourceMetrics": [
    {
      "resource": {
        "attributes": []
      },
      "scopeMetrics": [
        {
          "scope": {},
          "metrics": [
            {
              "name": "metric_name",
              "exponentialHistogram": {
                "dataPoints": [
                  {
                    "attributes": [
                      {
                        "key": "key",
                        "value": {
                          "stringValue": "value"
                        }
                      },
                    ],
                    "startTimeUnixNano": "1759836598724885410",
                    "timeUnixNano": "1759836613724140231",
                    "count": "2",
                    "sum": 10,
                    "scale": 8,
                    "positive": {
                      "offset": 511,
                      "bucketCounts": [
                        "1",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "0",
                        "1"
                      ]
                    },
                    "negative": {},
                    "min": 4,
                    "max": 6
                  }
                ],
                "aggregationTemporality": 1
              }
            }
          ]
        }
      ]
    }
  ]
}

[srikanthccv]

@nikhilmantri0902, in your local setup

1. enable the exponential histogram for span metrics processor https://github.com/SigNoz/signoz-otel-collector/blob/main/processor/signozspanmetricsprocessor/config.go#L92
2. enable the exponential histogram for the clickhouse metrics exporter https://github.com/SigNoz/signoz-otel-collector/blob/main/exporter/signozclickhousemetrics/config.go#L19

The above two steps will start writing the sketches to database

3. Add the file exporter to the metrics pipeline https://github.com/open-telemetry/opentelemetry-collector-contrib/tree/main/exporter/fileexporter, this will enable you to see the json representation of the metric data point

Review he datapoint representation, you may see a lots of zero values in the bucket counts as shared in the issue description. When we find a representation of histogram with a lot of zeros, instead directly writing it we should convert it to sparse encoded histogram and write it

Why are we doing this exercise? we want our APM latency calculation to be as close to if it were from the raw data

To go about it there are number of ways

• use the raw data, of course.
  • as we discussed, it has number of cons, 1. need to store enormous amounts of data 2. computationally expensive at high scale 3. won't work if the sampling is enabled
• explicit bucket histograms
  • buckets need to specified before hand, leading to sub-optimal experience

This leaves us with the exp hist but we need to test it at scale and see how does it perform. This exercise will get you more familiar than the theory you read.

The expected outcome, is a solution that looks at the buckets counts and decided if it should be written as is or should it be converted.

[nikhilmantri0902]

Solution Discussion 1:
Using nonzero to totalBuckets ratio

1. We will to define one flag called exp_hist_sparse_threshold ( range 0 to 1 ) in signozclickhousemetrics exporter config. This will serve as the threshold above which dense encoding is to be used.
2. Additonally we can define one more flag called exp_hist_sparse_min_len for minimum number of total buckets above which sparse encoding can be considered.
3. In func (c *clickhouseMetricsExporter) processExponentialHistogram(b *batch, metric pmetric.Metric, env string, resourceFingerprint, scopeFingerprint *pkgfingerprint.Fingerprint) we currently define exponential histograms as dense arrays as belows:

	toStore := func(buckets pmetric.ExponentialHistogramDataPointBuckets) *chproto.Store {
		bincounts := make([]float64, 0, buckets.BucketCounts().Len())
		for _, bucket := range buckets.BucketCounts().AsRaw() {
			bincounts = append(bincounts, float64(bucket))
		}

		store := &chproto.Store{
			ContiguousBinIndexOffset: int32(buckets.Offset()),
			ContiguousBinCounts:      bincounts,
		}
		return store
	}

The chproto.Store allows us to define a map of index to value also which we can see below. This will be populated for the cases where we have decided to use sparse encodings based on thresholds above.

The toStore function will be modified to first calculate the number of nonZero buckets and totalBuckets in the loop above. Then we can define useSparse boolean as follows:

useSparse := false
	if totalBuckets >= c.cfg.ExpHistSparseMinLen {
		density := float64(nonZeroCount) / float64(totalBuckets)
		if density <= c.cfg.ExpHistSparseThreshold {
			useSparse = true
		}
	}

if useSparse: then we can do:

binCounts := map[int]float64
for i, count := range rawBuckets {
			if count > 0 {
				binCounts[i] = count
			}
		}

and set binCounts as the value in chproto.Store instead of ContiguousBinCounts.

4. The thresholds needs to be chosen critically to avoid unnecessary sparse encoding when high non-zero bucket counts and avoid dense encoding when low non-zero bucket counts.

Pros this Solution:
Sparse histograms save significant space. Smaller sketches mean faster inserts.

Cons of this Solution:
Must iterate buckets twice—once to count non-zeros, once to build the store. For dense choice, this is wasted work. Maps also have a memory overhead. For moderately sparse data, map size might be larger than dense array ( this needs to be checked for limits ), so both in memory usage and clickhouse memory usage might increase.

[nikhilmantri0902]

Solution 2:
Using direct size estimates.

Inside toStore subfunction specified in solution 1, we can do direct comparison between size of a slice and size of a map and choose whichever is smaller.

toStore := func(buckets pmetric.ExponentialHistogramDataPointBuckets) *chproto.Store {
		bincounts := make([]float64, 0, buckets.BucketCounts().Len())
                 binMap :=. make(map[int32]float64, 0)                  

		for i, bucket := range buckets.BucketCounts().AsRaw() {
			bincounts = append(bincounts, float64(bucket))
                         if float64(bucket) > 0{
                                binMap[i] = float64(bucket)
                         }
		}
                
                 useSparse := getSizeOfMap(binMap) < getSizeofSlice(bincounts)
                
                 
		store := &chproto.Store{
                          // if useSparse then add binmap here, else keep ContiguousBinCounts. 
		}
		return store
	}

We can create helper functions getSizeOfMap ( calculates the estimated memory size for a map[int32]float64 -
returns the map header + data + bucket overhead) and getSizeofSlice ( Calculates the exact memory size for a []float64 slice - returns the slice header + underlying array size) that will help us estimate the size of both these data structures for the real set of values.

Pros: This is very accurate size based selection.
Cons: Higher CPU in computing sizes. Higher server memory usage.