--- a/toolkit/components/telemetry/Histograms.json
+++ b/toolkit/components/telemetry/Histograms.json
@@ -4335,16 +4335,28 @@
     "kind": "flag",
     "description": "a testing histogram; not meant to be touched"
   },
   "TELEMETRY_TEST_COUNT": {
     "expires_in_version": "default",
     "kind": "count",
     "description": "a testing histogram; not meant to be touched"
   },
+  "TELEMETRY_TEST_KEYED_FLAG": {
+    "expires_in_version": "default",
+    "kind": "flag",
+    "keyed": true,
+    "description": "a testing histogram; not meant to be touched"
+  },
+  "TELEMETRY_TEST_KEYED_COUNT": {
+    "expires_in_version": "default",
+    "kind": "count",
+    "keyed": true,
+    "description": "a testing histogram; not meant to be touched"
+  },
   "STARTUP_CRASH_DETECTED": {
     "expires_in_version": "never",
     "kind": "flag",
     "description": "Whether there was a crash during the last startup"
   },
   "SAFE_MODE_USAGE": {
     "expires_in_version": "never",
     "kind": "enumerated",

--- a/toolkit/components/telemetry/Telemetry.cpp
+++ b/toolkit/components/telemetry/Telemetry.cpp
@@ -45,16 +45,18 @@
 #include "nsXULAppAPI.h"
 #include "nsReadableUtils.h"
 #include "nsThreadUtils.h"
 #if defined(XP_WIN)
 #include "nsUnicharUtils.h"
 #endif
 #include "nsNetCID.h"
 #include "nsNetUtil.h"
+#include "nsJSUtils.h"
+#include "nsReadableUtils.h"
 #include "plstr.h"
 #include "nsAppDirectoryServiceDefs.h"
 #include "mozilla/BackgroundHangMonitor.h"
 #include "mozilla/ThreadHangStats.h"
 #include "mozilla/ProcessedStack.h"
 #include "mozilla/Mutex.h"
 #include "mozilla/FileUtils.h"
 #include "mozilla/Preferences.h"
@@ -68,16 +70,32 @@
 
 #define EXPIRED_ID "__expired__"
 
 namespace {
 
 using namespace base;
 using namespace mozilla;
 
+const char KEYED_HISTOGRAM_NAME_SEPARATOR[] = "#";
+
+enum reflectStatus {
+  REFLECT_OK,
+  REFLECT_CORRUPT,
+  REFLECT_FAILURE
+};
+
+nsresult
+HistogramGet(const char *name, const char *expiration, uint32_t histogramType,
+             uint32_t min, uint32_t max, uint32_t bucketCount, bool haveOptArgs,
+             Histogram **result);
+
+enum reflectStatus
+ReflectHistogramSnapshot(JSContext *cx, JS::Handle<JSObject*> obj, Histogram *h);
+
 template<class EntryType>
 class AutoHashtable : public nsTHashtable<EntryType>
 {
 public:
   explicit AutoHashtable(uint32_t initLength = PL_DHASH_DEFAULT_INITIAL_LENGTH);
   typedef bool (*ReflectEntryFunc)(EntryType *entry, JSContext *cx, JS::Handle<JSObject*> obj);
   bool ReflectIntoJS(ReflectEntryFunc entryFunc, JSContext *cx, JS::Handle<JSObject*> obj);
 private:
@@ -550,16 +568,186 @@ ClearIOReporting()
   if (!sTelemetryIOObserver) {
     return;
   }
   IOInterposer::Unregister(IOInterposeObserver::OpAllWithStaging,
                            sTelemetryIOObserver);
   sTelemetryIOObserver = nullptr;
 }
 
+class KeyedHistogram {
+public:
+  KeyedHistogram(const nsACString &name, const nsACString &expiration,
+                 uint32_t histogramType, uint32_t min, uint32_t max,
+                 uint32_t bucketCount);
+  nsresult GetHistogram(const nsCString& name, Histogram** histogram);
+  uint32_t GetHistogramType() const { return mHistogramType; }
+  nsresult GetJSKeys(JSContext* cx, JS::CallArgs& args);
+  nsresult GetJSSnapshot(JSContext* cx, JS::Handle<JSObject*> obj);
+  void Clear();
+
+private:
+  typedef nsBaseHashtableET<nsCStringHashKey, Histogram*> KeyedHistogramEntry;
+  typedef AutoHashtable<KeyedHistogramEntry> KeyedHistogramMapType;
+  KeyedHistogramMapType mHistogramMap;
+
+  struct ReflectKeysArgs {
+    JSContext* jsContext;
+    JS::AutoValueVector* vector;
+  };
+  static PLDHashOperator ReflectKeys(KeyedHistogramEntry* entry, void* arg);
+
+  static bool ReflectKeyedHistogram(KeyedHistogramEntry* entry,
+                                    JSContext* cx,
+                                    JS::Handle<JSObject*> obj);
+
+  static PLDHashOperator ClearHistogramEnumerator(KeyedHistogramEntry*, void*);
+
+  const nsCString mName;
+  const nsCString mExpiration;
+  const uint32_t mHistogramType;
+  const uint32_t mMin;
+  const uint32_t mMax;
+  const uint32_t mBucketCount;
+};
+
+KeyedHistogram::KeyedHistogram(const nsACString &name, const nsACString &expiration,
+                               uint32_t histogramType, uint32_t min, uint32_t max,
+                               uint32_t bucketCount)
+  : mHistogramMap()
+  , mName(name)
+  , mExpiration(expiration)
+  , mHistogramType(histogramType)
+  , mMin(min)
+  , mMax(max)
+  , mBucketCount(bucketCount)
+{
+}
+
+nsresult
+KeyedHistogram::GetHistogram(const nsCString& key, Histogram** histogram)
+{
+  KeyedHistogramEntry* entry = mHistogramMap.GetEntry(key);
+  if (entry) {
+    *histogram = entry->mData;
+    return NS_OK;
+  }
+
+  nsCString histogramName = mName;
+  histogramName.Append(KEYED_HISTOGRAM_NAME_SEPARATOR);
+  histogramName.Append(key);
+
+  Histogram* h;
+  nsresult rv = HistogramGet(histogramName.get(), mExpiration.get(),
+                             mHistogramType, mMin, mMax, mBucketCount,
+                             true, &h);
+  if (NS_FAILED(rv)) {
+    return rv;
+  }
+
+  h->ClearFlags(Histogram::kUmaTargetedHistogramFlag);
+  h->SetFlags(Histogram::kExtendedStatisticsFlag);
+  *histogram = h;
+
+  entry = mHistogramMap.PutEntry(key);
+  if (MOZ_UNLIKELY(!entry)) {
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
+
+  entry->mData = h;
+  return NS_OK;
+}
+
+/* static */
+PLDHashOperator
+KeyedHistogram::ClearHistogramEnumerator(KeyedHistogramEntry* entry, void*)
+{
+  entry->mData->Clear();
+  return PL_DHASH_NEXT;
+}
+
+void
+KeyedHistogram::Clear()
+{
+  mHistogramMap.EnumerateEntries(&KeyedHistogram::ClearHistogramEnumerator, nullptr);
+  mHistogramMap.Clear();
+}
+
+/* static */
+PLDHashOperator
+KeyedHistogram::ReflectKeys(KeyedHistogramEntry* entry, void* arg)
+{
+  ReflectKeysArgs* args = static_cast<ReflectKeysArgs*>(arg);
+  const nsACString& key = entry->GetKey();
+
+  JS::RootedValue jsKey(args->jsContext);
+  const nsCString& flat = nsPromiseFlatCString(key);
+  jsKey.setString(JS_NewStringCopyN(args->jsContext, flat.get(), flat.Length()));
+  args->vector->append(jsKey);
+
+  return PL_DHASH_NEXT;
+}
+
+nsresult
+KeyedHistogram::GetJSKeys(JSContext* cx, JS::CallArgs& args)
+{
+  JS::AutoValueVector keys(cx);
+  if (!keys.reserve(mHistogramMap.Count())) {
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
+
+  ReflectKeysArgs reflectArgs = { cx, &keys };
+  const uint32_t num = mHistogramMap.EnumerateEntries(&KeyedHistogram::ReflectKeys,
+                                                      static_cast<void*>(&reflectArgs));
+  if (num != mHistogramMap.Count()) {
+    return NS_ERROR_FAILURE;
+  }
+
+  JS::RootedObject jsKeys(cx, JS_NewArrayObject(cx, keys));
+  if (!jsKeys) {
+    return NS_ERROR_FAILURE;
+  }
+
+  args.rval().setObject(*jsKeys);
+  return NS_OK;
+}
+
+/* static */
+bool
+KeyedHistogram::ReflectKeyedHistogram(KeyedHistogramEntry* entry, JSContext* cx, JS::Handle<JSObject*> obj)
+{
+  JS::RootedObject histogramSnapshot(cx, JS_NewObject(cx, nullptr, JS::NullPtr(), JS::NullPtr()));
+  if (!histogramSnapshot) {
+    return false;
+  }
+
+  if (ReflectHistogramSnapshot(cx, histogramSnapshot, entry->mData) != REFLECT_OK) {
+    return false;
+  }
+
+  const nsACString& key = entry->GetKey();
+  const nsCString& flat = nsPromiseFlatCString(key);
+
+  if (!JS_DefineProperty(cx, obj, flat.get(), histogramSnapshot, JSPROP_ENUMERATE)) {
+    return false;
+  }
+
+  return true;
+}
+
+nsresult
+KeyedHistogram::GetJSSnapshot(JSContext* cx, JS::Handle<JSObject*> obj)
+{
+  if (!mHistogramMap.ReflectIntoJS(&KeyedHistogram::ReflectKeyedHistogram, cx, obj)) {
+    return NS_ERROR_FAILURE;
+  }
+
+  return NS_OK;
+}
+
 class TelemetryImpl MOZ_FINAL
   : public nsITelemetry
   , public nsIMemoryReporter
 {
   NS_DECL_THREADSAFE_ISUPPORTS
   NS_DECL_NSITELEMETRY
   NS_DECL_NSIMEMORYREPORTER
 
@@ -657,16 +845,25 @@ private:
   Mutex mThreadHangStatsMutex;
 
   CombinedStacks mLateWritesStacks; // This is collected out of the main thread.
   bool mCachedTelemetryData;
   uint32_t mLastShutdownTime;
   uint32_t mFailedLockCount;
   nsCOMArray<nsIFetchTelemetryDataCallback> mCallbacks;
   friend class nsFetchTelemetryData;
+
+  typedef nsClassHashtable<nsCStringHashKey, KeyedHistogram> KeyedHistogramMapType;
+  KeyedHistogramMapType mKeyedHistograms;
+
+  struct KeyedHistogramReflectArgs {
+    JSContext* jsContext;
+    JS::Handle<JSObject*> object;
+  };
+  static PLDHashOperator KeyedHistogramsReflector(const nsACString&, nsAutoPtr<KeyedHistogram>&, void* args);
 };
 
 TelemetryImpl*  TelemetryImpl::sTelemetry = nullptr;
 
 MOZ_DEFINE_MALLOC_SIZE_OF(TelemetryMallocSizeOf)
 
 NS_IMETHODIMP
 TelemetryImpl::CollectReports(nsIHandleReportCallback* aHandleReport,
@@ -685,16 +882,17 @@ StatisticsRecorder gStatisticsRecorder;
 struct TelemetryHistogram {
   uint32_t min;
   uint32_t max;
   uint32_t bucketCount;
   uint32_t histogramType;
   uint32_t id_offset;
   uint32_t expiration_offset;
   bool extendedStatisticsOK;
+  bool keyed;
 
   const char *id() const;
   const char *expiration() const;
 };
 
 #include "TelemetryHistogramData.inc"
 bool gCorruptHistograms[Telemetry::HistogramCount];
 
@@ -718,24 +916,25 @@ IsExpired(const char *expiration){
     (mozilla::Version(expiration) <= current_version);
 }
 
 bool
 IsExpired(const Histogram *histogram){
   return histogram->histogram_name() == EXPIRED_ID;
 }
 
-/*
- * min, max & bucketCount are optional for boolean, flag & count histograms.
- * haveOptArgs has to be set if the caller provides them.
- */
+bool
+IsValidHistogramName(const nsACString& name)
+{
+  return !FindInReadable(nsCString(KEYED_HISTOGRAM_NAME_SEPARATOR), name);
+}
+
 nsresult
-HistogramGet(const char *name, const char *expiration, uint32_t histogramType,
-             uint32_t min, uint32_t max, uint32_t bucketCount, bool haveOptArgs,
-             Histogram **result)
+CheckHistogramArguments(uint32_t histogramType, uint32_t min, uint32_t max,
+                        uint32_t bucketCount, bool haveOptArgs)
 {
   if (histogramType != nsITelemetry::HISTOGRAM_BOOLEAN
       && histogramType != nsITelemetry::HISTOGRAM_FLAG
       && histogramType != nsITelemetry::HISTOGRAM_COUNT) {
     // The min, max & bucketCount arguments are not optional for this type.
     if (!haveOptArgs)
       return NS_ERROR_ILLEGAL_VALUE;
 
@@ -745,16 +944,33 @@ HistogramGet(const char *name, const cha
 
     if (bucketCount <= 2)
       return NS_ERROR_ILLEGAL_VALUE;
 
     if (min < 1)
       return NS_ERROR_ILLEGAL_VALUE;
   }
 
+  return NS_OK;
+}
+
+/*
+ * min, max & bucketCount are optional for boolean, flag & count histograms.
+ * haveOptArgs has to be set if the caller provides them.
+ */
+nsresult
+HistogramGet(const char *name, const char *expiration, uint32_t histogramType,
+             uint32_t min, uint32_t max, uint32_t bucketCount, bool haveOptArgs,
+             Histogram **result)
+{
+  nsresult rv = CheckHistogramArguments(histogramType, min, max, bucketCount, haveOptArgs);
+  if (NS_FAILED(rv)) {
+    return rv;
+  }
+
   if (IsExpired(expiration)) {
     name = EXPIRED_ID;
     min = 1;
     max = 2;
     bucketCount = 3;
     histogramType = nsITelemetry::HISTOGRAM_LINEAR;
   }
 
@@ -770,16 +986,17 @@ HistogramGet(const char *name, const cha
     break;
   case nsITelemetry::HISTOGRAM_FLAG:
     *result = FlagHistogram::FactoryGet(name, Histogram::kUmaTargetedHistogramFlag);
     break;
   case nsITelemetry::HISTOGRAM_COUNT:
     *result = CountHistogram::FactoryGet(name, Histogram::kUmaTargetedHistogramFlag);
     break;
   default:
+    NS_ASSERTION(false, "Invalid histogram type");
     return NS_ERROR_INVALID_ARG;
   }
   return NS_OK;
 }
 
 // O(1) histogram lookup by numeric id
 nsresult
 GetHistogramByEnumId(Telemetry::ID id, Histogram **ret)
@@ -787,16 +1004,20 @@ GetHistogramByEnumId(Telemetry::ID id, H
   static Histogram* knownHistograms[Telemetry::HistogramCount] = {0};
   Histogram *h = knownHistograms[id];
   if (h) {
     *ret = h;
     return NS_OK;
   }
 
   const TelemetryHistogram &p = gHistograms[id];
+  if (p.keyed) {
+    return NS_ERROR_FAILURE;
+  }
+
   nsresult rv = HistogramGet(p.id(), p.expiration(), p.histogramType,
                              p.min, p.max, p.bucketCount, true, &h);
   if (NS_FAILED(rv))
     return rv;
 
 #ifdef DEBUG
   // Check that the C++ Histogram code computes the same ranges as the
   // Python histogram code.
@@ -827,22 +1048,16 @@ FillRanges(JSContext *cx, JS::Handle<JSO
   for (size_t i = 0; i < h->bucket_count(); i++) {
     range = INT_TO_JSVAL(h->ranges(i));
     if (!JS_DefineElement(cx, array, i, range, JSPROP_ENUMERATE))
       return false;
   }
   return true;
 }
 
-enum reflectStatus {
-  REFLECT_OK,
-  REFLECT_CORRUPT,
-  REFLECT_FAILURE
-};
-
 enum reflectStatus
 ReflectHistogramAndSamples(JSContext *cx, JS::Handle<JSObject*> obj, Histogram *h,
                            const Histogram::SampleSet &ss)
 {
   // We don't want to reflect corrupt histograms.
   if (h->FindCorruption(ss) != Histogram::NO_INCONSISTENCIES) {
     return REFLECT_CORRUPT;
   }
@@ -1010,16 +1225,196 @@ WrapAndReturnHistogram(Histogram *h, JSC
         && JS_DefineFunction(cx, obj, "clear", JSHistogram_Clear, 0, 0))) {
     return NS_ERROR_FAILURE;
   }
   JS_SetPrivate(obj, h);
   ret.setObject(*obj);
   return NS_OK;
 }
 
+bool
+JSKeyedHistogram_Add(JSContext *cx, unsigned argc, JS::Value *vp)
+{
+  JSObject *obj = JS_THIS_OBJECT(cx, vp);
+  if (!obj) {
+    return false;
+  }
+
+  KeyedHistogram* keyed = static_cast<KeyedHistogram*>(JS_GetPrivate(obj));
+  if (!keyed) {
+    return false;
+  }
+
+  JS::CallArgs args = CallArgsFromVp(argc, vp);
+  if (args.length() < 1) {
+    JS_ReportError(cx, "Expected one argument");
+    return false;
+  }
+
+  nsAutoJSString key;
+  if (!args[0].isString() || !key.init(cx, args[0])) {
+    JS_ReportError(cx, "Not a string");
+    return false;
+  }
+
+  const uint32_t type = keyed->GetHistogramType();
+  int32_t value = 1;
+
+  if (type != base::CountHistogram::COUNT_HISTOGRAM) {
+    if (args.length() < 2) {
+      JS_ReportError(cx, "Expected two arguments for this histogram type");
+      return false;
+    }
+
+    if (!(args[1].isNumber() || args[1].isBoolean())) {
+      JS_ReportError(cx, "Not a number");
+      return false;
+    }
+
+    if (!JS::ToInt32(cx, args[0], &value)) {
+      return false;
+    }
+  }
+
+  Histogram* h = nullptr;
+  nsresult rv = keyed->GetHistogram(NS_ConvertUTF16toUTF8(key), &h);
+  if (NS_FAILED(rv)) {
+    JS_ReportError(cx, "Failed to get histogram");
+    return false;
+  }
+
+  if (TelemetryImpl::CanRecord()) {
+    h->Add(value);
+  }
+
+  return true;
+}
+
+bool
+JSKeyedHistogram_Keys(JSContext *cx, unsigned argc, JS::Value *vp)
+{
+  JSObject *obj = JS_THIS_OBJECT(cx, vp);
+  if (!obj) {
+    return false;
+  }
+
+  KeyedHistogram* keyed = static_cast<KeyedHistogram*>(JS_GetPrivate(obj));
+  if (!keyed) {
+    return false;
+  }
+
+  JS::CallArgs args = JS::CallArgsFromVp(argc, vp);
+  return NS_SUCCEEDED(keyed->GetJSKeys(cx, args));
+}
+
+bool
+JSKeyedHistogram_Snapshot(JSContext *cx, unsigned argc, JS::Value *vp)
+{
+  JSObject *obj = JS_THIS_OBJECT(cx, vp);
+  if (!obj) {
+    return false;
+  }
+
+  KeyedHistogram* keyed = static_cast<KeyedHistogram*>(JS_GetPrivate(obj));
+  if (!keyed) {
+    return false;
+  }
+
+  JS::CallArgs args = JS::CallArgsFromVp(argc, vp);
+
+  if (args.length() == 0) {
+    JS::RootedObject snapshot(cx, JS_NewObject(cx, nullptr, JS::NullPtr(), JS::NullPtr()));
+    if (!snapshot) {
+      JS_ReportError(cx, "Failed to create object");
+      return false;
+    }
+
+    if (!NS_SUCCEEDED(keyed->GetJSSnapshot(cx, snapshot))) {
+      JS_ReportError(cx, "Failed to reflect keyed histograms");
+      return false;
+    }
+
+    args.rval().setObject(*snapshot);
+    return true;
+  }
+
+  nsAutoJSString key;
+  if (!args[0].isString() || !key.init(cx, args[0])) {
+    JS_ReportError(cx, "Not a string");
+    return false;
+  }
+
+  Histogram* h = nullptr;
+  nsresult rv = keyed->GetHistogram(NS_ConvertUTF16toUTF8(key), &h);
+  if (NS_FAILED(rv)) {
+    JS_ReportError(cx, "Failed to get histogram");
+    return false;
+  }
+
+  JS::RootedObject snapshot(cx, JS_NewObject(cx, nullptr, JS::NullPtr(), JS::NullPtr()));
+  if (!snapshot) {
+    return false;
+  }
+
+  switch (ReflectHistogramSnapshot(cx, snapshot, h)) {
+  case REFLECT_FAILURE:
+    return false;
+  case REFLECT_CORRUPT:
+    JS_ReportError(cx, "Histogram is corrupt");
+    return false;
+  case REFLECT_OK:
+    args.rval().setObject(*snapshot);
+    return true;
+  default:
+    MOZ_CRASH("unhandled reflection status");
+  }
+}
+
+bool
+JSKeyedHistogram_Clear(JSContext *cx, unsigned argc, JS::Value *vp)
+{
+  JSObject *obj = JS_THIS_OBJECT(cx, vp);
+  if (!obj) {
+    return false;
+  }
+
+  KeyedHistogram* keyed = static_cast<KeyedHistogram*>(JS_GetPrivate(obj));
+  if (!keyed) {
+    return false;
+  }
+
+  keyed->Clear();
+  return true;
+}
+
+nsresult
+WrapAndReturnKeyedHistogram(KeyedHistogram *h, JSContext *cx, JS::MutableHandle<JS::Value> ret)
+{
+  static const JSClass JSHistogram_class = {
+    "JSKeyedHistogram",  /* name */
+    JSCLASS_HAS_PRIVATE, /* flags */
+    JS_PropertyStub, JS_DeletePropertyStub, JS_PropertyStub, JS_StrictPropertyStub,
+    JS_EnumerateStub, JS_ResolveStub, JS_ConvertStub
+  };
+
+  JS::Rooted<JSObject*> obj(cx, JS_NewObject(cx, &JSHistogram_class, JS::NullPtr(), JS::NullPtr()));
+  if (!obj)
+    return NS_ERROR_FAILURE;
+  if (!(JS_DefineFunction(cx, obj, "add", JSKeyedHistogram_Add, 2, 0)
+        && JS_DefineFunction(cx, obj, "snapshot", JSKeyedHistogram_Snapshot, 1, 0)
+        && JS_DefineFunction(cx, obj, "keys", JSKeyedHistogram_Keys, 0, 0)
+        && JS_DefineFunction(cx, obj, "clear", JSKeyedHistogram_Clear, 0, 0))) {
+    return NS_ERROR_FAILURE;
+  }
+
+  JS_SetPrivate(obj, h);
+  ret.setObject(*obj);
+  return NS_OK;
+}
+
 static uint32_t
 ReadLastShutdownDuration(const char *filename) {
   FILE *f = fopen(filename, "r");
   if (!f) {
     return 0;
   }
 
   int shutdownTime;
@@ -1274,42 +1669,83 @@ mFailedLockCount(0)
 
   for (size_t i = 0; i < ArrayLength(trackedDBs); i++)
     mTrackedDBs.PutEntry(nsDependentCString(trackedDBs[i]));
 
 #ifdef DEBUG
   // Mark immutable to prevent asserts on simultaneous access from multiple threads
   mTrackedDBs.MarkImmutable();
 #endif
+
+  for (size_t i = 0; i < ArrayLength(gHistograms); ++i) {
+    const TelemetryHistogram& h = gHistograms[i];
+    if (!h.keyed) {
+      continue;
+    }
+
+    const nsDependentCString id(h.id());
+    const nsDependentCString expiration(h.expiration());
+    mKeyedHistograms.Put(id, new KeyedHistogram(id, expiration, h.histogramType,
+                                                    h.min, h.max, h.bucketCount));
+  }
 }
 
 TelemetryImpl::~TelemetryImpl() {
   UnregisterWeakMemoryReporter(this);
 }
 
 void
 TelemetryImpl::InitMemoryReporter() {
   RegisterWeakMemoryReporter(this);
 }
 
 NS_IMETHODIMP
 TelemetryImpl::NewHistogram(const nsACString &name, const nsACString &expiration, uint32_t histogramType,
                             uint32_t min, uint32_t max, uint32_t bucketCount, JSContext *cx,
                             uint8_t optArgCount, JS::MutableHandle<JS::Value> ret)
 {
+  if (!IsValidHistogramName(name)) {
+    return NS_ERROR_INVALID_ARG;
+  }
+
   Histogram *h;
   nsresult rv = HistogramGet(PromiseFlatCString(name).get(), PromiseFlatCString(expiration).get(),
                              histogramType, min, max, bucketCount, optArgCount == 3, &h);
   if (NS_FAILED(rv))
     return rv;
   h->ClearFlags(Histogram::kUmaTargetedHistogramFlag);
   h->SetFlags(Histogram::kExtendedStatisticsFlag);
   return WrapAndReturnHistogram(h, cx, ret);
 }
 
+NS_IMETHODIMP
+TelemetryImpl::NewKeyedHistogram(const nsACString &name, const nsACString &expiration, uint32_t histogramType,
+                            uint32_t min, uint32_t max, uint32_t bucketCount, JSContext *cx,
+                            uint8_t optArgCount, JS::MutableHandle<JS::Value> ret)
+{
+  if (!IsValidHistogramName(name)) {
+    return NS_ERROR_INVALID_ARG;
+  }
+
+  nsresult rv = CheckHistogramArguments(histogramType, min, max, bucketCount, optArgCount == 3);
+  if (NS_FAILED(rv)) {
+    return rv;
+  }
+
+  KeyedHistogram* keyed = new KeyedHistogram(name, expiration, histogramType,
+                                             min, max, bucketCount);
+  if (MOZ_UNLIKELY(!mKeyedHistograms.Put(name, keyed, fallible_t()))) {
+    delete keyed;
+    return NS_ERROR_OUT_OF_MEMORY;
+  }
+
+  return WrapAndReturnKeyedHistogram(keyed, cx, ret);
+}
+
+
 bool
 TelemetryImpl::ReflectSQL(const SlowSQLEntryType *entry,
                           const Stat *stat,
                           JSContext *cx,
                           JS::Handle<JSObject*> obj)
 {
   if (stat->hitCount == 0)
     return true;
@@ -1600,16 +2036,19 @@ TelemetryImpl::GetHistogramSnapshots(JSC
   JS::Rooted<JSObject*> root_obj(cx, JS_NewObject(cx, nullptr, JS::NullPtr(), JS::NullPtr()));
   if (!root_obj)
     return NS_ERROR_FAILURE;
   ret.setObject(*root_obj);
 
   // Ensure that all the HISTOGRAM_FLAG & HISTOGRAM_COUNT histograms have
   // been created, so that their values are snapshotted.
   for (size_t i = 0; i < Telemetry::HistogramCount; ++i) {
+    if (gHistograms[i].keyed) {
+      continue;
+    }
     const uint32_t type = gHistograms[i].histogramType;
     if (type == nsITelemetry::HISTOGRAM_FLAG ||
         type == nsITelemetry::HISTOGRAM_COUNT) {
       Histogram *h;
       DebugOnly<nsresult> rv = GetHistogramByEnumId(Telemetry::ID(i), &h);
       MOZ_ASSERT(NS_SUCCEEDED(rv));
     }
   };
@@ -1744,16 +2183,58 @@ TelemetryImpl::GetAddonHistogramSnapshot
 
   if (!mAddonMap.ReflectIntoJS(AddonReflector, cx, obj)) {
     return NS_ERROR_FAILURE;
   }
   ret.setObject(*obj);
   return NS_OK;
 }
 
+/* static */
+PLDHashOperator
+TelemetryImpl::KeyedHistogramsReflector(const nsACString& key, nsAutoPtr<KeyedHistogram>& entry, void* arg)
+{
+  KeyedHistogramReflectArgs* args = static_cast<KeyedHistogramReflectArgs*>(arg);
+  JSContext *cx = args->jsContext;
+  JS::RootedObject snapshot(cx, JS_NewObject(cx, nullptr, JS::NullPtr(), JS::NullPtr()));
+  if (!snapshot) {
+    return PL_DHASH_STOP;
+  }
+
+  if (!NS_SUCCEEDED(entry->GetJSSnapshot(cx, snapshot))) {
+    return PL_DHASH_STOP;
+  }
+
+  if (!JS_DefineProperty(cx, args->object, PromiseFlatCString(key).get(),
+                         snapshot, JSPROP_ENUMERATE)) {
+    return PL_DHASH_STOP;
+  }
+
+  return PL_DHASH_NEXT;
+}
+
+NS_IMETHODIMP
+TelemetryImpl::GetKeyedHistogramSnapshots(JSContext *cx, JS::MutableHandle<JS::Value> ret)
+{
+  JS::Rooted<JSObject*> obj(cx, JS_NewObject(cx, nullptr, JS::NullPtr(), JS::NullPtr()));
+  if (!obj) {
+    return NS_ERROR_FAILURE;
+  }
+
+  KeyedHistogramReflectArgs reflectArgs = {cx, obj};
+  const uint32_t num = mKeyedHistograms.Enumerate(&TelemetryImpl::KeyedHistogramsReflector,
+                                                      static_cast<void*>(&reflectArgs));
+  if (num != mKeyedHistograms.Count()) {
+    return NS_ERROR_FAILURE;
+  }
+
+  ret.setObject(*obj);
+  return NS_OK;
+}
+
 bool
 TelemetryImpl::GetSQLStats(JSContext *cx, JS::MutableHandle<JS::Value> ret, bool includePrivateSql)
 {
   JS::Rooted<JSObject*> root_obj(cx, JS_NewObject(cx, nullptr, JS::NullPtr(), JS::NullPtr()));
   if (!root_obj)
     return false;
   ret.setObject(*root_obj);
 
@@ -2269,52 +2750,78 @@ TelemetryImpl::GetLateWrites(JSContext *
   if (report == nullptr) {
     return NS_ERROR_FAILURE;
   }
 
   ret.setObject(*report);
   return NS_OK;
 }
 
+nsresult
+GetRegisteredHistogramIds(bool keyed, uint32_t *aCount, char*** aHistograms)
+{
+  nsTArray<char*> collection;
+
+  for (size_t i = 0; i < ArrayLength(gHistograms); ++i) {
+    const TelemetryHistogram& h = gHistograms[i];
+    if (IsExpired(h.expiration()) || h.keyed != keyed) {
+      continue;
+    }
+
+    const char* id = h.id();
+    const size_t len = strlen(id);
+    collection.AppendElement(static_cast<char*>(nsMemory::Clone(id, len+1)));
+  }
+
+  const size_t bytes = collection.Length() * sizeof(char*);
+  char** histograms = static_cast<char**>(nsMemory::Alloc(bytes));
+  memcpy(histograms, collection.Elements(), bytes);
+  *aHistograms = histograms;
+  *aCount = collection.Length();
+
+  return NS_OK;
+}
+
 NS_IMETHODIMP
 TelemetryImpl::RegisteredHistograms(uint32_t *aCount, char*** aHistograms)
 {
-  size_t count = ArrayLength(gHistograms);
-  size_t offset = 0;
-  char** histograms = static_cast<char**>(nsMemory::Alloc(count * sizeof(char*)));
-
-  for (size_t i = 0; i < count; ++i) {
-    if (IsExpired(gHistograms[i].expiration())) {
-      offset++;
-      continue;
-    }
-
-    const char* h = gHistograms[i].id();
-    size_t len = strlen(h);
-    histograms[i - offset] = static_cast<char*>(nsMemory::Clone(h, len+1));
-  }
-
-  *aCount = count - offset;
-  *aHistograms = histograms;
-  return NS_OK;
+  return GetRegisteredHistogramIds(false, aCount, aHistograms);
+}
+
+NS_IMETHODIMP
+TelemetryImpl::RegisteredKeyedHistograms(uint32_t *aCount, char*** aHistograms)
+{
+  return GetRegisteredHistogramIds(true, aCount, aHistograms);
 }
 
 NS_IMETHODIMP
 TelemetryImpl::GetHistogramById(const nsACString &name, JSContext *cx,
                                 JS::MutableHandle<JS::Value> ret)
 {
   Histogram *h;
   nsresult rv = GetHistogramByName(name, &h);
   if (NS_FAILED(rv))
     return rv;
 
   return WrapAndReturnHistogram(h, cx, ret);
 }
 
 NS_IMETHODIMP
+TelemetryImpl::GetKeyedHistogramById(const nsACString &name, JSContext *cx,
+                                     JS::MutableHandle<JS::Value> ret)
+{
+  KeyedHistogram* keyed = nullptr;
+  if (!mKeyedHistograms.Get(name, &keyed)) {
+    return NS_ERROR_FAILURE;
+  }
+
+  return WrapAndReturnKeyedHistogram(keyed, cx, ret);
+}
+
+NS_IMETHODIMP
 TelemetryImpl::GetCanRecord(bool *ret) {
   *ret = mCanRecord;
   return NS_OK;
 }
 
 NS_IMETHODIMP
 TelemetryImpl::SetCanRecord(bool canRecord) {
   mCanRecord = !!canRecord;

--- a/toolkit/components/telemetry/Telemetry.h
+++ b/toolkit/components/telemetry/Telemetry.h
@@ -60,16 +60,21 @@ void Accumulate(const char* name, uint32
 void AccumulateTimeDelta(ID id, TimeStamp start, TimeStamp end = TimeStamp::Now());
 
 /**
  * Return a raw Histogram for direct manipulation for users who can not use Accumulate().
  */
 base::Histogram* GetHistogramById(ID id);
 
 /**
+ * Return a raw histogram for keyed histograms.
+ */
+base::Histogram* GetKeyedHistogramById(ID id, const nsAString&);
+
+/**
  * Those wrappers are needed because the VS versions we use do not support free
  * functions with default template arguments.
  */
 template<TimerResolution res>
 struct AccumulateDelta_impl
 {
   static void compute(ID id, TimeStamp start, TimeStamp end = TimeStamp::Now());
 };

--- a/toolkit/components/telemetry/TelemetryPing.jsm
+++ b/toolkit/components/telemetry/TelemetryPing.jsm
@@ -430,16 +430,32 @@ let Impl = {
       }
       if (Object.keys(packedHistograms).length != 0)
         ret[addonName] = packedHistograms;
     }
 
     return ret;
   },
 
+  getKeyedHistograms: function() {
+    let registered = Telemetry.registeredKeyedHistograms([]);
+    let ret = {};
+
+    for (let id of registered) {
+      ret[id] = {};
+      let keyed = Telemetry.getKeyedHistogramById(id);
+      let snapshot = keyed.snapshot();
+      for (let key of Object.keys(snapshot)) {
+        ret[id][key] = this.packHistogram(snapshot[key]);
+      }
+    }
+
+    return ret;
+  },
+
   getThreadHangStats: function getThreadHangStats(stats) {
     stats.forEach((thread) => {
       thread.activity = this.packHistogram(thread.activity);
       thread.hangs.forEach((hang) => {
         hang.histogram = this.packHistogram(hang.histogram);
       });
     });
     return stats;
@@ -698,16 +714,17 @@ let Impl = {
    * to |this.getSimpleMeasurements| and |this.getMetadata|,
    * respectively.
    */
   assemblePayloadWithMeasurements: function assemblePayloadWithMeasurements(simpleMeasurements, info) {
     let payloadObj = {
       ver: PAYLOAD_VERSION,
       simpleMeasurements: simpleMeasurements,
       histograms: this.getHistograms(Telemetry.histogramSnapshots),
+      keyedHistograms: this.getKeyedHistograms(),
       slowSQL: Telemetry.slowSQL,
       fileIOReports: Telemetry.fileIOReports,
       chromeHangs: Telemetry.chromeHangs,
       threadHangStats: this.getThreadHangStats(Telemetry.threadHangStats),
       lateWrites: Telemetry.lateWrites,
       addonHistograms: this.getAddonHistograms(),
       addonDetails: AddonManagerPrivate.getTelemetryDetails(),
       UIMeasurements: UITelemetry.getUIMeasurements(),

--- a/toolkit/components/telemetry/gen-histogram-data.py
+++ b/toolkit/components/telemetry/gen-histogram-data.py
@@ -55,21 +55,22 @@ class StringTable:
                 f.write("  /* %5d */ '\\0',\n" % offset)
         f.write("  /* %5d */ %s, '\\0' };\n\n"
                 % (entries[-1][1], explodeToCharArray(entries[-1][0])))
 
 def print_array_entry(histogram, name_index, exp_index):
     cpp_guard = histogram.cpp_guard()
     if cpp_guard:
         print "#if defined(%s)" % cpp_guard
-    print "  { %s, %s, %s, %s, %d, %d, %s }," \
+    print "  { %s, %s, %s, %s, %d, %d, %s, %s }," \
         % (histogram.low(), histogram.high(),
            histogram.n_buckets(), histogram.nsITelemetry_kind(),
            name_index, exp_index,
-           "true" if histogram.extended_statistics_ok() else "false")
+           "true" if histogram.extended_statistics_ok() else "false",
+           "true" if histogram.keyed() else "false")
     if cpp_guard:
         print "#endif"
 
 def write_histogram_table(histograms):
     table = StringTable()
 
     print "const TelemetryHistogram gHistograms[] = {"
     for histogram in histograms:

--- a/toolkit/components/telemetry/histogram_tools.py
+++ b/toolkit/components/telemetry/histogram_tools.py
@@ -50,36 +50,38 @@ def exponential_buckets(dmin, dmax, n_bu
         next_value = int(math.floor(math.exp(log_next) + 0.5))
         if next_value > current:
             current = next_value
         else:
             current = current + 1
         ret_array[bucket_index] = current
     return ret_array
 
-always_allowed_keys = ['kind', 'description', 'cpp_guard', 'expires_in_version', "alert_emails"]
+always_allowed_keys = ['kind', 'description', 'cpp_guard', 'expires_in_version', "alert_emails", 'keyed']
 
 class Histogram:
     """A class for representing a histogram definition."""
 
     def __init__(self, name, definition):
         """Initialize a histogram named name with the given definition.
 definition is a dict-like object that must contain at least the keys:
 
  - 'kind': The kind of histogram.  Must be one of 'boolean', 'flag',
    'count', 'enumerated', 'linear', or 'exponential'.
  - 'description': A textual description of the histogram.
 
 The key 'cpp_guard' is optional; if present, it denotes a preprocessor
 symbol that should guard C/C++ definitions associated with the histogram."""
+        self.check_name(name)
         self.verify_attributes(name, definition)
         self._name = name
         self._description = definition['description']
         self._kind = definition['kind']
         self._cpp_guard = definition.get('cpp_guard')
+        self._keyed = definition.get('keyed', False)
         self._extended_statistics_ok = definition.get('extended_statistics_ok', False)
         self._expiration = definition.get('expires_in_version')
         self.compute_bucket_parameters(definition)
         table = { 'boolean': 'BOOLEAN',
                   'flag': 'FLAG',
                   'count': 'COUNT',
                   'enumerated': 'LINEAR',
                   'linear': 'LINEAR',
@@ -124,16 +126,20 @@ the histogram."""
         """Return the number of buckets in the histogram.  May be a string."""
         return self._n_buckets
 
     def cpp_guard(self):
         """Return the preprocessor symbol that should guard C/C++ definitions
 associated with the histogram.  Returns None if no guarding is necessary."""
         return self._cpp_guard
 
+    def keyed(self):
+        """Returns True if this a keyed histogram, false otherwise."""
+        return self._keyed
+
     def extended_statistics_ok(self):
         """Return True if gathering extended statistics for this histogram
 is enabled."""
         return self._extended_statistics_ok
 
     def ranges(self):
         """Return an array of lower bounds for each bucket in the histogram."""
         table = { 'boolean': linear_buckets,
@@ -169,16 +175,20 @@ is enabled."""
             'linear': general_keys,
             'exponential': general_keys + ['extended_statistics_ok']
             }
         table_dispatch(definition['kind'], table,
                        lambda allowed_keys: Histogram.check_keys(name, definition, allowed_keys))
 
         Histogram.check_expiration(name, definition)
 
+    def check_name(self, name):
+        if '#' in name:
+            raise ValueError, '"#" not permitted for %s' % (name)
+
     @staticmethod
     def check_expiration(name, definition):
         expiration = definition.get('expires_in_version')
 
         if not expiration:
             return
 
         if re.match(r'^[1-9][0-9]*$', expiration):

--- a/toolkit/components/telemetry/nsITelemetry.idl
+++ b/toolkit/components/telemetry/nsITelemetry.idl
@@ -7,17 +7,17 @@
 #include "nsIFile.idl"
 
 [scriptable,function, uuid(3d3b9075-5549-4244-9c08-b64fefa1dd60)]
 interface nsIFetchTelemetryDataCallback : nsISupports
 {
   void complete();
 };
 
-[scriptable, uuid(4c7ba1fc-8253-4bb6-b434-325e51c26109)]
+[scriptable, uuid(080b55ca-2469-4a61-a230-fc9dac02c2c1)]
 interface nsITelemetry : nsISupports
 {
   /**
    * Histogram types:
    * HISTOGRAM_EXPONENTIAL - buckets increase exponentially
    * HISTOGRAM_LINEAR - buckets increase linearly
    * HISTOGRAM_BOOLEAN - For storing 0/1 values
    * HISTOGRAM_FLAG - For storing a single value; its count is always == 1.
@@ -173,16 +173,63 @@ interface nsITelemetry : nsISupports
   /**
    * Same as newHistogram above, but for histograms registered in TelemetryHistograms.h.
    *
    * @param id - unique identifier from TelemetryHistograms.h
    */
   [implicit_jscontext]
   jsval getHistogramById(in ACString id);
 
+  /*
+   * An object containing a snapshot from all of the currently registered keyed histograms.
+   * { name1: {histogramData1}, name2:{histogramData2}...}
+   * where the histogramData is as described in histogramSnapshots.
+   */
+  [implicit_jscontext]
+  readonly attribute jsval keyedHistogramSnapshots;
+
+  /**
+   * Create and return a keyed histogram.  Parameters:
+   *
+   * @param name Unique histogram name
+   * @param expiration Expiration version
+   * @param type - HISTOGRAM_EXPONENTIAL, HISTOGRAM_LINEAR, HISTOGRAM_BOOLEAN, HISTOGRAM_FLAG or HISTOGRAM_COUNT
+   * @param min - Minimal bucket size
+   * @param max - Maximum bucket size
+   * @param bucket_count - number of buckets in the histogram.
+   * The returned object has the following functions:
+   *   add(string key, [optional] int) - Add an int value to the histogram for that key. If no histogram for that key exists yet, it is created.
+   *   snapshot([optional] string key) - If key is provided, returns a snapshot for the histogram with that key or null. If key is not provided, returns the snapshots of all the registered keys in the form {key1: snapshot1, key2: snapshot2, ...}.
+   *   keys() - Returns an array with the string keys of the currently registered histograms
+   *   clear() - Clears the registered histograms from this.
+   */
+  [implicit_jscontext, optional_argc]
+  jsval newKeyedHistogram(in ACString name,
+                          in ACString expiration,
+                          in unsigned long histogram_type,
+                          [optional] in uint32_t min,
+                          [optional] in uint32_t max,
+                          [optional] in uint32_t bucket_count);
+
+  /**
+   * Returns an array whose values are the names of histograms defined
+   * in Histograms.json.
+   */
+  void registeredKeyedHistograms(out uint32_t count,
+                                 [retval, array, size_is(count)] out string histograms);
+
+  /**
+   * Same as newKeyedHistogram above, but for histograms registered in TelemetryHistograms.h.
+   *
+   * @param id - unique identifier from TelemetryHistograms.h
+   * The returned object has the same functions as a histogram returned from newKeyedHistogram.
+   */
+  [implicit_jscontext]
+  jsval getKeyedHistogramById(in ACString id);
+
   /**
    * Set this to false to disable gathering of telemetry statistics.
    */
   attribute boolean canRecord;
 
   /**
    * A flag indicating whether Telemetry can submit official results.
    */

--- a/toolkit/components/telemetry/tests/unit/test_TelemetryPing.js
+++ b/toolkit/components/telemetry/tests/unit/test_TelemetryPing.js
@@ -89,16 +89,21 @@ function setupTestData() {
   Telemetry.histogramFrom(IGNORE_CLONED_HISTOGRAM, IGNORE_HISTOGRAM_TO_CLONE);
   Services.startup.interrupted = true;
   Telemetry.registerAddonHistogram(ADDON_NAME, ADDON_HISTOGRAM, 1, 5, 6,
                                    Telemetry.HISTOGRAM_LINEAR);
   let h1 = Telemetry.getAddonHistogram(ADDON_NAME, ADDON_HISTOGRAM);
   h1.add(1);
   let h2 = Telemetry.getHistogramById("TELEMETRY_TEST_COUNT");
   h2.add();
+
+  let k1 = Telemetry.getKeyedHistogramById("TELEMETRY_TEST_KEYED_COUNT");
+  k1.add("a");
+  k1.add("a");
+  k1.add("b");
 }
 
 function getSavedHistogramsFile(basename) {
   let tmpDir = Services.dirsvc.get("ProfD", Ci.nsIFile);
   let histogramsFile = tmpDir.clone();
   histogramsFile.append(basename);
   if (histogramsFile.exists()) {
     histogramsFile.remove(true);
@@ -226,16 +231,18 @@ function checkPayload(request, reason, s
     do_check_true(payload.simpleMeasurements.startupSessionRestoreReadBytes > 0);
     do_check_true(payload.simpleMeasurements.startupSessionRestoreWriteBytes > 0);
   }
 
   const TELEMETRY_PING = "TELEMETRY_PING";
   const TELEMETRY_SUCCESS = "TELEMETRY_SUCCESS";
   const TELEMETRY_TEST_FLAG = "TELEMETRY_TEST_FLAG";
   const TELEMETRY_TEST_COUNT = "TELEMETRY_TEST_COUNT";
+  const TELEMETRY_TEST_KEYED_FLAG = "TELEMETRY_TEST_KEYED_FLAG";
+  const TELEMETRY_TEST_KEYED_COUNT = "TELEMETRY_TEST_KEYED_COUNT";
   const READ_SAVED_PING_SUCCESS = "READ_SAVED_PING_SUCCESS";
 
   do_check_true(TELEMETRY_PING in payload.histograms);
   do_check_true(READ_SAVED_PING_SUCCESS in payload.histograms);
   do_check_true(TELEMETRY_TEST_FLAG in payload.histograms);
   do_check_true(TELEMETRY_TEST_COUNT in payload.histograms);
 
   let rh = Telemetry.registeredHistograms([]);
@@ -304,16 +311,47 @@ function checkPayload(request, reason, s
 
   // We should have included addon histograms.
   do_check_true("addonHistograms" in payload);
   do_check_true(ADDON_NAME in payload.addonHistograms);
   do_check_true(ADDON_HISTOGRAM in payload.addonHistograms[ADDON_NAME]);
 
   do_check_true(("mainThread" in payload.slowSQL) &&
                 ("otherThreads" in payload.slowSQL));
+
+  // Check keyed histogram payload.
+
+  do_check_true("keyedHistograms" in payload);
+  let keyedHistograms = payload.keyedHistograms;
+  do_check_true(TELEMETRY_TEST_KEYED_FLAG in keyedHistograms);
+  do_check_true(TELEMETRY_TEST_KEYED_COUNT in keyedHistograms);
+
+  Assert.deepEqual({}, keyedHistograms[TELEMETRY_TEST_KEYED_FLAG]);
+
+  const expected_keyed_count = {
+    "a": {
+      range: [1, 2],
+      bucket_count: 3,
+      histogram_type: 4,
+      values: {0:2, 1:0},
+      sum: 2,
+      sum_squares_lo: 2,
+      sum_squares_hi: 0,
+    },
+    "b": {
+      range: [1, 2],
+      bucket_count: 3,
+      histogram_type: 4,
+      values: {0:1, 1:0},
+      sum: 1,
+      sum_squares_lo: 1,
+      sum_squares_hi: 0,
+    },
+  };
+  Assert.deepEqual(expected_keyed_count, keyedHistograms[TELEMETRY_TEST_KEYED_COUNT]);
 }
 
 function dummyTheme(id) {
   return {
     id: id,
     name: Math.random().toString(),
     headerURL: "http://lwttest.invalid/a.png",
     footerURL: "http://lwttest.invalid/b.png",

--- a/toolkit/components/telemetry/tests/unit/test_nsITelemetry.js
+++ b/toolkit/components/telemetry/tests/unit/test_nsITelemetry.js
@@ -372,16 +372,162 @@ function test_extended_stats() {
   do_check_eq(s.log_sum_squares, 0);
   h.add(1);
   s = h.snapshot();
   do_check_eq(s.sum, 1);
   do_check_eq(s.log_sum, 0);
   do_check_eq(s.log_sum_squares, 0);
 }
 
+// Return an array of numbers from lower up to, excluding, upper
+function numberRange(lower, upper)
+{
+  let a = [];
+  for (let i=lower; i<upper; ++i) {
+    a.push(i);
+  }
+  return a;
+}
+
+function test_keyed_boolean_histogram()
+{
+  const KEYED_ID = "test::keyed::boolean";
+  const KEYS = ["key"+(i+1) for (i of numberRange(0, 3))];
+  let histogramBase = {
+    "min": 1,
+    "max": 2,
+    "histogram_type": 2,
+    "sum": 0,
+    "sum_squares_lo": 0,
+    "sum_squares_hi": 0,
+    "ranges": [0, 1, 2],
+    "counts": [1, 0, 0]
+  };
+  let testHistograms = [JSON.parse(JSON.stringify(histogramBase)) for (i of numberRange(0, 3))];
+  let testKeys = [];
+  let testSnapShot = {};
+
+  let h = Telemetry.newKeyedHistogram(KEYED_ID, "never", Telemetry.HISTOGRAM_BOOLEAN);
+  for (let i=0; i<2; ++i) {
+    let key = KEYS[i];
+    h.add(key, true);
+    testSnapShot[key] = testHistograms[i];
+    testKeys.push(key);
+
+    Assert.deepEqual(h.keys().sort(), testKeys);
+    Assert.deepEqual(h.snapshot(), testSnapShot);
+  }
+
+  h = Telemetry.getKeyedHistogramById(KEYED_ID);
+  Assert.deepEqual(h.keys().sort(), testKeys);
+  Assert.deepEqual(h.snapshot(), testSnapShot);
+
+  let key = KEYS[2];
+  h.add(key, false);
+  testKeys.push(key);
+  testSnapShot[key] = testHistograms[2];
+  Assert.deepEqual(h.keys().sort(), testKeys);
+  Assert.deepEqual(h.snapshot(), testSnapShot);
+
+  let allSnapshots = Telemetry.keyedHistogramSnapshots;
+  Assert.deepEqual(allSnapshots[KEYED_ID], testSnapShot);
+
+  h.clear();
+  Assert.deepEqual(h.keys(), []);
+  Assert.deepEqual(h.snapshot(), {});
+}
+
+function test_keyed_count_histogram()
+{
+  const KEYED_ID = "test::keyed::count";
+  const KEYS = ["key"+(i+1) for (i of numberRange(0, 5))];
+  let histogramBase = {
+    "min": 1,
+    "max": 2,
+    "histogram_type": 4,
+    "sum": 0,
+    "sum_squares_lo": 0,
+    "sum_squares_hi": 0,
+    "ranges": [0, 1, 2],
+    "counts": [1, 0, 0]
+  };
+  let testHistograms = [JSON.parse(JSON.stringify(histogramBase)) for (i of numberRange(0, 5))];
+  let testKeys = [];
+  let testSnapShot = {};
+
+  let h = Telemetry.newKeyedHistogram(KEYED_ID, "never", Telemetry.HISTOGRAM_COUNT);
+  for (let i=0; i<4; ++i) {
+    let key = KEYS[i];
+    let value = i*2 + 1;
+
+    for (let k=0; k<value; ++k) {
+      h.add(key);
+    }
+    testHistograms[i].counts[0] = value;
+    testHistograms[i].sum = value;
+    testHistograms[i].sum_squares_lo = value;
+    testSnapShot[key] = testHistograms[i];
+    testKeys.push(key);
+
+    Assert.deepEqual(h.keys().sort(), testKeys);
+    Assert.deepEqual(h.snapshot(key), testHistograms[i]);
+    Assert.deepEqual(h.snapshot(), testSnapShot);
+  }
+
+  h = Telemetry.getKeyedHistogramById(KEYED_ID);
+  Assert.deepEqual(h.keys().sort(), testKeys);
+  Assert.deepEqual(h.snapshot(), testSnapShot);
+
+  let key = KEYS[4];
+  h.add(key);
+  testKeys.push(key);
+  testHistograms[4].counts[0] = 1;
+  testHistograms[4].sum = 1;
+  testHistograms[4].sum_squares_lo = 1;
+  testSnapShot[key] = testHistograms[4];
+
+  Assert.deepEqual(h.keys().sort(), testKeys);
+  Assert.deepEqual(h.snapshot(), testSnapShot);
+
+  let allSnapshots = Telemetry.keyedHistogramSnapshots;
+  Assert.deepEqual(allSnapshots[KEYED_ID], testSnapShot);
+
+  h.clear();
+  Assert.deepEqual(h.keys(), []);
+  Assert.deepEqual(h.snapshot(), {});
+}
+
+
+function test_keyed_histogram() {
+  // Check that invalid names get rejected.
+
+  let threw = false;
+  try {
+    Telemetry.newKeyedHistogram("test::invalid # histogram", "never", Telemetry.HISTOGRAM_BOOLEAN);
+  } catch (e) {
+    // This should throw as we reject names with the # separator
+    threw = true;
+  }
+  Assert.ok(threw, "newKeyedHistogram should have thrown");
+
+  threw = false;
+  try {
+    Telemetry.getKeyedHistogramById("test::unknown histogram", "never", Telemetry.HISTOGRAM_BOOLEAN);
+  } catch (e) {
+    // This should throw as it is an unknown ID
+    threw = true;
+  }
+  Assert.ok(threw, "getKeyedHistogramById should have thrown");
+
+  // Check specific keyed histogram types working properly.
+
+  test_keyed_boolean_histogram();
+  test_keyed_count_histogram();
+}
+
 function generateUUID() {
   let str = Cc["@mozilla.org/uuid-generator;1"].getService(Ci.nsIUUIDGenerator).generateUUID().toString();
   // strip {}
   return str.substring(1, str.length - 1);
 }
 
 function run_test()
 {
@@ -405,9 +551,10 @@ function run_test()
   test_count_histogram();
   test_getHistogramById();
   test_histogramFrom();
   test_getSlowSQL();
   test_privateMode();
   test_addons();
   test_extended_stats();
   test_expired_histogram();
+  test_keyed_histogram();
 }