diff --git a/BUILD b/BUILD
index 2b386fb..ae1a690 100644
--- a/BUILD
+++ b/BUILD
@@ -268,6 +268,7 @@
     "src/core/census/aggregation.h",
     "src/core/census/context.h",
     "src/core/census/rpc_metric_id.h",
+    "src/core/census/tag_set.h",
     "src/core/httpcli/httpcli_security_connector.c",
     "src/core/security/base64.c",
     "src/core/security/client_auth_filter.c",
@@ -417,6 +418,7 @@
     "src/core/census/context.c",
     "src/core/census/initialize.c",
     "src/core/census/operation.c",
+    "src/core/census/tag_set.c",
     "src/core/census/tracing.c",
   ],
   hdrs = [
@@ -559,6 +561,7 @@
     "src/core/census/aggregation.h",
     "src/core/census/context.h",
     "src/core/census/rpc_metric_id.h",
+    "src/core/census/tag_set.h",
     "src/core/surface/init_unsecure.c",
     "src/core/census/grpc_context.c",
     "src/core/census/grpc_filter.c",
@@ -688,6 +691,7 @@
     "src/core/census/context.c",
     "src/core/census/initialize.c",
     "src/core/census/operation.c",
+    "src/core/census/tag_set.c",
     "src/core/census/tracing.c",
   ],
   hdrs = [
@@ -1222,6 +1226,7 @@
     "src/core/census/context.c",
     "src/core/census/initialize.c",
     "src/core/census/operation.c",
+    "src/core/census/tag_set.c",
     "src/core/census/tracing.c",
   ],
   hdrs = [
@@ -1362,6 +1367,7 @@
     "src/core/census/aggregation.h",
     "src/core/census/context.h",
     "src/core/census/rpc_metric_id.h",
+    "src/core/census/tag_set.h",
   ],
   includes = [
     "include",
diff --git a/Makefile b/Makefile
index 449077b..3d607c2 100644
--- a/Makefile
+++ b/Makefile
@@ -875,6 +875,7 @@
 sockaddr_resolver_test: $(BINDIR)/$(CONFIG)/sockaddr_resolver_test
 sockaddr_utils_test: $(BINDIR)/$(CONFIG)/sockaddr_utils_test
 socket_utils_test: $(BINDIR)/$(CONFIG)/socket_utils_test
+tag_set_test: $(BINDIR)/$(CONFIG)/tag_set_test
 tcp_client_posix_test: $(BINDIR)/$(CONFIG)/tcp_client_posix_test
 tcp_posix_test: $(BINDIR)/$(CONFIG)/tcp_posix_test
 tcp_server_posix_test: $(BINDIR)/$(CONFIG)/tcp_server_posix_test
@@ -1180,6 +1181,7 @@
   $(BINDIR)/$(CONFIG)/sockaddr_resolver_test \
   $(BINDIR)/$(CONFIG)/sockaddr_utils_test \
   $(BINDIR)/$(CONFIG)/socket_utils_test \
+  $(BINDIR)/$(CONFIG)/tag_set_test \
   $(BINDIR)/$(CONFIG)/tcp_client_posix_test \
   $(BINDIR)/$(CONFIG)/tcp_posix_test \
   $(BINDIR)/$(CONFIG)/tcp_server_posix_test \
@@ -1471,6 +1473,8 @@
 	$(Q) $(BINDIR)/$(CONFIG)/sockaddr_utils_test || ( echo test sockaddr_utils_test failed ; exit 1 )
 	$(E) "[RUN]     Testing socket_utils_test"
 	$(Q) $(BINDIR)/$(CONFIG)/socket_utils_test || ( echo test socket_utils_test failed ; exit 1 )
+	$(E) "[RUN]     Testing tag_set_test"
+	$(Q) $(BINDIR)/$(CONFIG)/tag_set_test || ( echo test tag_set_test failed ; exit 1 )
 	$(E) "[RUN]     Testing tcp_client_posix_test"
 	$(Q) $(BINDIR)/$(CONFIG)/tcp_client_posix_test || ( echo test tcp_client_posix_test failed ; exit 1 )
 	$(E) "[RUN]     Testing tcp_posix_test"
@@ -2446,6 +2450,7 @@
     src/core/census/context.c \
     src/core/census/initialize.c \
     src/core/census/operation.c \
+    src/core/census/tag_set.c \
     src/core/census/tracing.c \
 
 PUBLIC_HEADERS_C += \
@@ -2748,6 +2753,7 @@
     src/core/census/context.c \
     src/core/census/initialize.c \
     src/core/census/operation.c \
+    src/core/census/tag_set.c \
     src/core/census/tracing.c \
 
 PUBLIC_HEADERS_C += \
@@ -8190,6 +8196,37 @@
 endif
 
 
+TAG_SET_TEST_SRC = \
+    test/core/census/tag_set_test.c \
+
+TAG_SET_TEST_OBJS = $(addprefix $(OBJDIR)/$(CONFIG)/, $(addsuffix .o, $(basename $(TAG_SET_TEST_SRC))))
+ifeq ($(NO_SECURE),true)
+
+# You can't build secure targets if you don't have OpenSSL.
+
+$(BINDIR)/$(CONFIG)/tag_set_test: openssl_dep_error
+
+else
+
+
+
+$(BINDIR)/$(CONFIG)/tag_set_test: $(TAG_SET_TEST_OBJS) $(LIBDIR)/$(CONFIG)/libgrpc_test_util.a $(LIBDIR)/$(CONFIG)/libgrpc.a $(LIBDIR)/$(CONFIG)/libgpr_test_util.a $(LIBDIR)/$(CONFIG)/libgpr.a
+	$(E) "[LD]      Linking $@"
+	$(Q) mkdir -p `dirname $@`
+	$(Q) $(LD) $(LDFLAGS) $(TAG_SET_TEST_OBJS) $(LIBDIR)/$(CONFIG)/libgrpc_test_util.a $(LIBDIR)/$(CONFIG)/libgrpc.a $(LIBDIR)/$(CONFIG)/libgpr_test_util.a $(LIBDIR)/$(CONFIG)/libgpr.a $(LDLIBS) $(LDLIBS_SECURE) -o $(BINDIR)/$(CONFIG)/tag_set_test
+
+endif
+
+$(OBJDIR)/$(CONFIG)/test/core/census/tag_set_test.o:  $(LIBDIR)/$(CONFIG)/libgrpc_test_util.a $(LIBDIR)/$(CONFIG)/libgrpc.a $(LIBDIR)/$(CONFIG)/libgpr_test_util.a $(LIBDIR)/$(CONFIG)/libgpr.a
+deps_tag_set_test: $(TAG_SET_TEST_OBJS:.o=.dep)
+
+ifneq ($(NO_SECURE),true)
+ifneq ($(NO_DEPS),true)
+-include $(TAG_SET_TEST_OBJS:.o=.dep)
+endif
+endif
+
+
 TCP_CLIENT_POSIX_TEST_SRC = \
     test/core/iomgr/tcp_client_posix_test.c \
 
diff --git a/binding.gyp b/binding.gyp
index 75e2f3c..cd4265f 100644
--- a/binding.gyp
+++ b/binding.gyp
@@ -301,6 +301,7 @@
         'src/core/census/context.c',
         'src/core/census/initialize.c',
         'src/core/census/operation.c',
+        'src/core/census/tag_set.c',
         'src/core/census/tracing.c',
       ],
       "conditions": [
diff --git a/build.yaml b/build.yaml
index 6227b18..367ef98 100644
--- a/build.yaml
+++ b/build.yaml
@@ -16,10 +16,12 @@
   - src/core/census/aggregation.h
   - src/core/census/context.h
   - src/core/census/rpc_metric_id.h
+  - src/core/census/tag_set.h
   src:
   - src/core/census/context.c
   - src/core/census/initialize.c
   - src/core/census/operation.c
+  - src/core/census/tag_set.c
   - src/core/census/tracing.c
 - name: grpc++_base
   public_headers:
@@ -1617,6 +1619,16 @@
   - mac
   - linux
   - posix
+- name: tag_set_test
+  build: test
+  language: c
+  src:
+  - test/core/census/tag_set_test.c
+  deps:
+  - grpc_test_util
+  - grpc
+  - gpr_test_util
+  - gpr
 - name: tcp_client_posix_test
   build: test
   language: c
diff --git a/gRPC.podspec b/gRPC.podspec
index 80f2681..4acf2d7 100644
--- a/gRPC.podspec
+++ b/gRPC.podspec
@@ -272,6 +272,7 @@
                       'src/core/census/aggregation.h',
                       'src/core/census/context.h',
                       'src/core/census/rpc_metric_id.h',
+                      'src/core/census/tag_set.h',
                       'include/grpc/grpc_security.h',
                       'include/grpc/byte_buffer.h',
                       'include/grpc/byte_buffer_reader.h',
@@ -428,6 +429,7 @@
                       'src/core/census/context.c',
                       'src/core/census/initialize.c',
                       'src/core/census/operation.c',
+                      'src/core/census/tag_set.c',
                       'src/core/census/tracing.c'
 
     ss.private_header_files = 'src/core/profiling/timers.h',
@@ -569,7 +571,8 @@
                               'src/core/transport/transport_impl.h',
                               'src/core/census/aggregation.h',
                               'src/core/census/context.h',
-                              'src/core/census/rpc_metric_id.h'
+                              'src/core/census/rpc_metric_id.h',
+                              'src/core/census/tag_set.h'
 
     ss.header_mappings_dir = '.'
     # This isn't officially supported in Cocoapods. We've asked for an alternative:
diff --git a/include/grpc/census.h b/include/grpc/census.h
index d0bc904..b127669 100644
--- a/include/grpc/census.h
+++ b/include/grpc/census.h
@@ -324,61 +324,71 @@
 /** End a scan previously started by census_trace_scan_start() */
 void census_trace_scan_end();
 
-/* Max number of characters in tag key */
-#define CENSUS_MAX_TAG_KEY_LENGTH 20
-/* Max number of tag value characters */
-#define CENSUS_MAX_TAG_VALUE_LENGTH 50
-
 /* A Census tag set is a collection of key:value string pairs; these form the
    basis against which Census metrics will be recorded. Keys are unique within
    a tag set. All contexts have an associated tag set. */
 typedef struct census_tag_set census_tag_set;
 
-/* Returns a pointer to a newly created, empty tag set. If size_hint > 0,
-   indicates that the tag set is intended to hold approximately that number
-   of tags. */
-census_tag_set *census_tag_set_create(size_t size_hint);
+/* A tag is a key:value pair. The key is a printable, nil-terminate
+   string. The value is a binary string, that may be printable. There are no
+   limits on the sizes of either keys or values, but code authors should
+   remember that systems may have inbuilt limits (e.g. for propagated tags,
+   the bytes on the wire) and that larger tags means more memory consumed and
+   time in processing. */
+typedef struct {
+  const char *key;
+  const char *value;
+  size_t value_len;
+  gpr_uint8 flags;
+} census_tag;
 
-/* Add a new tag key/value to an existing tag set; if the tag key already exists
-   in the tag set, then its value is overwritten with the new one. Can also be
-   used to delete a tag, by specifying a NULL value. If key is NULL, returns
-   the number of tags in the tag set.
-   Return values:
-   -1: invalid length key or value
-   non-negative value: the number of tags in the tag set. */
-int census_tag_set_add(census_tag_set *tags, const char *key,
-                       const char *value);
+/* Tag flags. */
+#define CENSUS_TAG_PROPAGATE 1 /* Tag should be propagated over RPC */
+#define CENSUS_TAG_STATS 2     /* Tag will be used for statistics aggregation */
+#define CENSUS_TAG_BINARY 4    /* Tag value is not printable */
+#define CENSUS_TAG_RESERVED 8  /* Reserved for internal use. */
+/* Flag values 8,16,32,64,128 are reserved for future/internal use. Clients
+   should not use or rely on their values. */
 
-/* Destroys a tag set. This function must be called to prevent memory leaks.
-   Once called, the tag set cannot be used again. */
+#define CENSUS_TAG_IS_PROPAGATED(flags) (flags & CENSUS_TAG_PROPAGATE)
+#define CENSUS_TAG_IS_STATS(flags) (flags & CENSUS_TAG_STATS)
+#define CENSUS_TAG_IS_BINARY(flags) (flags & CENSUS_TAG_BINARY)
+
+#define CENSUS_MAX_TAG_KV_LEN 255 /* Maximum length of key/value in a tag. */
+#define CENSUS_MAX_TAGS 255       /* Maximum number of tags in a tag set. */
+
+/* Create a new tag set, adding and removing tags from an existing tag set.
+   @param base Base tag set to build upon. Can be NULL.
+   @param tags A set of tags to be added/changed/deleted. Tags with keys that
+   are in 'tags', but not 'base', are added to the tag set. Keys that are in
+   both 'tags' and 'base' will have their value replaced. Tags with keys in
+   both, but with NULL or zero-length values, will be deleted from the
+   tag set.
+   @param ntags number of tags in 'tags'
+*/
+census_tag_set *census_tag_set_create(const census_tag_set *base,
+                                      const census_tag *tags, int ntags);
+
+/* Destroy a tag set created by census_tag_set_create(). Once this function
+   has been called, the tag set cannot be reused. */
 void census_tag_set_destroy(census_tag_set *tags);
 
+/* Get the number of tags in the tag set. */
+int census_tag_set_ntags(const census_tag_set *tags);
+
+/* Get a tag by it's index in the tag set. Returns 0 if the index is invalid
+   (<0 or >= census_tag_set_ntags). There is no guarantee on tag ordering. */
+int census_tag_set_get_tag_by_index(const census_tag_set *tags, int index,
+                                    census_tag *tag);
+
+/* Get a tag by its key. Returns 0 if the key is not present in the tag
+   set. */
+int census_tag_set_get_tag_by_key(const census_tag_set *tags, const char *key,
+                                  census_tag *tag);
+
 /* Get a contexts tag set. */
 census_tag_set *census_context_tag_set(census_context *context);
 
-/* A read-only representation of a tag for use by census clients. */
-typedef struct {
-  size_t key_len;    /* Number of bytes in tag key. */
-  const char *key;   /* A pointer to the tag key. May not be null-terminated. */
-  size_t value_len;  /* Number of bytes in tag value. */
-  const char *value; /* Pointer to the tag value. May not be null-terminated. */
-} census_tag_const;
-
-/* Used to iterate through a tag sets contents. */
-typedef struct census_tag_set_iterator census_tag_set_iterator;
-
-/* Open a tag set for iteration. The tag set must not be modified while
-   iteration is ongoing. Returns an iterator for use in following functions. */
-census_tag_set_iterator *census_tag_set_open(census_tag_set *tags);
-
-/* Get the next tag in the tag set, by writing into the 'tag' argument. Returns
-   1 if there is a "next" tag, 0 if there are no more tags. */
-int census_tag_set_next(census_tag_set_iterator *it, census_tag_const *tag);
-
-/* Close an iterator opened by census_tag_set_open(). The iterator will be
-   invalidated, and should not be used once close is called. */
-void census_tag_set_close(census_tag_set_iterator *it);
-
 /* Core stats collection API's. The following concepts are used:
    * Aggregation: A collection of values. Census supports the following
        aggregation types:
@@ -424,8 +434,8 @@
     construction via census_define_view(). */
 typedef struct {
   const census_aggregation_ops *ops;
-  const void *
-      create_arg; /* Argument to be used for aggregation initialization. */
+  const void
+      *create_arg; /* Argument to be used for aggregation initialization. */
 } census_aggregation;
 
 /** A census view type. Opaque. */
diff --git a/src/core/census/tag_set.c b/src/core/census/tag_set.c
new file mode 100644
index 0000000..80c2090
--- /dev/null
+++ b/src/core/census/tag_set.c
@@ -0,0 +1,527 @@
+/*
+ *
+ * Copyright 2015, Google Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *     * Neither the name of Google Inc. nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ */
+
+#include "tag_set.h"
+
+#include <grpc/census.h>
+#include <grpc/support/alloc.h>
+#include <grpc/support/log.h>
+#include <grpc/support/port_platform.h>
+#include <grpc/support/sync.h>
+#include <grpc/support/useful.h>
+#include <stdbool.h>
+#include <string.h>
+#include "src/core/support/murmur_hash.h"
+#include "src/core/support/string.h"
+
+// Functions in this file support the public tag_set API, as well as
+// encoding/decoding tag_sets as part of context transmission across
+// RPC's. The overall requirements (in approximate priority order) for the
+// tag_set representations:
+// 1. Efficient conversion to/from wire format
+// 2. Minimal bytes used on-wire
+// 3. Efficient tag set creation
+// 4. Efficient lookup of value for a key
+// 5. Efficient lookup of value for an index (to support iteration)
+// 6. Minimal memory footprint
+//
+// Notes on tradeoffs/decisions:
+// * tag includes 1 byte length of key, as well as nil-terminating byte. These
+//   are to aid in efficient parsing and the ability to directly return key
+//   strings. This is more important than saving a single byte/tag on the wire.
+// * The wire encoding uses only single byte values. This eliminates the need
+//   to handle endian-ness conversions.
+// * Keep all tag information (keys/values/flags) in a single memory buffer,
+//   that can be directly copied to the wire. This makes iteration by index
+//   somewhat less efficient.
+// * Binary tags are encoded seperately from non-binary tags. There are a
+//   primarily because non-binary tags are far more likely to be repeated
+//   across multiple RPC calls, so are more efficiently cached and
+//   compressed in any metadata schemes.
+// * deleted/modified tags are kept in memory, just marked with a deleted
+//   flag. This enables faster processing TODO: benchmark this
+// * all lengths etc. are restricted to one byte. This eliminates endian
+//   issues.
+
+// Structure representing a set of tags. Essentially a count of number of tags
+// present, and pointer to a chunk of memory that contains the per-tag details.
+struct tag_set {
+  int ntags;        // number of tags.
+  int ntags_alloc;  // ntags + number of deleted tags (total number of tags
+                    // in all of kvm).
+  size_t kvm_size;  // number of bytes allocated for key/value storage.
+  size_t kvm_used;  // number of bytes of used key/value memory
+  char *kvm;        // key/value memory. Consists of repeated entries of:
+                    //   Offset  Size  Description
+                    //     0      1    Key length, including trailing 0. (K)
+                    //     1      1    Value length. (V)
+                    //     2      1    Flags
+                    //     3      K    Key bytes
+                    //     3 + K  V    Value bytes
+                    //
+                    // We refer to the first 3 entries as the 'tag header'.
+};
+
+// Number of bytes in tag header.
+#define TAG_HEADER_SIZE 3  // key length (1) + value length (1) + flags (1)
+// Offsets to tag header entries.
+#define KEY_LEN_OFFSET 0
+#define VALUE_LEN_OFFSET 1
+#define FLAG_OFFSET 2
+
+// raw_tag represents the raw-storage form of a tag in the kvm of a tag_set.
+struct raw_tag {
+  uint8_t key_len;
+  uint8_t value_len;
+  uint8_t flags;
+  char *key;
+  char *value;
+};
+
+// use reserved flag bit for indication of deleted tag.
+#define CENSUS_TAG_DELETED CENSUS_TAG_RESERVED
+#define CENSUS_TAG_IS_DELETED(flags) (flags & CENSUS_TAG_DELETED)
+
+// Primary (external) representation of a tag set. Composed of 3 underlying
+// tag_set structs, one for each of the binary/printable propagated tags, and
+// one for everything else.
+struct census_tag_set {
+  struct tag_set propagated_tags;
+  struct tag_set propagated_binary_tags;
+  struct tag_set local_tags;
+};
+
+// Extract a raw tag given a pointer (raw) to the tag header. Allow for some
+// extra bytes in the tag header (see encode/decode for usage: allows for
+// future expansion of the tag header).
+static char *decode_tag(struct raw_tag *tag, char *header, int offset) {
+  tag->key_len = (uint8_t)(*header++);
+  tag->value_len = (uint8_t)(*header++);
+  tag->flags = (uint8_t)(*header++);
+  header += offset;
+  tag->key = header;
+  header += tag->key_len;
+  tag->value = header;
+  return header + tag->value_len;
+}
+
+// Make a copy (in 'to') of an existing tag_set.
+static void tag_set_copy(struct tag_set *to, const struct tag_set *from) {
+  memcpy(to, from, sizeof(struct tag_set));
+  to->kvm = gpr_malloc(to->kvm_size);
+  memcpy(to->kvm, from->kvm, to->kvm_used);
+}
+
+// We may want to keep information about a deleted tag for a short time,
+// in case we can reuse the space (same tag is reinserted). This structure
+// is used for that purpose.
+struct deleted_tag_info {
+  struct raw_tag raw;    // raw tag information.
+  uint8_t *raw_flags_p;  // pointer to original flags
+  struct tag_set *tags;  // the tag set from which tag was deleted.
+};
+
+// Delete a tag from a tag set, if it exists. Returns true if the tag was
+// originally present (and is now deleted), false if it wasn't.
+static bool tag_set_delete_tag(struct tag_set *tags,
+                               struct deleted_tag_info *dtag, const char *key,
+                               size_t key_len) {
+  char *kvp = tags->kvm;
+  for (int i = 0; i < tags->ntags_alloc; i++) {
+    dtag->raw_flags_p = (uint8_t *)(kvp + FLAG_OFFSET);
+    kvp = decode_tag(&dtag->raw, kvp, 0);
+    if (CENSUS_TAG_IS_DELETED(dtag->raw.flags)) continue;
+    if ((key_len == dtag->raw.key_len) &&
+        (memcmp(key, dtag->raw.key, key_len) == 0)) {
+      *(dtag->raw_flags_p) |= CENSUS_TAG_DELETED;
+      tags->ntags--;
+      return true;
+    }
+  }
+  return false;
+}
+
+// Delete a tag from a tag set. If the tag is found in any of the underlying
+// tag sets, *and* that tag set corresponds to the one in which the tag (if
+// later inserted) would be placed, then fills in dtag, and returns true.
+// Returns false otherwise. This information is later used to optimize the
+// placement of the tag if the value space can be reused, effectively
+// "undeleting" the tag.
+static bool cts_delete_tag(census_tag_set *tags, const census_tag *tag,
+                           size_t key_len, struct deleted_tag_info *dtag) {
+  // use the to-be-deleted tag flags as a hint to determine the order in which
+  // we delete from the underlying tag sets.
+  if (CENSUS_TAG_IS_PROPAGATED(tag->flags)) {
+    if (CENSUS_TAG_IS_BINARY(tag->flags)) {
+      if (tag_set_delete_tag(&tags->propagated_binary_tags, dtag, tag->key,
+                             key_len)) {
+        dtag->tags = &tags->propagated_binary_tags;
+        return true;
+      }
+      if (tag_set_delete_tag(&tags->propagated_tags, dtag, tag->key, key_len))
+        return false;
+      tag_set_delete_tag(&tags->local_tags, dtag, tag->key, key_len);
+    } else {
+      if (tag_set_delete_tag(&tags->propagated_tags, dtag, tag->key, key_len)) {
+        dtag->tags = &tags->propagated_tags;
+        return true;
+      }
+      if (tag_set_delete_tag(&tags->propagated_binary_tags, dtag, tag->key,
+                             key_len))
+        return false;
+      tag_set_delete_tag(&tags->local_tags, dtag, tag->key, key_len);
+    }
+  } else {
+    if (tag_set_delete_tag(&tags->local_tags, dtag, tag->key, key_len)) {
+      dtag->tags = &tags->local_tags;
+      return true;
+    }
+    if (tag_set_delete_tag(&tags->propagated_tags, dtag, tag->key, key_len))
+      return false;
+    tag_set_delete_tag(&tags->propagated_binary_tags, dtag, tag->key, key_len);
+  }
+  return false;
+}
+
+// Add a tag to a tag set.
+static void tag_set_add_tag(struct tag_set *tags, const census_tag *tag,
+                            size_t key_len) {
+  const size_t tag_size = key_len + tag->value_len + TAG_HEADER_SIZE;
+  // drop tag if too many.
+  if (tags->ntags == CENSUS_MAX_TAGS) {
+    return;
+  }
+  if (tags->kvm_used + tag_size > tags->kvm_size) {
+    tags->kvm_size += 2 * CENSUS_MAX_TAG_KV_LEN + TAG_HEADER_SIZE;
+    char *new_kvm = gpr_malloc(tags->kvm_size);
+    memcpy(new_kvm, tags->kvm, tags->kvm_used);
+    gpr_free(tags->kvm);
+    tags->kvm = new_kvm;
+  }
+  char *kvp = tags->kvm + tags->kvm_used;
+  *kvp++ = (char)key_len;
+  *kvp++ = (char)tag->value_len;
+  // ensure reserved flags are not used.
+  *kvp++ = (char)(tag->flags & (CENSUS_TAG_PROPAGATE | CENSUS_TAG_STATS |
+                                CENSUS_TAG_BINARY));
+  memcpy(kvp, tag->key, key_len);
+  kvp += key_len;
+  memcpy(kvp, tag->value, tag->value_len);
+  tags->kvm_used += tag_size;
+  tags->ntags++;
+  tags->ntags_alloc++;
+}
+
+// Add a tag to a census_tag_set
+static void cts_add_tag(census_tag_set *tags, const census_tag *tag,
+                        size_t key_len) {
+  // first delete the tag if it is already present
+  struct deleted_tag_info dtag;
+  bool deleted_match = cts_delete_tag(tags, tag, key_len, &dtag);
+  if (tag->value != NULL && tag->value_len != 0) {
+    if (deleted_match && tag->value_len == dtag.raw.value_len) {
+      // if we have a close match for tag being added to one just deleted,
+      // only need to modify value and flags.
+      memcpy(dtag.raw.value, tag->value, tag->value_len);
+      *dtag.raw_flags_p = (tag->flags & (CENSUS_TAG_PROPAGATE |
+                                         CENSUS_TAG_STATS | CENSUS_TAG_BINARY));
+      dtag.tags->ntags++;
+    } else {
+      if (CENSUS_TAG_IS_PROPAGATED(tag->flags)) {
+        if (CENSUS_TAG_IS_BINARY(tag->flags)) {
+          tag_set_add_tag(&tags->propagated_binary_tags, tag, key_len);
+        } else {
+          tag_set_add_tag(&tags->propagated_tags, tag, key_len);
+        }
+      } else {
+        tag_set_add_tag(&tags->local_tags, tag, key_len);
+      }
+    }
+  }
+}
+
+census_tag_set *census_tag_set_create(const census_tag_set *base,
+                                      const census_tag *tags, int ntags) {
+  census_tag_set *new_ts = gpr_malloc(sizeof(census_tag_set));
+  if (base == NULL) {
+    memset(new_ts, 0, sizeof(census_tag_set));
+  } else {
+    tag_set_copy(&new_ts->propagated_tags, &base->propagated_tags);
+    tag_set_copy(&new_ts->propagated_binary_tags,
+                 &base->propagated_binary_tags);
+    tag_set_copy(&new_ts->local_tags, &base->local_tags);
+  }
+  for (int i = 0; i < ntags; i++) {
+    const census_tag *tag = &tags[i];
+    size_t key_len = strlen(tag->key) + 1;
+    // ignore the tag if it is too long/short.
+    if (key_len != 1 && key_len <= CENSUS_MAX_TAG_KV_LEN &&
+        tag->value_len <= CENSUS_MAX_TAG_KV_LEN) {
+      cts_add_tag(new_ts, tag, key_len);
+    }
+  }
+  return new_ts;
+}
+
+void census_tag_set_destroy(census_tag_set *tags) {
+  gpr_free(tags->propagated_tags.kvm);
+  gpr_free(tags->propagated_binary_tags.kvm);
+  gpr_free(tags->local_tags.kvm);
+  gpr_free(tags);
+}
+
+int census_tag_set_ntags(const census_tag_set *tags) {
+  return tags->propagated_tags.ntags + tags->propagated_binary_tags.ntags +
+         tags->local_tags.ntags;
+}
+
+// Get the nth tag in a tag set. The caller must validate that index is
+// in range.
+static void tag_set_get_tag_by_index(const struct tag_set *tags, int index,
+                                     census_tag *tag) {
+  GPR_ASSERT(index < tags->ntags);
+  char *kvp = tags->kvm;
+  for (;;) {
+    struct raw_tag raw;
+    kvp = decode_tag(&raw, kvp, 0);
+    if (CENSUS_TAG_IS_DELETED(raw.flags)) {
+      continue;
+    } else if (index == 0) {
+      tag->key = raw.key;
+      tag->value = raw.value;
+      tag->value_len = raw.value_len;
+      tag->flags = raw.flags;
+      return;
+    }
+    index--;
+  }
+  // NOT REACHED
+}
+
+int census_tag_set_get_tag_by_index(const census_tag_set *tags, int index,
+                                    census_tag *tag) {
+  if (index < 0) return 0;
+  if (index < tags->propagated_tags.ntags) {
+    tag_set_get_tag_by_index(&tags->propagated_tags, index, tag);
+    return 1;
+  }
+  index -= tags->propagated_tags.ntags;
+  if (index < tags->propagated_binary_tags.ntags) {
+    tag_set_get_tag_by_index(&tags->propagated_binary_tags, index, tag);
+    return 1;
+  }
+  index -= tags->propagated_binary_tags.ntags;
+  if (index < tags->local_tags.ntags) {
+    tag_set_get_tag_by_index(&tags->local_tags, index, tag);
+    return 1;
+  }
+  return 0;
+}
+
+// Find a tag in a tag_set by key. Return true if found, false otherwise.
+static bool tag_set_get_tag_by_key(const struct tag_set *tags, const char *key,
+                                   size_t key_len, census_tag *tag) {
+  char *kvp = tags->kvm;
+  for (int i = 0; i < tags->ntags; i++) {
+    struct raw_tag raw;
+    do {
+      kvp = decode_tag(&raw, kvp, 0);
+    } while (CENSUS_TAG_IS_DELETED(raw.flags));
+    if (key_len == raw.key_len && memcmp(raw.key, key, key_len) == 0) {
+      tag->key = raw.key;
+      tag->value = raw.value;
+      tag->value_len = raw.value_len;
+      tag->flags = raw.flags;
+      return true;
+    }
+  }
+  return false;
+}
+
+int census_tag_set_get_tag_by_key(const census_tag_set *tags, const char *key,
+                                  census_tag *tag) {
+  size_t key_len = strlen(key) + 1;
+  if (key_len == 1) {
+    return 0;
+  }
+  if (tag_set_get_tag_by_key(&tags->propagated_tags, key, key_len, tag) ||
+      tag_set_get_tag_by_key(&tags->propagated_binary_tags, key, key_len,
+                             tag) ||
+      tag_set_get_tag_by_key(&tags->local_tags, key, key_len, tag)) {
+    return 1;
+  }
+  return 0;
+}
+
+// tag_set encoding and decoding functions.
+//
+// Wire format for tag sets on the wire:
+//
+// First, a tag set header:
+//
+// offset   bytes  description
+//   0        1    version number
+//   1        1    number of bytes in this header. This allows for future
+//                 expansion.
+//   2        1    number of bytes in each tag header.
+//   3        1    ntags value from tag set.
+//   4        1    ntags_alloc value from tag set.
+//
+//   This is followed by the key/value memory from struct tag_set.
+
+#define ENCODED_VERSION 0      // Version number
+#define ENCODED_HEADER_SIZE 5  // size of tag set header
+
+// Pack a tag set into as few bytes as possible (eliding deleted tags). Assumes
+// header is already generated.
+static size_t tag_set_encode_packed(const struct tag_set *tags, char *buffer,
+                                    size_t buf_size) {
+  size_t encoded_size = 0;
+  char *kvp = tags->kvm;
+  for (int i = 0; i < tags->ntags_alloc; i++) {
+    struct raw_tag raw;
+    char *base = kvp;
+    kvp = decode_tag(&raw, kvp, 0);
+    size_t tag_size =
+        TAG_HEADER_SIZE + (size_t)raw.key_len + (size_t)raw.value_len;
+    if (!(CENSUS_TAG_IS_DELETED(raw.flags))) {
+      if (tag_size > buf_size) {
+        return 0;
+      }
+      memcpy(buffer, base, tag_size);
+      buffer += tag_size;
+      encoded_size += tag_size;
+      buf_size -= tag_size;
+    }
+  }
+  return encoded_size;
+}
+
+// Encode a tag set. Returns 0 if buffer is too small.
+static size_t tag_set_encode(const struct tag_set *tags, char *buffer,
+                             size_t buf_size) {
+  if (buf_size < ENCODED_HEADER_SIZE) {
+    return 0;
+  }
+  buf_size -= ENCODED_HEADER_SIZE;
+  *buffer++ = (char)ENCODED_VERSION;
+  *buffer++ = (char)ENCODED_HEADER_SIZE;
+  *buffer++ = (char)TAG_HEADER_SIZE;
+  *buffer++ = (char)tags->ntags;
+  if (tags->ntags == 0) {
+    *buffer = (char)tags->ntags;
+    return ENCODED_HEADER_SIZE;
+  }
+  if (buf_size < tags->kvm_used || tags->ntags_alloc > CENSUS_MAX_TAGS) {
+    *buffer++ = (char)tags->ntags;
+    size_t enc_size = tag_set_encode_packed(tags, buffer, buf_size);
+    if (enc_size == 0) {
+      return 0;
+    }
+    return ENCODED_HEADER_SIZE + enc_size;
+  }
+  *buffer++ = (char)tags->ntags_alloc;
+  memcpy(buffer, tags->kvm, tags->kvm_used);
+  return ENCODED_HEADER_SIZE + tags->kvm_used;
+}
+
+size_t census_tag_set_encode_propagated(const census_tag_set *tags,
+                                        char *buffer, size_t buf_size) {
+  return tag_set_encode(&tags->propagated_tags, buffer, buf_size);
+}
+
+size_t census_tag_set_encode_propagated_binary(const census_tag_set *tags,
+                                               char *buffer, size_t buf_size) {
+  return tag_set_encode(&tags->propagated_binary_tags, buffer, buf_size);
+}
+
+// Decode a tag set.
+static void tag_set_decode(struct tag_set *tags, const char *buffer,
+                           size_t size) {
+  uint8_t version = (uint8_t)(*buffer++);
+  uint8_t header_size = (uint8_t)(*buffer++);
+  uint8_t tag_header_size = (uint8_t)(*buffer++);
+  tags->ntags = (int)(*buffer++);
+  if (tags->ntags == 0) {
+    tags->ntags_alloc = 0;
+    tags->kvm_size = 0;
+    tags->kvm_used = 0;
+    tags->kvm = NULL;
+    return;
+  }
+  tags->ntags_alloc = (uint8_t)(*buffer++);
+  if (header_size != ENCODED_HEADER_SIZE) {
+    GPR_ASSERT(version != ENCODED_VERSION);
+    GPR_ASSERT(ENCODED_HEADER_SIZE < header_size);
+    buffer += (header_size - ENCODED_HEADER_SIZE);
+  }
+  tags->kvm_used = size - header_size;
+  tags->kvm_size = tags->kvm_used + CENSUS_MAX_TAG_KV_LEN;
+  tags->kvm = gpr_malloc(tags->kvm_size);
+  if (tag_header_size != TAG_HEADER_SIZE) {
+    // something new in the tag information. I don't understand it, so
+    // don't copy it over.
+    GPR_ASSERT(version != ENCODED_VERSION);
+    GPR_ASSERT(tag_header_size > TAG_HEADER_SIZE);
+    char *kvp = tags->kvm;
+    for (int i = 0; i < tags->ntags_alloc; i++) {
+      memcpy(kvp, buffer, TAG_HEADER_SIZE);
+      kvp += header_size;
+      struct raw_tag raw;
+      buffer =
+          decode_tag(&raw, (char *)buffer, tag_header_size - TAG_HEADER_SIZE);
+      memcpy(kvp, raw.key, (size_t)raw.key_len + raw.value_len);
+      kvp += raw.key_len + raw.value_len;
+    }
+  } else {
+    memcpy(tags->kvm, buffer, tags->kvm_used);
+  }
+}
+
+census_tag_set *census_tag_set_decode(const char *buffer, size_t size,
+                                      const char *bin_buffer, size_t bin_size) {
+  census_tag_set *new_ts = gpr_malloc(sizeof(census_tag_set));
+  memset(&new_ts->local_tags, 0, sizeof(struct tag_set));
+  if (buffer == NULL) {
+    memset(&new_ts->propagated_tags, 0, sizeof(struct tag_set));
+  } else {
+    tag_set_decode(&new_ts->propagated_tags, buffer, size);
+  }
+  if (bin_buffer == NULL) {
+    memset(&new_ts->propagated_binary_tags, 0, sizeof(struct tag_set));
+  } else {
+    tag_set_decode(&new_ts->propagated_binary_tags, bin_buffer, bin_size);
+  }
+  // TODO(aveitch): check that BINARY flag is correct for each type.
+  return new_ts;
+}
diff --git a/src/core/census/tag_set.h b/src/core/census/tag_set.h
new file mode 100644
index 0000000..9eec0ad
--- /dev/null
+++ b/src/core/census/tag_set.h
@@ -0,0 +1,57 @@
+/*
+ *
+ * Copyright 2015, Google Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *     * Neither the name of Google Inc. nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ */
+
+#ifndef GRPC_INTERNAL_CORE_CENSUS_TAG_SET_H
+#define GRPC_INTERNAL_CORE_CENSUS_TAG_SET_H
+
+#include <grpc/census.h>
+#include <grpc/support/port_platform.h>
+#include <grpc/support/sync.h>
+
+/* Encode to-be-propagated tags from a tag set into a memory buffer. The total
+   number of bytes used in the buffer is returned. If the buffer is too small
+   to contain the encoded tag set, then 0 is returned. */
+size_t census_tag_set_encode_propagated(const census_tag_set *tags,
+                                        char *buffer, size_t buf_size);
+
+/* Encode to-be-propagated binary tags from a tag set into a memory
+   buffer. The total number of bytes used in the buffer is returned. If the
+   buffer is too small to contain the encoded tag set, then 0 is returned. */
+size_t census_tag_set_encode_propagated_binary(const census_tag_set *tags,
+                                               char *buffer, size_t buf_size);
+
+/* Decode tag set buffers encoded with census_tag_set_encode_*(). */
+census_tag_set *census_tag_set_decode(const char *buffer, size_t size,
+                                      const char *bin_buffer, size_t bin_size);
+
+#endif /* GRPC_INTERNAL_CORE_CENSUS_TAG_SET_H */
diff --git a/test/core/census/tag_set_test.c b/test/core/census/tag_set_test.c
new file mode 100644
index 0000000..d6a7e45
--- /dev/null
+++ b/test/core/census/tag_set_test.c
@@ -0,0 +1,404 @@
+/*
+ *
+ * Copyright 2015-2016, Google Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *     * Neither the name of Google Inc. nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ */
+
+// Test census_tag_set functions, including encoding/decoding
+
+#include "src/core/census/tag_set.h"
+#include <grpc/support/log.h>
+#include <grpc/support/time.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "test/core/util/test_config.h"
+
+static uint8_t one_byte_val = 7;
+static uint32_t four_byte_val = 0x12345678;
+static uint64_t eight_byte_val = 0x1234567890abcdef;
+
+// A set of tags Used to create a basic tag_set for testing. Each tag has a
+// unique set of flags. Note that replace_add_delete_test() relies on specific
+// offsets into this array - if you add or delete entries, you will also need
+// to change the test.
+#define BASIC_TAG_COUNT 8
+static census_tag basic_tags[BASIC_TAG_COUNT] = {
+    /* 0 */ {"key0", "printable", 10, 0},
+    /* 1 */ {"k1", "a", 2, CENSUS_TAG_PROPAGATE},
+    /* 2 */ {"k2", "longer printable string", 24, CENSUS_TAG_STATS},
+    /* 3 */ {"key_three", (char *)&one_byte_val, 1, CENSUS_TAG_BINARY},
+    /* 4 */ {"really_long_key_4", "random", 7,
+             CENSUS_TAG_PROPAGATE | CENSUS_TAG_STATS},
+    /* 5 */ {"k5", (char *)&four_byte_val, 4,
+             CENSUS_TAG_PROPAGATE | CENSUS_TAG_BINARY},
+    /* 6 */ {"k6", (char *)&eight_byte_val, 8,
+             CENSUS_TAG_STATS | CENSUS_TAG_BINARY},
+    /* 7 */ {"k7", (char *)&four_byte_val, 4,
+             CENSUS_TAG_PROPAGATE | CENSUS_TAG_STATS | CENSUS_TAG_BINARY}};
+
+// Set of tags used to modify the basic tag_set. Note that
+// replace_add_delete_test() relies on specific offsets into this array - if
+// you add or delete entries, you will also need to change the test. Other
+// tests that rely on specific instances have XXX_XXX_OFFSET definitions (also
+// change the defines below if you add/delete entires).
+#define MODIFY_TAG_COUNT 10
+static census_tag modify_tags[MODIFY_TAG_COUNT] = {
+#define REPLACE_VALUE_OFFSET 0
+    /* 0 */ {"key0", "replace printable", 18, 0},  // replaces tag value only
+#define ADD_TAG_OFFSET 1
+    /* 1 */ {"new_key", "xyzzy", 6, CENSUS_TAG_STATS},  // new tag
+#define DELETE_TAG_OFFSET 2
+    /* 2 */ {"k5", NULL, 5,
+             0},  // should delete tag, despite bogus value length
+    /* 3 */ {"k6", "foo", 0, 0},  // should delete tag, despite bogus value
+    /* 4 */ {"k6", "foo", 0, 0},  // try deleting already-deleted tag
+    /* 5 */ {"non-existent", NULL, 0, 0},  // another non-existent tag
+#define REPLACE_FLAG_OFFSET 6
+    /* 6 */ {"k1", "a", 2, 0},                   // change flags only
+    /* 7 */ {"k7", "bar", 4, CENSUS_TAG_STATS},  // change flags and value
+    /* 8 */ {"k2", (char *)&eight_byte_val, 8,
+             CENSUS_TAG_BINARY | CENSUS_TAG_PROPAGATE},  // more flags change
+                                                         // non-binary -> binary
+    /* 9 */ {"k6", "bar", 4,
+             0}  // add back tag, with different value, but same length
+};
+
+// Utility function to compare tags. Returns true if all fields match.
+static bool compare_tag(const census_tag *t1, const census_tag *t2) {
+  return (strcmp(t1->key, t2->key) == 0 && t1->value_len == t2->value_len &&
+          memcmp(t1->value, t2->value, t1->value_len) == 0 &&
+          t1->flags == t2->flags);
+}
+
+// Utility function to validate a tag exists in tag set.
+static bool validate_tag(const census_tag_set *cts, const census_tag *tag) {
+  census_tag tag2;
+  if (census_tag_set_get_tag_by_key(cts, tag->key, &tag2) != 1) return false;
+  return compare_tag(tag, &tag2);
+}
+
+// Create an empty tag_set.
+static void empty_test(void) {
+  struct census_tag_set *cts = census_tag_set_create(NULL, NULL, 0);
+  GPR_ASSERT(census_tag_set_ntags(cts) == 0);
+  census_tag_set_destroy(cts);
+}
+
+// Create basic tag set, and test that retreiving tag by index works.
+static void basic_test(void) {
+  struct census_tag_set *cts =
+      census_tag_set_create(NULL, basic_tags, BASIC_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts) == BASIC_TAG_COUNT);
+  for (int i = 0; i < census_tag_set_ntags(cts); i++) {
+    census_tag tag;
+    GPR_ASSERT(census_tag_set_get_tag_by_index(cts, i, &tag) == 1);
+    // can't rely on tag return order: make sure it matches exactly one.
+    int matches = 0;
+    for (int j = 0; j < BASIC_TAG_COUNT; j++) {
+      if (compare_tag(&tag, &basic_tags[j])) matches++;
+    }
+    GPR_ASSERT(matches == 1);
+  }
+  census_tag_set_destroy(cts);
+}
+
+// Try census_tag_set_get_tag_by_index() with bad indices.
+static void bad_index_test(void) {
+  struct census_tag_set *cts =
+      census_tag_set_create(NULL, basic_tags, BASIC_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts) == BASIC_TAG_COUNT);
+  census_tag tag;
+  GPR_ASSERT(census_tag_set_get_tag_by_index(cts, -1, &tag) == 0);
+  GPR_ASSERT(census_tag_set_get_tag_by_index(cts, BASIC_TAG_COUNT, &tag) == 0);
+  GPR_ASSERT(census_tag_set_get_tag_by_index(cts, BASIC_TAG_COUNT + 1, &tag) ==
+             0);
+  census_tag_set_destroy(cts);
+}
+
+// Test that census_tag_set_get_tag_by_key().
+static void lookup_by_key_test(void) {
+  struct census_tag_set *cts =
+      census_tag_set_create(NULL, basic_tags, BASIC_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts) == BASIC_TAG_COUNT);
+  census_tag tag;
+  for (int i = 0; i < census_tag_set_ntags(cts); i++) {
+    GPR_ASSERT(census_tag_set_get_tag_by_key(cts, basic_tags[i].key, &tag) ==
+               1);
+    GPR_ASSERT(compare_tag(&tag, &basic_tags[i]));
+  }
+  // non-existent keys
+  GPR_ASSERT(census_tag_set_get_tag_by_key(cts, "key", &tag) == 0);
+  GPR_ASSERT(census_tag_set_get_tag_by_key(cts, "key01", &tag) == 0);
+  GPR_ASSERT(census_tag_set_get_tag_by_key(cts, "k9", &tag) == 0);
+  GPR_ASSERT(census_tag_set_get_tag_by_key(cts, "random", &tag) == 0);
+  GPR_ASSERT(census_tag_set_get_tag_by_key(cts, "", &tag) == 0);
+  census_tag_set_destroy(cts);
+}
+
+// Try creating tag set with invalid entries.
+static void invalid_test(void) {
+  char key[300];
+  memset(key, 'k', 299);
+  key[299] = 0;
+  char value[300];
+  memset(value, 'v', 300);
+  census_tag tag = {key, value, 3, CENSUS_TAG_BINARY};
+  // long keys, short value. Key lengths (including terminator) should be
+  // <= 255 (CENSUS_MAX_TAG_KV_LEN)
+  GPR_ASSERT(strlen(key) == 299);
+  struct census_tag_set *cts = census_tag_set_create(NULL, &tag, 1);
+  GPR_ASSERT(census_tag_set_ntags(cts) == 0);
+  census_tag_set_destroy(cts);
+  key[CENSUS_MAX_TAG_KV_LEN] = 0;
+  GPR_ASSERT(strlen(key) == CENSUS_MAX_TAG_KV_LEN);
+  cts = census_tag_set_create(NULL, &tag, 1);
+  GPR_ASSERT(census_tag_set_ntags(cts) == 0);
+  census_tag_set_destroy(cts);
+  key[CENSUS_MAX_TAG_KV_LEN - 1] = 0;
+  GPR_ASSERT(strlen(key) == CENSUS_MAX_TAG_KV_LEN - 1);
+  cts = census_tag_set_create(NULL, &tag, 1);
+  GPR_ASSERT(census_tag_set_ntags(cts) == 1);
+  census_tag_set_destroy(cts);
+  // now try with long values
+  tag.value_len = 300;
+  cts = census_tag_set_create(NULL, &tag, 1);
+  GPR_ASSERT(census_tag_set_ntags(cts) == 0);
+  census_tag_set_destroy(cts);
+  tag.value_len = CENSUS_MAX_TAG_KV_LEN + 1;
+  cts = census_tag_set_create(NULL, &tag, 1);
+  GPR_ASSERT(census_tag_set_ntags(cts) == 0);
+  census_tag_set_destroy(cts);
+  tag.value_len = CENSUS_MAX_TAG_KV_LEN;
+  cts = census_tag_set_create(NULL, &tag, 1);
+  GPR_ASSERT(census_tag_set_ntags(cts) == 1);
+  census_tag_set_destroy(cts);
+  // 0 length key.
+  key[0] = 0;
+  cts = census_tag_set_create(NULL, &tag, 1);
+  GPR_ASSERT(census_tag_set_ntags(cts) == 0);
+  census_tag_set_destroy(cts);
+}
+
+// Make a copy of a tag set
+static void copy_test(void) {
+  struct census_tag_set *cts =
+      census_tag_set_create(NULL, basic_tags, BASIC_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts) == BASIC_TAG_COUNT);
+  struct census_tag_set *cts2 = census_tag_set_create(cts, NULL, 0);
+  GPR_ASSERT(census_tag_set_ntags(cts2) == BASIC_TAG_COUNT);
+  for (int i = 0; i < census_tag_set_ntags(cts2); i++) {
+    census_tag tag;
+    GPR_ASSERT(census_tag_set_get_tag_by_key(cts2, basic_tags[i].key, &tag) ==
+               1);
+    GPR_ASSERT(compare_tag(&tag, &basic_tags[i]));
+  }
+  census_tag_set_destroy(cts);
+  census_tag_set_destroy(cts2);
+}
+
+// replace a single tag value
+static void replace_value_test(void) {
+  struct census_tag_set *cts =
+      census_tag_set_create(NULL, basic_tags, BASIC_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts) == BASIC_TAG_COUNT);
+  struct census_tag_set *cts2 =
+      census_tag_set_create(cts, modify_tags + REPLACE_VALUE_OFFSET, 1);
+  GPR_ASSERT(census_tag_set_ntags(cts2) == BASIC_TAG_COUNT);
+  census_tag tag;
+  GPR_ASSERT(census_tag_set_get_tag_by_key(
+                 cts2, modify_tags[REPLACE_VALUE_OFFSET].key, &tag) == 1);
+  GPR_ASSERT(compare_tag(&tag, &modify_tags[REPLACE_VALUE_OFFSET]));
+  census_tag_set_destroy(cts);
+  census_tag_set_destroy(cts2);
+}
+
+// replace a single tags flags
+static void replace_flags_test(void) {
+  struct census_tag_set *cts =
+      census_tag_set_create(NULL, basic_tags, BASIC_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts) == BASIC_TAG_COUNT);
+  struct census_tag_set *cts2 =
+      census_tag_set_create(cts, modify_tags + REPLACE_FLAG_OFFSET, 1);
+  GPR_ASSERT(census_tag_set_ntags(cts2) == BASIC_TAG_COUNT);
+  census_tag tag;
+  GPR_ASSERT(census_tag_set_get_tag_by_key(
+                 cts2, modify_tags[REPLACE_FLAG_OFFSET].key, &tag) == 1);
+  GPR_ASSERT(compare_tag(&tag, &modify_tags[REPLACE_FLAG_OFFSET]));
+  census_tag_set_destroy(cts);
+  census_tag_set_destroy(cts2);
+}
+
+// delete a single tag.
+static void delete_tag_test(void) {
+  struct census_tag_set *cts =
+      census_tag_set_create(NULL, basic_tags, BASIC_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts) == BASIC_TAG_COUNT);
+  struct census_tag_set *cts2 =
+      census_tag_set_create(cts, modify_tags + DELETE_TAG_OFFSET, 1);
+  GPR_ASSERT(census_tag_set_ntags(cts2) == BASIC_TAG_COUNT - 1);
+  census_tag tag;
+  GPR_ASSERT(census_tag_set_get_tag_by_key(
+                 cts2, modify_tags[DELETE_TAG_OFFSET].key, &tag) == 0);
+  census_tag_set_destroy(cts);
+  census_tag_set_destroy(cts2);
+}
+
+// add a single new tag.
+static void add_tag_test(void) {
+  struct census_tag_set *cts =
+      census_tag_set_create(NULL, basic_tags, BASIC_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts) == BASIC_TAG_COUNT);
+  struct census_tag_set *cts2 =
+      census_tag_set_create(cts, modify_tags + ADD_TAG_OFFSET, 1);
+  GPR_ASSERT(census_tag_set_ntags(cts2) == BASIC_TAG_COUNT + 1);
+  census_tag tag;
+  GPR_ASSERT(census_tag_set_get_tag_by_key(
+                 cts2, modify_tags[ADD_TAG_OFFSET].key, &tag) == 1);
+  GPR_ASSERT(compare_tag(&tag, &modify_tags[ADD_TAG_OFFSET]));
+  census_tag_set_destroy(cts);
+  census_tag_set_destroy(cts2);
+}
+
+// test many changes at once.
+static void replace_add_delete_test(void) {
+  struct census_tag_set *cts =
+      census_tag_set_create(NULL, basic_tags, BASIC_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts) == BASIC_TAG_COUNT);
+  struct census_tag_set *cts2 =
+      census_tag_set_create(cts, modify_tags, MODIFY_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts2) == 8);
+  // validate tag set contents. Use specific indices into the two arrays
+  // holding tag values.
+  GPR_ASSERT(validate_tag(cts2, &basic_tags[3]));
+  GPR_ASSERT(validate_tag(cts2, &basic_tags[4]));
+  GPR_ASSERT(validate_tag(cts2, &modify_tags[0]));
+  GPR_ASSERT(validate_tag(cts2, &modify_tags[1]));
+  GPR_ASSERT(validate_tag(cts2, &modify_tags[6]));
+  GPR_ASSERT(validate_tag(cts2, &modify_tags[7]));
+  GPR_ASSERT(validate_tag(cts2, &modify_tags[8]));
+  GPR_ASSERT(validate_tag(cts2, &modify_tags[9]));
+  GPR_ASSERT(!validate_tag(cts2, &basic_tags[0]));
+  GPR_ASSERT(!validate_tag(cts2, &basic_tags[1]));
+  GPR_ASSERT(!validate_tag(cts2, &basic_tags[2]));
+  GPR_ASSERT(!validate_tag(cts2, &basic_tags[5]));
+  GPR_ASSERT(!validate_tag(cts2, &basic_tags[6]));
+  GPR_ASSERT(!validate_tag(cts2, &basic_tags[7]));
+  census_tag_set_destroy(cts);
+  census_tag_set_destroy(cts2);
+}
+
+// Use the basic tag set to test encode/decode.
+static void simple_encode_decode_test(void) {
+  char buf1[1000];
+  char buf2[1000];
+  struct census_tag_set *cts =
+      census_tag_set_create(NULL, basic_tags, BASIC_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts) == BASIC_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_encode_propagated(cts, buf1, 1) == 0);
+  size_t b1 = census_tag_set_encode_propagated(cts, buf1, 1000);
+  GPR_ASSERT(b1 != 0);
+  GPR_ASSERT(census_tag_set_encode_propagated_binary(cts, buf2, 1) == 0);
+  size_t b2 = census_tag_set_encode_propagated_binary(cts, buf2, 1000);
+  GPR_ASSERT(b2 != 0);
+  census_tag_set *cts2 = census_tag_set_decode(buf1, b1, buf2, b2);
+  GPR_ASSERT(cts2 != NULL);
+  GPR_ASSERT(census_tag_set_ntags(cts2) == 4);
+  for (int i = 0; i < census_tag_set_ntags(cts); i++) {
+    census_tag tag;
+    if (CENSUS_TAG_IS_PROPAGATED(basic_tags[i].flags)) {
+      GPR_ASSERT(census_tag_set_get_tag_by_key(cts2, basic_tags[i].key, &tag) ==
+                 1);
+      GPR_ASSERT(compare_tag(&tag, &basic_tags[i]));
+    } else {
+      GPR_ASSERT(census_tag_set_get_tag_by_key(cts2, basic_tags[i].key, &tag) ==
+                 0);
+    }
+  }
+  census_tag_set_destroy(cts2);
+  census_tag_set_destroy(cts);
+}
+
+// Use more complex/modified tag set to test encode/decode.
+static void complex_encode_decode_test(void) {
+  char buf1[500];
+  char buf2[500];
+  struct census_tag_set *cts =
+      census_tag_set_create(NULL, basic_tags, BASIC_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts) == BASIC_TAG_COUNT);
+  struct census_tag_set *cts2 =
+      census_tag_set_create(cts, modify_tags, MODIFY_TAG_COUNT);
+  GPR_ASSERT(census_tag_set_ntags(cts2) == 8);
+
+  size_t b1 = census_tag_set_encode_propagated(cts2, buf1, 500);
+  GPR_ASSERT(b1 != 0);
+  size_t b2 = census_tag_set_encode_propagated_binary(cts2, buf2, 500);
+  GPR_ASSERT(b2 != 0);
+  census_tag_set *cts3 = census_tag_set_decode(buf1, b1, buf2, b2);
+  GPR_ASSERT(cts3 != NULL);
+  GPR_ASSERT(census_tag_set_ntags(cts3) == 2);
+  GPR_ASSERT(validate_tag(cts3, &basic_tags[4]));
+  GPR_ASSERT(validate_tag(cts3, &modify_tags[8]));
+  // Now force tag set to be in smaller space
+  census_tag_set_destroy(cts3);
+  size_t nb1 = census_tag_set_encode_propagated(cts2, buf1, b1 - 1);
+  GPR_ASSERT(nb1 != 0);
+  GPR_ASSERT(nb1 < b1);
+  size_t nb2 = census_tag_set_encode_propagated_binary(cts2, buf2, b2 - 1);
+  GPR_ASSERT(nb2 != 0);
+  GPR_ASSERT(nb2 < b2);
+  cts3 = census_tag_set_decode(buf1, nb1, buf2, nb2);
+  GPR_ASSERT(cts3 != NULL);
+  GPR_ASSERT(census_tag_set_ntags(cts3) == 2);
+  GPR_ASSERT(validate_tag(cts3, &basic_tags[4]));
+  GPR_ASSERT(validate_tag(cts3, &modify_tags[8]));
+  census_tag_set_destroy(cts3);
+  census_tag_set_destroy(cts2);
+  census_tag_set_destroy(cts);
+}
+
+int main(int argc, char *argv[]) {
+  grpc_test_init(argc, argv);
+  empty_test();
+  basic_test();
+  bad_index_test();
+  lookup_by_key_test();
+  invalid_test();
+  copy_test();
+  replace_value_test();
+  replace_flags_test();
+  delete_tag_test();
+  add_tag_test();
+  replace_add_delete_test();
+  simple_encode_decode_test();
+  complex_encode_decode_test();
+  return 0;
+}
diff --git a/tools/doxygen/Doxyfile.core.internal b/tools/doxygen/Doxyfile.core.internal
index aef5bec..ac57dd0 100644
--- a/tools/doxygen/Doxyfile.core.internal
+++ b/tools/doxygen/Doxyfile.core.internal
@@ -897,6 +897,7 @@
 src/core/census/aggregation.h \
 src/core/census/context.h \
 src/core/census/rpc_metric_id.h \
