--- a/toolkit/components/telemetry/Histograms.json
+++ b/toolkit/components/telemetry/Histograms.json
@@ -4170,38 +4170,40 @@
     "alert_emails": ["safebrowsing-telemetry@mozilla.org"],
     "expires_in_version": "never",
     "kind": "enumerated",
     "keyed": true,
     "n_values": 16,
     "bug_numbers": [1311910],
     "description": "Server HTTP status code from SafeBrowsing database updates. (0=1xx, 1=200, 2=2xx, 3=204, 4=3xx, 5=400, 6=4xx, 7=403, 8=404, 9=408, 10=413, 11=5xx, 12=502|504|511, 13=503, 14=505, 15=Other). Keyed by provider"
   },
-  "URLCLASSIFIER_COMPLETE_REMOTE_STATUS": {
+  "URLCLASSIFIER_COMPLETE_REMOTE_STATUS2": {
     "alert_emails": ["safebrowsing-telemetry@mozilla.org"],
     "expires_in_version": "never",
     "kind": "enumerated",
+    "keyed": true,
     "n_values": 16,
-    "bug_numbers": [1150921],
-    "description": "Server HTTP status code from remote SafeBrowsing gethash lookups. (0=1xx, 1=200, 2=2xx, 3=204, 4=3xx, 5=400, 6=4xx, 7=403, 8=404, 9=408, 10=413, 11=5xx, 12=502|504|511, 13=503, 14=505, 15=Other)"
+    "bug_numbers": [1150921, 1311926],
+    "description": "Server HTTP status code from remote SafeBrowsing gethash lookups. (0=1xx, 1=200, 2=2xx, 3=204, 4=3xx, 5=400, 6=4xx, 7=403, 8=404, 9=408, 10=413, 11=5xx, 12=502|504|511, 13=503, 14=505, 15=Other). Keyed by provider"
   },
   "URLCLASSIFIER_COMPLETION_ERROR": {
     "alert_emails": ["safebrowsing-telemetry@mozilla.org"],
     "expires_in_version": "59",
     "kind": "enumerated",
     "n_values": 16,
     "bug_numbers": [1276826],
     "description": "SafeBrowsing v4 hash completion error (0 = success, 1 = parsing failure, 2 = unknown threat type)"
   },
-  "URLCLASSIFIER_COMPLETE_TIMEOUT": {
+  "URLCLASSIFIER_COMPLETE_TIMEOUT2": {
     "alert_emails": ["safebrowsing-telemetry@mozilla.org"],
-    "expires_in_version": "56",
-    "kind": "boolean",
-    "bug_numbers": [1172688],
-    "description": "This metric is recorded every time a gethash lookup is performed, `true` is recorded if the lookup times out."
+    "expires_in_version": "59",
+    "kind": "boolean",
+    "keyed": true,
+    "bug_numbers": [1172688, 1311926],
+    "description": "This metric is recorded every time a gethash lookup is performed, `true` is recorded if the lookup times out. Keyed by provider"
   },
   "URLCLASSIFIER_UPDATE_ERROR": {
     "alert_emails": ["safebrowsing-telemetry@mozilla.org"],
     "expires_in_version": "59",
     "kind": "enumerated",
     "keyed": true,
     "n_values": 16,
     "bug_numbers": [1311910],

--- a/toolkit/components/url-classifier/nsUrlClassifierHashCompleter.js
+++ b/toolkit/components/url-classifier/nsUrlClassifierHashCompleter.js
@@ -285,16 +285,18 @@ function HashCompleterRequest(aCompleter
   this._response = "";
   // Whether we have been informed of a shutdown by the quit-application event.
   this._shuttingDown = false;
   this.gethashUrl = aGethashUrl;
 
   // Multiple partial hashes can be associated with the same tables
   // so we use a map here.
   this.tableNames = new Map();
+
+  this.telemetryProvider = "";
 }
 HashCompleterRequest.prototype = {
   QueryInterface: XPCOMUtils.generateQI([Ci.nsIRequestObserver,
                                          Ci.nsIStreamListener,
                                          Ci.nsIObserver,
                                          Ci.nsISupports]),
 
   // This is called by the HashCompleter to add a hash and callback to the
@@ -311,16 +313,21 @@ HashCompleterRequest.prototype = {
       if (0 === this.tableNames.size) {
         // Decide if this request is v4 by the first added partial hash.
         this.isV4 = isTableNameV4;
       } else if (this.isV4 !== isTableNameV4) {
         log('ERROR: Cannot mix "proto" tables with other types within ' +
             'the same gethash URL.');
       }
       this.tableNames.set(aTableName);
+
+      // Assuming all tables with the same gethash URL have the same provider
+      if (this.telemetryProvider == "") {
+        this.telemetryProvider = gUrlUtil.getTelemetryProvider(aTableName);
+      }
     }
   },
 
   fillTableStatesBase64: function HCR_fillTableStatesBase64(aCallback) {
     gDbService.getTables(aTableData => {
       aTableData.split("\n").forEach(line => {
         let p = line.indexOf(";");
         if (-1 === p) {
@@ -371,17 +378,18 @@ HashCompleterRequest.prototype = {
   },
 
   notify: function HCR_notify() {
     // If we haven't gotten onStopRequest, just cancel. This will call us
     // with onStopRequest since we implement nsIStreamListener on the
     // channel.
     if (this._channel && this._channel.isPending()) {
       log("cancelling request to " + this.gethashUrl + "\n");
-      Services.telemetry.getHistogramById("URLCLASSIFIER_COMPLETE_TIMEOUT").add(1);
+      Services.telemetry.getKeyedHistogramById("URLCLASSIFIER_COMPLETE_TIMEOUT2").
+        add(this.telemetryProvider, 1);
       this._channel.cancel(Cr.NS_BINDING_ABORTED);
     }
   },
 
   // Creates an nsIChannel for the request and fills the body.
   openChannel: function HCR_openChannel() {
     let loadFlags = Ci.nsIChannel.INHIBIT_CACHING |
                     Ci.nsIChannel.LOAD_BYPASS_CACHE;
@@ -659,20 +667,20 @@ HashCompleterRequest.prototype = {
       httpStatus = channel.responseStatus;
       if (!success) {
         aStatusCode = Cr.NS_ERROR_ABORT;
       }
     }
     let success = Components.isSuccessCode(aStatusCode);
     log('Received a ' + httpStatus + ' status code from the gethash server (success=' + success + ').');
 
-    let histogram =
-      Services.telemetry.getHistogramById("URLCLASSIFIER_COMPLETE_REMOTE_STATUS");
-    histogram.add(httpStatusToBucket(httpStatus));
-    Services.telemetry.getHistogramById("URLCLASSIFIER_COMPLETE_TIMEOUT").add(0);
+    Services.telemetry.getKeyedHistogramById("URLCLASSIFIER_COMPLETE_REMOTE_STATUS2").
+      add(this.telemetryProvider, httpStatusToBucket(httpStatus));
+    Services.telemetry.getKeyedHistogramById("URLCLASSIFIER_COMPLETE_TIMEOUT2").
+      add(this.telemetryProvider, 0);
 
     // Notify the RequestBackoff once a response is received.
     this._completer.finishRequest(this.gethashUrl, httpStatus);
 
     if (success) {
       try {
         this.handleResponse();
       }