diff --git a/resources/sql/autopatches/20151014.harbor.circle.1.sql b/resources/sql/autopatches/20151014.harbor.circle.1.sql
new file mode 100644
--- /dev/null
+++ b/resources/sql/autopatches/20151014.harbor.circle.1.sql
@@ -0,0 +1,11 @@
+CREATE TABLE {$NAMESPACE}_harbormaster.harbormaster_keyvaluepair (
+  id INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY,
+  objectPHID VARBINARY(64) NOT NULL,
+  pairIndex BINARY(12) NOT NULL,
+  pairKey LONGTEXT NOT NULL COLLATE {$COLLATE_TEXT},
+  pairValue LONGTEXT NOT NULL COLLATE {$COLLATE_TEXT},
+  dateCreated INT UNSIGNED NOT NULL,
+  dateModified INT UNSIGNED NOT NULL,
+  KEY `key_object` (objectPHID),
+  UNIQUE KEY `key_index` (pairIndex)
+) ENGINE=InnoDB, COLLATE {$COLLATE_TEXT};
diff --git a/src/__phutil_library_map__.php b/src/__phutil_library_map__.php
--- a/src/__phutil_library_map__.php
+++ b/src/__phutil_library_map__.php
@@ -1041,6 +1041,7 @@
     'HarbormasterFileArtifact' => 'applications/harbormaster/artifact/HarbormasterFileArtifact.php',
     'HarbormasterHTTPRequestBuildStepImplementation' => 'applications/harbormaster/step/HarbormasterHTTPRequestBuildStepImplementation.php',
     'HarbormasterHostArtifact' => 'applications/harbormaster/artifact/HarbormasterHostArtifact.php',
+    'HarbormasterKeyValuePair' => 'applications/harbormaster/storage/HarbormasterKeyValuePair.php',
     'HarbormasterLeaseHostBuildStepImplementation' => 'applications/harbormaster/step/HarbormasterLeaseHostBuildStepImplementation.php',
     'HarbormasterLeaseWorkingCopyBuildStepImplementation' => 'applications/harbormaster/step/HarbormasterLeaseWorkingCopyBuildStepImplementation.php',
     'HarbormasterLintMessagesController' => 'applications/harbormaster/controller/HarbormasterLintMessagesController.php',
@@ -4874,6 +4875,7 @@
     'HarbormasterFileArtifact' => 'HarbormasterArtifact',
     'HarbormasterHTTPRequestBuildStepImplementation' => 'HarbormasterBuildStepImplementation',
     'HarbormasterHostArtifact' => 'HarbormasterDrydockLeaseArtifact',
+    'HarbormasterKeyValuePair' => 'HarbormasterDAO',
     'HarbormasterLeaseHostBuildStepImplementation' => 'HarbormasterBuildStepImplementation',
     'HarbormasterLeaseWorkingCopyBuildStepImplementation' => 'HarbormasterBuildStepImplementation',
     'HarbormasterLintMessagesController' => 'HarbormasterController',
diff --git a/src/applications/harbormaster/storage/HarbormasterKeyValuePair.php b/src/applications/harbormaster/storage/HarbormasterKeyValuePair.php
new file mode 100644
--- /dev/null
+++ b/src/applications/harbormaster/storage/HarbormasterKeyValuePair.php
@@ -0,0 +1,64 @@
+<?php
+
+/**
+ * Generic map for build steps that need to store a mapping between some
+ * external identifier and some internal identifier.
+ */
+final class HarbormasterKeyValuePair extends HarbormasterDAO {
+
+  protected $objectPHID;
+  protected $pairIndex;
+  protected $pairKey;
+  protected $pairValue;
+
+  protected function getConfiguration() {
+    return array(
+      self::CONFIG_SERIALIZATION => array(
+        'pairValue' => self::SERIALIZATION_JSON,
+      ),
+      self::CONFIG_COLUMN_SCHEMA => array(
+        'pairIndex' => 'bytes12',
+        'pairKey' => 'text',
+      ),
+      self::CONFIG_KEY_SCHEMA => array(
+        'key_object' => array(
+          'columns' => array('objectPHID'),
+        ),
+        'key_index' => array(
+          'columns' => array('pairIndex'),
+          'unique' => true,
+        ),
+      ),
+    ) + parent::getConfiguration();
+  }
+
+  public function save() {
+    $this->pairIndex = PhabricatorHash::digestForIndex($this->pairKey);
+    return parent::save();
+  }
+
+  public static function loadPairsByKey(array $keys) {
+    if (!$keys) {
+      return array();
+    }
+
+    $hashes = array();
+    foreach ($keys as $key) {
+      $hashes[] = PhabricatorHash::digestForIndex($key);
+    }
+
+    $pairs = id(new HarbormasterKeyValuePair())->loadAllWhere(
+      'pairIndex IN (%Ls)',
+      $hashes);
+
+    return mpull($pairs, null, 'getPairKey');
+  }
+
+  public static function loadPairsByObject($object_phid) {
+    return id(new HarbormasterKeyValuePair())->loadAllWhere(
+      'objectPHID = %s',
+      $object_phid);
+  }
+
+
+}