Core component to compute attribute sets needed

[jmacd]

Is your feature request related to a problem? Please describe.

It is common to aggregate telemetry signals by attribute sets. It requires custom code to do this with pdata objects, which leads to inefficiency and repetition in our code.

As a concrete example, note that the current core component batchprocessor makes no effort to combine similar containers in the OTLP hierarchy. For example, when two scopes are identical it should be possible to combine the entries and avoid repeating the scope details, but for this we need a helper library. Compression performance would improve with better batching, but it takes a lot of code to achieve this and we should standardize this code as part of the collector core.

Describe the solution you'd like
This is a complicated question because there are heavy performance costs associated with the decisions we make here. In early prototypes for OTel-Go metrics, the https://github.com/open-telemetry/opentelemetry-go/blob/main/attribute/set.go package was created. This package is one ideal solution to the problem, except that it takes OTel-Go attribute lists as input instead of pcommon.Map objects. We need a solution that works for pcommon.Map without requiring error-prone conversion to []attribute.KeyValue from the OTel-Go library.

The cost of attribute set construction is expensive--no matter what. Frequently, we see code written that attempts to avoid a memory allocation by first hashing the set of attributes. This may require sorting the attributes, which also can trigger memory allocation. There is a question of whether the user of a hashing approach will also check for hash collisions, because checking hash collisions implies the use of memory to maintain the exact set of attributes.

In my own code, when I want to optimize the cost of attribute processing I arrange to use OTel-Go's attribute.NewSetWithSortable() because it avoids all but one obligatory allocation associated with constructing a flat set of attributes. However, even that one allocation can be too much in a fast code path, so for the Lightstep metrics SDK I've written an optimization to use a hash function. As discussed above, a hash function alone does not give as much optimization as some users want if you also implement collision detection. To be very clear, the cost benefit of hashing is limited by the impact of collision detection, so we should survey existing services and libraries to see how they treat this. For the Lightstep metrics SDK, I gave the user an option to ignore collisions. (Lightstep chooses to run with this option.)

I do not believe we should force users to ignore collisions, it should be a choice. The Prometheus server, when it hashes, will check collisions. Here's a code snippet:

// seriesHashmap is a simple hashmap for memSeries by their label set.
// It is built on top of a regular hashmap and holds a slice of series to
// resolve hash collisions. Its methods require the hash to be submitted
// with the label set to avoid re-computing hash throughout the code.
type seriesHashmap map[uint64][]*memSeries

func (m seriesHashmap) Get(hash uint64, lset labels.Labels) *memSeries {
	for _, s := range m[hash] {
		if labels.Equal(s.lset, lset) {
			return s
		}
	}
	return nil
}

func (m seriesHashmap) Set(hash uint64, s *memSeries) {
	seriesSet := m[hash]
	for i, prev := range seriesSet {
		if labels.Equal(prev.lset, s.lset) {
			seriesSet[i] = s
			return
		}
	}
	m[hash] = append(seriesSet, s)
}

I won't furnish a link to the Prometheus Golang client, but I've checked and it does the same.

Summarizing, this is a complex issue. The map key I would suggest we standardize is one that contains both a hash value and an optional slice of exact values for checking collisions. It is impossible to discuss this further without looking at performance and code complexity. My own implementation is heavily optimized and supports the IgnoreCollisions option, but it is also very tricky. If we're going to play these tricks, we should place them in a standard library for wide use.

Describe alternatives you've considered

@bogdandrutu promoted this library: https://github.com/open-telemetry/opentelemetry-collector-contrib/blob/main/pkg/pdatautil/hash.go

Additional context

I've explained why the API behind https://github.com/open-telemetry/opentelemetry-go/blob/main/attribute/set.go is too expensive for a fast code path, so that I think hashing makes sense, but with the option to ignore collisions.