+src/core/census/tag_set.h \
 src/core/httpcli/httpcli_security_connector.c \
 src/core/security/base64.c \
 src/core/security/client_auth_filter.c \
@@ -1046,6 +1047,7 @@
 src/core/census/context.c \
 src/core/census/initialize.c \
 src/core/census/operation.c \
+src/core/census/tag_set.c \
 src/core/census/tracing.c \
 include/grpc/support/alloc.h \
 include/grpc/support/atm.h \
diff --git a/tools/run_tests/sources_and_headers.json b/tools/run_tests/sources_and_headers.json
index a1beafd..529a417 100644
--- a/tools/run_tests/sources_and_headers.json
+++ b/tools/run_tests/sources_and_headers.json
@@ -1098,6 +1098,20 @@
     ], 
     "headers": [], 
     "language": "c", 
+    "name": "tag_set_test", 
+    "src": [
+      "test/core/census/tag_set_test.c"
+    ]
+  }, 
+  {
+    "deps": [
+      "gpr", 
+      "gpr_test_util", 
+      "grpc", 
+      "grpc_test_util"
+    ], 
+    "headers": [], 
+    "language": "c", 
     "name": "tcp_client_posix_test", 
     "src": [
       "test/core/iomgr/tcp_client_posix_test.c"
@@ -2845,6 +2859,7 @@
       "src/core/census/context.h", 
       "src/core/census/grpc_filter.h", 
       "src/core/census/rpc_metric_id.h", 
+      "src/core/census/tag_set.h", 
       "src/core/channel/channel_args.h", 
       "src/core/channel/channel_stack.h", 
       "src/core/channel/client_channel.h", 
@@ -2991,6 +3006,8 @@
       "src/core/census/initialize.c", 
       "src/core/census/operation.c", 
       "src/core/census/rpc_metric_id.h", 
+      "src/core/census/tag_set.c", 
+      "src/core/census/tag_set.h", 
       "src/core/census/tracing.c", 
       "src/core/channel/channel_args.c", 
       "src/core/channel/channel_args.h", 
@@ -3357,6 +3374,7 @@
       "src/core/census/context.h", 
       "src/core/census/grpc_filter.h", 
       "src/core/census/rpc_metric_id.h", 
+      "src/core/census/tag_set.h", 
       "src/core/channel/channel_args.h", 
       "src/core/channel/channel_stack.h", 
       "src/core/channel/client_channel.h", 
@@ -3488,6 +3506,8 @@
       "src/core/census/initialize.c", 
       "src/core/census/operation.c", 
       "src/core/census/rpc_metric_id.h", 
+      "src/core/census/tag_set.c", 
+      "src/core/census/tag_set.h", 
       "src/core/census/tracing.c", 
       "src/core/channel/channel_args.c", 
       "src/core/channel/channel_args.h", 
diff --git a/tools/run_tests/tests.json b/tools/run_tests/tests.json
index 0b5f847..a8398eb 100644
--- a/tools/run_tests/tests.json
+++ b/tools/run_tests/tests.json
@@ -1333,6 +1333,25 @@
     "ci_platforms": [
       "linux", 
       "mac", 
+      "posix", 
+      "windows"
+    ], 
+    "exclude_configs": [], 
+    "flaky": false, 
+    "language": "c", 
+    "name": "tag_set_test", 
+    "platforms": [
+      "linux", 
+      "mac", 
+      "posix", 
+      "windows"
+    ]
+  }, 
+  {
+    "args": [], 
+    "ci_platforms": [
+      "linux", 
+      "mac", 
       "posix"
     ], 
     "exclude_configs": [], 
diff --git a/vsprojects/buildtests_c.sln b/vsprojects/buildtests_c.sln
index 06e882e..592b398 100644
--- a/vsprojects/buildtests_c.sln
+++ b/vsprojects/buildtests_c.sln
@@ -848,6 +848,17 @@
 		{B23D3D1A-9438-4EDA-BEB6-9A0A03D17792} = {B23D3D1A-9438-4EDA-BEB6-9A0A03D17792}
 	EndProjectSection
 EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "tag_set_test", "vcxproj\test\tag_set_test\tag_set_test.vcxproj", "{430F8F07-6AAD-0150-B35B-DB9E2E21941A}"
+	ProjectSection(myProperties) = preProject
+        	lib = "False"
+	EndProjectSection
+	ProjectSection(ProjectDependencies) = postProject
+		{17BCAFC0-5FDC-4C94-AEB9-95F3E220614B} = {17BCAFC0-5FDC-4C94-AEB9-95F3E220614B}
+		{29D16885-7228-4C31-81ED-5F9187C7F2A9} = {29D16885-7228-4C31-81ED-5F9187C7F2A9}
+		{EAB0A629-17A9-44DB-B5FF-E91A721FE037} = {EAB0A629-17A9-44DB-B5FF-E91A721FE037}
+		{B23D3D1A-9438-4EDA-BEB6-9A0A03D17792} = {B23D3D1A-9438-4EDA-BEB6-9A0A03D17792}
+	EndProjectSection
+EndProject
 Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "time_averaged_stats_test", "vcxproj\test\time_averaged_stats_test\time_averaged_stats_test.vcxproj", "{D1EB2A9B-8508-62D7-8FC4-11A11B1CBFD3}"
 	ProjectSection(myProperties) = preProject
         	lib = "False"
@@ -2624,6 +2635,22 @@
 		{529771F0-10B0-9B1A-1E7E-8A8E01870348}.Release-DLL|Win32.Build.0 = Release|Win32
 		{529771F0-10B0-9B1A-1E7E-8A8E01870348}.Release-DLL|x64.ActiveCfg = Release|x64
 		{529771F0-10B0-9B1A-1E7E-8A8E01870348}.Release-DLL|x64.Build.0 = Release|x64
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Debug|Win32.ActiveCfg = Debug|Win32
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Debug|x64.ActiveCfg = Debug|x64
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Release|Win32.ActiveCfg = Release|Win32
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Release|x64.ActiveCfg = Release|x64
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Debug|Win32.Build.0 = Debug|Win32
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Debug|x64.Build.0 = Debug|x64
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Release|Win32.Build.0 = Release|Win32
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Release|x64.Build.0 = Release|x64
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Debug-DLL|Win32.ActiveCfg = Debug|Win32
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Debug-DLL|Win32.Build.0 = Debug|Win32
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Debug-DLL|x64.ActiveCfg = Debug|x64
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Debug-DLL|x64.Build.0 = Debug|x64
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Release-DLL|Win32.ActiveCfg = Release|Win32
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Release-DLL|Win32.Build.0 = Release|Win32
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Release-DLL|x64.ActiveCfg = Release|x64
+		{430F8F07-6AAD-0150-B35B-DB9E2E21941A}.Release-DLL|x64.Build.0 = Release|x64
 		{D1EB2A9B-8508-62D7-8FC4-11A11B1CBFD3}.Debug|Win32.ActiveCfg = Debug|Win32
 		{D1EB2A9B-8508-62D7-8FC4-11A11B1CBFD3}.Debug|x64.ActiveCfg = Debug|x64
 		{D1EB2A9B-8508-62D7-8FC4-11A11B1CBFD3}.Release|Win32.ActiveCfg = Release|Win32
diff --git a/vsprojects/vcxproj/grpc/grpc.vcxproj b/vsprojects/vcxproj/grpc/grpc.vcxproj
index 9d64615..037b8ff 100644
--- a/vsprojects/vcxproj/grpc/grpc.vcxproj
+++ b/vsprojects/vcxproj/grpc/grpc.vcxproj
@@ -404,6 +404,7 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\census\aggregation.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\census\context.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\census\rpc_metric_id.h" />
+    <ClInclude Include="$(SolutionDir)\..\src\core\census\tag_set.h" />
   </ItemGroup>
   <ItemGroup>
     <ClCompile Include="$(SolutionDir)\..\src\core\httpcli\httpcli_security_connector.c">
@@ -704,6 +705,8 @@
     </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\census\operation.c">
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\census\tag_set.c">
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\census\tracing.c">
     </ClCompile>
   </ItemGroup>
diff --git a/vsprojects/vcxproj/grpc/grpc.vcxproj.filters b/vsprojects/vcxproj/grpc/grpc.vcxproj.filters
index 055256a..0ddbd5e 100644
--- a/vsprojects/vcxproj/grpc/grpc.vcxproj.filters
+++ b/vsprojects/vcxproj/grpc/grpc.vcxproj.filters
@@ -448,6 +448,9 @@
     <ClCompile Include="$(SolutionDir)\..\src\core\census\operation.c">
       <Filter>src\core\census</Filter>
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\census\tag_set.c">
+      <Filter>src\core\census</Filter>
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\census\tracing.c">
       <Filter>src\core\census</Filter>
     </ClCompile>
@@ -866,6 +869,9 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\census\rpc_metric_id.h">
       <Filter>src\core\census</Filter>
     </ClInclude>
+    <ClInclude Include="$(SolutionDir)\..\src\core\census\tag_set.h">
+      <Filter>src\core\census</Filter>
+    </ClInclude>
   </ItemGroup>
 
   <ItemGroup>
diff --git a/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj b/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj
index b296521..a3532e5 100644
--- a/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj
+++ b/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj
@@ -382,6 +382,7 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\census\aggregation.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\census\context.h" />
     <ClInclude Include="$(SolutionDir)\..\src\core\census\rpc_metric_id.h" />
+    <ClInclude Include="$(SolutionDir)\..\src\core\census\tag_set.h" />
   </ItemGroup>
   <ItemGroup>
     <ClCompile Include="$(SolutionDir)\..\src\core\surface\init_unsecure.c">
@@ -642,6 +643,8 @@
     </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\census\operation.c">
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\census\tag_set.c">
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\census\tracing.c">
     </ClCompile>
   </ItemGroup>
diff --git a/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj.filters b/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj.filters
index e30ca5f..f63e301 100644
--- a/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj.filters
+++ b/vsprojects/vcxproj/grpc_unsecure/grpc_unsecure.vcxproj.filters
@@ -388,6 +388,9 @@
     <ClCompile Include="$(SolutionDir)\..\src\core\census\operation.c">
       <Filter>src\core\census</Filter>
     </ClCompile>
+    <ClCompile Include="$(SolutionDir)\..\src\core\census\tag_set.c">
+      <Filter>src\core\census</Filter>
+    </ClCompile>
     <ClCompile Include="$(SolutionDir)\..\src\core\census\tracing.c">
       <Filter>src\core\census</Filter>
     </ClCompile>
@@ -761,6 +764,9 @@
     <ClInclude Include="$(SolutionDir)\..\src\core\census\rpc_metric_id.h">
       <Filter>src\core\census</Filter>
     </ClInclude>
+    <ClInclude Include="$(SolutionDir)\..\src\core\census\tag_set.h">
+      <Filter>src\core\census</Filter>
+    </ClInclude>
   </ItemGroup>
 
   <ItemGroup>
diff --git a/vsprojects/vcxproj/test/tag_set_test/tag_set_test.vcxproj b/vsprojects/vcxproj/test/tag_set_test/tag_set_test.vcxproj
new file mode 100644
index 0000000..3894902
--- /dev/null
+++ b/vsprojects/vcxproj/test/tag_set_test/tag_set_test.vcxproj
@@ -0,0 +1,197 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project DefaultTargets="Build" ToolsVersion="12.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <Import Project="$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.openssl.1.0.204.1\build\native\grpc.dependencies.openssl.props" Condition="Exists('$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.openssl.1.0.204.1\build\native\1.0.204.1.props')" />
+  <ItemGroup Label="ProjectConfigurations">
+    <ProjectConfiguration Include="Debug|Win32">
+      <Configuration>Debug</Configuration>
+      <Platform>Win32</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="Debug|x64">
+      <Configuration>Debug</Configuration>
+      <Platform>x64</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="Release|Win32">
+      <Configuration>Release</Configuration>
+      <Platform>Win32</Platform>
+    </ProjectConfiguration>
+    <ProjectConfiguration Include="Release|x64">
+      <Configuration>Release</Configuration>
+      <Platform>x64</Platform>
+    </ProjectConfiguration>
+  </ItemGroup>
+  <PropertyGroup Label="Globals">
+    <ProjectGuid>{430F8F07-6AAD-0150-B35B-DB9E2E21941A}</ProjectGuid>
+    <IgnoreWarnIntDirInTempDetected>true</IgnoreWarnIntDirInTempDetected>
+    <IntDir>$(SolutionDir)IntDir\$(MSBuildProjectName)\</IntDir>
+  </PropertyGroup>
+  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.Default.props" />
+  <PropertyGroup Condition="'$(VisualStudioVersion)' == '10.0'" Label="Configuration">
+    <PlatformToolset>v100</PlatformToolset>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(VisualStudioVersion)' == '11.0'" Label="Configuration">
+    <PlatformToolset>v110</PlatformToolset>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(VisualStudioVersion)' == '12.0'" Label="Configuration">
+    <PlatformToolset>v120</PlatformToolset>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(VisualStudioVersion)' == '14.0'" Label="Configuration">
+    <PlatformToolset>v140</PlatformToolset>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)'=='Debug'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>true</UseDebugLibraries>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)'=='Release'" Label="Configuration">
+    <ConfigurationType>Application</ConfigurationType>
+    <UseDebugLibraries>false</UseDebugLibraries>
+    <WholeProgramOptimization>true</WholeProgramOptimization>
+    <CharacterSet>Unicode</CharacterSet>
+  </PropertyGroup>
+  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.props" />
+  <ImportGroup Label="ExtensionSettings">
+  </ImportGroup>
+  <ImportGroup Label="PropertySheets">
+    <Import Project="$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props" Condition="exists('$(UserRootDir)\Microsoft.Cpp.$(Platform).user.props')" Label="LocalAppDataPlatform" />
+    <Import Project="$(SolutionDir)\..\vsprojects\global.props" />
+    <Import Project="$(SolutionDir)\..\vsprojects\openssl.props" />
+    <Import Project="$(SolutionDir)\..\vsprojects\winsock.props" />
+    <Import Project="$(SolutionDir)\..\vsprojects\zlib.props" />
+  </ImportGroup>
+  <PropertyGroup Label="UserMacros" />
+  <PropertyGroup Condition="'$(Configuration)'=='Debug'">
+    <TargetName>tag_set_test</TargetName>
+    <Linkage-grpc_dependencies_zlib>static</Linkage-grpc_dependencies_zlib>
+    <Configuration-grpc_dependencies_zlib>Debug</Configuration-grpc_dependencies_zlib>
+    <Configuration-grpc_dependencies_openssl>Debug</Configuration-grpc_dependencies_openssl>
+  </PropertyGroup>
+  <PropertyGroup Condition="'$(Configuration)'=='Release'">
+    <TargetName>tag_set_test</TargetName>
+    <Linkage-grpc_dependencies_zlib>static</Linkage-grpc_dependencies_zlib>
+    <Configuration-grpc_dependencies_zlib>Release</Configuration-grpc_dependencies_zlib>
+    <Configuration-grpc_dependencies_openssl>Release</Configuration-grpc_dependencies_openssl>
+  </PropertyGroup>
+    <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|Win32'">
+    <ClCompile>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <WarningLevel>Level3</WarningLevel>
+      <Optimization>Disabled</Optimization>
+      <PreprocessorDefinitions>WIN32;_DEBUG;_LIB;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <SDLCheck>true</SDLCheck>
+      <RuntimeLibrary>MultiThreadedDebug</RuntimeLibrary>
+      <TreatWarningAsError>true</TreatWarningAsError>
+      <DebugInformationFormat Condition="$(Jenkins)">None</DebugInformationFormat>
+      <MinimalRebuild Condition="$(Jenkins)">false</MinimalRebuild>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <GenerateDebugInformation Condition="!$(Jenkins)">true</GenerateDebugInformation>
+      <GenerateDebugInformation Condition="$(Jenkins)">false</GenerateDebugInformation>
+    </Link>
+  </ItemDefinitionGroup>
+
+    <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Debug|x64'">
+    <ClCompile>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <WarningLevel>Level3</WarningLevel>
+      <Optimization>Disabled</Optimization>
+      <PreprocessorDefinitions>WIN32;_DEBUG;_LIB;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <SDLCheck>true</SDLCheck>
+      <RuntimeLibrary>MultiThreadedDebug</RuntimeLibrary>
+      <TreatWarningAsError>true</TreatWarningAsError>
+      <DebugInformationFormat Condition="$(Jenkins)">None</DebugInformationFormat>
+      <MinimalRebuild Condition="$(Jenkins)">false</MinimalRebuild>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <GenerateDebugInformation Condition="!$(Jenkins)">true</GenerateDebugInformation>
+      <GenerateDebugInformation Condition="$(Jenkins)">false</GenerateDebugInformation>
+    </Link>
+  </ItemDefinitionGroup>
+
+    <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|Win32'">
+    <ClCompile>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <WarningLevel>Level3</WarningLevel>
+      <Optimization>MaxSpeed</Optimization>
+      <PreprocessorDefinitions>WIN32;NDEBUG;_LIB;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <FunctionLevelLinking>true</FunctionLevelLinking>
+      <IntrinsicFunctions>true</IntrinsicFunctions>
+      <SDLCheck>true</SDLCheck>
+      <RuntimeLibrary>MultiThreaded</RuntimeLibrary>
+      <TreatWarningAsError>true</TreatWarningAsError>
+      <DebugInformationFormat Condition="$(Jenkins)">None</DebugInformationFormat>
+      <MinimalRebuild Condition="$(Jenkins)">false</MinimalRebuild>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <GenerateDebugInformation Condition="!$(Jenkins)">true</GenerateDebugInformation>
+      <GenerateDebugInformation Condition="$(Jenkins)">false</GenerateDebugInformation>
+      <EnableCOMDATFolding>true</EnableCOMDATFolding>
+      <OptimizeReferences>true</OptimizeReferences>
+    </Link>
+  </ItemDefinitionGroup>
+
+    <ItemDefinitionGroup Condition="'$(Configuration)|$(Platform)'=='Release|x64'">
+    <ClCompile>
+      <PrecompiledHeader>NotUsing</PrecompiledHeader>
+      <WarningLevel>Level3</WarningLevel>
+      <Optimization>MaxSpeed</Optimization>
+      <PreprocessorDefinitions>WIN32;NDEBUG;_LIB;%(PreprocessorDefinitions)</PreprocessorDefinitions>
+      <FunctionLevelLinking>true</FunctionLevelLinking>
+      <IntrinsicFunctions>true</IntrinsicFunctions>
+      <SDLCheck>true</SDLCheck>
+      <RuntimeLibrary>MultiThreaded</RuntimeLibrary>
+      <TreatWarningAsError>true</TreatWarningAsError>
+      <DebugInformationFormat Condition="$(Jenkins)">None</DebugInformationFormat>
+      <MinimalRebuild Condition="$(Jenkins)">false</MinimalRebuild>
+    </ClCompile>
+    <Link>
+      <SubSystem>Console</SubSystem>
+      <GenerateDebugInformation Condition="!$(Jenkins)">true</GenerateDebugInformation>
+      <GenerateDebugInformation Condition="$(Jenkins)">false</GenerateDebugInformation>
+      <EnableCOMDATFolding>true</EnableCOMDATFolding>
+      <OptimizeReferences>true</OptimizeReferences>
+    </Link>
+  </ItemDefinitionGroup>
+
+  <ItemGroup>
+    <ClCompile Include="$(SolutionDir)\..\test\core\census\tag_set_test.c">
+    </ClCompile>
+  </ItemGroup>
+  <ItemGroup>
+    <ProjectReference Include="$(SolutionDir)\..\vsprojects\vcxproj\.\grpc_test_util\grpc_test_util.vcxproj">
+      <Project>{17BCAFC0-5FDC-4C94-AEB9-95F3E220614B}</Project>
+    </ProjectReference>
+    <ProjectReference Include="$(SolutionDir)\..\vsprojects\vcxproj\.\grpc\grpc.vcxproj">
+      <Project>{29D16885-7228-4C31-81ED-5F9187C7F2A9}</Project>
+    </ProjectReference>
+    <ProjectReference Include="$(SolutionDir)\..\vsprojects\vcxproj\.\gpr_test_util\gpr_test_util.vcxproj">
+      <Project>{EAB0A629-17A9-44DB-B5FF-E91A721FE037}</Project>
+    </ProjectReference>
+    <ProjectReference Include="$(SolutionDir)\..\vsprojects\vcxproj\.\gpr\gpr.vcxproj">
+      <Project>{B23D3D1A-9438-4EDA-BEB6-9A0A03D17792}</Project>
+    </ProjectReference>
+  </ItemGroup>
+  <ItemGroup>
+    <None Include="packages.config" />
+  </ItemGroup>
+  <Import Project="$(VCTargetsPath)\Microsoft.Cpp.targets" />
+  <ImportGroup Label="ExtensionTargets">
+  <Import Project="$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.zlib.redist.1.2.8.10\build\native\grpc.dependencies.zlib.redist.targets" Condition="Exists('$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.zlib.redist.1.2.8.10\build\native\grpc.dependencies\grpc.dependencies.zlib.targets')" />
+  <Import Project="$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.zlib.1.2.8.10\build\native\grpc.dependencies.zlib.targets" Condition="Exists('$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.zlib.1.2.8.10\build\native\grpc.dependencies\grpc.dependencies.zlib.targets')" />
+  <Import Project="$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.openssl.redist.1.0.204.1\build\native\grpc.dependencies.openssl.redist.targets" Condition="Exists('$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.openssl.redist.1.0.204.1\build\native\grpc.dependencies\grpc.dependencies.openssl.targets')" />
+  <Import Project="$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.openssl.1.0.204.1\build\native\grpc.dependencies.openssl.targets" Condition="Exists('$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.openssl.1.0.204.1\build\native\grpc.dependencies\grpc.dependencies.openssl.targets')" />
+  </ImportGroup>
+  <Target Name="EnsureNuGetPackageBuildImports" BeforeTargets="PrepareForBuild">
+    <PropertyGroup>
+      <ErrorText>This project references NuGet package(s) that are missing on this computer. Enable NuGet Package Restore to download them.  For more information, see http://go.microsoft.com/fwlink/?LinkID=322105. The missing file is {0}.</ErrorText>
+    </PropertyGroup>
+    <Error Condition="!Exists('$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.zlib.redist.1.2.8.10\build\native\grpc.dependencies.zlib.redist.targets')" Text="$([System.String]::Format('$(ErrorText)', '$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.zlib.redist.1.2.8.10\build\native\grpc.dependencies.zlib.redist.targets')" />
+    <Error Condition="!Exists('$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.zlib.1.2.8.10\build\native\grpc.dependencies.zlib.targets')" Text="$([System.String]::Format('$(ErrorText)', '$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.zlib.1.2.8.10\build\native\grpc.dependencies.zlib.targets')" />
+    <Error Condition="!Exists('$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.openssl.redist.1.0.204.1\build\native\grpc.dependencies.openssl.redist.targets')" Text="$([System.String]::Format('$(ErrorText)', '$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.openssl.redist.1.0.204.1\build\native\grpc.dependencies.openssl.redist.targets')" />
+    <Error Condition="!Exists('$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.openssl.1.0.204.1\build\native\grpc.dependencies.openssl.props')" Text="$([System.String]::Format('$(ErrorText)', '$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.openssl.1.0.204.1\build\native\grpc.dependencies.openssl.props')" />
+    <Error Condition="!Exists('$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.openssl.1.0.204.1\build\native\grpc.dependencies.openssl.targets')" Text="$([System.String]::Format('$(ErrorText)', '$(SolutionDir)\..\vsprojects\packages\grpc.dependencies.openssl.1.0.204.1\build\native\grpc.dependencies.openssl.targets')" />
+  </Target>
+</Project>
+
diff --git a/vsprojects/vcxproj/test/tag_set_test/tag_set_test.vcxproj.filters b/vsprojects/vcxproj/test/tag_set_test/tag_set_test.vcxproj.filters
new file mode 100644
index 0000000..6b31532
--- /dev/null
+++ b/vsprojects/vcxproj/test/tag_set_test/tag_set_test.vcxproj.filters
@@ -0,0 +1,21 @@
+<?xml version="1.0" encoding="utf-8"?>
+<Project ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
+  <ItemGroup>
+    <ClCompile Include="$(SolutionDir)\..\test\core\census\tag_set_test.c">
+      <Filter>test\core\census</Filter>
+    </ClCompile>
+  </ItemGroup>
+
+  <ItemGroup>
+    <Filter Include="test">
+      <UniqueIdentifier>{500aa440-5924-8047-996a-4c5096d1ef96}</UniqueIdentifier>
+    </Filter>
+    <Filter Include="test\core">
+      <UniqueIdentifier>{a3bf80f0-5b13-f623-277b-05f0231dd933}</UniqueIdentifier>
+    </Filter>
+    <Filter Include="test\core\census">
+      <UniqueIdentifier>{b6ed1b86-7795-4da9-a169-9eccf836852c}</UniqueIdentifier>
+    </Filter>
+  </ItemGroup>
+</Project>
+