API design: SpanBuilder::attributes

[LukeMathWalker]

Attributes attached to a SpanBuilder are currently stored as a Vec<opentelemetry::KeyValue> - see docs.

This makes it impossible to access the value attached to a specific key or to verify that an attribute is present in O(1). It always take O(n), where n is the number of attributes - this can be significant.

Why was a Vec<KeyValue> chosen over a HashMap<Key, Value>?
I see it gets later processed into an EvictedHashMap when SpanBuilder gets converted into a Span 🤔

[TommyCpp]

SpanBuilder is more of a tempory object to hold configurations before span starts. I think the design choice is more of the it's easier to construct a Vec compared with HashMap(vec![...] vs HashMap::from([...])). And before rust-lang/rust#84111 it's even harder to initialize a Hashmap.

I image the use case here is to tweak the attributes from a library? With the new Hashmap API maybe we can change it to accept a iterator of the Key value pairs.

[LukeMathWalker]

That's exactly the use case: insertion of new attributes (based on the values of existing ones) and manipulation of existing attributes.

This is currently done inside a custom tracing layer.

[TommyCpp]

I think it's a reasonable ask from library developers. I guess another problem using HashMap is it doesn't preserve the order of attributes, which is later used to decide which attributes need to be dropped if the number of the attributes is exceed the limit.
max_attributes_per_span
The limit on the attributes is configurable in the span builder so we won't be able to evict attributes before building the spans.

If we want to use HashMap inside the SpanBuilder we need to figure out a different method to evict the attributes.
or we use a hashmap + double linked list of nodes to have O(1) insert, delete, and query.

[LukeMathWalker]

We could use indexmap if we need to preserve insertion order for deciding what should be evicted later on.

[djc]

Sounds like we should maybe use some kind of LRU map?

[TommyCpp]

We could use indexmap if we need to preserve insertion order for deciding what should be evicted later on.

I think indexmap does not guarantee the order after removal but I think it is worth a try.

Sounds like we should maybe use some kind of LRU map?

The tricky thing here is in common use cases users shouldn't read attributes in span builder much before building & evicting.

[LukeMathWalker]

It is also true that by postponing eviction we might be exposing users to unnecessary memory pressure - i.e. pushing way more attributes into SpanBuilder than what is going to fit into the specified upper limit when a Span is built.

[TommyCpp]

On the other hand, if we evict the attributes in SpanBuilder then there is no guarantee the attributes library authors care for will remain.

Let's say you want to check if there is a service_name attribute and if there isn't insert one. If SpanBuilder doesn't contain all attributes then it's hard to tell if service_name is not provided by users or it was evicted.

[LukeMathWalker]

I agree with your argument @TommyCpp.
I'll work on a PR to introduce indexmap then!

[LukeMathWalker]

I have a sketch in #799 👍🏻