Repository: open-telemetry/opentelemetry-go
Pull request #1931 (2021-05-19 21:29:49)

Refactor Tracestate
The main purpose of these changes is to restructure the `TraceState` type around a list of `string`s. The methods have all been updated to accept key/value values as `string` instead of `attribute.KeyValue`.

- Move `TraceStateFromKeyValues` from the `trace` API to the `oteltest` package.
- Update `TraceState.MarshalJSON` to return the tracestate string.
- Move tracestate header parsing logic to the tracestate.go file in the `trace` package.
- Move the `TraceState` type and associated code to its own file.
- Correct the tracestate list regex to allow leading and trailing whitespace in accordance with the W3C Trace Context specification.
- Add a `ParseTraceState` function that attempts to decode a TraceState from a passed string
- Change the `TraceState.Delete` method to not return an error. The only time it would return an error is when the user passed an invalid key. Now it "handles" this error by not deleting the member associated with the invalid key (something that can never be in a `TraceState`) and just returns a copy of the `TraceState`.
- Remove the `TraceState.IsEmpty` method in favor of the added `TraceState.Len` method. This new method has a more diverse use and solves the same use case the original did.

Part of #1539 

codecov[bot]: # [Codecov](https://codecov.io/gh/open-telemetry/opentelemetry-go/pull/1931?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=open-telemetry) Report
> Merging [#1931](https://codecov.io/gh/open-telemetry/opentelemetry-go/pull/1931?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=open-telemetry) (ecc481a) into [main](https://codecov.io/gh/open-telemetry/opentelemetry-go/commit/ab5facb36cc55e2a29e9479356ae072aa3fba58a?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=open-telemetry) (ab5facb) will **increase** coverage by `0.0%`.
> The diff coverage is `100.0%`.

[![Impacted file tree graph](https://codecov.io/gh/open-telemetry/opentelemetry-go/pull/1931/graphs/tree.svg?width=650&height=150&src=pr&token=8efTmh4kvf&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=open-telemetry)](https://codecov.io/gh/open-telemetry/opentelemetry-go/pull/1931?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=open-telemetry)

```diff
@@          Coverage Diff          @@
##            main   #1931   +/-   ##
=====================================
  Coverage   79.5%   79.6%           
=====================================
  Files        139     141    +2     
  Lines       7463    7471    +8     
=====================================
+ Hits        5937    5948   +11     
+ Misses      1278    1275    -3     
  Partials     248     248           
```


| [Impacted Files](https://codecov.io/gh/open-telemetry/opentelemetry-go/pull/1931?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=open-telemetry) | Coverage Δ | |
|---|---|---|
| [trace/trace.go](https://codecov.io/gh/open-telemetry/opentelemetry-go/pull/1931/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=open-telemetry#diff-dHJhY2UvdHJhY2UuZ28=) | `83.6% <ø> (-3.2%)` | :arrow_down: |
| [oteltest/tracestate.go](https://codecov.io/gh/open-telemetry/opentelemetry-go/pull/1931/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=open-telemetry#diff-b3RlbHRlc3QvdHJhY2VzdGF0ZS5nbw==) | `100.0% <100.0%> (ø)` | |
| [propagation/trace\_context.go](https://codecov.io/gh/open-telemetry/opentelemetry-go/pull/1931/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=open-telemetry#diff-cHJvcGFnYXRpb24vdHJhY2VfY29udGV4dC5nbw==) | `64.9% <100.0%> (-4.8%)` | :arrow_down: |
| [trace/tracestate.go](https://codecov.io/gh/open-telemetry/opentelemetry-go/pull/1931/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=open-telemetry#diff-dHJhY2UvdHJhY2VzdGF0ZS5nbw==) | `100.0% <100.0%> (ø)` | |

MrAlias: One thing I considered when making these changes, and am still not sure if it would make this better, is to move the trace state stuff into it's own package. I would rename the `TraceState` type to `List` to match the W3C specification and change `ParseTraceState` to just `Parse`. That would mean calling `tracestate.Parse` would return a `tracestate.List`. We could even export the `Member` type and have it be structured in a way, [similar to this](https://github.com/iredelmeier/tracecontext.go/blob/1757c391b1acf4147823503f13e003115ea4e5df/tracestate/package.go#L29-L37) but made static, that it would contain vendor and tenant information instead of just a `Key`.

The issues I was not able to resolve for this approach were:

- Where should the `tracestate` package live?
- What about the rest of the Trace Context specification? This would seem to be an incomplete implementation of the specification.

Patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index c59e6c59..905eb249 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -26,6 +26,10 @@ This project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.htm
   This type can be used as a testing replacement for the `SpanSnapshot` that was removed from the `go.opentelemetry.io/otel/sdk/trace` package. (#1873)
 - Adds support for scheme in `OTEL_EXPORTER_OTLP_ENDPOINT` according to the spec. (#1886)
 - An example of using OpenTelemetry Go as a trace context forwarder. (#1912)
+- `ParseTraceState` is added to the `go.opentelemetry.io/otel/trace` package.
+  It can be used to decode a `TraceState` from a `tracestate` header string value. (#1937)
+- The `Len` method is added to the `TraceState` type in the `go.opentelemetry.io/otel/trace` package.
+  This method returns the number of list-members the `TraceState` holds. (#1937)
 
 ### Changed
 
@@ -47,6 +51,14 @@ This project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.htm
 - The `"go.opentelemetry.io/otel".Tracer` function now accepts tracer options. (#1902)
 - Move the `go.opentelemetry.io/otel/unit` package to `go.opentelemetry.io/otel/metric/unit`. (#1903)
 - Refactor option types according to the contribution style guide. (#1882)
+- Move the `go.opentelemetry.io/otel/trace.TraceStateFromKeyValues` function to the `go.opentelemetry.io/otel/oteltest` package.
+  This function is preserved for testing purposes where it may be useful to create a `TraceState` from `attribute.KeyValue`s, but it is not intended for production use.
+  The new `ParseTraceState` function should be used to create a `TraceState`. (#1931)
+- The `MarshalJSON` method of the `go.opentelemetry.io/otel/trace.TraceState` type is updated to marshal the type in to the string representation of the `TraceState`. (#1931)
+- The `TraceState.Delete` method from the `go.opentelemetry.io/otel/trace` package no longer returns an error in addition to a `TraceState`. (#1931)
+- The `Get` method of the `TraceState` type from the `go.opentelemetry.io/otel/trace` package has been updated to accept a `string` instead of an `attribute.Key` type. (#1931)
+- The `Insert` method of the `TraceState` type from the `go.opentelemetry.io/otel/trace` package has been updated to accept a pair of `string`s instead of an `attribute.KeyValue` type. (#1931)
+- The `Delete` method of the `TraceState` type from the `go.opentelemetry.io/otel/trace` package has been updated to accept a `string` instead of an `attribute.Key` type. (#1931)
 
 ### Deprecated
 
@@ -66,6 +78,7 @@ This project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.htm
   Using the same tracer that created a span introduces the error where an instrumentation library's `Tracer` is used by other code instead of their own.
   The `"go.opentelemetry.io/otel".Tracer` function or a `TracerProvider` should be used to acquire a library specific `Tracer` instead. (#1900)
 - The `http.url` attribute generated by `HTTPClientAttributesFromHTTPRequest` will no longer include username or password information. (#1919)
+- The `IsEmpty` method of the `TraceState` type in the `go.opentelemetry.io/otel/trace` package is removed in favor of using the added `TraceState.Len` method. (#1931)
 
 ### Fixed
 
@@ -73,6 +86,7 @@ This project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0.htm
 - The `Shutdown` method of the simple `SpanProcessor` in the `go.opentelemetry.io/otel/sdk/trace` package now honors the context deadline or cancellation. (#1616, #1856)
 - BatchSpanProcessor now drops span batches that failed to be exported. (#1860)
 - Use `http://localhost:14268/api/traces` as default Jaeger collector endpoint instead of `http://localhost:14250`. (#1898)
+- Allow trailing and leading whitespace in the parsing of a `tracestate` header. (#1931)
 
 ### Security
 
diff --git a/exporters/otlp/go.mod b/exporters/otlp/go.mod
index f96eb308..ce561507 100644
--- a/exporters/otlp/go.mod
+++ b/exporters/otlp/go.mod
@@ -13,6 +13,7 @@ require (
 	github.com/stretchr/testify v1.7.0
 	go.opentelemetry.io/otel v0.20.0
 	go.opentelemetry.io/otel/metric v0.20.0
+	go.opentelemetry.io/otel/oteltest v0.20.0
 	go.opentelemetry.io/otel/sdk v0.20.0
 	go.opentelemetry.io/otel/sdk/export/metric v0.20.0
 	go.opentelemetry.io/otel/sdk/metric v0.20.0
diff --git a/exporters/stdout/go.mod b/exporters/stdout/go.mod
index d64847ec..0c98f2b7 100644
--- a/exporters/stdout/go.mod
+++ b/exporters/stdout/go.mod
@@ -11,6 +11,7 @@ require (
 	github.com/stretchr/testify v1.7.0
 	go.opentelemetry.io/otel v0.20.0
 	go.opentelemetry.io/otel/metric v0.20.0
+	go.opentelemetry.io/otel/oteltest v0.20.0
 	go.opentelemetry.io/otel/sdk v0.20.0
 	go.opentelemetry.io/otel/sdk/export/metric v0.20.0
 	go.opentelemetry.io/otel/sdk/metric v0.20.0
diff --git a/propagation/trace_context.go b/propagation/trace_context.go
index 82de416b..445f81f7 100644
--- a/propagation/trace_context.go
+++ b/propagation/trace_context.go
@@ -19,9 +19,7 @@ import (
 	"encoding/hex"
 	"fmt"
 	"regexp"
-	"strings"
 
-	"go.opentelemetry.io/otel/attribute"
 	"go.opentelemetry.io/otel/trace"
 )
 
@@ -139,7 +137,10 @@ func (tc TraceContext) extract(carrier TextMapCarrier) trace.SpanContext {
 	// Clear all flags other than the trace-context supported sampling bit.
 	scc.TraceFlags = trace.TraceFlags(opts[0]) & trace.FlagsSampled
 
-	scc.TraceState = parseTraceState(carrier.Get(tracestateHeader))
+	// Ignore the error returned here. Failure to parse tracestate MUST NOT
+	// affect the parsing of traceparent according to the W3C tracecontext
+	// specification.
+	scc.TraceState, _ = trace.ParseTraceState(carrier.Get(tracestateHeader))
 	scc.Remote = true
 
 	sc := trace.NewSpanContext(scc)
@@ -154,25 +155,3 @@ func (tc TraceContext) extract(carrier TextMapCarrier) trace.SpanContext {
 func (tc TraceContext) Fields() []string {
 	return []string{traceparentHeader, tracestateHeader}
 }
-
-func parseTraceState(in string) trace.TraceState {
-	if in == "" {
-		return trace.TraceState{}
-	}
-
-	kvs := []attribute.KeyValue{}
-	for _, entry := range strings.Split(in, ",") {
-		parts := strings.SplitN(entry, "=", 2)
-		if len(parts) != 2 {
-			// Parse failure, abort!
-			return trace.TraceState{}
-		}
-		kvs = append(kvs, attribute.String(parts[0], parts[1]))
-	}
-
-	// Ignoring error here as "failure to parse tracestate MUST NOT
-	// affect the parsing of traceparent."
-	// https://www.w3.org/TR/trace-context/#tracestate-header
-	ts, _ := trace.TraceStateFromKeyValues(kvs...)
-	return ts
-}
diff --git a/trace/trace.go b/trace/trace.go
index 41a2e279..d368760e 100644
--- a/trace/trace.go
+++ b/trace/trace.go
@@ -19,8 +19,6 @@ import (
 	"context"
 	"encoding/hex"
 	"encoding/json"
-	"regexp"
-	"strings"
 
 	"go.opentelemetry.io/otel/attribute"
 	"go.opentelemetry.io/otel/codes"
@@ -38,18 +36,6 @@ const (
 
 	errInvalidSpanIDLength errorConst = "hex encoded span-id must have length equals to 16"
 	errNilSpanID           errorConst = "span-id can't be all zero"
-
-	// based on the W3C Trace Context specification, see https://www.w3.org/TR/trace-context-1/#tracestate-header
-	traceStateKeyFormat                      = `[a-z][_0-9a-z\-\*\/]{0,255}`
-	traceStateKeyFormatWithMultiTenantVendor = `[a-z0-9][_0-9a-z\-\*\/]{0,240}@[a-z][_0-9a-z\-\*\/]{0,13}`
-	traceStateValueFormat                    = `[\x20-\x2b\x2d-\x3c\x3e-\x7e]{0,255}[\x21-\x2b\x2d-\x3c\x3e-\x7e]`
-
-	traceStateMaxListMembers = 32
-
-	errInvalidTraceStateKeyValue errorConst = "provided key or value is not valid according to the" +
-		" W3C Trace Context specification"
-	errInvalidTraceStateMembersNumber errorConst = "trace state would exceed the maximum limit of members (32)"
-	errInvalidTraceStateDuplicate     errorConst = "trace state key/value pairs with duplicate keys provided"
 )
 
 type errorConst string
@@ -165,153 +151,6 @@ func decodeHex(h string, b []byte) error {
 	return nil
 }
 
-// TraceState provides additional vendor-specific trace identification information
-// across different distributed tracing systems. It represents an immutable list consisting
-// of key/value pairs. There can be a maximum of 32 entries in the list.
-//
-// Key and value of each list member must be valid according to the W3C Trace Context specification
-// (see https://www.w3.org/TR/trace-context-1/#key and https://www.w3.org/TR/trace-context-1/#value
-// respectively).
-//
-// Trace state must be valid according to the W3C Trace Context specification at all times. All
-// mutating operations validate their input and, in case of valid parameters, return a new TraceState.
-type TraceState struct { //nolint:golint
-	// TODO @matej-g: Consider implementing this as attribute.Set, see
-	// comment https://github.com/open-telemetry/opentelemetry-go/pull/1340#discussion_r540599226
-	kvs []attribute.KeyValue
-}
-
-var _ json.Marshaler = TraceState{}
-var _ json.Marshaler = SpanContext{}
-
-var keyFormatRegExp = regexp.MustCompile(
-	`^((` + traceStateKeyFormat + `)|(` + traceStateKeyFormatWithMultiTenantVendor + `))$`,
-)
-var valueFormatRegExp = regexp.MustCompile(`^(` + traceStateValueFormat + `)$`)
-
-// MarshalJSON implements a custom marshal function to encode trace state.
-func (ts TraceState) MarshalJSON() ([]byte, error) {
-	return json.Marshal(ts.kvs)
-}
-
-// String returns trace state as a string valid according to the
-// W3C Trace Context specification.
-func (ts TraceState) String() string {
-	var sb strings.Builder
-
-	for i, kv := range ts.kvs {
-		sb.WriteString((string)(kv.Key))
-		sb.WriteByte('=')
-		sb.WriteString(kv.Value.Emit())
-
-		if i != len(ts.kvs)-1 {
-			sb.WriteByte(',')
-		}
-	}
-
-	return sb.String()
-}
-
-// Get returns a value for given key from the trace state.
-// If no key is found or provided key is invalid, returns an empty value.
-func (ts TraceState) Get(key attribute.Key) attribute.Value {
-	if !isTraceStateKeyValid(key) {
-		return attribute.Value{}
-	}
-
-	for _, kv := range ts.kvs {
-		if kv.Key == key {
-			return kv.Value
-		}
-	}
-
-	return attribute.Value{}
-}
-
-// Insert adds a new key/value, if one doesn't exists; otherwise updates the existing entry.
-// The new or updated entry is always inserted at the beginning of the TraceState, i.e.
-// on the left side, as per the W3C Trace Context specification requirement.
-func (ts TraceState) Insert(entry attribute.KeyValue) (TraceState, error) {
-	if !isTraceStateKeyValueValid(entry) {
-		return ts, errInvalidTraceStateKeyValue
-	}
-
-	ckvs := ts.copyKVsAndDeleteEntry(entry.Key)
-	if len(ckvs)+1 > traceStateMaxListMembers {
-		return ts, errInvalidTraceStateMembersNumber
-	}
-
-	ckvs = append(ckvs, attribute.KeyValue{})
-	copy(ckvs[1:], ckvs)
-	ckvs[0] = entry
-
-	return TraceState{ckvs}, nil
-}
-
-// Delete removes specified entry from the trace state.
-func (ts TraceState) Delete(key attribute.Key) (TraceState, error) {
-	if !isTraceStateKeyValid(key) {
-		return ts, errInvalidTraceStateKeyValue
-	}
-
-	return TraceState{ts.copyKVsAndDeleteEntry(key)}, nil
-}
-
-// IsEmpty returns true if the TraceState does not contain any entries
-func (ts TraceState) IsEmpty() bool {
-	return len(ts.kvs) == 0
-}
-
-func (ts TraceState) copyKVsAndDeleteEntry(key attribute.Key) []attribute.KeyValue {
-	ckvs := make([]attribute.KeyValue, len(ts.kvs))
-	copy(ckvs, ts.kvs)
-	for i, kv := range ts.kvs {
-		if kv.Key == key {
-			ckvs = append(ckvs[:i], ckvs[i+1:]...)
-			break
-		}
-	}
-
-	return ckvs
-}
-
-// TraceStateFromKeyValues is a convenience method to create a new TraceState from
-// provided key/value pairs.
-func TraceStateFromKeyValues(kvs ...attribute.KeyValue) (TraceState, error) { //nolint:golint
-	if len(kvs) == 0 {
-		return TraceState{}, nil
-	}
-
-	if len(kvs) > traceStateMaxListMembers {
-		return TraceState{}, errInvalidTraceStateMembersNumber
-	}
-
-	km := make(map[attribute.Key]bool)
-	for _, kv := range kvs {
-		if !isTraceStateKeyValueValid(kv) {
-			return TraceState{}, errInvalidTraceStateKeyValue
-		}
-		_, ok := km[kv.Key]
-		if ok {
-			return TraceState{}, errInvalidTraceStateDuplicate
-		}
-		km[kv.Key] = true
-	}
-
-	ckvs := make([]attribute.KeyValue, len(kvs))
-	copy(ckvs, kvs)
-	return TraceState{ckvs}, nil
-}
-
-func isTraceStateKeyValid(key attribute.Key) bool {
-	return keyFormatRegExp.MatchString(string(key))
-}
-
-func isTraceStateKeyValueValid(kv attribute.KeyValue) bool {
-	return isTraceStateKeyValid(kv.Key) &&
-		valueFormatRegExp.MatchString(kv.Value.Emit())
-}
-
 // TraceFlags contains flags that can be set on a SpanContext
 type TraceFlags byte //nolint:golint
 
@@ -371,6 +210,8 @@ type SpanContext struct {
 	remote     bool
 }
 
+var _ json.Marshaler = SpanContext{}
+
 // IsValid returns if the SpanContext is valid. A valid span context has a
 // valid TraceID and SpanID.
 func (sc SpanContext) IsValid() bool {
diff --git a/trace/tracestate.go b/trace/tracestate.go
new file mode 100644
index 00000000..d743264e
--- /dev/null
+++ b/trace/tracestate.go
@@ -0,0 +1,217 @@
+// Copyright The OpenTelemetry Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package trace
+
+import (
+	"encoding/json"
+	"fmt"
+	"regexp"
+	"strings"
+)
+
+var (
+	maxListMembers = 32
+
+	listDelimiter = ","
+
+	// based on the W3C Trace Context specification, see
+	// https://www.w3.org/TR/trace-context-1/#tracestate-header
+	noTenantKeyFormat   = `[a-z][_0-9a-z\-\*\/]{0,255}`
+	withTenantKeyFormat = `[a-z0-9][_0-9a-z\-\*\/]{0,240}@[a-z][_0-9a-z\-\*\/]{0,13}`
+	valueFormat         = `[\x20-\x2b\x2d-\x3c\x3e-\x7e]{0,255}[\x21-\x2b\x2d-\x3c\x3e-\x7e]`
+
+	keyRe    = regexp.MustCompile(`^((` + noTenantKeyFormat + `)|(` + withTenantKeyFormat + `))$`)
+	valueRe  = regexp.MustCompile(`^(` + valueFormat + `)$`)
+	memberRe = regexp.MustCompile(`^\s*((` + noTenantKeyFormat + `)|(` + withTenantKeyFormat + `))=(` + valueFormat + `)\s*$`)
+
+	errInvalidKey    errorConst = "invalid tracestate key"
+	errInvalidValue  errorConst = "invalid tracestate value"
+	errInvalidMember errorConst = "invalid tracestate list-member"
+	errMemberNumber  errorConst = "too many list-members in tracestate"
+	errDuplicate     errorConst = "duplicate list-member in tracestate"
+)
+
+type member struct {
+	Key   string
+	Value string
+}
+
+func newMember(key, value string) (member, error) {
+	if !keyRe.MatchString(key) {
+		return member{}, fmt.Errorf("%w: %s", errInvalidKey, key)
+	}
+	if !valueRe.MatchString(value) {
+		return member{}, fmt.Errorf("%w: %s", errInvalidValue, value)
+	}
+	return member{Key: key, Value: value}, nil
+}
+
+func parseMemeber(m string) (member, error) {
+	matches := memberRe.FindStringSubmatch(m)
+	if len(matches) != 5 {
+		return member{}, fmt.Errorf("%w: %s", errInvalidMember, m)
+	}
+
+	return member{
+		Key:   matches[1],
+		Value: matches[4],
+	}, nil
+
+}
+
+// String encodes member into a string compliant with the W3C Trace Context
+// specification.
+func (m member) String() string {
+	return fmt.Sprintf("%s=%s", m.Key, m.Value)
+}
+
+// TraceState provides additional vendor-specific trace identification
+// information across different distributed tracing systems. It represents an
+// immutable list consisting of key/value pairs, each pair is referred to as a
+// list-member.
+//
+// TraceState conforms to the W3C Trace Context specification
+// (https://www.w3.org/TR/trace-context-1). All operations that create or copy
+// a TraceState do so by validating all input and will only produce TraceState
+// that conform to the specification. Specifically, this means that all
+// list-member's key/value pairs are valid, no duplicate list-members exist,
+// and the maximum number of list-members (32) is not exceeded.
+type TraceState struct { //nolint:golint
+	// list is the members in order.
+	list []member
+}
+
+var _ json.Marshaler = TraceState{}
+
+// ParseTraceState attempts to decode a TraceState from the passed
+// string. It returns an error if the input is invalid according to the W3C
+// Trace Context specification.
+func ParseTraceState(tracestate string) (TraceState, error) {
+	if tracestate == "" {
+		return TraceState{}, nil
+	}
+
+	wrapErr := func(err error) error {
+		return fmt.Errorf("failed to parse tracestate: %w", err)
+	}
+
+	var members []member
+	found := make(map[string]struct{})
+	for _, memberStr := range strings.Split(tracestate, listDelimiter) {
+		if len(memberStr) == 0 {
+			continue
+		}
+
+		m, err := parseMemeber(memberStr)
+		if err != nil {
+			return TraceState{}, wrapErr(err)
+		}
+
+		if _, ok := found[m.Key]; ok {
+			return TraceState{}, wrapErr(errDuplicate)
+		}
+		found[m.Key] = struct{}{}
+
+		members = append(members, m)
+		if n := len(members); n > maxListMembers {
+			return TraceState{}, wrapErr(errMemberNumber)
+		}
+	}
+
+	return TraceState{list: members}, nil
+}
+
+// MarshalJSON marshals the TraceState into JSON.
+func (ts TraceState) MarshalJSON() ([]byte, error) {
+	return json.Marshal(ts.String())
+}
+
+// String encodes the TraceState into a string compliant with the W3C
+// Trace Context specification. The returned string will be invalid if the
+// TraceState contains any invalid members.
+func (ts TraceState) String() string {
+	members := make([]string, len(ts.list))
+	for i, m := range ts.list {
+		members[i] = m.String()
+	}
+	return strings.Join(members, listDelimiter)
+}
+
+// Get returns the value paired with key from the corresponding TraceState
+// list-member if it exists, otherwise an empty string is returned.
+func (ts TraceState) Get(key string) string {
+	for _, member := range ts.list {
+		if member.Key == key {
+			return member.Value
+		}
+	}
+
+	return ""
+}
+
+// Insert adds a new list-member defined by the key/value pair to the
+// TraceState. If a list-member already exists for the given key, that
+// list-member's value is updated. The new or updated list-member is always
+// moved to the beginning of the TraceState as specified by the W3C Trace
+// Context specification.
+//
+// If key or value are invalid according to the W3C Trace Context
+// specification an error is returned with the original TraceState.
+//
+// If adding a new list-member means the TraceState would have more members
+// than is allowed an error is returned instead with the original TraceState.
+func (ts TraceState) Insert(key, value string) (TraceState, error) {
+	m, err := newMember(key, value)
+	if err != nil {
+		return ts, err
+	}
+
+	cTS := ts.Delete(key)
+	if cTS.Len()+1 > maxListMembers {
+		// TODO (MrAlias): When the second version of the Trace Context
+		// specification is published this needs to not return an error.
+		// Instead it should drop the "right-most" member and insert the new
+		// member at the front.
+		//
+		// https://github.com/w3c/trace-context/pull/448
+		return ts, fmt.Errorf("failed to insert: %w", errMemberNumber)
+	}
+
+	cTS.list = append(cTS.list, member{})
+	copy(cTS.list[1:], cTS.list)
+	cTS.list[0] = m
+
+	return cTS, nil
+}
+
+// Delete returns a copy of the TraceState with the list-member identified by
+// key removed.
+func (ts TraceState) Delete(key string) TraceState {
+	members := make([]member, ts.Len())
+	copy(members, ts.list)
+	for i, member := range ts.list {
+		if member.Key == key {
+			members = append(members[:i], members[i+1:]...)
+			// TraceState should contain no duplicate members.
+			break
+		}
+	}
+	return TraceState{list: members}
+}
+
+// Len returns the number of list-members in the TraceState.
+func (ts TraceState) Len() int {
+	return len(ts.list)
+}


Test patch:
diff --git a/exporters/otlp/internal/transform/span_test.go b/exporters/otlp/internal/transform/span_test.go
index d32fefed..9fec4f44 100644
--- a/exporters/otlp/internal/transform/span_test.go
+++ b/exporters/otlp/internal/transform/span_test.go
@@ -25,6 +25,7 @@ import (
 	"google.golang.org/protobuf/proto"
 
 	"go.opentelemetry.io/otel/attribute"
+	"go.opentelemetry.io/otel/oteltest"
 	"go.opentelemetry.io/otel/trace"
 	tracepb "go.opentelemetry.io/proto/otlp/trace/v1"
 
@@ -199,7 +200,7 @@ func TestSpanData(t *testing.T) {
 	// March 31, 2020 5:01:26 1234nanos (UTC)
 	startTime := time.Unix(1585674086, 1234)
 	endTime := startTime.Add(10 * time.Second)
-	traceState, _ := trace.TraceStateFromKeyValues(attribute.String("key1", "val1"), attribute.String("key2", "val2"))
+	traceState, _ := oteltest.TraceStateFromKeyValues(attribute.String("key1", "val1"), attribute.String("key2", "val2"))
 	spanData := tracetest.SpanStub{
 		SpanContext: trace.NewSpanContext(trace.SpanContextConfig{
 			TraceID:    trace.TraceID{0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F},
diff --git a/exporters/stdout/trace_test.go b/exporters/stdout/trace_test.go
index 8b60790d..f9cccef9 100644
--- a/exporters/stdout/trace_test.go
+++ b/exporters/stdout/trace_test.go
@@ -27,6 +27,7 @@ import (
 	"go.opentelemetry.io/otel/attribute"
 	"go.opentelemetry.io/otel/codes"
 	"go.opentelemetry.io/otel/exporters/stdout"
+	"go.opentelemetry.io/otel/oteltest"
 	"go.opentelemetry.io/otel/sdk/resource"
 	tracesdk "go.opentelemetry.io/otel/sdk/trace"
 	"go.opentelemetry.io/otel/sdk/trace/tracetest"
@@ -45,7 +46,7 @@ func TestExporter_ExportSpan(t *testing.T) {
 	now := time.Now()
 	traceID, _ := trace.TraceIDFromHex("0102030405060708090a0b0c0d0e0f10")
 	spanID, _ := trace.SpanIDFromHex("0102030405060708")
-	traceState, _ := trace.TraceStateFromKeyValues(attribute.String("key", "val"))
+	traceState, _ := oteltest.TraceStateFromKeyValues(attribute.String("key", "val"))
 	keyValue := "value"
 	doubleValue := 123.456
 	resource := resource.NewWithAttributes(attribute.String("rk1", "rv11"))
@@ -90,22 +91,14 @@ func TestExporter_ExportSpan(t *testing.T) {
 			"TraceID": "0102030405060708090a0b0c0d0e0f10",
 			"SpanID": "0102030405060708",
 			"TraceFlags": "00",
-			"TraceState": [
-				{
-					"Key": "key",
-					"Value": {
-						"Type": "STRING",
-						"Value": "val"
-					}
-				}
-			],
+			"TraceState": "key=val",
 			"Remote": false
 		},
 		"Parent": {
 			"TraceID": "00000000000000000000000000000000",
 			"SpanID": "0000000000000000",
 			"TraceFlags": "00",
-			"TraceState": null,
+			"TraceState": "",
 			"Remote": false
 		},
 		"SpanKind": 1,
diff --git a/oteltest/go.mod b/oteltest/go.mod
index cb37a2aa..dac471e8 100644
--- a/oteltest/go.mod
+++ b/oteltest/go.mod
@@ -47,6 +47,7 @@ replace go.opentelemetry.io/otel/sdk/metric => ../sdk/metric
 replace go.opentelemetry.io/otel/trace => ../trace
 
 require (
+	github.com/stretchr/testify v1.7.0
 	go.opentelemetry.io/otel v0.20.0
 	go.opentelemetry.io/otel/metric v0.20.0
 	go.opentelemetry.io/otel/trace v0.20.0
diff --git a/oteltest/tracestate.go b/oteltest/tracestate.go
new file mode 100644
index 00000000..b12743fd
--- /dev/null
+++ b/oteltest/tracestate.go
@@ -0,0 +1,41 @@
+// Copyright The OpenTelemetry Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package oteltest
+
+import (
+	"fmt"
+	"strings"
+
+	"go.opentelemetry.io/otel/attribute"
+	"go.opentelemetry.io/otel/trace"
+)
+
+// TraceStateFromKeyValues is a convenience function to create a
+// trace.TraceState from provided key/value pairs. There is no inverse to this
+// function, returning attributes from a TraceState, because the TraceState,
+// by definition from the W3C tracecontext specification, stores values as
+// opaque strings.  Therefore, it is not possible to decode the original value
+// type from TraceState. Be sure to not use this outside of testing purposes.
+func TraceStateFromKeyValues(kvs ...attribute.KeyValue) (trace.TraceState, error) {
+	if len(kvs) == 0 {
+		return trace.TraceState{}, nil
+	}
+
+	members := make([]string, len(kvs))
+	for i, kv := range kvs {
+		members[i] = fmt.Sprintf("%s=%s", string(kv.Key), kv.Value.Emit())
+	}
+	return trace.ParseTraceState(strings.Join(members, ","))
+}
diff --git a/oteltest/tracestate_test.go b/oteltest/tracestate_test.go
new file mode 100644
index 00000000..df3c926f
--- /dev/null
+++ b/oteltest/tracestate_test.go
@@ -0,0 +1,41 @@
+// Copyright The OpenTelemetry Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package oteltest
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+	"github.com/stretchr/testify/require"
+
+	"go.opentelemetry.io/otel/attribute"
+)
+
+func TestTraceStateFromKeyValues(t *testing.T) {
+	ts, err := TraceStateFromKeyValues()
+	require.NoError(t, err)
+	assert.Equal(t, 0, ts.Len(), "empty attributes creats zero value TraceState")
+
+	ts, err = TraceStateFromKeyValues(
+		attribute.String("key0", "string"),
+		attribute.Bool("key1", true),
+		attribute.Int64("key2", 1),
+		attribute.Float64("key3", 1.1),
+		attribute.Array("key4", []int{1, 1}),
+	)
+	require.NoError(t, err)
+	expected := "key0=string,key1=true,key2=1,key3=1.1,key4=[1 1]"
+	assert.Equal(t, expected, ts.String())
+}
diff --git a/propagation/trace_context_test.go b/propagation/trace_context_test.go
index fb712d82..3f92c5f1 100644
--- a/propagation/trace_context_test.go
+++ b/propagation/trace_context_test.go
@@ -288,7 +288,7 @@ func TestTraceStatePropagation(t *testing.T) {
 	prop := propagation.TraceContext{}
 	stateHeader := "tracestate"
 	parentHeader := "traceparent"
-	state, err := trace.TraceStateFromKeyValues(attribute.String("key1", "value1"), attribute.String("key2", "value2"))
+	state, err := oteltest.TraceStateFromKeyValues(attribute.String("key1", "value1"), attribute.String("key2", "value2"))
 	if err != nil {
 		t.Fatalf("Unable to construct expected TraceState: %s", err.Error())
 	}
diff --git a/sdk/trace/sampling_test.go b/sdk/trace/sampling_test.go
index 98bb4f42..b2ff015d 100644
--- a/sdk/trace/sampling_test.go
+++ b/sdk/trace/sampling_test.go
@@ -24,6 +24,7 @@ import (
 	"github.com/stretchr/testify/require"
 
 	"go.opentelemetry.io/otel/attribute"
+	"go.opentelemetry.io/otel/oteltest"
 	"go.opentelemetry.io/otel/trace"
 )
 
@@ -240,7 +241,7 @@ func TestTracestateIsPassed(t *testing.T) {
 
 	for _, tc := range testCases {
 		t.Run(tc.name, func(t *testing.T) {
-			traceState, err := trace.TraceStateFromKeyValues(attribute.String("k", "v"))
+			traceState, err := oteltest.TraceStateFromKeyValues(attribute.String("k", "v"))
 			if err != nil {
 				t.Error(err)
 			}
diff --git a/sdk/trace/trace_test.go b/sdk/trace/trace_test.go
index a340ddb1..46454e8f 100644
--- a/sdk/trace/trace_test.go
+++ b/sdk/trace/trace_test.go
@@ -354,7 +354,7 @@ func TestStartSpanWithParent(t *testing.T) {
 		t.Error(err)
 	}
 
-	ts, err := trace.TraceStateFromKeyValues(attribute.String("k", "v"))
+	ts, err := oteltest.TraceStateFromKeyValues(attribute.String("k", "v"))
 	if err != nil {
 		t.Error(err)
 	}
@@ -1597,13 +1597,13 @@ func TestSamplerTraceState(t *testing.T) {
 	makeInserter := func(k attribute.KeyValue, prefix string) Sampler {
 		return &stateSampler{
 			prefix: prefix,
-			f:      func(t trace.TraceState) trace.TraceState { return mustTS(t.Insert(k)) },
+			f:      func(t trace.TraceState) trace.TraceState { return mustTS(t.Insert(string(k.Key), k.Value.Emit())) },
 		}
 	}
 	makeDeleter := func(k attribute.Key, prefix string) Sampler {
 		return &stateSampler{
 			prefix: prefix,
-			f:      func(t trace.TraceState) trace.TraceState { return mustTS(t.Delete(k)) },
+			f:      func(t trace.TraceState) trace.TraceState { return t.Delete(string(k)) },
 		}
 	}
 	clearer := func(prefix string) Sampler {
@@ -1624,55 +1624,55 @@ func TestSamplerTraceState(t *testing.T) {
 		{
 			name:       "alwaysOn",
 			sampler:    AlwaysSample(),
-			input:      mustTS(trace.TraceStateFromKeyValues(kv1)),
-			want:       mustTS(trace.TraceStateFromKeyValues(kv1)),
+			input:      mustTS(oteltest.TraceStateFromKeyValues(kv1)),
+			want:       mustTS(oteltest.TraceStateFromKeyValues(kv1)),
 			exportSpan: true,
 		},
 		{
 			name:       "alwaysOff",
 			sampler:    NeverSample(),
-			input:      mustTS(trace.TraceStateFromKeyValues(kv1)),
-			want:       mustTS(trace.TraceStateFromKeyValues(kv1)),
+			input:      mustTS(oteltest.TraceStateFromKeyValues(kv1)),
+			want:       mustTS(oteltest.TraceStateFromKeyValues(kv1)),
 			exportSpan: false,
 		},
 		{
 			name:       "insertKeySampled",
 			sampler:    makeInserter(kv2, "span"),
 			spanName:   "span0",
-			input:      mustTS(trace.TraceStateFromKeyValues(kv1)),
-			want:       mustTS(trace.TraceStateFromKeyValues(kv2, kv1)),
+			input:      mustTS(oteltest.TraceStateFromKeyValues(kv1)),
+			want:       mustTS(oteltest.TraceStateFromKeyValues(kv2, kv1)),
 			exportSpan: true,
 		},
 		{
 			name:       "insertKeyDropped",
 			sampler:    makeInserter(kv2, "span"),
 			spanName:   "nospan0",
-			input:      mustTS(trace.TraceStateFromKeyValues(kv1)),
-			want:       mustTS(trace.TraceStateFromKeyValues(kv2, kv1)),
+			input:      mustTS(oteltest.TraceStateFromKeyValues(kv1)),
+			want:       mustTS(oteltest.TraceStateFromKeyValues(kv2, kv1)),
 			exportSpan: false,
 		},
 		{
 			name:       "deleteKeySampled",
 			sampler:    makeDeleter(k1, "span"),
 			spanName:   "span0",
-			input:      mustTS(trace.TraceStateFromKeyValues(kv1, kv2)),
-			want:       mustTS(trace.TraceStateFromKeyValues(kv2)),
+			input:      mustTS(oteltest.TraceStateFromKeyValues(kv1, kv2)),
+			want:       mustTS(oteltest.TraceStateFromKeyValues(kv2)),
 			exportSpan: true,
 		},
 		{
 			name:       "deleteKeyDropped",
 			sampler:    makeDeleter(k1, "span"),
 			spanName:   "nospan0",
-			input:      mustTS(trace.TraceStateFromKeyValues(kv1, kv2, kv3)),
-			want:       mustTS(trace.TraceStateFromKeyValues(kv2, kv3)),
+			input:      mustTS(oteltest.TraceStateFromKeyValues(kv1, kv2, kv3)),
+			want:       mustTS(oteltest.TraceStateFromKeyValues(kv2, kv3)),
 			exportSpan: false,
 		},
 		{
 			name:       "clearer",
 			sampler:    clearer("span"),
 			spanName:   "span0",
-			input:      mustTS(trace.TraceStateFromKeyValues(kv1, kv3)),
-			want:       mustTS(trace.TraceStateFromKeyValues()),
+			input:      mustTS(oteltest.TraceStateFromKeyValues(kv1, kv3)),
+			want:       mustTS(oteltest.TraceStateFromKeyValues()),
 			exportSpan: true,
 		},
 	}
diff --git a/trace/trace_test.go b/trace/trace_test.go
index dc8afe47..9e6b6aae 100644
--- a/trace/trace_test.go
+++ b/trace/trace_test.go
@@ -15,14 +15,9 @@
 package trace
 
 import (
-	"fmt"
 	"testing"
 
 	"github.com/google/go-cmp/cmp"
-	"github.com/stretchr/testify/assert"
-	"github.com/stretchr/testify/require"
-
-	"go.opentelemetry.io/otel/attribute"
 )
 
 func TestIsValid(t *testing.T) {
@@ -370,571 +365,14 @@ func TestSpanKindString(t *testing.T) {
 	}
 }
 
-func TestTraceStateString(t *testing.T) {
-	testCases := []struct {
-		name        string
-		traceState  TraceState
-		expectedStr string
-	}{
-		{
-			name: "Non-empty trace state",
-			traceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key1", "val1"),
-					attribute.String("key2", "val2"),
-					attribute.String("key3@vendor", "val3"),
-				},
-			},
-			expectedStr: "key1=val1,key2=val2,key3@vendor=val3",
-		},
-		{
-			name:        "Empty trace state",
-			traceState:  TraceState{},
-			expectedStr: "",
-		},
-	}
-
-	for _, tc := range testCases {
-		t.Run(tc.name, func(t *testing.T) {
-			assert.Equal(t, tc.expectedStr, tc.traceState.String())
-		})
-	}
-}
-
-func TestTraceStateGet(t *testing.T) {
-	testCases := []struct {
-		name          string
-		traceState    TraceState
-		key           attribute.Key
-		expectedValue string
-	}{
-		{
-			name:          "OK case",
-			traceState:    TraceState{kvsWithMaxMembers},
-			key:           "key16",
-			expectedValue: "value16",
-		},
-		{
-			name:          "Not found",
-			traceState:    TraceState{kvsWithMaxMembers},
-			key:           "keyxx",
-			expectedValue: "",
-		},
-		{
-			name:          "Invalid key",
-			traceState:    TraceState{kvsWithMaxMembers},
-			key:           "key!",
-			expectedValue: "",
-		},
-	}
-
-	for _, tc := range testCases {
-		t.Run(tc.name, func(t *testing.T) {
-			kv := tc.traceState.Get(tc.key)
-			assert.Equal(t, tc.expectedValue, kv.AsString())
-		})
-	}
-}
-
-func TestTraceStateDelete(t *testing.T) {
-	testCases := []struct {
-		name               string
-		traceState         TraceState
-		key                attribute.Key
-		expectedTraceState TraceState
-		expectedErr        error
-	}{
-		{
-			name: "OK case",
-			traceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key1", "val1"),
-					attribute.String("key2", "val2"),
-					attribute.String("key3", "val3"),
-				},
-			},
-			key: "key2",
-			expectedTraceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key1", "val1"),
-					attribute.String("key3", "val3"),
-				},
-			},
-		},
-		{
-			name: "Non-existing key",
-			traceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key1", "val1"),
-					attribute.String("key2", "val2"),
-					attribute.String("key3", "val3"),
-				},
-			},
-			key: "keyx",
-			expectedTraceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key1", "val1"),
-					attribute.String("key2", "val2"),
-					attribute.String("key3", "val3"),
-				},
-			},
-		},
-		{
-			name: "Invalid key",
-			traceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key1", "val1"),
-					attribute.String("key2", "val2"),
-					attribute.String("key3", "val3"),
-				},
-			},
-			key: "in va lid",
-			expectedTraceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key1", "val1"),
-					attribute.String("key2", "val2"),
-					attribute.String("key3", "val3"),
-				},
-			},
-			expectedErr: errInvalidTraceStateKeyValue,
-		},
-	}
-
-	for _, tc := range testCases {
-		t.Run(tc.name, func(t *testing.T) {
-			result, err := tc.traceState.Delete(tc.key)
-			if tc.expectedErr != nil {
-				require.Error(t, err)
-				assert.Equal(t, tc.expectedErr, err)
-				assert.Equal(t, tc.traceState, result)
-			} else {
-				require.NoError(t, err)
-				assert.Equal(t, tc.expectedTraceState, result)
-			}
-		})
-	}
-}
-
-func TestTraceStateInsert(t *testing.T) {
-	testCases := []struct {
-		name               string
-		traceState         TraceState
-		keyValue           attribute.KeyValue
-		expectedTraceState TraceState
-		expectedErr        error
-	}{
-		{
-			name: "OK case - add new",
-			traceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key1", "val1"),
-					attribute.String("key2", "val2"),
-					attribute.String("key3", "val3"),
-				},
-			},
-			keyValue: attribute.String("key4@vendor", "val4"),
-			expectedTraceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key4@vendor", "val4"),
-					attribute.String("key1", "val1"),
-					attribute.String("key2", "val2"),
-					attribute.String("key3", "val3"),
-				},
-			},
-		},
-		{
-			name: "OK case - replace",
-			traceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key1", "val1"),
-					attribute.String("key2", "val2"),
-					attribute.String("key3", "val3"),
-				},
-			},
-			keyValue: attribute.String("key2", "valX"),
-			expectedTraceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key2", "valX"),
-					attribute.String("key1", "val1"),
-					attribute.String("key3", "val3"),
-				},
-			},
-		},
-		{
-			name: "Invalid key/value",
-			traceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key1", "val1"),
-				},
-			},
-			keyValue: attribute.String("key!", "val!"),
-			expectedTraceState: TraceState{
-				kvs: []attribute.KeyValue{
-					attribute.String("key1", "val1"),
-				},
-			},
-			expectedErr: errInvalidTraceStateKeyValue,
-		},
-		{
-			name:               "Too many entries",
-			traceState:         TraceState{kvsWithMaxMembers},
-			keyValue:           attribute.String("keyx", "valx"),
-			expectedTraceState: TraceState{kvsWithMaxMembers},
-			expectedErr:        errInvalidTraceStateMembersNumber,
-		},
-	}
-
-	for _, tc := range testCases {
-		t.Run(tc.name, func(t *testing.T) {
-			result, err := tc.traceState.Insert(tc.keyValue)
-			if tc.expectedErr != nil {
-				require.Error(t, err)
-				assert.Equal(t, tc.expectedErr, err)
-				assert.Equal(t, tc.traceState, result)
-			} else {
-				require.NoError(t, err)
-				assert.Equal(t, tc.expectedTraceState, result)
-			}
-		})
-	}
-}
-
-func TestTraceStateFromKeyValues(t *testing.T) {
-	testCases := []struct {
-		name               string
-		kvs                []attribute.KeyValue
-		expectedTraceState TraceState
-		expectedErr        error
-	}{
-		{
-			name:               "OK case",
-			kvs:                kvsWithMaxMembers,
-			expectedTraceState: TraceState{kvsWithMaxMembers},
-		},
-		{
-			name:               "OK case (empty)",
-			expectedTraceState: TraceState{},
-		},
-		{
-			name: "Too many entries",
-			kvs: func() []attribute.KeyValue {
-				kvs := kvsWithMaxMembers
-				kvs = append(kvs, attribute.String("keyx", "valX"))
-				return kvs
-			}(),
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateMembersNumber,
-		},
-		{
-			name: "Duplicate key",
-			kvs: []attribute.KeyValue{
-				attribute.String("key1", "val1"),
-				attribute.String("key1", "val2"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateDuplicate,
-		},
-		{
-			name: "Duplicate key/value",
-			kvs: []attribute.KeyValue{
-				attribute.String("key1", "val1"),
-				attribute.String("key1", "val1"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateDuplicate,
-		},
-		{
-			name: "Invalid key/value",
-			kvs: []attribute.KeyValue{
-				attribute.String("key!", "val!"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Full character set",
-			kvs: []attribute.KeyValue{
-				attribute.String(
-					"abcdefghijklmnopqrstuvwxyz0123456789_-*/",
-					" !\"#$%&'()*+-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
-				),
-			},
-			expectedTraceState: TraceState{[]attribute.KeyValue{
-				attribute.String(
-					"abcdefghijklmnopqrstuvwxyz0123456789_-*/",
-					" !\"#$%&'()*+-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
-				),
-			}},
-		},
-		{
-			name: "Full character set with vendor",
-			kvs: []attribute.KeyValue{
-				attribute.String(
-					"abcdefghijklmnopqrstuvwxyz0123456789_-*/@a-z0-9_-*/",
-					"!\"#$%&'()*+-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
-				),
-			},
-			expectedTraceState: TraceState{[]attribute.KeyValue{
-				attribute.String(
-					"abcdefghijklmnopqrstuvwxyz0123456789_-*/@a-z0-9_-*/",
-					"!\"#$%&'()*+-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
-				),
-			}},
-		},
-		{
-			name: "Full character with vendor starting with number",
-			kvs: []attribute.KeyValue{
-				attribute.String(
-					"0123456789_-*/abcdefghijklmnopqrstuvwxyz@a-z0-9_-*/",
-					"!\"#$%&'()*+-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
-				),
-			},
-			expectedTraceState: TraceState{[]attribute.KeyValue{
-				attribute.String(
-					"0123456789_-*/abcdefghijklmnopqrstuvwxyz@a-z0-9_-*/",
-					"!\"#$%&'()*+-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
-				),
-			}},
-		},
-		{
-			name: "One field",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo", "1"),
-			},
-			expectedTraceState: TraceState{[]attribute.KeyValue{
-				attribute.String("foo", "1"),
-			}},
-		},
-		{
-			name: "Two fields",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo", "1"),
-				attribute.String("bar", "2"),
-			},
-			expectedTraceState: TraceState{[]attribute.KeyValue{
-				attribute.String("foo", "1"),
-				attribute.String("bar", "2"),
-			}},
-		},
-		{
-			name: "Long field key",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo", "1"),
-				attribute.String(
-					"zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz",
-					"1",
-				),
-			},
-			expectedTraceState: TraceState{[]attribute.KeyValue{
-				attribute.String("foo", "1"),
-				attribute.String(
-					"zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz",
-					"1",
-				),
-			}},
-		},
-		{
-			name: "Long field key with vendor",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo", "1"),
-				attribute.String(
-					"ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt@vvvvvvvvvvvvvv",
-					"1",
-				),
-			},
-			expectedTraceState: TraceState{[]attribute.KeyValue{
-				attribute.String("foo", "1"),
-				attribute.String(
-					"ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt@vvvvvvvvvvvvvv",
-					"1",
-				),
-			}},
-		},
-		{
-			name: "Invalid whitespace value",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo", "1 \t "),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Invalid whitespace key",
-			kvs: []attribute.KeyValue{
-				attribute.String(" \t bar", "2"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Empty header value",
-			kvs: []attribute.KeyValue{
-				attribute.String("", ""),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Space in key",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo ", "1"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Capitalized key",
-			kvs: []attribute.KeyValue{
-				attribute.String("FOO", "1"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Period in key",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo.bar", "1"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Empty vendor",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo@", "1"),
-				attribute.String("bar", "2"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Empty key for vendor",
-			kvs: []attribute.KeyValue{
-				attribute.String("@foo", "1"),
-				attribute.String("bar", "2"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Double @",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo@@bar", "1"),
-				attribute.String("bar", "2"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Compound vendor",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo@bar@baz", "1"),
-				attribute.String("bar", "2"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Key too long",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo", "1"),
-				attribute.String("zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz", "1"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Key too long with vendor",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo", "1"),
-				attribute.String("tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt@v", "1"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Vendor too long",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo", "1"),
-				attribute.String("t@vvvvvvvvvvvvvvv", "1"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Equal sign in value",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo", "bar=baz"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-		{
-			name: "Empty value",
-			kvs: []attribute.KeyValue{
-				attribute.String("foo", ""),
-				attribute.String("bar", "3"),
-			},
-			expectedTraceState: TraceState{},
-			expectedErr:        errInvalidTraceStateKeyValue,
-		},
-	}
-
-	messageFunc := func(kvs []attribute.KeyValue) []string {
-		var out []string
-		for _, kv := range kvs {
-			out = append(out, fmt.Sprintf("%s=%s", kv.Key, kv.Value.AsString()))
-		}
-		return out
-	}
-
-	for _, tc := range testCases {
-		t.Run(tc.name, func(t *testing.T) {
-			result, err := TraceStateFromKeyValues(tc.kvs...)
-			if tc.expectedErr != nil {
-				require.Error(t, err, messageFunc(tc.kvs))
-				assert.Equal(t, TraceState{}, result)
-				assert.Equal(t, tc.expectedErr, err)
-			} else {
-				require.NoError(t, err, messageFunc(tc.kvs))
-				assert.NotNil(t, tc.expectedTraceState)
-				assert.Equal(t, tc.expectedTraceState, result)
-			}
-		})
-	}
-}
-
 func assertSpanContextEqual(got SpanContext, want SpanContext) bool {
 	return got.spanID == want.spanID &&
 		got.traceID == want.traceID &&
 		got.traceFlags == want.traceFlags &&
 		got.remote == want.remote &&
-		assertTraceStateEqual(got.traceState, want.traceState)
+		got.traceState.String() == want.traceState.String()
 }
 
-func assertTraceStateEqual(got TraceState, want TraceState) bool {
-	if len(got.kvs) != len(want.kvs) {
-		return false
-	}
-
-	for i, kv := range got.kvs {
-		if kv != want.kvs[i] {
-			return false
-		}
-	}
-
-	return true
-}
-
-var kvsWithMaxMembers = func() []attribute.KeyValue {
-	kvs := make([]attribute.KeyValue, traceStateMaxListMembers)
-	for i := 0; i < traceStateMaxListMembers; i++ {
-		kvs[i] = attribute.String(fmt.Sprintf("key%d", i+1),
-			fmt.Sprintf("value%d", i+1))
-	}
-	return kvs
-}()
-
 func TestNewSpanContext(t *testing.T) {
 	testCases := []struct {
 		name                string
@@ -947,16 +385,16 @@ func TestNewSpanContext(t *testing.T) {
 				TraceID:    TraceID([16]byte{1}),
 				SpanID:     SpanID([8]byte{42}),
 				TraceFlags: 0x1,
-				TraceState: TraceState{kvs: []attribute.KeyValue{
-					attribute.String("foo", "bar"),
+				TraceState: TraceState{list: []member{
+					{"foo", "bar"},
 				}},
 			},
 			expectedSpanContext: SpanContext{
 				traceID:    TraceID([16]byte{1}),
 				spanID:     SpanID([8]byte{42}),
 				traceFlags: 0x1,
-				traceState: TraceState{kvs: []attribute.KeyValue{
-					attribute.String("foo", "bar"),
+				traceState: TraceState{list: []member{
+					{"foo", "bar"},
 				}},
 			},
 		},
@@ -1016,7 +454,7 @@ func TestSpanContextDerivation(t *testing.T) {
 	}
 
 	from = to
-	to.traceState = TraceState{kvs: []attribute.KeyValue{attribute.String("foo", "bar")}}
+	to.traceState = TraceState{list: []member{{"foo", "bar"}}}
 
 	modified = from.WithTraceState(to.TraceState())
 	if !assertSpanContextEqual(modified, to) {
diff --git a/trace/tracestate_test.go b/trace/tracestate_test.go
new file mode 100644
index 00000000..edb89073
--- /dev/null
+++ b/trace/tracestate_test.go
@@ -0,0 +1,506 @@
+// Copyright The OpenTelemetry Authors
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package trace
+
+import (
+	"encoding/json"
+	"fmt"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+	"github.com/stretchr/testify/require"
+)
+
+// Taken from the W3C tests:
+// https://github.com/w3c/trace-context/blob/dcd3ad9b7d6ac36f70ff3739874b73c11b0302a1/test/test_data.json
+var testcases = []struct {
+	in         string
+	tracestate TraceState
+	out        string
+	err        error
+}{
+	{
+		in:  "foo=1,foo=1",
+		err: errDuplicate,
+	},
+	{
+		in:  "foo=1,foo=2",
+		err: errDuplicate,
+	},
+	{
+		in:  "foo =1",
+		err: errInvalidMember,
+	},
+	{
+		in:  "FOO=1",
+		err: errInvalidMember,
+	},
+	{
+		in:  "foo.bar=1",
+		err: errInvalidMember,
+	},
+	{
+		in:  "foo@=1,bar=2",
+		err: errInvalidMember,
+	},
+	{
+		in:  "@foo=1,bar=2",
+		err: errInvalidMember,
+	},
+	{
+		in:  "foo@@bar=1,bar=2",
+		err: errInvalidMember,
+	},
+	{
+		in:  "foo@bar@baz=1,bar=2",
+		err: errInvalidMember,
+	},
+	{
+		in:  "foo=1,zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz=1",
+		err: errInvalidMember,
+	},
+	{
+		in:  "foo=1,tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt@v=1",
+		err: errInvalidMember,
+	},
+	{
+		in:  "foo=1,t@vvvvvvvvvvvvvvv=1",
+		err: errInvalidMember,
+	},
+	{
+		in:  "foo=bar=baz",
+		err: errInvalidMember,
+	},
+	{
+		in:  "foo=,bar=3",
+		err: errInvalidMember,
+	},
+	{
+		in:  "bar01=01,bar02=02,bar03=03,bar04=04,bar05=05,bar06=06,bar07=07,bar08=08,bar09=09,bar10=10,bar11=11,bar12=12,bar13=13,bar14=14,bar15=15,bar16=16,bar17=17,bar18=18,bar19=19,bar20=20,bar21=21,bar22=22,bar23=23,bar24=24,bar25=25,bar26=26,bar27=27,bar28=28,bar29=29,bar30=30,bar31=31,bar32=32,bar33=33",
+		err: errMemberNumber,
+	},
+	{
+		in:  "abcdefghijklmnopqrstuvwxyz0123456789_-*/= !\"#$%&'()*+-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
+		out: "abcdefghijklmnopqrstuvwxyz0123456789_-*/= !\"#$%&'()*+-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
+		tracestate: TraceState{list: []member{
+			{
+				Key:   "abcdefghijklmnopqrstuvwxyz0123456789_-*/",
+				Value: " !\"#$%&'()*+-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
+			},
+		}},
+	},
+	{
+		in:  "abcdefghijklmnopqrstuvwxyz0123456789_-*/@a-z0-9_-*/= !\"#$%&'()*+-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
+		out: "abcdefghijklmnopqrstuvwxyz0123456789_-*/@a-z0-9_-*/= !\"#$%&'()*+-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
+		tracestate: TraceState{list: []member{
+			{
+				Key:   "abcdefghijklmnopqrstuvwxyz0123456789_-*/@a-z0-9_-*/",
+				Value: " !\"#$%&'()*+-./0123456789:;<>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~",
+			},
+		}},
+	},
+	{
+		// Empty input should result in no error and a zero value
+		// TraceState being returned, that TraceState should be encoded as an
+		// empty string.
+	},
+	{
+		in:  "foo=1",
+		out: "foo=1",
+		tracestate: TraceState{list: []member{
+			{Key: "foo", Value: "1"},
+		}},
+	},
+	{
+		in:  "foo=1,",
+		out: "foo=1",
+		tracestate: TraceState{list: []member{
+			{Key: "foo", Value: "1"},
+		}},
+	},
+	{
+		in:  "foo=1,bar=2",
+		out: "foo=1,bar=2",
+		tracestate: TraceState{list: []member{
+			{Key: "foo", Value: "1"},
+			{Key: "bar", Value: "2"},
+		}},
+	},
+	{
+		in:  "foo=1,zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz=1",
+		out: "foo=1,zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz=1",
+		tracestate: TraceState{list: []member{
+			{
+				Key:   "foo",
+				Value: "1",
+			},
+			{
+				Key:   "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz",
+				Value: "1",
+			},
+		}},
+	},
+	{
+		in:  "foo=1,ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt@vvvvvvvvvvvvvv=1",
+		out: "foo=1,ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt@vvvvvvvvvvvvvv=1",
+		tracestate: TraceState{list: []member{
+			{
+				Key:   "foo",
+				Value: "1",
+			},
+			{
+				Key:   "ttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt@vvvvvvvvvvvvvv",
+				Value: "1",
+			},
+		}},
+	},
+	{
+		in:  "bar01=01,bar02=02,bar03=03,bar04=04,bar05=05,bar06=06,bar07=07,bar08=08,bar09=09,bar10=10,bar11=11,bar12=12,bar13=13,bar14=14,bar15=15,bar16=16,bar17=17,bar18=18,bar19=19,bar20=20,bar21=21,bar22=22,bar23=23,bar24=24,bar25=25,bar26=26,bar27=27,bar28=28,bar29=29,bar30=30,bar31=31,bar32=32",
+		out: "bar01=01,bar02=02,bar03=03,bar04=04,bar05=05,bar06=06,bar07=07,bar08=08,bar09=09,bar10=10,bar11=11,bar12=12,bar13=13,bar14=14,bar15=15,bar16=16,bar17=17,bar18=18,bar19=19,bar20=20,bar21=21,bar22=22,bar23=23,bar24=24,bar25=25,bar26=26,bar27=27,bar28=28,bar29=29,bar30=30,bar31=31,bar32=32",
+		tracestate: TraceState{list: []member{
+			{Key: "bar01", Value: "01"},
+			{Key: "bar02", Value: "02"},
+			{Key: "bar03", Value: "03"},
+			{Key: "bar04", Value: "04"},
+			{Key: "bar05", Value: "05"},
+			{Key: "bar06", Value: "06"},
+			{Key: "bar07", Value: "07"},
+			{Key: "bar08", Value: "08"},
+			{Key: "bar09", Value: "09"},
+			{Key: "bar10", Value: "10"},
+			{Key: "bar11", Value: "11"},
+			{Key: "bar12", Value: "12"},
+			{Key: "bar13", Value: "13"},
+			{Key: "bar14", Value: "14"},
+			{Key: "bar15", Value: "15"},
+			{Key: "bar16", Value: "16"},
+			{Key: "bar17", Value: "17"},
+			{Key: "bar18", Value: "18"},
+			{Key: "bar19", Value: "19"},
+			{Key: "bar20", Value: "20"},
+			{Key: "bar21", Value: "21"},
+			{Key: "bar22", Value: "22"},
+			{Key: "bar23", Value: "23"},
+			{Key: "bar24", Value: "24"},
+			{Key: "bar25", Value: "25"},
+			{Key: "bar26", Value: "26"},
+			{Key: "bar27", Value: "27"},
+			{Key: "bar28", Value: "28"},
+			{Key: "bar29", Value: "29"},
+			{Key: "bar30", Value: "30"},
+			{Key: "bar31", Value: "31"},
+			{Key: "bar32", Value: "32"},
+		}},
+	},
+	{
+		in:  "foo=1,bar=2,rojo=1,congo=2,baz=3",
+		out: "foo=1,bar=2,rojo=1,congo=2,baz=3",
+		tracestate: TraceState{list: []member{
+			{Key: "foo", Value: "1"},
+			{Key: "bar", Value: "2"},
+			{Key: "rojo", Value: "1"},
+			{Key: "congo", Value: "2"},
+			{Key: "baz", Value: "3"},
+		}},
+	},
+	{
+		in:  "foo=1 \t , \t bar=2, \t baz=3",
+		out: "foo=1,bar=2,baz=3",
+		tracestate: TraceState{list: []member{
+			{Key: "foo", Value: "1"},
+			{Key: "bar", Value: "2"},
+			{Key: "baz", Value: "3"},
+		}},
+	},
+	{
+		in:  "foo=1\t \t,\t \tbar=2,\t \tbaz=3",
+		out: "foo=1,bar=2,baz=3",
+		tracestate: TraceState{list: []member{
+			{Key: "foo", Value: "1"},
+			{Key: "bar", Value: "2"},
+			{Key: "baz", Value: "3"},
+		}},
+	},
+	{
+		in:  "foo=1 ",
+		out: "foo=1",
+		tracestate: TraceState{list: []member{
+			{Key: "foo", Value: "1"},
+		}},
+	},
+	{
+		in:  "foo=1\t",
+		out: "foo=1",
+		tracestate: TraceState{list: []member{
+			{Key: "foo", Value: "1"},
+		}},
+	},
+	{
+		in:  "foo=1 \t",
+		out: "foo=1",
+		tracestate: TraceState{list: []member{
+			{Key: "foo", Value: "1"},
+		}},
+	},
+}
+
+var maxMembers = func() TraceState {
+	members := make([]member, maxListMembers)
+	for i := 0; i < maxListMembers; i++ {
+		members[i] = member{
+			Key:   fmt.Sprintf("key%d", i+1),
+			Value: fmt.Sprintf("value%d", i+1),
+		}
+	}
+	return TraceState{list: members}
+}()
+
+func TestParseTraceState(t *testing.T) {
+	for _, tc := range testcases {
+		got, err := ParseTraceState(tc.in)
+		assert.Equal(t, tc.tracestate, got)
+		if tc.err != nil {
+			assert.ErrorIs(t, err, tc.err, tc.in)
+		} else {
+			assert.NoError(t, err, tc.in)
+		}
+	}
+}
+
+func TestTraceStateString(t *testing.T) {
+	for _, tc := range testcases {
+		if tc.err != nil {
+			// Only test non-zero value TraceState.
+			continue
+		}
+
+		assert.Equal(t, tc.out, tc.tracestate.String())
+	}
+}
+
+func TestTraceStateMarshalJSON(t *testing.T) {
+	for _, tc := range testcases {
+		if tc.err != nil {
+			// Only test non-zero value TraceState.
+			continue
+		}
+
+		// Encode UTF-8.
+		expected, err := json.Marshal(tc.out)
+		require.NoError(t, err)
+
+		actual, err := json.Marshal(tc.tracestate)
+		require.NoError(t, err)
+
+		assert.Equal(t, expected, actual)
+	}
+}
+
+func TestTraceStateGet(t *testing.T) {
+	testCases := []struct {
+		name     string
+		key      string
+		expected string
+	}{
+		{
+			name:     "OK case",
+			key:      "key16",
+			expected: "value16",
+		},
+		{
+			name:     "not found",
+			key:      "keyxx",
+			expected: "",
+		},
+		{
+			name:     "invalid W3C key",
+			key:      "key!",
+			expected: "",
+		},
+	}
+
+	for _, tc := range testCases {
+		assert.Equal(t, tc.expected, maxMembers.Get(tc.key), tc.name)
+	}
+}
+
+func TestTraceStateDelete(t *testing.T) {
+	ts := TraceState{list: []member{
+		{Key: "key1", Value: "val1"},
+		{Key: "key2", Value: "val2"},
+		{Key: "key3", Value: "val3"},
+	}}
+
+	testCases := []struct {
+		name     string
+		key      string
+		expected TraceState
+	}{
+		{
+			name: "OK case",
+			key:  "key2",
+			expected: TraceState{list: []member{
+				{Key: "key1", Value: "val1"},
+				{Key: "key3", Value: "val3"},
+			}},
+		},
+		{
+			name: "Non-existing key",
+			key:  "keyx",
+			expected: TraceState{list: []member{
+				{Key: "key1", Value: "val1"},
+				{Key: "key2", Value: "val2"},
+				{Key: "key3", Value: "val3"},
+			}},
+		},
+		{
+			name: "Invalid key",
+			key:  "in va lid",
+			expected: TraceState{list: []member{
+				{Key: "key1", Value: "val1"},
+				{Key: "key2", Value: "val2"},
+				{Key: "key3", Value: "val3"},
+			}},
+		},
+	}
+
+	for _, tc := range testCases {
+		assert.Equal(t, tc.expected, ts.Delete(tc.key), tc.name)
+	}
+}
+
+func TestTraceStateInsert(t *testing.T) {
+	ts := TraceState{list: []member{
+		{Key: "key1", Value: "val1"},
+		{Key: "key2", Value: "val2"},
+		{Key: "key3", Value: "val3"},
+	}}
+
+	testCases := []struct {
+		name       string
+		tracestate TraceState
+		key, value string
+		expected   TraceState
+		err        error
+	}{
+		{
+			name:       "add new",
+			tracestate: ts,
+			key:        "key4@vendor",
+			value:      "val4",
+			expected: TraceState{list: []member{
+				{Key: "key4@vendor", Value: "val4"},
+				{Key: "key1", Value: "val1"},
+				{Key: "key2", Value: "val2"},
+				{Key: "key3", Value: "val3"},
+			}},
+		},
+		{
+			name:       "replace",
+			tracestate: ts,
+			key:        "key2",
+			value:      "valX",
+			expected: TraceState{list: []member{
+				{Key: "key2", Value: "valX"},
+				{Key: "key1", Value: "val1"},
+				{Key: "key3", Value: "val3"},
+			}},
+		},
+		{
+			name:       "invalid key",
+			tracestate: ts,
+			key:        "key!",
+			value:      "val",
+			expected:   ts,
+			err:        errInvalidKey,
+		},
+		{
+			name:       "invalid value",
+			tracestate: ts,
+			key:        "key",
+			value:      "v=l",
+			expected:   ts,
+			err:        errInvalidValue,
+		},
+		{
+			name:       "invalid key/value",
+			tracestate: ts,
+			key:        "key!",
+			value:      "v=l",
+			expected:   ts,
+			err:        errInvalidKey,
+		},
+		{
+			name:       "too many entries",
+			tracestate: maxMembers,
+			key:        "keyx",
+			value:      "valx",
+			expected:   maxMembers,
+			err:        errMemberNumber,
+		},
+	}
+
+	for _, tc := range testCases {
+		actual, err := tc.tracestate.Insert(tc.key, tc.value)
+		assert.ErrorIs(t, err, tc.err, tc.name)
+		if tc.err != nil {
+			assert.Equal(t, tc.tracestate, actual, tc.name)
+		} else {
+			assert.Equal(t, tc.expected, actual, tc.name)
+		}
+	}
+}
+
+func TestTraceStateLen(t *testing.T) {
+	ts := TraceState{}
+	assert.Equal(t, 0, ts.Len(), "zero value TraceState is empty")
+
+	key := "key"
+	ts = TraceState{list: []member{{key, "value"}}}
+	assert.Equal(t, 1, ts.Len(), "TraceState with one value")
+}
+
+func TestTraceStateImmutable(t *testing.T) {
+	k0, v0 := "k0", "v0"
+	ts0 := TraceState{list: []member{{k0, v0}}}
+	assert.Equal(t, v0, ts0.Get(k0))
+
+	// Insert should not modify the original.
+	k1, v1 := "k1", "v1"
+	ts1, err := ts0.Insert(k1, v1)
+	require.NoError(t, err)
+	assert.Equal(t, v0, ts0.Get(k0))
+	assert.Equal(t, "", ts0.Get(k1))
+	assert.Equal(t, v0, ts1.Get(k0))
+	assert.Equal(t, v1, ts1.Get(k1))
+
+	// Update should not modify the original.
+	v2 := "v2"
+	ts2, err := ts1.Insert(k1, v2)
+	require.NoError(t, err)
+	assert.Equal(t, v0, ts0.Get(k0))
+	assert.Equal(t, "", ts0.Get(k1))
+	assert.Equal(t, v0, ts1.Get(k0))
+	assert.Equal(t, v1, ts1.Get(k1))
+	assert.Equal(t, v0, ts2.Get(k0))
+	assert.Equal(t, v2, ts2.Get(k1))
+
+	// Delete should not modify the original.
+	ts3 := ts2.Delete(k0)
+	assert.Equal(t, v0, ts0.Get(k0))
+	assert.Equal(t, v0, ts1.Get(k0))
+	assert.Equal(t, v0, ts2.Get(k0))
+	assert.Equal(t, "", ts3.Get(k0))
+}