diff --git a/htrace-c/src/CMakeLists.txt b/htrace-c/src/CMakeLists.txt
index c34a7c2..20a0d51 100644
--- a/htrace-c/src/CMakeLists.txt
+++ b/htrace-c/src/CMakeLists.txt
@@ -75,6 +75,7 @@
     core/htracer.c
     core/scope.c
     core/span.c
+    core/span_id.c
     receiver/hrpc.c
     receiver/htraced.c
     receiver/local_file.c
@@ -198,8 +199,8 @@
     test/span-unit.c
 )
 
-add_utest(span_util-unit
-    test/span_util-unit.c
+add_utest(span_id-unit
+    test/span_id-unit.c
 )
 
 add_utest(string-unit
diff --git a/htrace-c/src/core/htrace.h b/htrace-c/src/core/htrace.h
index e7dc93b..03c02bb 100644
--- a/htrace-c/src/core/htrace.h
+++ b/htrace-c/src/core/htrace.h
@@ -329,16 +329,6 @@
                                              struct htrace_span *span);
 
     /**
-     * Get the span id of an HTrace scope.
-     *
-     * @param scope     The trace scope, or NULL.
-     *
-     * @return          The span ID of the trace span, or 0 if there is no trace
-     *                      span inside the scope, or if NULL was passed.
-     */
-    uint64_t htrace_scope_get_span_id(const struct htrace_scope *scope);
-
-    /**
      * Close a trace scope.
      *
      * This must be called from the same thread that the trace scope was created
diff --git a/htrace-c/src/core/htrace.hpp b/htrace-c/src/core/htrace.hpp
index e4a87cb..0378c57 100644
--- a/htrace-c/src/core/htrace.hpp
+++ b/htrace-c/src/core/htrace.hpp
@@ -221,10 +221,6 @@
       scope_ = NULL;
     }
 
-    uint64_t GetSpanId() {
-      return htrace_scope_get_span_id(scope_);
-    }
-
   private:
     friend class Tracer;
     Scope(htrace::Scope &other); // Can't copy
diff --git a/htrace-c/src/core/scope.c b/htrace-c/src/core/scope.c
index 93008cb..442bf52 100644
--- a/htrace-c/src/core/scope.c
+++ b/htrace-c/src/core/scope.c
@@ -43,7 +43,7 @@
 {
     struct htrace_scope *cur_scope, *scope = NULL, *pscope;
     struct htrace_span *span = NULL;
-    uint64_t span_id;
+    struct htrace_span_id span_id;
 
     // Validate the description string.  This ensures that it doesn't have
     // anything silly in it like embedded double quotes, backslashes, or control
@@ -54,15 +54,16 @@
         return NULL;
     }
     cur_scope = htracer_cur_scope(tracer);
-    if (!cur_scope) {
+    if ((!cur_scope) || (!cur_scope->span)) {
         if (!sampler->ty->next(sampler)) {
             return NULL;
         }
+        htrace_span_id_generate(&span_id, tracer->rnd, NULL);
+    } else {
+        htrace_span_id_generate(&span_id, tracer->rnd,
+                                &cur_scope->span->span_id);
     }
-    do {
-        span_id = random_u64(tracer->rnd);
-    } while (span_id == 0);
-    span = htrace_span_alloc(desc, now_ms(tracer->lg), span_id);
+    span = htrace_span_alloc(desc, now_ms(tracer->lg), &span_id);
     if (!span) {
         htrace_log(tracer->lg, "htrace_span_alloc(desc=%s): OOM\n", desc);
         return NULL;
@@ -112,12 +113,14 @@
                                          struct htrace_span *span)
 {
     struct htrace_scope *cur_scope, *scope = NULL;
+    char buf[HTRACE_SPAN_ID_STRING_LENGTH + 1];
 
     scope = malloc(sizeof(*scope));
     if (!scope) {
+        htrace_span_id_to_str(&span->span_id, buf, sizeof(buf));
+        htrace_log(tracer->lg, "htrace_start_span(desc=%s, parent_id=%s"
+                   "): OOM\n", span->desc, buf);
         htrace_span_free(span);
-        htrace_log(tracer->lg, "htrace_start_span(desc=%s, parent_id=%016"PRIx64
-                   "): OOM\n", span->desc, span->span_id);
         return NULL;
     }
     scope->tracer = tracer;
@@ -132,15 +135,21 @@
     return scope;
 }
 
-uint64_t htrace_scope_get_span_id(const struct htrace_scope *scope)
+void htrace_scope_get_span_id(const struct htrace_scope *scope,
+                              struct htrace_span_id *id)
 {
     struct htrace_span *span;
 
     if (!scope) {
-        return 0;
+        htrace_span_id_clear(id);
+        return;
     }
     span = scope->span;
-    return span ? span->span_id : 0;
+    if (!span) {
+        htrace_span_id_clear(id);
+        return;
+    }
+    htrace_span_id_copy(id, &span->span_id);
 }
 
 void htrace_scope_close(struct htrace_scope *scope)
diff --git a/htrace-c/src/core/scope.h b/htrace-c/src/core/scope.h
index f76cd42..9f00b13 100644
--- a/htrace-c/src/core/scope.h
+++ b/htrace-c/src/core/scope.h
@@ -27,6 +27,8 @@
  * This is an internal header, not intended for external use.
  */
 
+struct htrace_span_id;
+
 #include <stdint.h>
 
 /**
@@ -53,6 +55,17 @@
     struct htrace_span *span;
 };
 
+/**
+ * Get the span id of an HTrace scope.
+ *
+ * @param scope     The trace scope, or NULL.
+ * @param id        (out param) The htrace span ID object to modify.
+ *                      It will be set to the invalid span ID if the scope
+ *                      is null or has no span.
+ */
+void htrace_scope_get_span_id(const struct htrace_scope *scope,
+                              struct htrace_span_id *id);
+
 #endif
 
 // vim: ts=4:sw=4:et
diff --git a/htrace-c/src/core/span.c b/htrace-c/src/core/span.c
index b82f4f1..44f4e6c 100644
--- a/htrace-c/src/core/span.c
+++ b/htrace-c/src/core/span.c
@@ -38,7 +38,7 @@
  */
 
 struct htrace_span *htrace_span_alloc(const char *desc,
-                uint64_t begin_ms, uint64_t span_id)
+                uint64_t begin_ms, struct htrace_span_id *span_id)
 {
     struct htrace_span *span;
 
@@ -53,10 +53,10 @@
     }
     span->begin_ms = begin_ms;
     span->end_ms = 0;
-    span->span_id = span_id;
+    htrace_span_id_copy(&span->span_id, span_id);
     span->trid = NULL;
     span->num_parents = 0;
-    span->parent.single = 0;
+    htrace_span_id_clear(&span->parent.single);
     span->parent.list = NULL;
     return span;
 }
@@ -74,35 +74,26 @@
     free(span);
 }
 
-static int compare_spanids(const void *va, const void *vb)
-{
-    uint64_t a = *((uint64_t*)va);
-    uint64_t b = *((uint64_t*)vb);
-    if (a < b) {
-        return -1;
-    } else if (a > b) {
-        return 1;
-    } else {
-        return 0;
-    }
-}
+typedef int (*qsort_fn_t)(const void *, const void *);
 
 void htrace_span_sort_and_dedupe_parents(struct htrace_span *span)
 {
     int i, j, num_parents = span->num_parents;
-    uint64_t prev;
+    struct htrace_span_id prev;
 
     if (num_parents <= 1) {
         return;
     }
-    qsort(span->parent.list, num_parents, sizeof(uint64_t), compare_spanids);
+    qsort(span->parent.list, num_parents, sizeof(struct htrace_span_id),
+          (qsort_fn_t)htrace_span_id_compare);
     prev = span->parent.list[0];
+    htrace_span_id_copy(&prev, &span->parent.list[0]);
     j = 1;
     for (i = 1; i < num_parents; i++) {
-        uint64_t id = span->parent.list[i];
-        if (id != prev) {
-            span->parent.list[j++] = span->parent.list[i];
-            prev = id;
+        if (htrace_span_id_compare(&prev, span->parent.list + i) != 0) {
+            htrace_span_id_copy(&prev, span->parent.list + i);
+            htrace_span_id_copy(span->parent.list + j, span->parent.list + i);
+            j++;
         }
     }
     span->num_parents = j;
@@ -114,7 +105,8 @@
     } else if (j != num_parents) {
         // After deduplication, there are now fewer entries.  Use realloc to
         // shrink the size of our dynamic allocation if possible.
-        uint64_t *nlist = realloc(span->parent.list, sizeof(uint64_t) * j);
+        struct htrace_span_id *nlist =
+            realloc(span->parent.list, sizeof(struct htrace_span_id) * j);
         if (nlist) {
             span->parent.list = nlist;
         }
@@ -141,13 +133,15 @@
 {
     int num_parents, i, ret = 0;
     const char *prefix = "";
+    char sbuf[HTRACE_SPAN_ID_STRING_LENGTH + 1];
 
     // Note that we have validated the description and process ID strings to
     // make sure they don't contain anything evil.  So we don't need to escape
     // them here.
 
-    ret += fwdprintf(&buf, &max, "{\"s\":\"%016" PRIx64 "\",\"b\":%" PRId64
-                 ",\"e\":%" PRId64",", span->span_id, span->begin_ms,
+    htrace_span_id_to_str(&span->span_id, sbuf, sizeof(sbuf));
+    ret += fwdprintf(&buf, &max, "{\"a\":\"%s\",\"b\":%" PRId64
+                 ",\"e\":%" PRId64",", sbuf, span->begin_ms,
                  span->end_ms);
     if (span->desc[0]) {
         ret += fwdprintf(&buf, &max, "\"d\":\"%s\",", span->desc);
@@ -159,13 +153,13 @@
     if (num_parents == 0) {
         ret += fwdprintf(&buf, &max, "\"p\":[]");
     } else if (num_parents == 1) {
-        ret += fwdprintf(&buf, &max, "\"p\":[\"%016"PRIx64"\"]",
-                         span->parent.single);
+        htrace_span_id_to_str(&span->parent.single, sbuf, sizeof(sbuf));
+        ret += fwdprintf(&buf, &max, "\"p\":[\"%s\"]", sbuf);
     } else if (num_parents > 1) {
         ret += fwdprintf(&buf, &max, "\"p\":[");
         for (i = 0; i < num_parents; i++) {
-            ret += fwdprintf(&buf, &max, "%s\"%016" PRIx64 "\"", prefix,
-                             span->parent.list[i]);
+            htrace_span_id_to_str(span->parent.list + i, sbuf, sizeof(sbuf));
+            ret += fwdprintf(&buf, &max, "%s\"%s\"", prefix, sbuf);
             prefix = ",";
         }
         ret += fwdprintf(&buf, &max, "]");
@@ -205,6 +199,12 @@
     if (!cmp_write_map16(ctx, map_size)) {
         return 0;
     }
+    if (!cmp_write_fixstr(ctx, "a", 1)) {
+        return 0;
+    }
+    if (!htrace_span_id_write_msgpack(&span->span_id, ctx)) {
+        return 0;
+    }
     if (!cmp_write_fixstr(ctx, "d", 1)) {
         return 0;
     }
@@ -223,12 +223,6 @@
     if (!cmp_write_u64(ctx, span->end_ms)) {
         return 0;
     }
-    if (!cmp_write_fixstr(ctx, "s", 1)) {
-        return 0;
-    }
-    if (!cmp_write_u64(ctx, span->span_id)) {
-        return 0;
-    }
     if (span->trid) {
         if (!cmp_write_fixstr(ctx, "r", 1)) {
             return 0;
@@ -245,12 +239,12 @@
             return 0;
         }
         if (num_parents == 1) {
-            if (!cmp_write_u64(ctx, span->parent.single)) {
+            if (!htrace_span_id_write_msgpack(&span->parent.single, ctx)) {
                 return 0;
             }
         } else {
             for (i = 0; i < num_parents; i++) {
-                if (!cmp_write_u64(ctx, span->parent.list[i])) {
+                if (!htrace_span_id_write_msgpack(span->parent.list + i, ctx)) {
                     return 0;
                 }
             }
diff --git a/htrace-c/src/core/span.h b/htrace-c/src/core/span.h
index 4d28e75..d6fbeb5 100644
--- a/htrace-c/src/core/span.h
+++ b/htrace-c/src/core/span.h
@@ -27,6 +27,8 @@
  * This is an internal header, not intended for external use.
  */
 
+#include "core/span_id.h"
+
 #include <stdint.h>
 
 struct cmp_ctx_s;
@@ -52,7 +54,7 @@
     /**
      * The span id.
      */
-    uint64_t span_id;
+    struct htrace_span_id span_id;
 
     /**
      * The tracer ID of this trace scope.
@@ -69,13 +71,13 @@
         /**
          * If there is 1 parent, this is the parent ID.
          */
-        uint64_t single;
+        struct htrace_span_id single;
 
         /**
          * If there are multiple parents, this is a pointer to a dynamically
          * allocated array of parent IDs.
          */
-        uint64_t *list;
+        struct htrace_span_id *list;
     } parent;
 };
 
@@ -89,7 +91,7 @@
  * @return              NULL on OOM; the span otherwise.
  */
 struct htrace_span *htrace_span_alloc(const char *desc,
-                uint64_t begin_ms, uint64_t span_id);
+                uint64_t begin_ms, struct htrace_span_id *span_id);
 
 /**
  * Free the memory associated with an htrace span.
diff --git a/htrace-c/src/core/span_id.c b/htrace-c/src/core/span_id.c
new file mode 100644
index 0000000..7ea23eb
--- /dev/null
+++ b/htrace-c/src/core/span_id.c
@@ -0,0 +1,221 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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.
+ */
+
+#include "core/span_id.h"
+#include "util/cmp.h"
+#include "util/log.h"
+#include "util/rand.h"
+#include "util/string.h"
+#include "util/time.h"
+
+#include <errno.h>
+#include <inttypes.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/**
+ * @file span_id.c
+ *
+ * Implementation of HTrace span IDs.
+ *
+ * Span IDs are 128 bits in total.  The upper 64 bits of a span ID is the same
+ * as the upper 64 bits of the first parent span, if there is one.  The lower 64
+ * bits are always random.
+ */
+
+const struct htrace_span_id INVALID_SPAN_ID;
+
+static uint64_t parse_hex_range(const char *str, int start, int end,
+                                char *err, size_t err_len)
+{
+    char *endptr = NULL;
+    uint64_t ret;
+    char substr[HTRACE_SPAN_ID_STRING_LENGTH + 1];
+
+    err[0] = '\0';
+    if (end - start >= HTRACE_SPAN_ID_STRING_LENGTH) {
+        snprintf(err, err_len, "parse_hex_range buffer too short.");
+        return 0;
+    }
+    memcpy(substr, str + start, end - start);
+    substr[end - start] = '\0';
+    errno = 0;
+    ret = strtoull(substr, &endptr, 16);
+    if (errno) {
+        int e = errno;
+        snprintf(err, err_len, "parse_hex_range error: %s", terror(e));
+        return 0;
+    }
+    while (1) {
+        char c = *endptr;
+        if (c == '\0') {
+            break;
+        }
+        if ((c != ' ') || (c != '\t')) {
+            snprintf(err, err_len, "parse_hex_range error: garbage at end "
+                     "of string.");
+            return 0;
+        }
+        endptr++;
+    }
+    return ret;
+}
+
+void htrace_span_id_parse(struct htrace_span_id *id, const char *str,
+                   char *err, size_t err_len)
+{
+    size_t len;
+
+    err[0] = '\0';
+    len = strlen(str);
+    if (len < HTRACE_SPAN_ID_STRING_LENGTH) {
+        snprintf(err, err_len, "too short: must be %d characters.",
+                 HTRACE_SPAN_ID_STRING_LENGTH);
+        return;
+    }
+    id->high = (parse_hex_range(str, 0, 8, err, err_len) << 32);
+    if (err[0]) {
+        return;
+    }
+    id->high |= (parse_hex_range(str, 8, 16, err, err_len));
+    if (err[0]) {
+        return;
+    }
+    id->low = (parse_hex_range(str, 16, 24, err, err_len) << 32);
+    if (err[0]) {
+        return;
+    }
+    id->low |= (parse_hex_range(str, 24, 32, err, err_len));
+    if (err[0]) {
+        return;
+    }
+}
+
+int htrace_span_id_to_str(const struct htrace_span_id *id,
+                          char *str, size_t len)
+{
+    int res = snprintf(str, len,
+        "%08"PRIx32"%08"PRIx32"%08"PRIx32"%08"PRIx32,
+        (uint32_t)(0xffffffffUL & (id->high >> 32)),
+        (uint32_t)(0xffffffffUL & id->high),
+        (uint32_t)(0xffffffffUL & (id->low >> 32)),
+        (uint32_t)(0xffffffffUL & id->low));
+    return (res == HTRACE_SPAN_ID_STRING_LENGTH);
+}
+
+void htrace_span_id_copy(struct htrace_span_id *dst,
+                         const struct htrace_span_id *src)
+{
+    memmove(dst, src, sizeof(*dst));
+}
+
+int htrace_span_id_write_msgpack(const struct htrace_span_id *id,
+                                 struct cmp_ctx_s *ctx)
+{
+    uint8_t buf[HTRACE_SPAN_ID_NUM_BYTES];
+    buf[0] = (id->high >> 56) & 0xff;
+    buf[1] = (id->high >> 48) & 0xff;
+    buf[2] = (id->high >> 40) & 0xff;
+    buf[3] = (id->high >> 32) & 0xff;
+    buf[4] = (id->high >> 24) & 0xff;
+    buf[5] = (id->high >> 16) & 0xff;
+    buf[6] = (id->high >> 8) & 0xff;
+    buf[7] = (id->high >> 0) & 0xff;
+    buf[8] = (id->low >> 56) & 0xff;
+    buf[9] = (id->low >> 48) & 0xff;
+    buf[10] = (id->low >> 40) & 0xff;
+    buf[11] = (id->low >> 32) & 0xff;
+    buf[12] = (id->low >> 24) & 0xff;
+    buf[13] = (id->low >> 16) & 0xff;
+    buf[14] = (id->low >> 8) & 0xff;
+    buf[15] = (id->low >> 0) & 0xff;
+    return cmp_write_bin(ctx, buf, HTRACE_SPAN_ID_NUM_BYTES);
+}
+
+int htrace_span_id_read_msgpack(struct htrace_span_id *id,
+                                struct cmp_ctx_s *ctx)
+{
+    uint8_t buf[HTRACE_SPAN_ID_NUM_BYTES];
+    uint32_t size = HTRACE_SPAN_ID_NUM_BYTES;
+
+    if (!cmp_read_bin(ctx, buf, &size)) {
+        return 0;
+    }
+    if (size != HTRACE_SPAN_ID_NUM_BYTES) {
+        return 0;
+    }
+    id->high =
+        (((uint64_t)buf[0]) << 56) |
+        (((uint64_t)buf[1]) << 48) |
+        (((uint64_t)buf[2]) << 40) |
+        (((uint64_t)buf[3]) << 32) |
+        (((uint64_t)buf[4]) << 24) |
+        (((uint64_t)buf[5]) << 16) |
+        (((uint64_t)buf[6]) << 8) |
+        (((uint64_t)buf[7]) << 0);
+    id->low =
+        (((uint64_t)buf[8]) << 56) |
+        (((uint64_t)buf[9]) << 48) |
+        (((uint64_t)buf[10]) << 40) |
+        (((uint64_t)buf[11]) << 32) |
+        (((uint64_t)buf[12]) << 24) |
+        (((uint64_t)buf[13]) << 16) |
+        (((uint64_t)buf[14]) << 8) |
+        (((uint64_t)buf[15]) << 0);
+    return 1;
+}
+
+void htrace_span_id_generate(struct htrace_span_id *id, struct random_src *rnd,
+                             const struct htrace_span_id *parent)
+{
+    if (parent) {
+        id->high = parent->high;
+    } else {
+        do {
+            id->high = random_u64(rnd);
+        } while (id->high == 0);
+    }
+    do {
+        id->low = random_u64(rnd);
+    } while (id->low == 0);
+}
+
+void htrace_span_id_clear(struct htrace_span_id *id)
+{
+    memset(id, 0, sizeof(*id));
+}
+
+int htrace_span_id_compare(const struct htrace_span_id *a,
+                           const struct htrace_span_id *b)
+{
+    if (a->high < b->high) {
+        return -1;
+    } else if (a->high > b->high) {
+        return 1;
+    } else if (a->low < b->low) {
+        return -1;
+    } else if (a->low > b->low) {
+        return 1;
+    } else {
+        return 0;
+    }
+}
+
+// vim:ts=4:sw=4:et
diff --git a/htrace-c/src/core/span_id.h b/htrace-c/src/core/span_id.h
new file mode 100644
index 0000000..af2e725
--- /dev/null
+++ b/htrace-c/src/core/span_id.h
@@ -0,0 +1,149 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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.
+ */
+
+#ifndef APACHE_HTRACE_SPAN_ID_H
+#define APACHE_HTRACE_SPAN_ID_H
+
+/**
+ * @file span_id.h
+ *
+ * Functions related to HTrace span IDs.
+ *
+ * This is an internal header, not intended for external use.
+ */
+
+#include <stdint.h> // for uint64_t
+#include <unistd.h> // for size_t
+
+struct cmp_ctx_s;
+struct random_src;
+
+/**
+ * Length of an HTrace span ID in hexadecimal string form.
+ */
+#define HTRACE_SPAN_ID_STRING_LENGTH 32
+
+/**
+ * The number of bytes in the HTrace span ID
+ */
+#define HTRACE_SPAN_ID_NUM_BYTES 16
+
+/**
+ * The invalid span ID, which is all zeroes.
+ */
+extern const struct htrace_span_id INVALID_SPAN_ID;
+
+/**
+ * The HTrace span id.
+ */
+struct htrace_span_id {
+    uint64_t high;
+    uint64_t low;
+};
+
+/**
+ * Parse a string containing an HTrace span ID.
+ *
+ * @param id            The HTrace span ID to fill in.
+ * @param str           The string to parse.
+ *
+ */
+void htrace_span_id_parse(struct htrace_span_id *id, const char *str,
+                         char *err, size_t err_len);
+
+/**
+ * Write an HTrace span ID to a string.
+ *
+ * @param id            The HTrace span ID.
+ * @param str           Where to put the string.
+ * @param len           The length of the string buffer.
+ * @param err           The error buffer to be set on failure.
+ * @param err_len       Length of the error buffer.
+ *
+ * @return              1 on success; 0 if the length was not long enough, or
+ *                          there was an internal snprintf error.
+ */
+int htrace_span_id_to_str(const struct htrace_span_id *id,
+                          char *str, size_t len);
+
+/**
+ * Copy an htrace span ID.
+ *
+ * dst and src can be the same.
+ *
+ * @param dst           The destination span ID.
+ * @param src           The source span ID.
+ */
+void htrace_span_id_copy(struct htrace_span_id *dst,
+                         const struct htrace_span_id *src);
+
+/**
+ * Write this span ID to the provided CMP context.
+ *
+ * @param span          The span.
+ * @param ctx           The CMP context.
+ *
+ * @return              0 on failure; 1 on success.
+ */
+int htrace_span_id_write_msgpack(const struct htrace_span_id *id,
+                                 struct cmp_ctx_s *ctx);
+
+/**
+ * Read this span ID from the provided CMP context.
+ *
+ * @param span          The span.
+ * @param ctx           The CMP context.
+ *
+ * @return              0 on failure; 1 on success.
+ */
+int htrace_span_id_read_msgpack(struct htrace_span_id *id,
+                                struct cmp_ctx_s *ctx);
+
+/**
+ * Generate a new span ID.
+ *
+ * @param id            The span ID to alter.
+ * @param rnd           The random source.
+ * @param parent        The parent span ID, or null if there is none.
+ */
+void htrace_span_id_generate(struct htrace_span_id *id, struct random_src *rnd,
+                             const struct htrace_span_id *parent);
+
+/**
+ * Set a span ID to the invalid span ID by clearing it.
+ *
+ * @param id            The span ID to clear.
+ */
+void htrace_span_id_clear(struct htrace_span_id *id);
+
+/**
+ * Compare two span IDs.
+ *
+ * @param a             The first span ID.
+ * @param b             The second span ID.
+ *
+ * @return              A number less than 0 if the first span ID is less;
+ *                      A number greater than 0 if the first span ID is greater;
+ *                      0 if the span IDs are equal.
+ */
+int htrace_span_id_compare(const struct htrace_span_id *a,
+                           const struct htrace_span_id *b);
+
+#endif
+
+// vim: ts=4:sw=4:et
diff --git a/htrace-c/src/test/cmp_util-unit.c b/htrace-c/src/test/cmp_util-unit.c
index 4675ca8..d272cae 100644
--- a/htrace-c/src/test/cmp_util-unit.c
+++ b/htrace-c/src/test/cmp_util-unit.c
@@ -39,27 +39,33 @@
     spans[0]->desc = xstrdup("FirstSpan");
     spans[0]->begin_ms = 1927;
     spans[0]->end_ms = 2000;
-    spans[0]->span_id = 1;
+    spans[0]->span_id.high = 0xface;
+    spans[0]->span_id.low = 1;
 
     spans[1] = xcalloc(sizeof(struct htrace_span));
     spans[1]->desc = xstrdup("SecondSpan");
     spans[1]->begin_ms = 1950;
     spans[1]->end_ms = 2000;
-    spans[1]->span_id = 0xffffffffffffffffULL;
+    spans[1]->span_id.high = 0xface;
+    spans[1]->span_id.low = 2;
     spans[1]->trid = xstrdup("SecondSpanProc");
     spans[1]->num_parents = 1;
-    spans[1]->parent.single = 1;
+    spans[1]->parent.single.high = 0xface;
+    spans[1]->parent.single.low = 1;
 
     spans[2] = xcalloc(sizeof(struct htrace_span));
     spans[2]->desc = xstrdup("ThirdSpan");
     spans[2]->begin_ms = 1969;
     spans[2]->end_ms = 1997;
-    spans[2]->span_id = 0xcfcfcfcfcfcfcfcfULL;
+    spans[1]->span_id.high = 0xface;
+    spans[1]->span_id.low = 0xcfcfcfcfcfcfcfcfULL;
     spans[2]->trid = xstrdup("ThirdSpanProc");
     spans[2]->num_parents = 2;
-    spans[2]->parent.list = xcalloc(sizeof(uint64_t) * 2);
-    spans[2]->parent.list[0] = 1;
-    spans[2]->parent.list[1] = 0xffffffffffffffffULL;
+    spans[2]->parent.list = xcalloc(sizeof(struct htrace_span_id) * 2);
+    spans[2]->parent.list[0].high = 0xface;
+    spans[2]->parent.list[0].low = 1;
+    spans[2]->parent.list[1].high = 0xface;
+    spans[2]->parent.list[1].low = 2;
 
     return spans;
 }
diff --git a/htrace-c/src/test/linkage-unit.c b/htrace-c/src/test/linkage-unit.c
index f3c5eba..bba73e1 100644
--- a/htrace-c/src/test/linkage-unit.c
+++ b/htrace-c/src/test/linkage-unit.c
@@ -45,7 +45,6 @@
     "htrace_sampler_to_str",
     "htrace_scope_close",
     "htrace_scope_detach",
-    "htrace_scope_get_span_id",
     "htrace_start_span",
     "htracer_create",
     "htracer_free",
diff --git a/htrace-c/src/test/rtest.c b/htrace-c/src/test/rtest.c
index ccae241..933315d 100644
--- a/htrace-c/src/test/rtest.c
+++ b/htrace-c/src/test/rtest.c
@@ -18,6 +18,7 @@
 
 #include "core/conf.h"
 #include "core/htrace.h"
+#include "core/scope.h"
 #include "core/span.h"
 #include "test/rtest.h"
 #include "test/span_table.h"
@@ -92,12 +93,17 @@
 static int doit(struct rtest_data *rdata)
 {
     struct htrace_scope *scope1, *scope2, *scope2_5;
+    struct htrace_span_id span_id;
 
     scope1 = htrace_start_span(rdata->tracer, NULL, "part1");
-    EXPECT_UINT64_GT(0L, htrace_scope_get_span_id(scope1));
+    htrace_scope_get_span_id(scope1, &span_id);
+    EXPECT_TRUE(0 !=
+        htrace_span_id_compare(&INVALID_SPAN_ID, &span_id));
     htrace_scope_close(scope1);
     scope2 = htrace_start_span(rdata->tracer, NULL, "part2");
-    EXPECT_UINT64_GT(0L, htrace_scope_get_span_id(scope2));
+    htrace_scope_get_span_id(scope2, &span_id);
+    EXPECT_TRUE(0 !=
+        htrace_span_id_compare(&INVALID_SPAN_ID, &span_id));
     scope2_5 = htrace_start_span(rdata->tracer, NULL, "part2.5");
     htrace_scope_close(scope2_5);
     htrace_scope_close(scope2);
@@ -122,27 +128,27 @@
 int rtest_simple_verify(struct rtest *rt, struct span_table *st)
 {
     struct htrace_span *span;
-    uint64_t doit_id, part2_id;
+    struct htrace_span_id doit_id, part2_id;
     char trid[128];
 
     EXPECT_INT_ZERO(rtest_verify_table_size(rt, st));
     get_receiver_test_trid(trid, sizeof(trid));
     EXPECT_INT_ZERO(span_table_get(st, &span, "doit", trid));
-    doit_id = span->span_id;
+    htrace_span_id_copy(&doit_id, &span->span_id);
     EXPECT_INT_ZERO(span->num_parents);
 
     EXPECT_INT_ZERO(span_table_get(st, &span, "part1", trid));
     EXPECT_INT_EQ(1, span->num_parents);
-    EXPECT_UINT64_EQ(doit_id, span->parent.single);
+    EXPECT_TRUE(0 == htrace_span_id_compare(&doit_id, &span->parent.single));
 
     EXPECT_INT_ZERO(span_table_get(st, &span, "part2", trid));
     EXPECT_INT_EQ(1, span->num_parents);
-    part2_id = span->span_id;
-    EXPECT_UINT64_EQ(doit_id, span->parent.single);
+    htrace_span_id_copy(&part2_id, &span->span_id);
+    EXPECT_TRUE(0 == htrace_span_id_compare(&doit_id, &span->parent.single));
 
     EXPECT_INT_ZERO(span_table_get(st, &span, "part2.5", trid));
     EXPECT_INT_EQ(1, span->num_parents);
-    EXPECT_UINT64_EQ(part2_id, span->parent.single);
+    EXPECT_TRUE(0 == htrace_span_id_compare(&part2_id, &span->parent.single));
 
     return EXIT_SUCCESS;
 }
diff --git a/htrace-c/src/test/rtestpp.cc b/htrace-c/src/test/rtestpp.cc
index 0cd7120..a5c2ac8 100644
--- a/htrace-c/src/test/rtestpp.cc
+++ b/htrace-c/src/test/rtestpp.cc
@@ -88,14 +88,11 @@
 {
     {
         htrace::Scope scope1(tdata.tracer_, "part1");
-        EXPECT_UINT64_GT(0L, scope1.GetSpanId());
     }
     {
         htrace::Scope scope2(tdata.tracer_, "part2");
-        EXPECT_UINT64_GT(0L, scope2.GetSpanId());
         {
             htrace::Scope scope2_5(tdata.tracer_, "part2.5");
-            EXPECT_UINT64_GT(0L, scope2_5.GetSpanId());
         }
     }
     return EXIT_SUCCESS;
@@ -115,27 +112,27 @@
 int rtestpp_simple_verify(struct rtest *rt, struct span_table *st)
 {
     struct htrace_span *span;
-    uint64_t doit_id, part2_id;
+    struct htrace_span_id doit_id, part2_id;
     char trid[128];
 
     EXPECT_INT_ZERO(rtest_generic_verify(rt, st));
     get_receiver_test_trid(trid, sizeof(trid));
     EXPECT_INT_ZERO(span_table_get(st, &span, "doit", trid));
-    doit_id = span->span_id;
+    htrace_span_id_copy(&doit_id, &span->span_id);
     EXPECT_INT_ZERO(span->num_parents);
 
     EXPECT_INT_ZERO(span_table_get(st, &span, "part1", trid));
     EXPECT_INT_EQ(1, span->num_parents);
-    EXPECT_UINT64_EQ(doit_id, span->parent.single);
+    EXPECT_TRUE(0 == htrace_span_id_compare(&doit_id, &span->parent.single));
 
     EXPECT_INT_ZERO(span_table_get(st, &span, "part2", trid));
     EXPECT_INT_EQ(1, span->num_parents);
-    part2_id = span->span_id;
-    EXPECT_UINT64_EQ(doit_id, span->parent.single);
+    htrace_span_id_copy(&part2_id, &span->span_id);
+    EXPECT_TRUE(0 == htrace_span_id_compare(&doit_id, &span->parent.single));
 
     EXPECT_INT_ZERO(span_table_get(st, &span, "part2.5", trid));
     EXPECT_INT_EQ(1, span->num_parents);
-    EXPECT_UINT64_EQ(part2_id, span->parent.single);
+    EXPECT_TRUE(0 == htrace_span_id_compare(&part2_id, &span->parent.single));
 
     return EXIT_SUCCESS;
 }
diff --git a/htrace-c/src/test/span-unit.c b/htrace-c/src/test/span-unit.c
index 5482b8d..652c9a7 100644
--- a/htrace-c/src/test/span-unit.c
+++ b/htrace-c/src/test/span-unit.c
@@ -20,153 +20,51 @@
 #include "core/htrace.h"
 #include "core/htracer.h"
 #include "core/span.h"
-#include "sampler/sampler.h"
 #include "test/span_util.h"
 #include "test/test.h"
-#include "util/htable.h"
-#include "util/log.h"
 
-#include <errno.h>
 #include <inttypes.h>
-#include <stdarg.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
-#define MAX_SPAN_JSON_LEN 100000
-
-static struct htrace_conf *g_test_conf;
-
-static struct htrace_log *g_test_lg;
-
-static struct htracer *g_test_tracer;
-
-static struct htrace_span *create_span(const char *desc,
-        uint64_t begin_ms, uint64_t end_ms, uint64_t span_id,
-        const char *trid, ...) __attribute__((sentinel));
-
-static int test_span_to_json(const char *expected,
-                             struct htrace_span *span)
+static int test_span_round_trip(const char *str)
 {
-    int buf_len;
-    char *buf;
-    struct htrace_span *rspan = NULL;
-    char err[128];
+    char err[512], *json = NULL;
     size_t err_len = sizeof(err);
+    struct htrace_span *span = NULL;
+    int json_size;
 
-    htrace_span_sort_and_dedupe_parents(span);
-    buf_len = span_json_size(span);
-    if ((0 > buf_len) || (buf_len > MAX_SPAN_JSON_LEN)) {
-        fprintf(stderr, "invalid span_json_size %d.\n", buf_len);
-        return EXIT_FAILURE;
-    }
-    buf = malloc(buf_len);
-    EXPECT_NONNULL(buf);
-    span_json_sprintf(span, buf_len, buf);
-    EXPECT_STR_EQ(expected, buf);
-    span_json_parse(buf, &rspan, err, err_len);
-    if (err[0]) {
-        fprintf(stderr, "Failed to parse span json %s: %s\n", buf, err);
-        return EXIT_FAILURE;
-    }
-    EXPECT_NONNULL(rspan);
-    if (span_compare(span, rspan) != 0) {
-        htrace_span_free(rspan);
-        fprintf(stderr, "Failed to parse the span json back into a span "
-                "which was identical to the input.  JSON: %s\n", buf);
-        return EXIT_FAILURE;
-    }
-    free(buf);
-    htrace_span_free(rspan);
-    return EXIT_SUCCESS;
-}
-
-static struct htrace_span *create_span(const char *desc,
-        uint64_t begin_ms, uint64_t end_ms, uint64_t span_id,
-        const char *trid, ...)
-{
-    struct htrace_span* span = NULL;
-    uint64_t *parents, parent;
-    int i, num_parents = 0;
-    va_list ap, ap2;
-
-    va_start(ap, trid);
-    va_copy(ap2, ap);
-    while (1) {
-        parent = va_arg(ap2, uint64_t);
-        if (!parent) {
-            break;
-        }
-        num_parents++;
-    } while (parent);
-    va_end(ap2);
-    if (num_parents > 0) {
-        parents = xcalloc(sizeof(uint64_t) * num_parents);
-        for (i = 0; i < num_parents; i++) {
-            parents[i] = va_arg(ap, uint64_t);
-        }
-    }
-    va_end(ap);
-    span = htrace_span_alloc(desc, begin_ms, span_id);
-    span->end_ms = end_ms;
-    span->span_id = span_id;
-    span->trid = xstrdup(trid);
-    span->num_parents = num_parents;
-    if (num_parents == 1) {
-        span->parent.single = parents[0];
-        free(parents);
-    } else if (num_parents > 1) {
-        span->parent.list = parents;
-    }
-    return span;
-}
-
-static int test_spans_to_str(void)
-{
-    struct htrace_span *span;
-
-    span = create_span("foo", 123LLU, 456LLU, 789LLU, "span-unit",
-                        NULL);
-    EXPECT_INT_ZERO(test_span_to_json(
-        "{\"s\":\"0000000000000315\",\"b\":123,\"e\":456,"
-            "\"d\":\"foo\",\"r\":\"span-unit\""
-            ",\"p\":[]}", span));
+    err[0] = '\0';
+    span_json_parse(str, &span, err, err_len);
+    EXPECT_STR_EQ("", err);
+    json_size = span_json_size(span);
+    json = malloc(json_size);
+    EXPECT_NONNULL(json);
+    span_json_sprintf(span, json_size, json);
+    EXPECT_STR_EQ(str, json);
+    free(json);
     htrace_span_free(span);
 
-    span = create_span("myspan", 34359738368LLU,
-                        34359739368LLU, 68719476736LLU, "span-unit2",
-                        1LLU, 2LLU, 3LLU, NULL);
-    EXPECT_INT_ZERO(test_span_to_json(
-        "{\"s\":\"0000001000000000\",\"b\":34359738368,\"e\":34359739368,"
-        "\"d\":\"myspan\",\"r\":\"span-unit2\"," "\"p\":[\"0000000000000001\","
-        "\"0000000000000002\",\"0000000000000003\"]}", span));
-    htrace_span_free(span);
-
-    span = create_span("nextSpan", 14359739368LLU, 18719476736LLU,
-                       0x8000001000000000LLU, "span-unit3",
-                        1LLU, 1LLU, 1LLU, NULL);
-    EXPECT_INT_ZERO(test_span_to_json(
-        "{\"s\":\"8000001000000000\",\"b\":14359739368,\"e\":18719476736,"
-        "\"d\":\"nextSpan\",\"r\":\"span-unit3\"," "\"p\":[\"0000000000000001\"]"
-        "}", span));
-    htrace_span_free(span);
-    return EXIT_SUCCESS;
+    return 0;
 }
 
 int main(void)
 {
-    g_test_conf = htrace_conf_from_strs("", HTRACE_TRACER_ID"=span-unit");
-    EXPECT_NONNULL(g_test_conf);
-    g_test_lg = htrace_log_alloc(g_test_conf);
-    EXPECT_NONNULL(g_test_lg);
-    g_test_tracer = htracer_create("span-unit", g_test_conf);
-    EXPECT_NONNULL(g_test_tracer);
-
-    EXPECT_INT_ZERO(test_spans_to_str());
-
-    htracer_free(g_test_tracer);
-    htrace_log_free(g_test_lg);
-    htrace_conf_free(g_test_conf);
+    EXPECT_INT_ZERO(test_span_round_trip(
+        "{\"a\":\"ba85631c2ce111e5b345feff819cdc9f\",\"b\":34359738368,"
+        "\"e\":34359739368,\"d\":\"myspan\",\"r\":\"span-unit2\","
+        "\"p\":[\"1549e8d42ce411e5b345feff819cdc9f\","
+        "\"1b6a1d242ce411e5b345feff819cdc9f\","
+        "\"25ab73822ce411e5b345feff819cdc9f\"]}"));
+    EXPECT_INT_ZERO(test_span_round_trip(
+        "{\"a\":\"000000002ce111e5b345feff819cdc9f\",\"b\":0,"
+        "\"e\":0,\"d\":\"secondSpan\",\"r\":\"other-tracerid\","
+        "\"p\":[]}"));
+    EXPECT_INT_ZERO(test_span_round_trip(
+        "{\"a\":\"6baba3842ce411e5b345feff819cdc9f\",\"b\":999,"
+        "\"e\":1000,\"d\":\"thirdSpan\",\"r\":\"other-tracerid\","
+        "\"p\":[\"000000002ce111e5b345feff819cdc9f\"]}"));
     return EXIT_SUCCESS;
 }
 
diff --git a/htrace-c/src/test/span_id-unit.c b/htrace-c/src/test/span_id-unit.c
new file mode 100644
index 0000000..06c0320
--- /dev/null
+++ b/htrace-c/src/test/span_id-unit.c
@@ -0,0 +1,104 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you 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.
+ */
+
+#include "core/span_id.h"
+#include "test/span_util.h"
+#include "test/test.h"
+
+#include <inttypes.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+static int test_span_id_round_trip(const char *str)
+{
+    struct htrace_span_id id;
+    char err[512], str2[HTRACE_SPAN_ID_STRING_LENGTH + 1];
+    size_t err_len = sizeof(err);
+
+    err[0] = '\0';
+    htrace_span_id_parse(&id, str, err, err_len);
+    EXPECT_STR_EQ("", err);
+    EXPECT_INT_EQ(1, htrace_span_id_to_str(&id, str2, sizeof(str2)));
+    EXPECT_STR_EQ(str, str2);
+    return 0;
+}
+
+static int test_span_id_compare(int isLess,
+                                const char *sa, const char *sb)
+{
+    struct htrace_span_id a, b;
+    char err[512];
+    size_t err_len = sizeof(err);
+    int cmp;
+
+    err[0] = '\0';
+
+    htrace_span_id_parse(&a, sa, err, err_len);
+    EXPECT_STR_EQ("", err);
+
+    htrace_span_id_parse(&b, sb, err, err_len);
+    EXPECT_STR_EQ("", err);
+
+    cmp = htrace_span_id_compare(&a, &b);
+    if (isLess) {
+        EXPECT_INT_GT(cmp, 0);
+    } else {
+        EXPECT_INT_ZERO(cmp);
+    }
+    cmp = htrace_span_id_compare(&b, &a);
+    if (isLess) {
+        EXPECT_INT_GT(0, cmp);
+    } else {
+        EXPECT_INT_ZERO(cmp);
+    }
+    return 0;
+}
+
+static int test_span_id_less(const char *sa, const char *sb)
+{
+    return test_span_id_compare(1, sa, sb);
+}
+
+static int test_span_id_eq(const char *sa, const char *sb)
+{
+    return test_span_id_compare(0, sa, sb);
+}
+
+int main(void)
+{
+    EXPECT_INT_ZERO(test_span_id_round_trip("0123456789abcdef0011223344556677"));
+    EXPECT_INT_ZERO(test_span_id_round_trip("a919f3d62ce111e5b345feff819cdc9f"));
+    EXPECT_INT_ZERO(test_span_id_round_trip("00000000000000000000000000000000"));
+    EXPECT_INT_ZERO(test_span_id_round_trip("ba85631c2ce111e5b345feff819cdc9f"));
+    EXPECT_INT_ZERO(test_span_id_round_trip("ffffffffffffffffffffffffffffffff"));
+    EXPECT_INT_ZERO(test_span_id_round_trip("ba85631c2ce111e5b345feff819cdc9f"));
+
+    EXPECT_INT_ZERO(test_span_id_less("a919f3d62ce111e5b345feff819cdc9e",
+                                      "a919f3d62ce111e5b345feff819cdc9f"));
+    EXPECT_INT_ZERO(test_span_id_eq("a919f3d62ce111e5b345feff819cdc9f",
+                                    "a919f3d62ce111e5b345feff819cdc9f"));
+    EXPECT_INT_ZERO(test_span_id_eq("ffffffff2ce111e5b345feff819cdc9f",
+                                    "ffffffff2ce111e5b345feff819cdc9f"));
+    EXPECT_INT_ZERO(test_span_id_less("1919f3d62ce111e5b345feff819cdc9f",
+                                      "f919f3d62ce111e5b345feff81900000"));
+    return EXIT_SUCCESS;
+}
+
+// vim: ts=4:sw=4:tw=79:et
diff --git a/htrace-c/src/test/span_table.c b/htrace-c/src/test/span_table.c
index 42ed5f6..b2b23fd 100644
--- a/htrace-c/src/test/span_table.c
+++ b/htrace-c/src/test/span_table.c
@@ -50,7 +50,8 @@
     EXPECT_NONNULL(span);
     EXPECT_STR_EQ(desc, span->desc);
     EXPECT_UINT64_GE(span->begin_ms, span->end_ms);
-    EXPECT_UINT64_GT(0L, span->span_id);
+    EXPECT_TRUE(0 !=
+        htrace_span_id_compare(&INVALID_SPAN_ID, &span->span_id));
     EXPECT_NONNULL(span->trid);
     EXPECT_STR_EQ(trid, span->trid);
     *out = span;
diff --git a/htrace-c/src/test/span_util-unit.c b/htrace-c/src/test/span_util-unit.c
deleted file mode 100644
index fc2a56c..0000000
--- a/htrace-c/src/test/span_util-unit.c
+++ /dev/null
@@ -1,74 +0,0 @@
-/**
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you 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.
- */
-
-#include "test/span_util.h"
-#include "test/test.h"
-
-#include <inttypes.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-static int test_parse_hex_id_error(const char *in)
-{
-    char err[128];
-
-    err[0] = '\0';
-    parse_hex_id(in, err, sizeof(err));
-    if (!err[0]) {
-        fprintf(stderr, "test_parse_hex_id_error(%s): expected error, but "
-                "was successful.\n", in);
-        return EXIT_FAILURE;
-    }
-    return EXIT_SUCCESS;
-}
-
-static int test_parse_hex_id(uint64_t expected, const char *in)
-{
-    char err[128];
-    size_t err_len = sizeof(err);
-    uint64_t val;
-
-    err[0] = '\0';
-    val = parse_hex_id(in, err, err_len);
-    if (err[0]) {
-        fprintf(stderr, "test_parse_hex_id(%s): got error %s\n",
-                in, err);
-        return EXIT_FAILURE;
-    }
-    EXPECT_UINT64_EQ(expected, val);
-    return EXIT_SUCCESS;
-}
-
-int main(void)
-{
-    EXPECT_INT_ZERO(test_parse_hex_id_error(""));
-    EXPECT_INT_ZERO(test_parse_hex_id_error("z"));
-    EXPECT_INT_ZERO(test_parse_hex_id_error("achoo"));
-    EXPECT_INT_ZERO(test_parse_hex_id(1LLU, "00000000000000001"));
-    EXPECT_INT_ZERO(test_parse_hex_id(0xffffffffffffffffLLU,
-                                       "ffffffffffffffff"));
-    EXPECT_INT_ZERO(test_parse_hex_id(0x8000000000000000LLU,
-                                       "8000000000000000"));
-    EXPECT_INT_ZERO(test_parse_hex_id(0x6297421fe159345fLLU,
-                                       "6297421fe159345f"));
-    EXPECT_INT_ZERO(test_parse_hex_id_error("6297421fe159345fzoo"));
-    return EXIT_SUCCESS;
-}
-
-// vim: ts=4:sw=4:tw=79:et
diff --git a/htrace-c/src/test/span_util.c b/htrace-c/src/test/span_util.c
index 625ba86..04490a9 100644
--- a/htrace-c/src/test/span_util.c
+++ b/htrace-c/src/test/span_util.c
@@ -29,46 +29,15 @@
 #include <stdlib.h>
 #include <string.h>
 
-uint64_t parse_hex_id(const char *in, char *err, size_t err_len)
-{
-    char *endptr;
-    unsigned long long int ret;
-
-    err[0] = '\0';
-    errno = 0;
-    ret = strtoull(in, &endptr, 16);
-    if (errno) {
-        int e = errno;
-        snprintf(err, err_len, "parse_hex_id(%s) failed: error %s",
-                 in, terror(e));
-        return 0;
-    }
-    if (endptr == in) {
-        snprintf(err, err_len, "parse_hex_id(%s) failed: empty string "
-                 "found.", in);
-        return 0;
-    }
-    while (1) {
-        char c = *endptr++;
-        if (c == '\0') {
-            break;
-        }
-        if ((c != ' ') || (c != '\t')) {
-            snprintf(err, err_len, "parse_hex_id(%s) failed: garbage at end "
-                     "of string.", in);
-            return 0;
-        }
-    }
-    return ret;
-}
-
 static void span_json_parse_parents(struct json_object *root,
                     struct htrace_span *span, char *err, size_t err_len)
 {
     char err2[128];
+    size_t err2_len = sizeof(err2);
     struct json_object *p = NULL, *e = NULL;
     int i, np;
 
+    err2[0] = '\0';
     if (!json_object_object_get_ex(root, "p", &p)) {
         return; // no parents
     }
@@ -80,14 +49,14 @@
     if (np == 1) {
         span->num_parents = 1;
         e = json_object_array_get_idx(p, 0);
-        span->parent.single = parse_hex_id(json_object_get_string(e),
-                                            err2, sizeof(err2));
+        htrace_span_id_parse(&span->parent.single,
+                             json_object_get_string(e), err2, err2_len);
         if (err2[0]) {
             snprintf(err, err_len, "failed to parse parent ID 1/1: %s.", err2);
             return;
         }
     } else if (np > 1) {
-        span->parent.list = malloc(sizeof(uint64_t) * np);
+        span->parent.list = malloc(sizeof(struct htrace_span_id) * np);
         if (!span->parent.list) {
             snprintf(err, err_len, "failed to allocate parent ID array of "
                      "%d elements", np);
@@ -96,8 +65,8 @@
         span->num_parents = np;
         for (i = 0; i < np; i++) {
             e = json_object_array_get_idx(p, i);
-            span->parent.list[i] = parse_hex_id(json_object_get_string(e),
-                                            err2, sizeof(err2));
+            htrace_span_id_parse(span->parent.list + i,
+                                 json_object_get_string(e), err2, err2_len);
             if (err2[0]) {
                 snprintf(err, err_len, "failed to parse parent ID %d/%d: %s",
                          i + 1, np, err2);
@@ -115,6 +84,7 @@
     int res;
 
     err[0] = '\0';
+    err2[0] = '\0';
     if (!json_object_object_get_ex(root, "d", &d)) {
         d = NULL;
     }
@@ -141,8 +111,8 @@
             return;
         }
     }
-    if (json_object_object_get_ex(root, "s", &s)) {
-        span->span_id = parse_hex_id(json_object_get_string(s),
+    if (json_object_object_get_ex(root, "a", &s)) {
+        htrace_span_id_parse(&span->span_id, json_object_get_string(s),
                                      err2, sizeof(err2));
         if (err2[0]) {
             snprintf(err, err_len, "error parsing span_id: %s", err2);
@@ -226,7 +196,7 @@
 
 static int compare_parents(struct htrace_span *a, struct htrace_span *b)
 {
-    int na, nb, i;
+    int na, nb, i, cmp;
 
     htrace_span_sort_and_dedupe_parents(a);
     na = a->num_parents;
@@ -234,7 +204,7 @@
     nb = b->num_parents;
 
     for (i = 0; ; i++) {
-        uint64_t sa, sb;
+        struct htrace_span_id sa, sb;
 
         if (i >= na) {
             if (i >= nb) {
@@ -246,21 +216,18 @@
             return 1;
         }
         if ((i == 0) && (na == 1)) {
-            sa = a->parent.single;
+            htrace_span_id_copy(&sa, &a->parent.single);
         } else {
-            sa = a->parent.list[i];
+            htrace_span_id_copy(&sa, a->parent.list + i);
         }
         if ((i == 0) && (nb == 1)) {
-            sb = b->parent.single;
+            htrace_span_id_copy(&sb, &b->parent.single);
         } else {
-            sb = b->parent.list[i];
+            htrace_span_id_copy(&sb, b->parent.list + i);
         }
-        // Use explicit comparison rather than subtraction to avoid numeric
-        // overflow issues.
-        if (sa < sb) {
-            return -1;
-        } else if (sa > sb) {
-            return 1;
+        cmp = htrace_span_id_compare(&sa, &sb);
+        if (cmp) {
+            return cmp;
         }
     }
 }
@@ -269,7 +236,7 @@
 {
     int c;
 
-    c = uint64_cmp(a->span_id, b->span_id);
+    c = htrace_span_id_compare(&a->span_id, &b->span_id);
     if (c) {
         return c;
     }
@@ -355,7 +322,7 @@
         free(span->parent.list);
         span->parent.list = NULL;
     }
-    span->parent.single = 0;
+    htrace_span_id_clear(&span->parent.single);
     span->num_parents = 0;
     if (!cmp_read_array(ctx, &size)) {
         snprintf(err, err_len, "span_parse_msgpack_parents: cmp_read_array "
@@ -363,22 +330,22 @@
         return;
     }
     if (size == 1) {
-        if (!cmp_read_u64(ctx, &span->parent.single)) {
+        if (!htrace_span_id_read_msgpack(&span->parent.single, ctx)) {
             snprintf(err, err_len, "span_parse_msgpack_parents: cmp_read_u64 "
                      "for single child ID failed");
             return;
         }
     } else if (size > 1) {
-        span->parent.list = malloc(sizeof(uint64_t) * size);
+        span->parent.list = malloc(sizeof(struct htrace_span_id) * size);
         if (!span->parent.list) {
             snprintf(err, err_len, "span_parse_msgpack_parents: failed to "
                      "malloc %"PRId32"-entry parent array.", size);
             return;
         }
         for (i = 0; i < size; i++) {
-            if (!cmp_read_u64(ctx, &span->parent.list[i])) {
-                snprintf(err, err_len, "span_parse_msgpack_parents: cmp_read_u64 "
-                         "for child %d ID failed", i);
+            if (!htrace_span_id_read_msgpack(span->parent.list + i, ctx)) {
+                snprintf(err, err_len, "span_parse_msgpack_parents: "
+                    "htrace_span_id_read_msgpack for child %d ID failed", i);
                 free(span->parent.list);
                 span->parent.list = NULL;
                 return;
@@ -412,6 +379,13 @@
             goto error;
         }
         switch (key[0]) {
+        case 'a':
+            if (!htrace_span_id_read_msgpack(&span->span_id, ctx)) {
+                snprintf(err, err_len, "span_read_msgpack: "
+                    "htrace_span_id_read_msgpack failed for span->span_id");
+                goto error;
+            }
+            break;
         case 'd':
             if (span->desc) {
                 free(span->desc);
@@ -436,13 +410,6 @@
                 goto error;
             }
             break;
-        case 's':
-            if (!cmp_read_u64(ctx, &span->span_id)) {
-                snprintf(err, err_len, "span_read_msgpack: cmp_read_u64 "
-                         "failed for span->span_id");
-                goto error;
-            }
-            break;
         case 'r':
             if (span->trid) {
                 free(span->trid);
diff --git a/htrace-core/src/main/java/org/apache/htrace/Span.java b/htrace-core/src/main/java/org/apache/htrace/Span.java
index f41da30..0897ee9 100644
--- a/htrace-core/src/main/java/org/apache/htrace/Span.java
+++ b/htrace-core/src/main/java/org/apache/htrace/Span.java
@@ -75,13 +75,7 @@
    * The spanId is immutable and cannot be changed.  It is safe to access this
    * from multiple threads.
    */
-  long getSpanId();
-
-  /**
-   * A pseudo-unique (random) number assigned to the trace associated with this
-   * span
-   */
-  long getTraceId();
+  SpanId getSpanId();
 
   /**
    * Create a child span of this span with the given description
@@ -96,14 +90,14 @@
    *
    * The array will be empty if there are no parents.
    */
-  long[] getParents();
+  SpanId[] getParents();
 
   /**
    * Set the parents of this span.<p/>
    *
    * Any existing parents will be cleared by this call.
    */
-  void setParents(long[] parents);
+  void setParents(SpanId[] parents);
 
   /**
    * Add a data annotation associated with this span
@@ -151,11 +145,8 @@
     public void serialize(Span span, JsonGenerator jgen, SerializerProvider provider)
         throws IOException {
       jgen.writeStartObject();
-      if (span.getTraceId() != 0) {
-        jgen.writeStringField("i", String.format("%016x", span.getTraceId()));
-      }
-      if (span.getSpanId() != 0) {
-        jgen.writeStringField("s", String.format("%016x", span.getSpanId()));
+      if (span.getSpanId().isValid()) {
+        jgen.writeStringField("a", span.getSpanId().toString());
       }
       if (span.getStartTimeMillis() != 0) {
         jgen.writeNumberField("b", span.getStartTimeMillis());
@@ -171,8 +162,8 @@
         jgen.writeStringField("r", tracerId);
       }
       jgen.writeArrayFieldStart("p");
-      for (long parent : span.getParents()) {
-        jgen.writeString(String.format("%016x", parent));
+      for (SpanId parent : span.getParents()) {
+        jgen.writeString(parent.toString());
       }
       jgen.writeEndArray();
       Map<String, String> traceInfoMap = span.getKVAnnotations();
diff --git a/htrace-core/src/main/java/org/apache/htrace/SpanId.java b/htrace-core/src/main/java/org/apache/htrace/SpanId.java
new file mode 100644
index 0000000..25dc108
--- /dev/null
+++ b/htrace-core/src/main/java/org/apache/htrace/SpanId.java
@@ -0,0 +1,149 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.htrace;
+
+import java.math.BigInteger;
+import java.lang.Void;
+import java.util.concurrent.ThreadLocalRandom;
+import java.util.Random;
+
+/**
+ * Uniquely identifies an HTrace span.
+ *
+ * Span IDs are 128 bits in total.  The upper 64 bits of a span ID is the same
+ * as the upper 64 bits of the parent span, if there is one.  The lower 64 bits
+ * are always random.
+ */
+public final class SpanId implements Comparable<SpanId> {
+  private static final int SPAN_ID_STRING_LENGTH = 32;
+  private final long high;
+  private final long low;
+
+  /**
+   * The invalid span ID, which is all zeroes.
+   *
+   * It is also the "least" span ID in the sense that it is considered
+   * smaller than any other span ID.
+   */
+  public static SpanId INVALID = new SpanId(0, 0);
+
+  private static long nonZeroRand64() {
+    while (true) {
+      long r = ThreadLocalRandom.current().nextLong();
+      if (r != 0) {
+        return r;
+      }
+    }
+  }
+
+  public static SpanId fromRandom() {
+    return new SpanId(nonZeroRand64(), nonZeroRand64());
+  }
+
+  public static SpanId fromString(String str) {
+    if (str.length() != SPAN_ID_STRING_LENGTH) {
+      throw new RuntimeException("Invalid SpanID string: length was not " +
+          SPAN_ID_STRING_LENGTH);
+    }
+    long high =
+      ((Long.parseLong(str.substring(0, 8), 16)) << 32) |
+      (Long.parseLong(str.substring(8, 16), 16));
+    long low =
+      ((Long.parseLong(str.substring(16, 24), 16)) << 32) |
+      (Long.parseLong(str.substring(24, 32), 16));
+    return new SpanId(high, low);
+  }
+
+  public SpanId(long high, long low) {
+    this.high = high;
+    this.low = low;
+  }
+
+  public long getHigh() {
+    return high;
+  }
+
+  public long getLow() {
+    return low;
+  }
+
+  @Override
+  public boolean equals(Object o) {
+    if (!(o instanceof SpanId)) {
+      return false;
+    }
+    SpanId other = (SpanId)o;
+    return ((other.high == high) && (other.low == low));
+  }
+
+  @Override
+  public int compareTo(SpanId other) {
+    int cmp = compareAsUnsigned(high, other.high);
+    if (cmp != 0) {
+      return cmp;
+    }
+    return compareAsUnsigned(low, other.low);
+  }
+
+  private static int compareAsUnsigned(long a, long b) {
+    boolean aSign = a < 0;
+    boolean bSign = b < 0;
+    if (aSign != bSign) {
+      if (aSign) {
+        return 1;
+      } else {
+        return -1;
+      }
+    }
+    if (aSign) {
+      a = -a;
+      b = -b;
+    }
+    if (a < b) {
+      return -1;
+    } else if (a > b) {
+      return 1;
+    } else {
+      return 0;
+    }
+  }
+
+  @Override
+  public int hashCode() {
+    return (int)((0xffffffff & (high >> 32))) ^
+           (int)((0xffffffff & (high >> 0))) ^
+           (int)((0xffffffff & (low >> 32))) ^
+           (int)((0xffffffff & (low >> 0)));
+  }
+
+  @Override
+  public String toString() {
+    return String.format("%08x%08x%08x%08x",
+        (0x00000000ffffffffL & (high >> 32)),
+        (0x00000000ffffffffL & high),
+        (0x00000000ffffffffL & (low >> 32)),
+        (0x00000000ffffffffL & low));
+  }
+
+  public boolean isValid() {
+    return (high != 0)  || (low != 0);
+  }
+
+  public SpanId newChildId() {
+    return new SpanId(high, nonZeroRand64());
+  }
+}
diff --git a/htrace-core/src/main/java/org/apache/htrace/Trace.java b/htrace-core/src/main/java/org/apache/htrace/Trace.java
index b9def45..e782309 100644
--- a/htrace-core/src/main/java/org/apache/htrace/Trace.java
+++ b/htrace-core/src/main/java/org/apache/htrace/Trace.java
@@ -75,15 +75,16 @@
     return startSpan(description, NeverSampler.INSTANCE);
   }
 
-  public static TraceScope startSpan(String description, TraceInfo tinfo) {
-    if (tinfo == null) return continueSpan(null);
+  public static TraceScope startSpan(String description, SpanId parentId) {
+    if (parentId == null) {
+      return continueSpan(null);
+    }
     Span newSpan = new MilliSpan.Builder().
         begin(System.currentTimeMillis()).
         end(0).
         description(description).
-        traceId(tinfo.traceId).
-        spanId(Tracer.nonZeroRandom64()).
-        parents(new long[] { tinfo.spanId }).
+        spanId(parentId.newChildId()).
+        parents(new SpanId[] { parentId }).
         build();
     return continueSpan(newSpan);
   }
diff --git a/htrace-core/src/main/java/org/apache/htrace/TraceInfo.java b/htrace-core/src/main/java/org/apache/htrace/TraceInfo.java
deleted file mode 100644
index 9e7d74a..0000000
--- a/htrace-core/src/main/java/org/apache/htrace/TraceInfo.java
+++ /dev/null
@@ -1,38 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one or more
- * contributor license agreements.  See the NOTICE file distributed with
- * this work for additional information regarding copyright ownership.
- * The ASF licenses this file to You 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 org.apache.htrace;
-
-
-public class TraceInfo {
-  public final long traceId;
-  public final long spanId;
-
-  public TraceInfo(long traceId, long spanId) {
-    this.traceId = traceId;
-    this.spanId = spanId;
-  }
-
-  @Override
-  public String toString() {
-    return "TraceInfo(traceId=" + traceId + ", spanId=" + spanId + ")";
-  }
-
-  public static TraceInfo fromSpan(Span s) {
-    if (s == null) return null;
-    return new TraceInfo(s.getTraceId(), s.getSpanId());
-  }
-}
diff --git a/htrace-core/src/main/java/org/apache/htrace/Tracer.java b/htrace-core/src/main/java/org/apache/htrace/Tracer.java
index b0ed451..d07e1a8 100644
--- a/htrace-core/src/main/java/org/apache/htrace/Tracer.java
+++ b/htrace-core/src/main/java/org/apache/htrace/Tracer.java
@@ -48,8 +48,7 @@
       return null;
     }
   };
-  public static final TraceInfo DONT_TRACE = new TraceInfo(-1, -1);
-  private static final long EMPTY_PARENT_ARRAY[] = new long[0];
+  private static final SpanId EMPTY_PARENT_ARRAY[] = new SpanId[0];
 
   /**
    * Log a client error, and throw an exception.
@@ -81,9 +80,8 @@
           begin(System.currentTimeMillis()).
           end(0).
           description(description).
-          traceId(nonZeroRandom64()).
           parents(EMPTY_PARENT_ARRAY).
-          spanId(nonZeroRandom64()).
+          spanId(SpanId.fromRandom()).
           build();
     } else {
       return parent.child(description);
diff --git a/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java b/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java
index 3f6e700..9d49cf9 100644
--- a/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java
+++ b/htrace-core/src/main/java/org/apache/htrace/impl/MilliSpan.java
@@ -26,6 +26,7 @@
 import com.fasterxml.jackson.databind.ObjectWriter;
 import com.fasterxml.jackson.databind.annotation.JsonDeserialize;
 import org.apache.htrace.Span;
+import org.apache.htrace.SpanId;
 import org.apache.htrace.TimelineAnnotation;
 import org.apache.htrace.Tracer;
 
@@ -40,8 +41,6 @@
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
-import java.util.Random;
-import java.util.concurrent.ThreadLocalRandom;
 
 /**
  * A Span implementation that stores its information in milliseconds since the
@@ -52,37 +51,26 @@
   private static ObjectMapper OBJECT_MAPPER = new ObjectMapper();
   private static ObjectReader JSON_READER = OBJECT_MAPPER.reader(MilliSpan.class);
   private static ObjectWriter JSON_WRITER = OBJECT_MAPPER.writer();
-  private static final long EMPTY_PARENT_ARRAY[] = new long[0];
+  private static final SpanId EMPTY_PARENT_ARRAY[] = new SpanId[0];
   private static final String EMPTY_STRING = "";
 
   private long begin;
   private long end;
   private final String description;
-  private final long traceId;
-  private long parents[];
-  private final long spanId;
+  private SpanId parents[];
+  private final SpanId spanId;
   private Map<String, String> traceInfo = null;
   private String tracerId;
   private List<TimelineAnnotation> timeline = null;
 
-  private static long nonZeroRandom64() {
-    long id;
-    Random random = ThreadLocalRandom.current();
-    do {
-      id = random.nextLong();
-    } while (id == 0);
-    return id;
-  }
-
   @Override
   public Span child(String childDescription) {
     return new MilliSpan.Builder().
       begin(System.currentTimeMillis()).
       end(0).
       description(childDescription).
-      traceId(traceId).
-      parents(new long[] {spanId}).
-      spanId(nonZeroRandom64()).
+      parents(new SpanId[] {spanId}).
+      spanId(spanId.newChildId()).
       tracerId(tracerId).
       build();
   }
@@ -94,9 +82,8 @@
     private long begin;
     private long end;
     private String description = EMPTY_STRING;
-    private long traceId;
-    private long parents[] = EMPTY_PARENT_ARRAY;
-    private long spanId;
+    private SpanId parents[] = EMPTY_PARENT_ARRAY;
+    private SpanId spanId = SpanId.INVALID;
     private Map<String, String> traceInfo = null;
     private String tracerId = EMPTY_STRING;
     private List<TimelineAnnotation> timeline = null;
@@ -119,26 +106,21 @@
       return this;
     }
 
-    public Builder traceId(long traceId) {
-      this.traceId = traceId;
-      return this;
-    }
-
-    public Builder parents(long parents[]) {
+    public Builder parents(SpanId parents[]) {
       this.parents = parents;
       return this;
     }
 
-    public Builder parents(List<Long> parentList) {
-      long[] parents = new long[parentList.size()];
+    public Builder parents(List<SpanId> parentList) {
+      SpanId[] parents = new SpanId[parentList.size()];
       for (int i = 0; i < parentList.size(); i++) {
-        parents[i] = parentList.get(i).longValue();
+        parents[i] = parentList.get(i);
       }
       this.parents = parents;
       return this;
     }
 
-    public Builder spanId(long spanId) {
+    public Builder spanId(SpanId spanId) {
       this.spanId = spanId;
       return this;
     }
@@ -167,9 +149,8 @@
     this.begin = 0;
     this.end = 0;
     this.description = EMPTY_STRING;
-    this.traceId = 0;
     this.parents = EMPTY_PARENT_ARRAY;
-    this.spanId = 0;
+    this.spanId = SpanId.INVALID;
     this.traceInfo = null;
     this.tracerId = EMPTY_STRING;
     this.timeline = null;
@@ -179,7 +160,6 @@
     this.begin = builder.begin;
     this.end = builder.end;
     this.description = builder.description;
-    this.traceId = builder.traceId;
     this.parents = builder.parents;
     this.spanId = builder.spanId;
     this.traceInfo = builder.traceInfo;
@@ -227,26 +207,21 @@
   }
 
   @Override
-  public long getSpanId() {
+  public SpanId getSpanId() {
     return spanId;
   }
 
   @Override
-  public long[] getParents() {
+  public SpanId[] getParents() {
     return parents;
   }
 
   @Override
-  public void setParents(long[] parents) {
+  public void setParents(SpanId[] parents) {
     this.parents = parents;
   }
 
   @Override
-  public long getTraceId() {
-    return traceId;
-  }
-
-  @Override
   public long getStartTimeMillis() {
     return begin;
   }
@@ -308,10 +283,6 @@
     return writer.toString();
   }
 
-  private static long parseUnsignedHexLong(String s) {
-    return new BigInteger(s, 16).longValue();
-  }
-
   public static class MilliSpanDeserializer
         extends JsonDeserializer<MilliSpan> {
     @Override
@@ -331,25 +302,21 @@
       if (dNode != null) {
         builder.description(dNode.asText());
       }
-      JsonNode iNode = root.get("i");
-      if (iNode != null) {
-        builder.traceId(parseUnsignedHexLong(iNode.asText()));
-      }
-      JsonNode sNode = root.get("s");
+      JsonNode sNode = root.get("a");
       if (sNode != null) {
-        builder.spanId(parseUnsignedHexLong(sNode.asText()));
+        builder.spanId(SpanId.fromString(sNode.asText()));
       }
       JsonNode rNode = root.get("r");
       if (rNode != null) {
         builder.tracerId(rNode.asText());
       }
       JsonNode parentsNode = root.get("p");
-      LinkedList<Long> parents = new LinkedList<Long>();
+      LinkedList<SpanId> parents = new LinkedList<SpanId>();
       if (parentsNode != null) {
         for (Iterator<JsonNode> iter = parentsNode.elements();
              iter.hasNext(); ) {
           JsonNode parentIdNode = iter.next();
-          parents.add(parseUnsignedHexLong(parentIdNode.asText()));
+          parents.add(SpanId.fromString(parentIdNode.asText()));
         }
       }
       builder.parents(parents);
diff --git a/htrace-core/src/test/java/org/apache/htrace/TestBadClient.java b/htrace-core/src/test/java/org/apache/htrace/TestBadClient.java
index e13a0f8..868c0d0 100644
--- a/htrace-core/src/test/java/org/apache/htrace/TestBadClient.java
+++ b/htrace-core/src/test/java/org/apache/htrace/TestBadClient.java
@@ -24,8 +24,6 @@
 import org.apache.htrace.Span;
 import org.apache.htrace.SpanReceiver;
 import org.apache.htrace.Tracer;
-import org.apache.htrace.TraceTree.SpansByParent;
-import org.apache.htrace.TraceTree;
 import org.apache.htrace.impl.AlwaysSampler;
 import org.apache.htrace.impl.LocalFileSpanReceiver;
 import org.apache.htrace.impl.POJOSpanReceiver;
diff --git a/htrace-core/src/test/java/org/apache/htrace/TestHTrace.java b/htrace-core/src/test/java/org/apache/htrace/TestHTrace.java
index 13338e9..92f96c8 100644
--- a/htrace-core/src/test/java/org/apache/htrace/TestHTrace.java
+++ b/htrace-core/src/test/java/org/apache/htrace/TestHTrace.java
@@ -16,7 +16,7 @@
  */
 package org.apache.htrace;
 
-import org.apache.htrace.TraceTree.SpansByParent;
+import org.apache.htrace.TraceGraph.SpansByParent;
 import org.apache.htrace.impl.LocalFileSpanReceiver;
 import org.apache.htrace.impl.POJOSpanReceiver;
 import org.apache.htrace.impl.StandardOutSpanReceiver;
@@ -67,8 +67,8 @@
     traceCreator.addReceiver(new POJOSpanReceiver(HTraceConfiguration.EMPTY){
       @Override
       public void close() {
-        TraceTree traceTree = new TraceTree(getSpans());
-        Collection<Span> roots = traceTree.getSpansByParent().find(0);
+        TraceGraph traceGraph = new TraceGraph(getSpans());
+        Collection<Span> roots = traceGraph.getSpansByParent().find(SpanId.INVALID);
         Assert.assertTrue("Trace tree must have roots", !roots.isEmpty());
         Assert.assertEquals(numTraces, roots.size());
 
@@ -84,7 +84,7 @@
         Assert.assertTrue(descriptionToRootSpan.keySet().contains(
             TraceCreator.THREADED_TRACE_ROOT));
 
-        SpansByParent spansByParentId = traceTree.getSpansByParent();
+        SpansByParent spansByParentId = traceGraph.getSpansByParent();
         Span rpcTraceRoot = descriptionToRootSpan.get(TraceCreator.RPC_TRACE_ROOT);
         Assert.assertEquals(1, spansByParentId.find(rpcTraceRoot.getSpanId()).size());
 
@@ -109,11 +109,10 @@
 
   @Test(timeout=60000)
   public void testRootSpansHaveNonZeroSpanId() throws Exception {
-    TraceInfo traceInfo = new TraceInfo(100L, 200L);
-    TraceScope scope = Trace.startSpan("myRootSpan", traceInfo);
+    TraceScope scope = Trace.startSpan("myRootSpan", new SpanId(100L, 200L));
     Assert.assertNotNull(scope);
     Assert.assertEquals("myRootSpan", scope.getSpan().getDescription());
-    Assert.assertEquals(100L, scope.getSpan().getTraceId());
-    Assert.assertTrue(0 != scope.getSpan().getSpanId());
+    Assert.assertEquals(100L, scope.getSpan().getSpanId().getHigh());
+    Assert.assertTrue(scope.getSpan().getSpanId().isValid());
   }
 }
diff --git a/htrace-core/src/test/java/org/apache/htrace/TestSpanId.java b/htrace-core/src/test/java/org/apache/htrace/TestSpanId.java
new file mode 100644
index 0000000..10e6cca
--- /dev/null
+++ b/htrace-core/src/test/java/org/apache/htrace/TestSpanId.java
@@ -0,0 +1,72 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You 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 org.apache.htrace;
+
+import java.util.Random;
+import org.apache.htrace.SpanId;
+import org.junit.Assert;
+import org.junit.Test;
+
+public class TestSpanId {
+  private void testRoundTrip(SpanId id) throws Exception {
+    String str = id.toString();
+    SpanId id2 = SpanId.fromString(str);
+    Assert.assertEquals(id, id2);
+  }
+
+  @Test
+  public void testToStringAndFromString() throws Exception {
+    testRoundTrip(SpanId.INVALID);
+    testRoundTrip(new SpanId(0x1234567812345678L, 0x1234567812345678L));
+    testRoundTrip(new SpanId(0xf234567812345678L, 0xf234567812345678L));
+    testRoundTrip(new SpanId(0xffffffffffffffffL, 0xffffffffffffffffL));
+    Random rand = new Random(12345);
+    for (int i = 0; i < 100; i++) {
+      testRoundTrip(new SpanId(rand.nextLong(), rand.nextLong()));
+    }
+  }
+
+  @Test
+  public void testValidAndInvalidIds() throws Exception {
+    Assert.assertFalse(SpanId.INVALID.isValid());
+    Assert.assertTrue(
+        new SpanId(0x1234567812345678L, 0x1234567812345678L).isValid());
+    Assert.assertTrue(
+        new SpanId(0xf234567812345678L, 0xf234567812345678L).isValid());
+  }
+
+  private void expectLessThan(SpanId a, SpanId b) throws Exception {
+    int cmp = a.compareTo(b);
+    Assert.assertTrue("Expected " + a + " to be less than " + b,
+        (cmp < 0));
+    int cmp2 = b.compareTo(a);
+    Assert.assertTrue("Expected " + b + " to be greater than " + a,
+        (cmp2 > 0));
+  }
+
+  @Test
+  public void testIdComparisons() throws Exception {
+    expectLessThan(new SpanId(0x0000000000000001L, 0x0000000000000001L),
+                   new SpanId(0x0000000000000001L, 0x0000000000000002L));
+    expectLessThan(new SpanId(0x0000000000000001L, 0x0000000000000001L),
+                   new SpanId(0x0000000000000002L, 0x0000000000000000L));
+    expectLessThan(SpanId.INVALID,
+                   new SpanId(0xffffffffffffffffL, 0xffffffffffffffffL));
+    expectLessThan(new SpanId(0x1234567812345678L, 0x1234567812345678L),
+                   new SpanId(0x1234567812345678L, 0xf234567812345678L));
+  }
+}
diff --git a/htrace-core/src/main/java/org/apache/htrace/TraceTree.java b/htrace-core/src/test/java/org/apache/htrace/TraceGraph.java
similarity index 79%
rename from htrace-core/src/main/java/org/apache/htrace/TraceTree.java
rename to htrace-core/src/test/java/org/apache/htrace/TraceGraph.java
index db781cb..9004ea6 100644
--- a/htrace-core/src/main/java/org/apache/htrace/TraceTree.java
+++ b/htrace-core/src/test/java/org/apache/htrace/TraceGraph.java
@@ -35,7 +35,7 @@
 /**
  * Used to create the graph formed by spans.
  */
-public class TraceTree {
+public class TraceGraph {
   private static final Log LOG = LogFactory.getLog(Tracer.class);
 
 
@@ -47,38 +47,32 @@
         new Comparator<Span>() {
           @Override
           public int compare(Span a, Span b) {
-            if (a.getSpanId() < b.getSpanId()) {
-              return -1;
-            } else if (a.getSpanId() > b.getSpanId()) {
-              return 1;
-            } else {
-              return 0;
-            }
+            return a.getSpanId().compareTo(b.getSpanId());
           }
         };
 
     private final TreeSet<Span> treeSet;
 
-    private final HashMap<Long, LinkedList<Span>> parentToSpans;
+    private final HashMap<SpanId, LinkedList<Span>> parentToSpans;
 
     SpansByParent(Collection<Span> spans) {
       TreeSet<Span> treeSet = new TreeSet<Span>(COMPARATOR);
-      parentToSpans = new HashMap<Long, LinkedList<Span>>();
+      parentToSpans = new HashMap<SpanId, LinkedList<Span>>();
       for (Span span : spans) {
         treeSet.add(span);
-        for (long parent : span.getParents()) {
-          LinkedList<Span> list = parentToSpans.get(Long.valueOf(parent));
+        for (SpanId parent : span.getParents()) {
+          LinkedList<Span> list = parentToSpans.get(parent);
           if (list == null) {
             list = new LinkedList<Span>();
-            parentToSpans.put(Long.valueOf(parent), list);
+            parentToSpans.put(parent, list);
           }
           list.add(span);
         }
         if (span.getParents().length == 0) {
-          LinkedList<Span> list = parentToSpans.get(Long.valueOf(0L));
+          LinkedList<Span> list = parentToSpans.get(SpanId.INVALID);
           if (list == null) {
             list = new LinkedList<Span>();
-            parentToSpans.put(Long.valueOf(0L), list);
+            parentToSpans.put(SpanId.INVALID, list);
           }
           list.add(span);
         }
@@ -86,7 +80,7 @@
       this.treeSet = treeSet;
     }
 
-    public List<Span> find(long parentId) {
+    public List<Span> find(SpanId parentId) {
       LinkedList<Span> spans = parentToSpans.get(parentId);
       if (spans == null) {
         return new LinkedList<Span>();
@@ -110,13 +104,8 @@
             int cmp = a.getTracerId().compareTo(b.getTracerId());
             if (cmp != 0) {
               return cmp;
-            } else if (a.getSpanId() < b.getSpanId()) {
-              return -1;
-            } else if (a.getSpanId() > b.getSpanId()) {
-              return 1;
-            } else {
-              return 0;
             }
+            return a.getSpanId().compareTo(b.getSpanId());
           }
         };
 
@@ -133,8 +122,7 @@
     public List<Span> find(String tracerId) {
       List<Span> spans = new ArrayList<Span>();
       Span span = new MilliSpan.Builder().
-                    traceId(Long.MIN_VALUE).
-                    spanId(Long.MIN_VALUE).
+                    spanId(SpanId.INVALID).
                     tracerId(tracerId).
                     build();
       while (true) {
@@ -159,12 +147,12 @@
   private final SpansByTracerId spansByTracerId;
 
   /**
-   * Create a new TraceTree
+   * Create a new TraceGraph
    *
-   * @param spans The collection of spans to use to create this TraceTree. Should
+   * @param spans The collection of spans to use to create this TraceGraph. Should
    *              have at least one root span.
    */
-  public TraceTree(Collection<Span> spans) {
+  public TraceGraph(Collection<Span> spans) {
     this.spansByParent = new SpansByParent(spans);
     this.spansByTracerId = new SpansByTracerId(spans);
   }
diff --git a/htrace-core/src/test/java/org/apache/htrace/impl/TestMilliSpan.java b/htrace-core/src/test/java/org/apache/htrace/impl/TestMilliSpan.java
index 74ee562..9a0be4a 100644
--- a/htrace-core/src/test/java/org/apache/htrace/impl/TestMilliSpan.java
+++ b/htrace-core/src/test/java/org/apache/htrace/impl/TestMilliSpan.java
@@ -20,10 +20,10 @@
 import static org.junit.Assert.assertTrue;
 
 import org.apache.htrace.Span;
+import org.apache.htrace.SpanId;
 import org.apache.htrace.TimelineAnnotation;
 import org.junit.Test;
 
-import java.security.SecureRandom;
 import java.util.Arrays;
 import java.util.HashMap;
 import java.util.Iterator;
@@ -31,13 +31,13 @@
 import java.util.List;
 import java.util.Map;
 import java.util.Random;
+import java.util.concurrent.ThreadLocalRandom;
 
 public class TestMilliSpan {
   private void compareSpans(Span expected, Span got) throws Exception {
     assertEquals(expected.getStartTimeMillis(), got.getStartTimeMillis());
     assertEquals(expected.getStopTimeMillis(), got.getStopTimeMillis());
     assertEquals(expected.getDescription(), got.getDescription());
-    assertEquals(expected.getTraceId(), got.getTraceId());
     assertEquals(expected.getSpanId(), got.getSpanId());
     assertEquals(expected.getTracerId(), got.getTracerId());
     assertTrue(Arrays.equals(expected.getParents(), got.getParents()));
@@ -74,10 +74,10 @@
         description("foospan").
         begin(123L).
         end(456L).
-        parents(new long[] { 7L }).
+        parents(new SpanId[] { new SpanId(7L, 7L) }).
         tracerId("b2404.halxg.com:8080").
-        spanId(989L).
-        traceId(444).build();
+        spanId(new SpanId(7L, 8L)).
+        build();
     String json = span.toJson();
     MilliSpan dspan = MilliSpan.fromJson(json);
     compareSpans(span, dspan);
@@ -89,10 +89,10 @@
         description("foospan").
         begin(-1L).
         end(-1L).
-        parents(new long[] { -1L }).
+        parents(new SpanId[] { new SpanId(-1L, -1L) }).
         tracerId("b2404.halxg.com:8080").
-        spanId(-1L).
-        traceId(-1L).build();
+        spanId(new SpanId(-1L, -2L)).
+        build();
     String json = span.toJson();
     MilliSpan dspan = MilliSpan.fromJson(json);
     compareSpans(span, dspan);
@@ -100,15 +100,15 @@
 
   @Test
   public void testJsonSerializationWithRandomLongValue() throws Exception {
-    Random random = new SecureRandom();
+    SpanId parentId = SpanId.fromRandom();
     MilliSpan span = new MilliSpan.Builder().
         description("foospan").
-        begin(random.nextLong()).
-        end(random.nextLong()).
-        parents(new long[] { random.nextLong() }).
+        begin(ThreadLocalRandom.current().nextLong()).
+        end(ThreadLocalRandom.current().nextLong()).
+        parents(new SpanId[] { parentId }).
         tracerId("b2404.halxg.com:8080").
-        spanId(random.nextLong()).
-        traceId(random.nextLong()).build();
+        spanId(parentId.newChildId()).
+        build();
     String json = span.toJson();
     MilliSpan dspan = MilliSpan.fromJson(json);
     compareSpans(span, dspan);
@@ -120,10 +120,9 @@
         description("foospan").
         begin(300).
         end(400).
-        parents(new long[] { }).
+        parents(new SpanId[] { }).
         tracerId("b2408.halxg.com:8080").
-        spanId(111111111L).
-        traceId(4443);
+        spanId(new SpanId(111111111L, 111111111L));
     Map<String, String> traceInfo = new HashMap<String, String>();
     traceInfo.put("abc", "123");
     traceInfo.put("def", "456");
diff --git a/htrace-flume/src/main/java/org/apache/htrace/impl/FlumeSpanReceiver.java b/htrace-flume/src/main/java/org/apache/htrace/impl/FlumeSpanReceiver.java
index a1352ab..f930c02 100644
--- a/htrace-flume/src/main/java/org/apache/htrace/impl/FlumeSpanReceiver.java
+++ b/htrace-flume/src/main/java/org/apache/htrace/impl/FlumeSpanReceiver.java
@@ -173,9 +173,8 @@
           for (Span span : dequeuedSpans) {
             // Headers allow Flume to filter
             Map<String, String> headers = new HashMap<String, String>();
-            headers.put("TraceId",      Long.toString(span.getTraceId()));
-            headers.put("SpanId",       Long.toString(span.getSpanId()));
-            headers.put("TracerId",    span.getTracerId());
+            headers.put("SpanId",       span.toString());
+            headers.put("TracerId",     span.getTracerId());
             headers.put("Description",  span.getDescription());
 
             String body = span.toJson();
diff --git a/htrace-flume/src/test/java/org/apache/htrace/impl/TestFlumeSpanReceiver.java b/htrace-flume/src/test/java/org/apache/htrace/impl/TestFlumeSpanReceiver.java
index 6743c85..d144b62 100644
--- a/htrace-flume/src/test/java/org/apache/htrace/impl/TestFlumeSpanReceiver.java
+++ b/htrace-flume/src/test/java/org/apache/htrace/impl/TestFlumeSpanReceiver.java
@@ -19,6 +19,7 @@
 
 import org.apache.htrace.HTraceConfiguration;
 import org.apache.htrace.Span;
+import org.apache.htrace.SpanId;
 import org.apache.htrace.TraceCreator;
 import org.junit.Assert;
 import org.junit.Rule;
@@ -42,8 +43,7 @@
 
     Span rootSpan = new MilliSpan.Builder().
         description("root").
-        traceId(1).
-        spanId(100).
+        spanId(new SpanId(100, 100)).
         tracerId("test").
         begin(System.currentTimeMillis()).
         build();
diff --git a/htrace-hbase/src/main/java/org/apache/htrace/impl/HBaseSpanReceiver.java b/htrace-hbase/src/main/java/org/apache/htrace/impl/HBaseSpanReceiver.java
index beb96b5..381010f 100644
--- a/htrace-hbase/src/main/java/org/apache/htrace/impl/HBaseSpanReceiver.java
+++ b/htrace-hbase/src/main/java/org/apache/htrace/impl/HBaseSpanReceiver.java
@@ -208,17 +208,17 @@
         try {
           for (Span span : dequeuedSpans) {
             sbuilder.clear()
-                    .setTraceId(span.getTraceId())
+                    .setTraceId(span.getSpanId().getHigh())
                     .setStart(span.getStartTimeMillis())
                     .setStop(span.getStopTimeMillis())
-                    .setSpanId(span.getSpanId())
+                    .setSpanId(span.getSpanId().getLow())
                     .setProcessId(span.getTracerId())
                     .setDescription(span.getDescription());
 
             if (span.getParents().length == 0) {
               sbuilder.setParentId(0);
             } else if (span.getParents().length > 0) {
-              sbuilder.setParentId(span.getParents()[0]);
+              sbuilder.setParentId(span.getParents()[0].getLow());
               if (span.getParents().length > 1) {
                 LOG.error("error: HBaseSpanReceiver does not support spans " +
                     "with multiple parents.  Ignoring multiple parents for " +
@@ -231,7 +231,7 @@
                                             .setMessage(ta.getMessage())
                                             .build());
             }
-            Put put = new Put(Bytes.toBytes(span.getTraceId()));
+            Put put = new Put(Bytes.toBytes(span.getSpanId().getHigh()));
             put.add(HBaseSpanReceiver.this.cf,
                     sbuilder.build().toByteArray(),
                     null);
@@ -360,7 +360,7 @@
     Trace.addReceiver(receiver);
     TraceScope parent = Trace.startSpan("HBaseSpanReceiver.main.parent", Sampler.ALWAYS);
     Thread.sleep(10);
-    long traceid = parent.getSpan().getTraceId();
+    long traceid = parent.getSpan().getSpanId().getHigh();
     TraceScope child1 = Trace.startSpan("HBaseSpanReceiver.main.child.1");
     Thread.sleep(10);
     TraceScope child2 = Trace.startSpan("HBaseSpanReceiver.main.child.2", parent.getSpan());
diff --git a/htrace-hbase/src/test/java/org/apache/htrace/impl/TestHBaseSpanReceiver.java b/htrace-hbase/src/test/java/org/apache/htrace/impl/TestHBaseSpanReceiver.java
index 5027891..2224599 100644
--- a/htrace-hbase/src/test/java/org/apache/htrace/impl/TestHBaseSpanReceiver.java
+++ b/htrace-hbase/src/test/java/org/apache/htrace/impl/TestHBaseSpanReceiver.java
@@ -38,11 +38,12 @@
 import org.apache.hadoop.hbase.client.Scan;
 import org.apache.hadoop.hbase.util.Bytes;
 import org.apache.htrace.Span;
+import org.apache.htrace.SpanId;
 import org.apache.htrace.SpanReceiver;
 import org.apache.htrace.TimelineAnnotation;
 import org.apache.htrace.TraceCreator;
-import org.apache.htrace.TraceTree.SpansByParent;
-import org.apache.htrace.TraceTree;
+import org.apache.htrace.TraceGraph.SpansByParent;
+import org.apache.htrace.TraceGraph;
 import org.apache.htrace.protobuf.generated.SpanProtos;
 import org.junit.AfterClass;
 import org.junit.Assert;
@@ -93,9 +94,9 @@
       Assert.fail("failed to get spans from HBase. " + e.getMessage());
     }
 
-    TraceTree traceTree = new TraceTree(spans);
+    TraceGraph traceGraph = new TraceGraph(spans);
     Collection<Span> roots =
-        traceTree.getSpansByParent().find(0);
+        traceGraph.getSpansByParent().find(SpanId.INVALID);
     Assert.assertTrue("Trace tree must have roots", !roots.isEmpty());
     Assert.assertEquals(3, roots.size());
 
@@ -107,7 +108,7 @@
     Assert.assertTrue(descs.keySet().contains(TraceCreator.SIMPLE_TRACE_ROOT));
     Assert.assertTrue(descs.keySet().contains(TraceCreator.THREADED_TRACE_ROOT));
 
-    SpansByParent spansByParentId = traceTree.getSpansByParent();
+    SpansByParent spansByParentId = traceGraph.getSpansByParent();
     Span rpcRoot = descs.get(TraceCreator.RPC_TRACE_ROOT);
     Assert.assertEquals(1, spansByParentId.find(rpcRoot.getSpanId()).size());
     Span rpcChild1 = spansByParentId.find(rpcRoot.getSpanId()).iterator().next();
@@ -144,19 +145,14 @@
     }
 
     @Override
-    public long getTraceId() {
-      return span.getTraceId();
-    }
-
-    @Override
-    public long[] getParents() {
+    public SpanId[] getParents() {
       return (span.getParentId() == 0L) ?
-        (new long[] {}) :
-        (new long[] { span.getParentId() });
+        (new SpanId[] {}) :
+        (new SpanId[] { new SpanId(span.getTraceId(), span.getParentId()) });
     }
 
     @Override
-    public void setParents(long[] parents) {
+    public void setParents(SpanId[] parents) {
       throw new UnsupportedOperationException();
     }
 
@@ -171,8 +167,8 @@
     }
 
     @Override
-    public long getSpanId() {
-      return span.getSpanId();
+    public SpanId getSpanId() {
+      return new SpanId(span.getTraceId(), span.getSpanId());
     }
 
     @Override
diff --git a/htrace-htraced/go/src/org/apache/htrace/client/client.go b/htrace-htraced/go/src/org/apache/htrace/client/client.go
index ef827e8..5051d94 100644
--- a/htrace-htraced/go/src/org/apache/htrace/client/client.go
+++ b/htrace-htraced/go/src/org/apache/htrace/client/client.go
@@ -69,7 +69,7 @@
 
 // Get information about a trace span.  Returns nil, nil if the span was not found.
 func (hcl *Client) FindSpan(sid common.SpanId) (*common.Span, error) {
-	buf, rc, err := hcl.makeGetRequest(fmt.Sprintf("span/%016x", uint64(sid)))
+	buf, rc, err := hcl.makeGetRequest(fmt.Sprintf("span/%s", sid.String()))
 	if err != nil {
 		if rc == http.StatusNoContent {
 			return nil, nil
@@ -133,8 +133,8 @@
 
 // Find the child IDs of a given span ID.
 func (hcl *Client) FindChildren(sid common.SpanId, lim int) ([]common.SpanId, error) {
-	buf, _, err := hcl.makeGetRequest(fmt.Sprintf("span/%016x/children?lim=%d",
-		uint64(sid), lim))
+	buf, _, err := hcl.makeGetRequest(fmt.Sprintf("span/%s/children?lim=%d",
+		sid.String(), lim))
 	if err != nil {
 		return nil, err
 	}
@@ -209,7 +209,7 @@
 	defer func() {
 		close(out)
 	}()
-	searchId := common.SpanId(0)
+	searchId := common.INVALID_SPAN_ID
 	for {
 		q := common.Query{
 			Lim: lim,
@@ -232,7 +232,7 @@
 		for i := range spans {
 			out <- &spans[i]
 		}
-		searchId = spans[len(spans)-1].Id + 1
+		searchId = spans[len(spans)-1].Id.Next()
 	}
 }
 
diff --git a/htrace-htraced/go/src/org/apache/htrace/common/span.go b/htrace-htraced/go/src/org/apache/htrace/common/span.go
index 720c4cd..1716c5a 100644
--- a/htrace-htraced/go/src/org/apache/htrace/common/span.go
+++ b/htrace-htraced/go/src/org/apache/htrace/common/span.go
@@ -20,10 +20,11 @@
 package common
 
 import (
+	"bytes"
 	"encoding/json"
 	"errors"
 	"fmt"
-	"strconv"
+	"hash/fnv"
 )
 
 //
@@ -43,18 +44,88 @@
 	Msg  string `json:"m"`
 }
 
-type SpanId uint64
+type SpanId []byte
+
+var INVALID_SPAN_ID SpanId = make([]byte, 16) // all zeroes
 
 func (id SpanId) String() string {
-	return fmt.Sprintf("%016x", uint64(id))
+	return fmt.Sprintf("%02x%02x%02x%02x"+
+		"%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x",
+		id[0], id[1], id[2], id[3], id[4], id[5], id[6], id[7], id[8],
+		id[9], id[10], id[11], id[12], id[13], id[14], id[15])
 }
 
-func (id SpanId) Val() uint64 {
-	return uint64(id)
+func (id SpanId) Val() []byte {
+	return []byte(id)
+}
+
+func (id SpanId) FindProblem() string {
+	if id == nil {
+		return "The span ID is nil"
+	}
+	if len(id) != 16 {
+		return "The span ID is not exactly 16 bytes."
+	}
+	if bytes.Equal(id.Val(), INVALID_SPAN_ID.Val()) {
+		return "The span ID is all zeros."
+	}
+	return ""
+}
+
+func (id SpanId) ToArray() [16]byte {
+	var ret [16]byte
+	copy(ret[:], id.Val()[:])
+	return ret
+}
+
+// Return the next ID in lexicographical order.  For the maximum ID,
+// returns the minimum.
+func (id SpanId) Next() SpanId {
+	next := make([]byte, 16)
+	copy(next, id)
+	for i := len(next) - 1; i >= 0; i-- {
+		if next[i] == 0xff {
+			next[i] = 0
+		} else {
+			next[i] = next[i] + 1
+			break
+		}
+	}
+	return next
+}
+
+// Return the previous ID in lexicographical order.  For the minimum ID,
+// returns the maximum ID.
+func (id SpanId) Prev() SpanId {
+	prev := make([]byte, 16)
+	copy(prev, id)
+	for i := len(prev) - 1; i >= 0; i-- {
+		if prev[i] == 0x00 {
+			prev[i] = 0xff
+		} else {
+			prev[i] = prev[i] - 1
+			break
+		}
+	}
+	return prev
 }
 
 func (id SpanId) MarshalJSON() ([]byte, error) {
-	return []byte(`"` + fmt.Sprintf("%016x", uint64(id)) + `"`), nil
+	return []byte(`"` + id.String() + `"`), nil
+}
+
+func (id SpanId) Compare(other SpanId) int {
+	return bytes.Compare(id.Val(), other.Val())
+}
+
+func (id SpanId) Equal(other SpanId) bool {
+	return bytes.Equal(id.Val(), other.Val())
+}
+
+func (id SpanId) Hash32() uint32 {
+	h := fnv.New32a()
+	h.Write(id.Val())
+	return h.Sum32()
 }
 
 type SpanSlice []*Span
@@ -64,7 +135,7 @@
 }
 
 func (s SpanSlice) Less(i, j int) bool {
-	return s[i].Id < s[j].Id
+	return s[i].Id.Compare(s[j].Id) < 0
 }
 
 func (s SpanSlice) Swap(i, j int) {
@@ -78,7 +149,7 @@
 }
 
 func (s SpanIdSlice) Less(i, j int) bool {
-	return s[i] < s[j]
+	return s[i].Compare(s[j]) < 0
 }
 
 func (s SpanIdSlice) Swap(i, j int) {
@@ -98,11 +169,18 @@
 }
 
 func (id *SpanId) FromString(str string) error {
-	v, err := strconv.ParseUint(str, 16, 64)
+	i := SpanId(make([]byte, 16))
+	n, err := fmt.Sscanf(str, "%02x%02x%02x%02x"+
+		"%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x%02x",
+		&i[0], &i[1], &i[2], &i[3], &i[4], &i[5], &i[6], &i[7], &i[8],
+		&i[9], &i[10], &i[11], &i[12], &i[13], &i[14], &i[15])
 	if err != nil {
 		return err
 	}
-	*id = SpanId(v)
+	if n != 16 {
+		return errors.New("Failed to find 16 hex digits in the SpanId")
+	}
+	*id = i
 	return nil
 }
 
@@ -110,7 +188,6 @@
 	Begin               int64                `json:"b"`
 	End                 int64                `json:"e"`
 	Description         string               `json:"d"`
-	TraceId             SpanId               `json:"i"`
 	Parents             []SpanId             `json:"p"`
 	Info                TraceInfoMap         `json:"n,omitempty"`
 	TracerId            string               `json:"r"`
@@ -118,7 +195,7 @@
 }
 
 type Span struct {
-	Id SpanId `json:"s"`
+	Id SpanId `json:"a"`
 	SpanData
 }
 
diff --git a/htrace-htraced/go/src/org/apache/htrace/common/span_test.go b/htrace-htraced/go/src/org/apache/htrace/common/span_test.go
index e3b44fe..9de7cee 100644
--- a/htrace-htraced/go/src/org/apache/htrace/common/span_test.go
+++ b/htrace-htraced/go/src/org/apache/htrace/common/span_test.go
@@ -20,33 +20,35 @@
 package common
 
 import (
+	"bytes"
+	"encoding/hex"
+	"fmt"
+	"github.com/ugorji/go/codec"
 	"testing"
 )
 
 func TestSpanToJson(t *testing.T) {
 	t.Parallel()
-	span := Span{Id: 2305843009213693952,
+	span := Span{Id: TestId("33f25a1a750a471db5bafa59309d7d6f"),
 		SpanData: SpanData{
 			Begin:       123,
 			End:         456,
 			Description: "getFileDescriptors",
-			TraceId:     999,
 			Parents:     []SpanId{},
 			TracerId:    "testTracerId",
 		}}
 	ExpectStrEqual(t,
-		`{"s":"2000000000000000","b":123,"e":456,"d":"getFileDescriptors","i":"00000000000003e7","p":[],"r":"testTracerId"}`,
+		`{"a":"33f25a1a750a471db5bafa59309d7d6f","b":123,"e":456,"d":"getFileDescriptors","p":[],"r":"testTracerId"}`,
 		string(span.ToJson()))
 }
 
 func TestAnnotatedSpanToJson(t *testing.T) {
 	t.Parallel()
-	span := Span{Id: 1305813009213693952,
+	span := Span{Id: TestId("11eace42e6404b40a7644214cb779a08"),
 		SpanData: SpanData{
 			Begin:       1234,
 			End:         4567,
 			Description: "getFileDescriptors2",
-			TraceId:     999,
 			Parents:     []SpanId{},
 			TracerId:    "testAnnotatedTracerId",
 			TimelineAnnotations: []TimelineAnnotation{
@@ -61,6 +63,54 @@
 			},
 		}}
 	ExpectStrEqual(t,
-		`{"s":"121f2e036d442000","b":1234,"e":4567,"d":"getFileDescriptors2","i":"00000000000003e7","p":[],"r":"testAnnotatedTracerId","t":[{"t":7777,"m":"contactedServer"},{"t":8888,"m":"passedFd"}]}`,
+		`{"a":"11eace42e6404b40a7644214cb779a08","b":1234,"e":4567,"d":"getFileDescriptors2","p":[],"r":"testAnnotatedTracerId","t":[{"t":7777,"m":"contactedServer"},{"t":8888,"m":"passedFd"}]}`,
 		string(span.ToJson()))
 }
+
+func TestSpanNext(t *testing.T) {
+	ExpectStrEqual(t, TestId("00000000000000000000000000000001").String(),
+		TestId("00000000000000000000000000000000").Next().String())
+	ExpectStrEqual(t, TestId("00000000000000000000000000f00000").String(),
+		TestId("00000000000000000000000000efffff").Next().String())
+	ExpectStrEqual(t, TestId("00000000000000000000000000000000").String(),
+		TestId("ffffffffffffffffffffffffffffffff").Next().String())
+}
+
+func TestSpanPrev(t *testing.T) {
+	ExpectStrEqual(t, TestId("00000000000000000000000000000000").String(),
+		TestId("00000000000000000000000000000001").Prev().String())
+	ExpectStrEqual(t, TestId("00000000000000000000000000efffff").String(),
+		TestId("00000000000000000000000000f00000").Prev().String())
+	ExpectStrEqual(t, TestId("ffffffffffffffffffffffffffffffff").String(),
+		TestId("00000000000000000000000000000000").Prev().String())
+}
+
+func TestSpanMsgPack(t *testing.T) {
+	span := Span{Id: TestId("33f25a1a750a471db5bafa59309d7d6f"),
+		SpanData: SpanData{
+			Begin:       1234,
+			End:         5678,
+			Description: "getFileDescriptors",
+			Parents:     []SpanId{},
+			TracerId:   "testTracerId",
+		}}
+	mh := new(codec.MsgpackHandle)
+	mh.WriteExt = true
+	w := bytes.NewBuffer(make([]byte, 0, 2048))
+	enc := codec.NewEncoder(w, mh)
+	err := enc.Encode(span)
+	if err != nil {
+		t.Fatal("Error encoding span as msgpack: " + err.Error())
+	}
+	buf := w.Bytes()
+	fmt.Printf("span: %s\n", hex.EncodeToString(buf))
+	mh = new(codec.MsgpackHandle)
+	mh.WriteExt = true
+	dec := codec.NewDecoder(bytes.NewReader(buf), mh)
+	var span2 Span
+	err = dec.Decode(&span2)
+	if err != nil {
+		t.Fatal("Failed to reverse msgpack encoding for " + span.String())
+	}
+	ExpectSpansEqual(t, &span, &span2)
+}
diff --git a/htrace-htraced/go/src/org/apache/htrace/common/test_util.go b/htrace-htraced/go/src/org/apache/htrace/common/test_util.go
index 871c847..ec9151b 100644
--- a/htrace-htraced/go/src/org/apache/htrace/common/test_util.go
+++ b/htrace-htraced/go/src/org/apache/htrace/common/test_util.go
@@ -72,3 +72,12 @@
 func ExpectSpansEqual(t *testing.T, spanA *Span, spanB *Span) {
 	ExpectStrEqual(t, string(spanA.ToJson()), string(spanB.ToJson()))
 }
+
+func TestId(str string) SpanId {
+	var spanId SpanId
+	err := spanId.FromString(str)
+	if err != nil {
+		panic(err.Error())
+	}
+	return spanId
+}
diff --git a/htrace-htraced/go/src/org/apache/htrace/htrace/cmd.go b/htrace-htraced/go/src/org/apache/htrace/htrace/cmd.go
index 38cdb58..8fd7067 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htrace/cmd.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htrace/cmd.go
@@ -63,10 +63,10 @@
 	version := app.Command("version", "Print the version of this program.")
 	serverInfo := app.Command("serverInfo", "Print information retrieved from an htraced server.")
 	findSpan := app.Command("findSpan", "Print information about a trace span with a given ID.")
-	findSpanId := findSpan.Arg("id", "Span ID to find. Example: 0x123456789abcdef").Required().Uint64()
+	findSpanId := findSpan.Arg("id", "Span ID to find. Example: be305e54-4534-2110-a0b2-e06b9effe112").Required().String()
 	findChildren := app.Command("findChildren", "Print out the span IDs that are children of a given span ID.")
-	parentSpanId := findChildren.Arg("id", "Span ID to print children for. Example: 0x123456789abcdef").
-		Required().Uint64()
+	parentSpanId := findChildren.Arg("id", "Span ID to print children for. Example: be305e54-4534-2110-a0b2-e06b9effe112").
+		Required().String()
 	childLim := findChildren.Flag("lim", "Maximum number of child IDs to print.").Default("20").Int()
 	loadFile := app.Command("loadFile", "Write whitespace-separated JSON spans from a file to the server.")
 	loadFilePath := loadFile.Arg("path",
@@ -123,9 +123,13 @@
 	case serverInfo.FullCommand():
 		os.Exit(printServerInfo(hcl))
 	case findSpan.FullCommand():
-		os.Exit(doFindSpan(hcl, common.SpanId(*findSpanId)))
+		var id *common.SpanId
+		id.FromString(*findSpanId)
+		os.Exit(doFindSpan(hcl, *id))
 	case findChildren.FullCommand():
-		os.Exit(doFindChildren(hcl, common.SpanId(*parentSpanId), *childLim))
+		var id *common.SpanId
+		id.FromString(*parentSpanId)
+		os.Exit(doFindChildren(hcl, *id, *childLim))
 	case loadJson.FullCommand():
 		os.Exit(doLoadSpanJson(hcl, *loadJsonArg))
 	case loadFile.FullCommand():
diff --git a/htrace-htraced/go/src/org/apache/htrace/htrace/file_test.go b/htrace-htraced/go/src/org/apache/htrace/htrace/file_test.go
index 6fd6789..98e5e6c 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htrace/file_test.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htrace/file_test.go
@@ -25,7 +25,6 @@
 	"io/ioutil"
 	"org/apache/htrace/common"
 	"org/apache/htrace/conf"
-	"org/apache/htrace/test"
 	"os"
 	"strings"
 	"testing"
@@ -116,10 +115,10 @@
 }
 
 func TestReadSpans(t *testing.T) {
-	SPAN_TEST_STR := `{"i":"bdd6d4ee48de59bf","s":"c0681027d3ea4928",` +
+	SPAN_TEST_STR := `{"a":"b9f2a1e07b6e4f16b0c2b27303b20e79",` +
 		`"b":1424736225037,"e":1424736225901,"d":"ClientNamenodeProtocol#getFileInfo",` +
-		`"r":"FsShell","p":["60538dfb4df91418"]}
-{"i":"bdd6d4ee48de59bf","s":"60538dfb4df91418","b":1424736224969,` +
+		`"r":"FsShell","p":["3afebdc0a13f4feb811cc5c0e42d30b1"]}
+{"a":"3afebdc0a13f4feb811cc5c0e42d30b1","b":1424736224969,` +
 		`"e":1424736225960,"d":"getFileInfo","r":"FsShell","p":[],"n":{"path":"/"}}
 `
 	r := strings.NewReader(SPAN_TEST_STR)
@@ -129,20 +128,18 @@
 	}
 	SPAN_TEST_EXPECTED := common.SpanSlice{
 		&common.Span{
-			Id: test.SpanId("c0681027d3ea4928"),
+			Id: common.TestId("b9f2a1e07b6e4f16b0c2b27303b20e79"),
 			SpanData: common.SpanData{
-				TraceId:     test.SpanId("bdd6d4ee48de59bf"),
 				Begin:       1424736225037,
 				End:         1424736225901,
 				Description: "ClientNamenodeProtocol#getFileInfo",
 				TracerId:    "FsShell",
-				Parents:     []common.SpanId{test.SpanId("60538dfb4df91418")},
+				Parents:     []common.SpanId{common.TestId("3afebdc0a13f4feb811cc5c0e42d30b1")},
 			},
 		},
 		&common.Span{
-			Id: test.SpanId("60538dfb4df91418"),
+			Id: common.TestId("3afebdc0a13f4feb811cc5c0e42d30b1"),
 			SpanData: common.SpanData{
-				TraceId:     test.SpanId("bdd6d4ee48de59bf"),
 				Begin:       1424736224969,
 				End:         1424736225960,
 				Description: "getFileInfo",
diff --git a/htrace-htraced/go/src/org/apache/htrace/htrace/graph.go b/htrace-htraced/go/src/org/apache/htrace/htrace/graph.go
index dabf2df..024d973 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htrace/graph.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htrace/graph.go
@@ -64,32 +64,32 @@
 // Create output in dotfile format from a set of spans.
 func spansToDot(spans common.SpanSlice, writer io.Writer) error {
 	sort.Sort(spans)
-	idMap := make(map[common.SpanId]*common.Span)
+	idMap := make(map[[16]byte]*common.Span)
 	for i := range spans {
 		span := spans[i]
-		if idMap[span.Id] != nil {
+		if idMap[span.Id.ToArray()] != nil {
 			fmt.Fprintf(os.Stderr, "There were multiple spans listed which "+
 				"had ID %s.\nFirst:%s\nOther:%s\n", span.Id.String(),
-				idMap[span.Id].ToJson(), span.ToJson())
+				idMap[span.Id.ToArray()].ToJson(), span.ToJson())
 		} else {
-			idMap[span.Id] = span
+			idMap[span.Id.ToArray()] = span
 		}
 	}
-	childMap := make(map[common.SpanId]common.SpanSlice)
+	childMap := make(map[[16]byte]common.SpanSlice)
 	for i := range spans {
 		child := spans[i]
 		for j := range child.Parents {
-			parent := idMap[child.Parents[j]]
+			parent := idMap[child.Parents[j].ToArray()]
 			if parent == nil {
 				fmt.Fprintf(os.Stderr, "Can't find parent id %s for %s\n",
 					child.Parents[j].String(), child.ToJson())
 			} else {
-				children := childMap[parent.Id]
+				children := childMap[parent.Id.ToArray()]
 				if children == nil {
 					children = make(common.SpanSlice, 0)
 				}
 				children = append(children, child)
-				childMap[parent.Id] = children
+				childMap[parent.Id.ToArray()] = children
 			}
 		}
 	}
@@ -102,7 +102,7 @@
 	}
 	// Write out the edges between nodes... the parent/children relationships
 	for i := range spans {
-		children := childMap[spans[i].Id]
+		children := childMap[spans[i].Id.ToArray()]
 		sort.Sort(children)
 		if children != nil {
 			for c := range children {
diff --git a/htrace-htraced/go/src/org/apache/htrace/htrace/graph_test.go b/htrace-htraced/go/src/org/apache/htrace/htrace/graph_test.go
index e614cec..621b3dc 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htrace/graph_test.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htrace/graph_test.go
@@ -22,16 +22,14 @@
 import (
 	"bytes"
 	"org/apache/htrace/common"
-	"org/apache/htrace/test"
 	"testing"
 )
 
 func TestSpansToDot(t *testing.T) {
 	TEST_SPANS := common.SpanSlice{
 		&common.Span{
-			Id: test.SpanId("6af3cc058e5d829d"),
+			Id: common.TestId("814c8ee0e7984be3a8af00ac64adccb6"),
 			SpanData: common.SpanData{
-				TraceId:     test.SpanId("0e4716fe911244de"),
 				Begin:       1424813349020,
 				End:         1424813349134,
 				Description: "newDFSInputStream",
@@ -43,25 +41,23 @@
 			},
 		},
 		&common.Span{
-			Id: test.SpanId("75d16cc5b2c07d8a"),
+			Id: common.TestId("cf2d5de696454548bc055d1e6024054c"),
 			SpanData: common.SpanData{
-				TraceId:     test.SpanId("0e4716fe911244de"),
 				Begin:       1424813349025,
 				End:         1424813349133,
 				Description: "getBlockLocations",
 				TracerId:    "FsShell",
-				Parents:     []common.SpanId{test.SpanId("6af3cc058e5d829d")},
+				Parents:     []common.SpanId{common.TestId("814c8ee0e7984be3a8af00ac64adccb6")},
 			},
 		},
 		&common.Span{
-			Id: test.SpanId("e2c7273efb280a8c"),
+			Id: common.TestId("37623806f9c64483b834b8ea5d6b4827"),
 			SpanData: common.SpanData{
-				TraceId:     test.SpanId("0e4716fe911244de"),
 				Begin:       1424813349027,
 				End:         1424813349073,
 				Description: "ClientNamenodeProtocol#getBlockLocations",
 				TracerId:    "FsShell",
-				Parents:     []common.SpanId{test.SpanId("75d16cc5b2c07d8a")},
+				Parents:     []common.SpanId{common.TestId("cf2d5de696454548bc055d1e6024054c")},
 			},
 		},
 	}
@@ -71,11 +67,11 @@
 		t.Fatalf("spansToDot failed: error %s\n", err.Error())
 	}
 	EXPECTED_STR := `digraph spans {
-  "6af3cc058e5d829d" [label="newDFSInputStream"];
-  "75d16cc5b2c07d8a" [label="getBlockLocations"];
-  "e2c7273efb280a8c" [label="ClientNamenodeProtocol#getBlockLocations"];
-  "6af3cc058e5d829d" -> "75d16cc5b2c07d8a";
-  "75d16cc5b2c07d8a" -> "e2c7273efb280a8c";
+  "37623806f9c64483b834b8ea5d6b4827" [label="ClientNamenodeProtocol#getBlockLocations"];
+  "814c8ee0e7984be3a8af00ac64adccb6" [label="newDFSInputStream"];
+  "cf2d5de696454548bc055d1e6024054c" [label="getBlockLocations"];
+  "814c8ee0e7984be3a8af00ac64adccb6" -> "cf2d5de696454548bc055d1e6024054c";
+  "cf2d5de696454548bc055d1e6024054c" -> "37623806f9c64483b834b8ea5d6b4827";
 }
 `
 	if w.String() != EXPECTED_STR {
diff --git a/htrace-htraced/go/src/org/apache/htrace/htraced/client_test.go b/htrace-htraced/go/src/org/apache/htrace/htraced/client_test.go
index 218c1c8..02a00f3 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htraced/client_test.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htraced/client_test.go
@@ -121,7 +121,7 @@
 		t.Fatalf("FindChildren(%s) returned an invalid number of "+
 			"children: expected %d, got %d\n", parentId, 1, len(children))
 	}
-	if children[0] != childSpan.Id {
+	if !children[0].Equal(childSpan.Id) {
 		t.Fatalf("FindChildren(%s) returned an invalid child id: expected %s, "+
 			" got %s\n", parentId, childSpan.Id, children[0])
 	}
diff --git a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go
index 48f02aa..5885168 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore.go
@@ -22,6 +22,7 @@
 import (
 	"bytes"
 	"encoding/gob"
+	"encoding/hex"
 	"errors"
 	"fmt"
 	"github.com/jmhodges/levigo"
@@ -68,6 +69,7 @@
 var EMPTY_BYTE_BUF []byte = []byte{}
 
 const VERSION_KEY = 'v'
+
 const SPAN_ID_INDEX_PREFIX = 's'
 const BEGIN_TIME_INDEX_PREFIX = 'b'
 const END_TIME_INDEX_PREFIX = 'e'
@@ -90,56 +92,6 @@
 	}
 }
 
-// Translate an 8-byte value into a leveldb key.
-func makeKey(tag byte, val uint64) []byte {
-	return []byte{
-		tag,
-		byte(0xff & (val >> 56)),
-		byte(0xff & (val >> 48)),
-		byte(0xff & (val >> 40)),
-		byte(0xff & (val >> 32)),
-		byte(0xff & (val >> 24)),
-		byte(0xff & (val >> 16)),
-		byte(0xff & (val >> 8)),
-		byte(0xff & (val >> 0)),
-	}
-}
-
-func keyToInt(key []byte) uint64 {
-	var id uint64
-	id = (uint64(key[0]) << 56) |
-		(uint64(key[1]) << 48) |
-		(uint64(key[2]) << 40) |
-		(uint64(key[3]) << 32) |
-		(uint64(key[4]) << 24) |
-		(uint64(key[5]) << 16) |
-		(uint64(key[6]) << 8) |
-		(uint64(key[7]) << 0)
-	return id
-}
-
-func makeSecondaryKey(tag byte, fir uint64, sec uint64) []byte {
-	return []byte{
-		tag,
-		byte(0xff & (fir >> 56)),
-		byte(0xff & (fir >> 48)),
-		byte(0xff & (fir >> 40)),
-		byte(0xff & (fir >> 32)),
-		byte(0xff & (fir >> 24)),
-		byte(0xff & (fir >> 16)),
-		byte(0xff & (fir >> 8)),
-		byte(0xff & (fir >> 0)),
-		byte(0xff & (sec >> 56)),
-		byte(0xff & (sec >> 48)),
-		byte(0xff & (sec >> 40)),
-		byte(0xff & (sec >> 32)),
-		byte(0xff & (sec >> 24)),
-		byte(0xff & (sec >> 16)),
-		byte(0xff & (sec >> 8)),
-		byte(0xff & (sec >> 0)),
-	}
-}
-
 // A single directory containing a levelDB instance.
 type shard struct {
 	// The data store that this shard is part of
@@ -186,6 +138,18 @@
 	return ret
 }
 
+func u64toSlice(val uint64) []byte {
+	return []byte{
+		byte(0xff & (val >> 56)),
+		byte(0xff & (val >> 48)),
+		byte(0xff & (val >> 40)),
+		byte(0xff & (val >> 32)),
+		byte(0xff & (val >> 24)),
+		byte(0xff & (val >> 16)),
+		byte(0xff & (val >> 8)),
+		byte(0xff & (val >> 0))}
+}
+
 func (shd *shard) writeSpan(span *common.Span) error {
 	batch := levigo.NewWriteBatch()
 	defer batch.Close()
@@ -197,21 +161,27 @@
 	if err != nil {
 		return err
 	}
-	batch.Put(makeKey(SPAN_ID_INDEX_PREFIX, span.Id.Val()), spanDataBuf.Bytes())
+	primaryKey :=
+		append([]byte{SPAN_ID_INDEX_PREFIX}, span.Id.Val()...)
+	batch.Put(primaryKey, spanDataBuf.Bytes())
 
 	// Add this to the parent index.
 	for parentIdx := range span.Parents {
-		batch.Put(makeSecondaryKey(PARENT_ID_INDEX_PREFIX,
-			span.Parents[parentIdx].Val(), span.Id.Val()), EMPTY_BYTE_BUF)
+		key := append(append([]byte{PARENT_ID_INDEX_PREFIX},
+			span.Parents[parentIdx].Val()...), span.Id.Val()...)
+		batch.Put(key, EMPTY_BYTE_BUF)
 	}
 
 	// Add to the other secondary indices.
-	batch.Put(makeSecondaryKey(BEGIN_TIME_INDEX_PREFIX, s2u64(span.Begin),
-		span.Id.Val()), EMPTY_BYTE_BUF)
-	batch.Put(makeSecondaryKey(END_TIME_INDEX_PREFIX, s2u64(span.End),
-		span.Id.Val()), EMPTY_BYTE_BUF)
-	batch.Put(makeSecondaryKey(DURATION_INDEX_PREFIX, s2u64(span.Duration()),
-		span.Id.Val()), EMPTY_BYTE_BUF)
+	beginTimeKey := append(append([]byte{BEGIN_TIME_INDEX_PREFIX},
+		u64toSlice(s2u64(span.Begin))...), span.Id.Val()...)
+	batch.Put(beginTimeKey, EMPTY_BYTE_BUF)
+	endTimeKey := append(append([]byte{END_TIME_INDEX_PREFIX},
+		u64toSlice(s2u64(span.End))...), span.Id.Val()...)
+	batch.Put(endTimeKey, EMPTY_BYTE_BUF)
+	durationKey := append(append([]byte{DURATION_INDEX_PREFIX},
+		u64toSlice(s2u64(span.Duration()))...), span.Id.Val()...)
+	batch.Put(durationKey, EMPTY_BYTE_BUF)
 
 	err = shd.ldb.Write(shd.store.writeOpts, batch)
 	if err != nil {
@@ -226,7 +196,7 @@
 
 func (shd *shard) FindChildren(sid common.SpanId, childIds []common.SpanId,
 	lim int32) ([]common.SpanId, int32, error) {
-	searchKey := makeKey('p', sid.Val())
+	searchKey := append([]byte{PARENT_ID_INDEX_PREFIX}, sid.Val()...)
 	iter := shd.ldb.NewIterator(shd.store.readOpts)
 	defer iter.Close()
 	iter.Seek(searchKey)
@@ -241,7 +211,7 @@
 		if !bytes.HasPrefix(key, searchKey) {
 			break
 		}
-		id := common.SpanId(keyToInt(key[9:]))
+		id := common.SpanId(key[17:])
 		childIds = append(childIds, id)
 		lim--
 		iter.Next()
@@ -462,7 +432,7 @@
 
 // Get the index of the shard which stores the given spanId.
 func (store *dataStore) getShardIndex(sid common.SpanId) int {
-	return int(sid.Val() % uint64(len(store.shards)))
+	return int(sid.Hash32() % uint32(len(store.shards)))
 }
 
 func (store *dataStore) WriteSpan(span *common.Span) {
@@ -475,7 +445,8 @@
 
 func (shd *shard) FindSpan(sid common.SpanId) *common.Span {
 	lg := shd.store.lg
-	buf, err := shd.ldb.Get(shd.store.readOpts, makeKey('s', sid.Val()))
+	primaryKey := append([]byte{SPAN_ID_INDEX_PREFIX}, sid.Val()...)
+	buf, err := shd.ldb.Get(shd.store.readOpts, primaryKey)
 	if err != nil {
 		if strings.Index(err.Error(), "NotFound:") != -1 {
 			return nil
@@ -541,8 +512,7 @@
 
 type predicateData struct {
 	*common.Predicate
-	uintKey uint64
-	strKey  string
+	key []byte
 }
 
 func loadPredicateData(pred *common.Predicate) (*predicateData, error) {
@@ -558,11 +528,11 @@
 			return nil, errors.New(fmt.Sprintf("Unable to parse span id '%s': %s",
 				pred.Val, err.Error()))
 		}
-		p.uintKey = id.Val()
+		p.key = id.Val()
 		break
 	case common.DESCRIPTION:
 		// Any string is valid for a description.
-		p.strKey = pred.Val
+		p.key = []byte(pred.Val)
 		break
 	case common.BEGIN_TIME, common.END_TIME, common.DURATION:
 		// Parse a base-10 signed numeric field.
@@ -571,11 +541,11 @@
 			return nil, errors.New(fmt.Sprintf("Unable to parse %s '%s': %s",
 				pred.Field, pred.Val, err.Error()))
 		}
-		p.uintKey = s2u64(v)
+		p.key = u64toSlice(s2u64(v))
 		break
 	case common.TRACER_ID:
 		// Any string is valid for a tracer ID.
-		p.strKey = pred.Val
+		p.key = []byte(pred.Val)
 		break
 	default:
 		return nil, errors.New(fmt.Sprintf("Unknown field %s", pred.Field))
@@ -626,22 +596,22 @@
 }
 
 // Get the values that this predicate cares about for a given span.
-func (pred *predicateData) extractRelevantSpanData(span *common.Span) (uint64, string) {
+func (pred *predicateData) extractRelevantSpanData(span *common.Span) []byte {
 	switch pred.Field {
 	case common.SPAN_ID:
-		return span.Id.Val(), ""
+		return span.Id.Val()
 	case common.DESCRIPTION:
-		return 0, span.Description
+		return []byte(span.Description)
 	case common.BEGIN_TIME:
-		return s2u64(span.Begin), ""
+		return u64toSlice(s2u64(span.Begin))
 	case common.END_TIME:
-		return s2u64(span.End), ""
+		return u64toSlice(s2u64(span.End))
 	case common.DURATION:
-		return s2u64(span.Duration()), ""
+		return u64toSlice(s2u64(span.Duration()))
 	case common.TRACER_ID:
-		return 0, span.TracerId
+		return []byte(span.TracerId)
 	default:
-		panic(fmt.Sprintf("Field type %s isn't a 64-bit integer.", pred.Field))
+		panic(fmt.Sprintf("Unknown field type %s.", pred.Field))
 	}
 }
 
@@ -656,56 +626,33 @@
 		return true
 	}
 	// Compare the spans according to this predicate.
-	aInt, aStr := pred.extractRelevantSpanData(a)
-	bInt, bStr := pred.extractRelevantSpanData(b)
-	if pred.fieldIsNumeric() {
-		if pred.Op.IsDescending() {
-			return aInt > bInt
-		} else {
-			return aInt < bInt
-		}
+	aVal := pred.extractRelevantSpanData(a)
+	bVal := pred.extractRelevantSpanData(b)
+	cmp := bytes.Compare(aVal, bVal)
+	if pred.Op.IsDescending() {
+		return cmp > 0
 	} else {
-		if pred.Op.IsDescending() {
-			return aStr > bStr
-		} else {
-			return aStr < bStr
-		}
+		return cmp < 0
 	}
 }
 
 // Returns true if the predicate is satisfied by the given span.
 func (pred *predicateData) satisfiedBy(span *common.Span) bool {
-	intVal, strVal := pred.extractRelevantSpanData(span)
-	if pred.fieldIsNumeric() {
-		switch pred.Op {
-		case common.EQUALS:
-			return intVal == pred.uintKey
-		case common.LESS_THAN_OR_EQUALS:
-			return intVal <= pred.uintKey
-		case common.GREATER_THAN_OR_EQUALS:
-			return intVal >= pred.uintKey
-		case common.GREATER_THAN:
-			return intVal > pred.uintKey
-		default:
-			panic(fmt.Sprintf("unknown Op type %s should have been caught "+
-				"during normalization", pred.Op))
-		}
-	} else {
-		switch pred.Op {
-		case common.CONTAINS:
-			return strings.Contains(strVal, pred.strKey)
-		case common.EQUALS:
-			return strVal == pred.strKey
-		case common.LESS_THAN_OR_EQUALS:
-			return strVal <= pred.strKey
-		case common.GREATER_THAN_OR_EQUALS:
-			return strVal >= pred.strKey
-		case common.GREATER_THAN:
-			return strVal > pred.strKey
-		default:
-			panic(fmt.Sprintf("unknown Op type %s should have been caught "+
-				"during normalization", pred.Op))
-		}
+	val := pred.extractRelevantSpanData(span)
+	switch pred.Op {
+	case common.CONTAINS:
+		return bytes.Contains(val, pred.key)
+	case common.EQUALS:
+		return bytes.Equal(val, pred.key)
+	case common.LESS_THAN_OR_EQUALS:
+		return bytes.Compare(val, pred.key) <= 0
+	case common.GREATER_THAN_OR_EQUALS:
+		return bytes.Compare(val, pred.key) >= 0
+	case common.GREATER_THAN:
+		return bytes.Compare(val, pred.key) > 0
+	default:
+		panic(fmt.Sprintf("unknown Op type %s should have been caught "+
+			"during normalization", pred.Op))
 	}
 }
 
@@ -746,7 +693,7 @@
 		// organized as [type-code][8b-secondary-key][8b-span-id], elements
 		// with the same secondary index field are ordered by span ID.  So we
 		// create a 17-byte key incorporating the span ID from 'prev.'
-		var startId common.SpanId
+		startId := common.INVALID_SPAN_ID
 		switch pred.Op {
 		case common.EQUALS:
 			if pred.Field == common.SPAN_ID {
@@ -759,17 +706,17 @@
 				lg.Debugf("Attempted to use a continuation token with an EQUALS "+
 					"SPAN_ID query. %s.  Setting search id = 0",
 					pred.Predicate.String())
-				startId = 0
+				startId = common.INVALID_SPAN_ID
 			} else {
 				// When doing an EQUALS search on a secondary index, the
 				// results are sorted by span id.
-				startId = prev.Id + 1
+				startId = prev.Id.Next()
 			}
 		case common.LESS_THAN_OR_EQUALS:
 			// Subtract one from the previous span id.  Since the previous
 			// start ID will never be 0 (0 is an illegal span id), we'll never
 			// wrap around when doing this.
-			startId = prev.Id - 1
+			startId = prev.Id.Prev()
 		case common.GREATER_THAN_OR_EQUALS:
 			// We can't add one to the span id, since the previous span ID
 			// might be the maximum value.  So just switch over to using
@@ -785,21 +732,22 @@
 			panic(str)
 		}
 		if pred.Field == common.SPAN_ID {
-			pred.uintKey = uint64(startId)
-			searchKey = makeKey(src.keyPrefix, uint64(startId))
+			pred.key = startId.Val()
+			searchKey = append([]byte{src.keyPrefix}, startId.Val()...)
 		} else {
 			// Start where the previous query left off.  This means adjusting
 			// our uintKey.
-			pred.uintKey, _ = pred.extractRelevantSpanData(prev)
-			searchKey = makeSecondaryKey(src.keyPrefix, pred.uintKey, uint64(startId))
+			pred.key = pred.extractRelevantSpanData(prev)
+			searchKey = append(append([]byte{src.keyPrefix}, pred.key...),
+				startId.Val()...)
 		}
 		if lg.TraceEnabled() {
 			lg.Tracef("Handling continuation token %s for %s.  startId=%d, "+
-				"pred.uintKey=%d\n", prev, pred.Predicate.String(), startId,
-				pred.uintKey)
+				"pred.uintKey=%s\n", prev, pred.Predicate.String(), startId,
+				hex.EncodeToString(pred.key))
 		}
 	} else {
-		searchKey = makeKey(src.keyPrefix, pred.uintKey)
+		searchKey = append([]byte{src.keyPrefix}, pred.key...)
 	}
 	for i := range src.iters {
 		src.iters[i].Seek(searchKey)
@@ -866,7 +814,7 @@
 		var sid common.SpanId
 		if src.keyPrefix == SPAN_ID_INDEX_PREFIX {
 			// The span id maps to the span itself.
-			sid = common.SpanId(keyToInt(key[1:]))
+			sid = common.SpanId(key[1:17])
 			span, err = src.store.shards[shardIdx].decodeSpan(sid, iter.Value())
 			if err != nil {
 				lg.Debugf("Internal error decoding span %s in shard %d: %s\n",
@@ -875,7 +823,7 @@
 			}
 		} else {
 			// With a secondary index, we have to look up the span by id.
-			sid = common.SpanId(keyToInt(key[9:]))
+			sid = common.SpanId(key[9:25])
 			span = src.store.shards[shardIdx].FindSpan(sid)
 			if span == nil {
 				lg.Debugf("Internal error rehydrating span %s in shard %d\n",
@@ -948,7 +896,7 @@
 	// If there are no predicates that are indexed, read rows in order of span id.
 	spanIdPred := common.Predicate{Op: common.GREATER_THAN_OR_EQUALS,
 		Field: common.SPAN_ID,
-		Val:   "0000000000000000",
+		Val:   common.INVALID_SPAN_ID.String(),
 	}
 	spanIdPredData, err := loadPredicateData(&spanIdPred)
 	if err != nil {
diff --git a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go
index 0c122fd..0caa509 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htraced/datastore_test.go
@@ -45,31 +45,28 @@
 }
 
 var SIMPLE_TEST_SPANS []common.Span = []common.Span{
-	common.Span{Id: 1,
+	common.Span{Id: common.TestId("00000000000000000000000000000001"),
 		SpanData: common.SpanData{
 			Begin:       123,
 			End:         456,
 			Description: "getFileDescriptors",
-			TraceId:     999,
 			Parents:     []common.SpanId{},
 			TracerId:    "firstd",
 		}},
-	common.Span{Id: 2,
+	common.Span{Id: common.TestId("00000000000000000000000000000002"),
 		SpanData: common.SpanData{
 			Begin:       125,
 			End:         200,
 			Description: "openFd",
-			TraceId:     999,
-			Parents:     []common.SpanId{1},
+			Parents:     []common.SpanId{common.TestId("00000000000000000000000000000001")},
 			TracerId:    "secondd",
 		}},
-	common.Span{Id: 3,
+	common.Span{Id: common.TestId("00000000000000000000000000000003"),
 		SpanData: common.SpanData{
 			Begin:       200,
 			End:         456,
 			Description: "passFd",
-			TraceId:     999,
-			Parents:     []common.SpanId{1},
+			Parents:     []common.SpanId{common.TestId("00000000000000000000000000000001")},
 			TracerId:    "thirdd",
 		}},
 }
@@ -98,27 +95,27 @@
 	if ht.Store.GetStatistics().NumSpansWritten < uint64(len(SIMPLE_TEST_SPANS)) {
 		t.Fatal()
 	}
-	span := ht.Store.FindSpan(1)
+	span := ht.Store.FindSpan(common.TestId("00000000000000000000000000000001"))
 	if span == nil {
 		t.Fatal()
 	}
-	if span.Id != 1 {
+	if !span.Id.Equal(common.TestId("00000000000000000000000000000001")) {
 		t.Fatal()
 	}
 	common.ExpectSpansEqual(t, &SIMPLE_TEST_SPANS[0], span)
-	children := ht.Store.FindChildren(1, 1)
+	children := ht.Store.FindChildren(common.TestId("00000000000000000000000000000001"), 1)
 	if len(children) != 1 {
 		t.Fatalf("expected 1 child, but got %d\n", len(children))
 	}
-	children = ht.Store.FindChildren(1, 2)
+	children = ht.Store.FindChildren(common.TestId("00000000000000000000000000000001"), 2)
 	if len(children) != 2 {
 		t.Fatalf("expected 2 children, but got %d\n", len(children))
 	}
 	sort.Sort(common.SpanIdSlice(children))
-	if children[0] != 2 {
+	if !children[0].Equal(common.TestId("00000000000000000000000000000002")) {
 		t.Fatal()
 	}
-	if children[1] != 3 {
+	if !children[1].Equal(common.TestId("00000000000000000000000000000003")) {
 		t.Fatal()
 	}
 }
@@ -258,7 +255,7 @@
 			common.Predicate{
 				Op:    common.LESS_THAN_OR_EQUALS,
 				Field: common.SPAN_ID,
-				Val:   "0",
+				Val:   common.TestId("00000000000000000000000000000000").String(),
 			},
 		},
 		Lim: 200,
@@ -269,7 +266,7 @@
 			common.Predicate{
 				Op:    common.LESS_THAN_OR_EQUALS,
 				Field: common.SPAN_ID,
-				Val:   "2",
+				Val:   common.TestId("00000000000000000000000000000002").String(),
 			},
 		},
 		Lim: 200,
@@ -477,7 +474,7 @@
 			common.Predicate{
 				Op:    common.EQUALS,
 				Field: common.SPAN_ID,
-				Val:   "1",
+				Val:   common.TestId("00000000000000000000000000000001").String(),
 			},
 		},
 		Lim:  100,
@@ -491,7 +488,7 @@
 			common.Predicate{
 				Op:    common.LESS_THAN_OR_EQUALS,
 				Field: common.SPAN_ID,
-				Val:   "2",
+				Val:   common.TestId("00000000000000000000000000000002").String(),
 			},
 		},
 		Lim:  100,
diff --git a/htrace-htraced/go/src/org/apache/htrace/htraced/hrpc.go b/htrace-htraced/go/src/org/apache/htrace/htraced/hrpc.go
index 71b9625..354d064 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htraced/hrpc.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htraced/hrpc.go
@@ -193,6 +193,10 @@
 		"defaultTrid = %s\n", len(req.Spans), req.DefaultTrid)
 	for i := range req.Spans {
 		span := req.Spans[i]
+		spanIdProblem := span.Id.FindProblem()
+		if spanIdProblem != "" {
+			return errors.New(fmt.Sprintf("Invalid span ID: %s", spanIdProblem))
+		}
 		if span.TracerId == "" {
 			span.TracerId = req.DefaultTrid
 		}
diff --git a/htrace-htraced/go/src/org/apache/htrace/htraced/rest.go b/htrace-htraced/go/src/org/apache/htrace/htraced/rest.go
index cd90038..66f78f8 100644
--- a/htrace-htraced/go/src/org/apache/htrace/htraced/rest.go
+++ b/htrace-htraced/go/src/org/apache/htrace/htraced/rest.go
@@ -76,14 +76,15 @@
 
 func (hand *dataStoreHandler) parseSid(w http.ResponseWriter,
 	str string) (common.SpanId, bool) {
-	val, err := strconv.ParseUint(str, 16, 64)
+	var id common.SpanId
+	err := id.FromString(str)
 	if err != nil {
 		writeError(hand.lg, w, http.StatusBadRequest,
 			fmt.Sprintf("Failed to parse span ID %s: %s", str, err.Error()))
 		w.Write([]byte("Error parsing : " + err.Error()))
-		return 0, false
+		return common.INVALID_SPAN_ID, false
 	}
-	return common.SpanId(val), true
+	return id, true
 }
 
 func (hand *dataStoreHandler) getReqField32(fieldName string, w http.ResponseWriter,
diff --git a/htrace-htraced/go/src/org/apache/htrace/test/random.go b/htrace-htraced/go/src/org/apache/htrace/test/random.go
index 96a3e8b..540ea14 100644
--- a/htrace-htraced/go/src/org/apache/htrace/test/random.go
+++ b/htrace-htraced/go/src/org/apache/htrace/test/random.go
@@ -38,6 +38,15 @@
 	}
 }
 
+func NonZeroRandSpanId(rnd *rand.Rand) common.SpanId {
+	var id common.SpanId
+	id = make([]byte, 16)
+	for i := 0; i < len(id); i++ {
+		id[i] = byte(rnd.Intn(0x100))
+	}
+	return id
+}
+
 func NonZeroRand32(rnd *rand.Rand) int32 {
 	for {
 		r := rnd.Int31()
@@ -60,12 +69,11 @@
 			parents = []common.SpanId{potentialParents[parentIdx].Id}
 		}
 	}
-	return &common.Span{Id: common.SpanId(NonZeroRand64(rnd)),
+	return &common.Span{Id: NonZeroRandSpanId(rnd),
 		SpanData: common.SpanData{
 			Begin:       NonZeroRand64(rnd),
 			End:         NonZeroRand64(rnd),
 			Description: "getFileDescriptors",
-			TraceId:     common.SpanId(NonZeroRand64(rnd)),
 			Parents:     parents,
 			TracerId:    fmt.Sprintf("tracer%d", NonZeroRand32(rnd)),
 		}}
diff --git a/htrace-htraced/go/src/org/apache/htrace/test/util.go b/htrace-htraced/go/src/org/apache/htrace/test/util.go
deleted file mode 100644
index cc058e0..0000000
--- a/htrace-htraced/go/src/org/apache/htrace/test/util.go
+++ /dev/null
@@ -1,33 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements.  See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership.  The ASF licenses this file
- * to you 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 test
-
-import (
-	"org/apache/htrace/common"
-)
-
-func SpanId(str string) common.SpanId {
-	var spanId common.SpanId
-	err := spanId.FromString(str)
-	if err != nil {
-		panic(err.Error())
-	}
-	return spanId
-}
diff --git a/htrace-htraced/src/test/java/org/apache/htrace/impl/TestHTracedRESTReceiver.java b/htrace-htraced/src/test/java/org/apache/htrace/impl/TestHTracedRESTReceiver.java
index 35d1f09..99f2c50 100644
--- a/htrace-htraced/src/test/java/org/apache/htrace/impl/TestHTracedRESTReceiver.java
+++ b/htrace-htraced/src/test/java/org/apache/htrace/impl/TestHTracedRESTReceiver.java
@@ -28,6 +28,7 @@
 import org.apache.commons.logging.LogFactory;
 import org.apache.htrace.HTraceConfiguration;
 import org.apache.htrace.Span;
+import org.apache.htrace.SpanId;
 import org.apache.htrace.util.DataDir;
 import org.apache.htrace.util.HTracedProcess;
 import org.apache.htrace.util.TestUtil;
@@ -126,8 +127,8 @@
     Span spans[] = new Span[NUM_SPANS];
     for (int i = 0; i < NUM_SPANS; i++) {
       MilliSpan.Builder builder = new MilliSpan.Builder().
-          parents(new long[]{1L}).
-          spanId(i);
+          parents(new SpanId[] { new SpanId(1L, 1L) }).
+          spanId(new SpanId(1L, i));
       if (i == NUM_SPANS - 1) {
         builder.tracerId("specialTrid");
       }
@@ -150,7 +151,8 @@
             for (int i = 0; i < NUM_SPANS; i++) {
               // This is what the REST server expects when querying for a
               // span id.
-              String findSpan = String.format("span/%016x", i);
+              String findSpan = String.format("span/%s",
+                  new SpanId(1L, i).toString());
               ContentResponse response =
                   http.GET(restServerUrl + findSpan);
               String content = processGET(response);
@@ -160,7 +162,8 @@
               }
               LOG.info("Got " + content + " for span " + i);
               MilliSpan dspan = MilliSpan.fromJson(content);
-              assertEquals((long)i, dspan.getSpanId());
+              assertEquals(new SpanId(1, i).toString(),
+                dspan.getSpanId().toString());
               // Every span should have the tracer ID we set in the
               // configuration... except for the last span, which had
               // a custom value set.
diff --git a/htrace-webapp/src/main/web/app/span.js b/htrace-webapp/src/main/web/app/span.js
index b56a2c9..cd87543 100644
--- a/htrace-webapp/src/main/web/app/span.js
+++ b/htrace-webapp/src/main/web/app/span.js
@@ -20,7 +20,7 @@
 var htrace = htrace || {};
 
 // The invalid span ID, which is all zeroes.
-htrace.INVALID_SPAN_ID = "0000000000000000";
+htrace.INVALID_SPAN_ID = "00000000000000000000000000000000";
 
 // Convert an array of htrace.Span models into a comma-separated string.
 htrace.spanModelsToString = function(spans) {
@@ -81,8 +81,7 @@
   // forced to be numbers.
   parse: function(response, options) {
     var span = {};
-    this.set("spanId", response.s ? response.s : htrace.INVALID_SPAN_ID);
-    this.set("traceId", response.i ? response.i : htrace.INVALID_SPAN_ID);
+    this.set("spanId", response.a ? response.a : htrace.INVALID_SPAN_ID);
     this.set("tracerId", response.r ? response.r : "");
     this.set("parents", response.p ? response.p : []);
     this.set("description", response.d ? response.d : "");
@@ -120,10 +119,7 @@
   unparse: function() {
     var obj = { };
     if (!(this.get("spanId") === htrace.INVALID_SPAN_ID)) {
-      obj.s = this.get("spanId");
-    }
-    if (!(this.get("traceId") === htrace.INVALID_SPAN_ID)) {
-      obj.i = this.get("traceId");
+      obj.a = this.get("spanId");
     }
     if (!(this.get("tracerId") === "")) {
       obj.r = this.get("tracerId");
diff --git a/htrace-webapp/src/main/web/app/string.js b/htrace-webapp/src/main/web/app/string.js
index b0dfb74..c9c514b 100644
--- a/htrace-webapp/src/main/web/app/string.js
+++ b/htrace-webapp/src/main/web/app/string.js
@@ -47,16 +47,12 @@
   return moment.utc(val).format("YYYY-MM-DDTHH:mm:ss,SSS");
 };
 
-// Normalize a span ID into the format the server expects to see
-// (no leading 0x).
+// Normalize a span ID into the format the server expects to see--
+// i.e. something like 00000000000000000000000000000000.
 htrace.normalizeSpanId = function(str) {
-  // Strip off the 0x prefix, if there is one.
-  if (str.indexOf("0x") == 0) {
-    str = str.substring(2);
-  }
-  if (str.length != 16) {
+  if (str.length != 36) {
     throw "The length of '" + str + "' was " + str.length +
-      ", but span IDs must be 16 characters long.";
+      ", but span IDs must be 36 characters long.";
   }
   if (str.search(/[^0-9a-fA-F]/) != -1) {
     throw "Span IDs must contain only hexadecimal digits, but '" + str +
diff --git a/htrace-zipkin/src/main/java/org/apache/htrace/zipkin/HTraceToZipkinConverter.java b/htrace-zipkin/src/main/java/org/apache/htrace/zipkin/HTraceToZipkinConverter.java
index f41ec10..3921370 100644
--- a/htrace-zipkin/src/main/java/org/apache/htrace/zipkin/HTraceToZipkinConverter.java
+++ b/htrace-zipkin/src/main/java/org/apache/htrace/zipkin/HTraceToZipkinConverter.java
@@ -110,15 +110,15 @@
     Endpoint ep = new Endpoint(ipv4Address, (short) getPort(serviceName), serviceName);
     List<Annotation> annotationList = createZipkinAnnotations(hTraceSpan, ep);
     List<BinaryAnnotation> binaryAnnotationList = createZipkinBinaryAnnotations(hTraceSpan, ep);
-    zipkinSpan.setTrace_id(hTraceSpan.getTraceId());
+    zipkinSpan.setTrace_id(hTraceSpan.getSpanId().getHigh());
     if (hTraceSpan.getParents().length > 0) {
       if (hTraceSpan.getParents().length > 1) {
         LOG.error("zipkin doesn't support spans with multiple parents.  Omitting " +
             "other parents for " + hTraceSpan);
       }
-      zipkinSpan.setParent_id(hTraceSpan.getParents()[0]);
+      zipkinSpan.setParent_id(hTraceSpan.getParents()[0].getLow());
     }
-    zipkinSpan.setId(hTraceSpan.getSpanId());
+    zipkinSpan.setId(hTraceSpan.getSpanId().getLow());
     zipkinSpan.setName(hTraceSpan.getDescription());
     zipkinSpan.setAnnotations(annotationList);
     zipkinSpan.setBinary_annotations(binaryAnnotationList);
diff --git a/htrace-zipkin/src/test/java/org/apache/htrace/TestHTraceSpanToZipkinSpan.java b/htrace-zipkin/src/test/java/org/apache/htrace/TestHTraceSpanToZipkinSpan.java
index 915bb89..579b98d 100644
--- a/htrace-zipkin/src/test/java/org/apache/htrace/TestHTraceSpanToZipkinSpan.java
+++ b/htrace-zipkin/src/test/java/org/apache/htrace/TestHTraceSpanToZipkinSpan.java
@@ -21,6 +21,7 @@
 
 import org.apache.htrace.HTraceConfiguration;
 import org.apache.htrace.Span;
+import org.apache.htrace.SpanId;
 import org.apache.htrace.Trace;
 import org.apache.htrace.impl.MilliSpan;
 import org.apache.htrace.impl.POJOSpanReceiver;
@@ -48,9 +49,8 @@
 
     Span rootSpan = new MilliSpan.Builder().
             description(ROOT_SPAN_DESC).
-            traceId(1).
-            parents(new long[] { } ).
-            spanId(100).
+            parents(new SpanId[] { } ).
+            spanId(new SpanId(100, 100)).
             tracerId("test").
             begin(System.currentTimeMillis()).
             build();
@@ -72,11 +72,13 @@
   @Test
   public void testHTraceAnnotationTimestamp() throws IOException, InterruptedException {
 
-    String traceName = "testHTraceAnnotationTimestamp";
+    String tracerId = "testHTraceAnnotationTimestamp";
     long startTime = System.currentTimeMillis() * 1000;
     Span ms = new MilliSpan.Builder().
-        description(traceName).traceId(1).parents(new long[] { }).
-        spanId(2).tracerId(traceName).begin(System.currentTimeMillis()).
+        description(tracerId).parents(new SpanId[] { }).
+        spanId(new SpanId(2L, 2L)).
+        tracerId(tracerId).
+        begin(System.currentTimeMillis()).
         build();
 
     Thread.sleep(500);
@@ -117,19 +119,23 @@
   @Test
   public void testHTraceDefaultPort() throws IOException {
     MilliSpan ms = new MilliSpan.Builder().description("test").
-                      traceId(1).parents(new long[] { 2 }).
-                      spanId(3).tracerId("hmaster").
-                      begin(System.currentTimeMillis()).build();
+                      parents(new SpanId[] { new SpanId(2L, 2L) }).
+                      spanId(new SpanId(2L, 3L)).
+                      tracerId("hmaster").
+                      begin(System.currentTimeMillis()).
+                      build();
     com.twitter.zipkin.gen.Span zs = new HTraceToZipkinConverter(12345, (short) -1).convert(ms);
     for (com.twitter.zipkin.gen.Annotation annotation:zs.getAnnotations()) {
       assertEquals((short)60000, annotation.getHost().getPort());
     }
 
     // make sure it's all lower cased
-    ms = new MilliSpan.Builder().description("test").traceId(1).
-                      parents(new long[] {2}).spanId(3).
+    ms = new MilliSpan.Builder().description("test").
+                      parents(new SpanId[] {new SpanId(2, 2)}).
+                      spanId(new SpanId(2, 3)).
                       tracerId("HregIonServer").
-                      begin(System.currentTimeMillis()).build();
+                      begin(System.currentTimeMillis()).
+                      build();
     zs = new HTraceToZipkinConverter(12345, (short) -1).convert(ms);
     for (com.twitter.zipkin.gen.Annotation annotation:zs.getAnnotations()) {
       assertEquals((short)60020, annotation.getHost().getPort());
@@ -137,13 +143,12 @@
   }
 
   private void assertSpansAreEquivalent(Span s, com.twitter.zipkin.gen.Span zs) {
-    assertEquals(s.getTraceId(), zs.getTrace_id());
     assertTrue("zipkin doesn't support multiple parents to a single span.",
           s.getParents().length <= 1);
     if (s.getParents().length == 1) {
-      assertEquals(s.getParents()[0], zs.getParent_id());
+      assertEquals(s.getParents()[0].getLow(), zs.getParent_id());
     }
-    assertEquals(s.getSpanId(), zs.getId());
+    assertEquals(s.getSpanId().getLow(), zs.getId());
     Assert.assertNotNull(zs.getAnnotations());
     if (ROOT_SPAN_DESC.equals(zs.getName())) {
       assertEquals(5, zs.getAnnotations().size());// two start, two stop + one timeline annotation
diff --git a/src/main/site/markdown/index.md b/src/main/site/markdown/index.md
index 9b3034f..6198472 100644
--- a/src/main/site/markdown/index.md
+++ b/src/main/site/markdown/index.md
@@ -184,13 +184,11 @@
 a new trace in the current thread (it will be a
 `ProcessRootMilliSpan`). All of the other `startSpan()` methods take some
 parameter describing the parent span of the span to be created. The
-versions that take a `TraceInfo` or a `long traceId` and `long
-parentId` will mostly be used when continuing a trace over RPC. The
-receiver of the RPC will check the message for the additional two
-`longs` and will call `startSpan()` if they are attached.  The last
-`startSpan()` takes a `Span parent`.  The result of `parent.child()`
-will be used for the new span.  `Span.child()` simply returns a span
-that is a child of `this`.
+version that takes a parent id will mostly be used when continuing a trace over
+RPC. The receiver of the RPC will check the message for the 128-bit parent trace
+ID and will call `startSpan()` if it is attached.  The last `startSpan()` takes
+a `Span parent`.  The result of `parent.child()` will be used for the new span.
+`Span.child()` simply returns a span that is a child of `this`.
 
 ###Span Receivers
 In order to use the tracing information consisting of spans,
@@ -260,11 +258,6 @@
 one. The expectation now is that SpanReceiver implementations
 provide a constructor that takes a single parameter of HTraceConfiguration.
 
-HTRACE-16 refactors the TraceTree interface. The handy
-getRoots() method has been replaced with the less obvious
-getSpansByParent().find(Span.ROOT_SPAN_ID) and .getSpansByParentIdMap() is
-also an invocation of getSpansByParent().find().
-
 
 Publishing to Maven Central
 -------------------------------