Migrate external IDs to NoteDb (part 2)

This is the second part of migrating external IDs from ReviewDb to
NoteDb.

This change:
* migrates the external IDs from ReviewDb to NoteDb (for single
  instance Gerrit servers)
* adds a configuration parameter (user.readExternalIdsFromGit) that
  controls whether external IDs are read from ReviewDb or NoteDb

The new ExternalIds class provides access to external IDs. All code that
needs external IDs is adapted to use this class to retrieve external IDs
(instead of reading directly from the database). ExternalIds gets the
external IDs either directly from the storage backend (via
ExternalIdReader) or from a cache (via ExternalIdCache).

ExternalIdReader reads the external IDs from the storage backend.
Depending on the value of the user.readExternalIdsFromGit parameter the
external IDs are read from ReviewDB or NoteDb.

If reading external IDs from NoteDb is enabled, reading the external IDs
of an account requires parsing all Git notes. This is because external
IDs are keyed by external ID key ('<scheme>:<id>') and the account ID is
only contained in the Git note content. Since parsing all Git notes is
too expensive if it is done frequently, there is a new external ID cache
which makes external IDs accessible by account. This cache is populated
once by reading all external IDs from NoteDb and is then kept up to date
by informing it whenever an external ID is added, updated or deleted.
The external ID cache uses the revision of the refs/meta/external-ids
branch as key, so that all external IDs are reloaded when the
refs/meta/external-ids branch is changed behind Gerrit's back. This
makes it easy to use this cache in a multimaster setup, since an update
of the refs/meta/external-ids branch which is done due to replication
between nodes causes a reload of the external IDs in the receiving node.
The ExternalIdCache is an implementation detail of how external IDs are
read and written, which is why it is package private. Callers should
always use ExternalIds to access external IDs and ExternalIdsUpdate /
ExternalIdsBatchUpdate to update external IDs.

The LocalUsernamesToLowerCase program needs to access all external IDs
only once to update them. After the update they are not accessed again.
Hence the LocalUsernamesToLowerCase program doesn't benefit from caching
external IDs and the external ID cache can be disabled for it.

The external ID cache is defined by the ExternalIdCache interface. It is
implemented by ExternalIdCacheImpl and DisabledExternalIdCache.
DisabledExternalIdCache can be used when an external ID cache is not
needed, e.g. in the LocalUsernamesToLowerCase program or in tests.

Pushing to the refs/meta/external-ids branch, which would only update
the external IDs in NoteDb, is still prevented by a commit validator so
that the external IDs in ReviewDb and NoteDb do not go out of sync.

Change-Id: Ia1dae9306b7ee07388b6c5e1f3dc4a1a5eea4b08
Signed-off-by: Edwin Kempin <ekempin@google.com>
diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/api/accounts/AccountIT.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/api/accounts/AccountIT.java
index 9a7a6b9..abaaefc 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/api/accounts/AccountIT.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/api/accounts/AccountIT.java
@@ -26,6 +26,7 @@
 import static com.google.gerrit.gpg.testutil.TestKeys.validKeyWithoutExpiration;
 import static com.google.gerrit.server.StarredChangesUtil.DEFAULT_LABEL;
 import static com.google.gerrit.server.StarredChangesUtil.IGNORE_LABEL;
+import static com.google.gerrit.server.account.externalids.ExternalId.SCHEME_GPGKEY;
 import static com.google.gerrit.server.group.SystemGroupBackend.ANONYMOUS_USERS;
 import static com.google.gerrit.server.group.SystemGroupBackend.REGISTERED_USERS;
 import static java.nio.charset.StandardCharsets.UTF_8;
@@ -59,7 +60,6 @@
 import com.google.gerrit.extensions.restapi.RestApiException;
 import com.google.gerrit.gpg.Fingerprint;
 import com.google.gerrit.gpg.PublicKeyStore;
-import com.google.gerrit.gpg.server.GpgKeys;
 import com.google.gerrit.gpg.testutil.TestKey;
 import com.google.gerrit.reviewdb.client.Account;
 import com.google.gerrit.reviewdb.client.RefNames;
@@ -67,6 +67,7 @@
 import com.google.gerrit.server.account.WatchConfig;
 import com.google.gerrit.server.account.WatchConfig.NotifyType;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.account.externalids.ExternalIdsUpdate;
 import com.google.gerrit.server.config.AllUsersName;
 import com.google.gerrit.server.git.ProjectConfig;
@@ -116,6 +117,8 @@
 
   @Inject private AccountByEmailCache byEmailCache;
 
+  @Inject private ExternalIds externalIds;
+
   @Inject private ExternalIdsUpdate.User externalIdsUpdateFactory;
 
   private ExternalIdsUpdate externalIdsUpdate;
@@ -913,7 +916,11 @@
     Iterable<String> expectedFps =
         expected.transform(k -> BaseEncoding.base16().encode(k.getPublicKey().getFingerprint()));
     Iterable<String> actualFps =
-        GpgKeys.getGpgExtIds(db, currAccountId).transform(e -> e.key().id());
+        externalIds
+            .byAccount(db, currAccountId, SCHEME_GPGKEY)
+            .stream()
+            .map(e -> e.key().id())
+            .collect(toSet());
     assertThat(actualFps).named("external IDs in database").containsExactlyElementsIn(expectedFps);
 
     // Check raw stored keys.
diff --git a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/account/ExternalIdIT.java b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/account/ExternalIdIT.java
index 65187ad..4039284 100644
--- a/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/account/ExternalIdIT.java
+++ b/gerrit-acceptance-tests/src/test/java/com/google/gerrit/acceptance/rest/account/ExternalIdIT.java
@@ -32,6 +32,7 @@
 import com.google.gerrit.common.data.Permission;
 import com.google.gerrit.extensions.common.AccountExternalIdInfo;
 import com.google.gerrit.reviewdb.client.RefNames;
+import com.google.gerrit.server.account.externalids.DisabledExternalIdCache;
 import com.google.gerrit.server.account.externalids.ExternalId;
 import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.account.externalids.ExternalIdsUpdate;
@@ -51,6 +52,7 @@
 import org.eclipse.jgit.errors.ConfigInvalidException;
 import org.eclipse.jgit.internal.storage.dfs.InMemoryRepository;
 import org.eclipse.jgit.junit.TestRepository;
+import org.eclipse.jgit.lib.ObjectId;
 import org.junit.Test;
 
 @Sandboxed
@@ -173,7 +175,7 @@
 
   @Test
   public void retryOnLockFailure() throws Exception {
-    Retryer<Void> retryer =
+    Retryer<ObjectId> retryer =
         ExternalIdsUpdate.retryerBuilder()
             .withBlockStrategy(
                 new BlockStrategy() {
@@ -192,6 +194,8 @@
         new ExternalIdsUpdate(
             repoManager,
             allUsers,
+            externalIds,
+            new DisabledExternalIdCache(),
             serverIdent.get(),
             serverIdent.get(),
             () -> {
@@ -208,8 +212,8 @@
     update.insert(db, ExternalId.create(fooId, admin.id));
     assertThat(doneBgUpdate.get()).isTrue();
 
-    assertThat(externalIds.get(fooId)).isNotNull();
-    assertThat(externalIds.get(barId)).isNotNull();
+    assertThat(externalIds.get(db, fooId)).isNotNull();
+    assertThat(externalIds.get(db, barId)).isNotNull();
   }
 
   @Test
@@ -224,6 +228,8 @@
         new ExternalIdsUpdate(
             repoManager,
             allUsers,
+            externalIds,
+            new DisabledExternalIdCache(),
             serverIdent.get(),
             serverIdent.get(),
             () -> {
@@ -235,7 +241,7 @@
                 // Ignore, the successful insertion of the external ID is asserted later
               }
             },
-            RetryerBuilder.<Void>newBuilder()
+            RetryerBuilder.<ObjectId>newBuilder()
                 .retryIfException(e -> e instanceof LockFailureException)
                 .withStopStrategy(StopStrategies.stopAfterAttempt(extIdsKeys.length))
                 .build());
@@ -248,7 +254,7 @@
     }
     assertThat(bgCounter.get()).isEqualTo(extIdsKeys.length);
     for (ExternalId.Key extIdKey : extIdsKeys) {
-      assertThat(externalIds.get(extIdKey)).isNotNull();
+      assertThat(externalIds.get(db, extIdKey)).isNotNull();
     }
   }
 }
diff --git a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/GpgKeys.java b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/GpgKeys.java
index 1596ce8..13fb368 100644
--- a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/GpgKeys.java
+++ b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/GpgKeys.java
@@ -17,9 +17,7 @@
 import static com.google.gerrit.server.account.externalids.ExternalId.SCHEME_GPGKEY;
 import static java.nio.charset.StandardCharsets.UTF_8;
 
-import com.google.common.annotations.VisibleForTesting;
 import com.google.common.base.CharMatcher;
-import com.google.common.collect.FluentIterable;
 import com.google.common.collect.ImmutableList;
 import com.google.common.io.BaseEncoding;
 import com.google.gerrit.extensions.common.GpgKeyInfo;
@@ -36,11 +34,11 @@
 import com.google.gerrit.gpg.GerritPublicKeyChecker;
 import com.google.gerrit.gpg.PublicKeyChecker;
 import com.google.gerrit.gpg.PublicKeyStore;
-import com.google.gerrit.reviewdb.client.Account;
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.account.AccountResource;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
 import com.google.inject.Provider;
@@ -70,6 +68,7 @@
   private final Provider<CurrentUser> self;
   private final Provider<PublicKeyStore> storeProvider;
   private final GerritPublicKeyChecker.Factory checkerFactory;
+  private final ExternalIds externalIds;
 
   @Inject
   GpgKeys(
@@ -77,12 +76,14 @@
       Provider<ReviewDb> db,
       Provider<CurrentUser> self,
       Provider<PublicKeyStore> storeProvider,
-      GerritPublicKeyChecker.Factory checkerFactory) {
+      GerritPublicKeyChecker.Factory checkerFactory,
+      ExternalIds externalIds) {
     this.views = views;
     this.db = db;
     this.self = self;
     this.storeProvider = storeProvider;
     this.checkerFactory = checkerFactory;
+    this.externalIds = externalIds;
   }
 
   @Override
@@ -198,16 +199,8 @@
     }
   }
 
-  @VisibleForTesting
-  public static FluentIterable<ExternalId> getGpgExtIds(ReviewDb db, Account.Id accountId)
-      throws OrmException {
-    return FluentIterable.from(
-            ExternalId.from(db.accountExternalIds().byAccount(accountId).toList()))
-        .filter(in -> in.isScheme(SCHEME_GPGKEY));
-  }
-
-  private Iterable<ExternalId> getGpgExtIds(AccountResource rsrc) throws OrmException {
-    return getGpgExtIds(db.get(), rsrc.getUser().getAccountId());
+  private Iterable<ExternalId> getGpgExtIds(AccountResource rsrc) throws IOException, OrmException {
+    return externalIds.byAccount(db.get(), rsrc.getUser().getAccountId(), SCHEME_GPGKEY);
   }
 
   private static long keyId(byte[] fp) {
diff --git a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/PostGpgKeys.java b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/PostGpgKeys.java
index 84eacdb..9c04ced 100644
--- a/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/PostGpgKeys.java
+++ b/gerrit-gpg/src/main/java/com/google/gerrit/gpg/server/PostGpgKeys.java
@@ -48,6 +48,7 @@
 import com.google.gerrit.server.account.AccountResource;
 import com.google.gerrit.server.account.AccountState;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.account.externalids.ExternalIdsUpdate;
 import com.google.gerrit.server.mail.send.AddKeySender;
 import com.google.gerrit.server.query.account.InternalAccountQuery;
@@ -91,6 +92,7 @@
   private final AddKeySender.Factory addKeyFactory;
   private final AccountCache accountCache;
   private final Provider<InternalAccountQuery> accountQueryProvider;
+  private final ExternalIds externalIds;
   private final ExternalIdsUpdate.User externalIdsUpdateFactory;
 
   @Inject
@@ -103,6 +105,7 @@
       AddKeySender.Factory addKeyFactory,
       AccountCache accountCache,
       Provider<InternalAccountQuery> accountQueryProvider,
+      ExternalIds externalIds,
       ExternalIdsUpdate.User externalIdsUpdateFactory) {
     this.serverIdent = serverIdent;
     this.db = db;
@@ -112,6 +115,7 @@
     this.addKeyFactory = addKeyFactory;
     this.accountCache = accountCache;
     this.accountQueryProvider = accountQueryProvider;
+    this.externalIds = externalIds;
     this.externalIdsUpdateFactory = externalIdsUpdateFactory;
   }
 
@@ -122,7 +126,7 @@
     GpgKeys.checkVisible(self, rsrc);
 
     Collection<ExternalId> existingExtIds =
-        GpgKeys.getGpgExtIds(db.get(), rsrc.getUser().getAccountId()).toList();
+        externalIds.byAccount(db.get(), rsrc.getUser().getAccountId(), SCHEME_GPGKEY);
     try (PublicKeyStore store = storeProvider.get()) {
       Set<Fingerprint> toRemove = readKeysToRemove(input, existingExtIds);
       List<PGPPublicKeyRing> newKeys = readKeysToAdd(input, toRemove);
diff --git a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/LocalUsernamesToLowerCase.java b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/LocalUsernamesToLowerCase.java
index 02d13a3..4e18ddc 100644
--- a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/LocalUsernamesToLowerCase.java
+++ b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/LocalUsernamesToLowerCase.java
@@ -20,10 +20,13 @@
 import com.google.gerrit.lifecycle.LifecycleManager;
 import com.google.gerrit.pgm.util.SiteProgram;
 import com.google.gerrit.reviewdb.server.ReviewDb;
+import com.google.gerrit.server.account.externalids.DisabledExternalIdCache;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.account.externalids.ExternalIdsBatchUpdate;
 import com.google.gerrit.server.schema.SchemaVersionCheck;
 import com.google.gwtorm.server.SchemaFactory;
+import com.google.inject.AbstractModule;
 import com.google.inject.Inject;
 import com.google.inject.Injector;
 import java.util.Collection;
@@ -37,6 +40,8 @@
 
   @Inject private SchemaFactory<ReviewDb> database;
 
+  @Inject private ExternalIds externalIds;
+
   @Inject private ExternalIdsBatchUpdate externalIdsBatchUpdate;
 
   @Override
@@ -44,10 +49,22 @@
     Injector dbInjector = createDbInjector(MULTI_USER);
     manager.add(dbInjector, dbInjector.createChildInjector(SchemaVersionCheck.module()));
     manager.start();
-    dbInjector.injectMembers(this);
+    dbInjector
+        .createChildInjector(
+            new AbstractModule() {
+              @Override
+              protected void configure() {
+                // The LocalUsernamesToLowerCase program needs to access all external IDs only
+                // once to update them. After the update they are not accessed again. Hence the
+                // LocalUsernamesToLowerCase program doesn't benefit from caching external IDs and
+                // the external ID cache can be disabled.
+                install(DisabledExternalIdCache.module());
+              }
+            })
+        .injectMembers(this);
 
     try (ReviewDb db = database.open()) {
-      Collection<ExternalId> todo = ExternalId.from(db.accountExternalIds().all().toList());
+      Collection<ExternalId> todo = externalIds.all(db);
       monitor.beginTask("Converting local usernames", todo.size());
 
       for (ExternalId extId : todo) {
@@ -56,9 +73,9 @@
       }
 
       externalIdsBatchUpdate.commit(db, "Convert local usernames to lower case");
+      monitor.endTask();
+      manager.stop();
     }
-    monitor.endTask();
-    manager.stop();
     return 0;
   }
 
diff --git a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/init/ExternalIdsOnInit.java b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/init/ExternalIdsOnInit.java
index 0ef7cab..5bedb1b 100644
--- a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/init/ExternalIdsOnInit.java
+++ b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/init/ExternalIdsOnInit.java
@@ -20,7 +20,7 @@
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.GerritPersonIdentProvider;
 import com.google.gerrit.server.account.externalids.ExternalId;
-import com.google.gerrit.server.account.externalids.ExternalIds;
+import com.google.gerrit.server.account.externalids.ExternalIdReader;
 import com.google.gerrit.server.account.externalids.ExternalIdsUpdate;
 import com.google.gerrit.server.config.SitePaths;
 import com.google.gwtorm.server.OrmException;
@@ -61,9 +61,9 @@
       try (Repository repo = new FileRepository(path);
           RevWalk rw = new RevWalk(repo);
           ObjectInserter ins = repo.newObjectInserter()) {
-        ObjectId rev = ExternalIds.readRevision(repo);
+        ObjectId rev = ExternalIdReader.readRevision(repo);
 
-        NoteMap noteMap = ExternalIds.readNoteMap(rw, rev);
+        NoteMap noteMap = ExternalIdReader.readNoteMap(rw, rev);
         for (ExternalId extId : extIds) {
           ExternalIdsUpdate.insert(rw, ins, noteMap, extId);
         }
diff --git a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/util/BatchProgramModule.java b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/util/BatchProgramModule.java
index aec0731..1574131 100644
--- a/gerrit-pgm/src/main/java/com/google/gerrit/pgm/util/BatchProgramModule.java
+++ b/gerrit-pgm/src/main/java/com/google/gerrit/pgm/util/BatchProgramModule.java
@@ -37,6 +37,7 @@
 import com.google.gerrit.server.account.GroupCacheImpl;
 import com.google.gerrit.server.account.GroupIncludeCacheImpl;
 import com.google.gerrit.server.account.Realm;
+import com.google.gerrit.server.account.externalids.ExternalIdModule;
 import com.google.gerrit.server.cache.CacheRemovalListener;
 import com.google.gerrit.server.cache.h2.DefaultCacheFactory;
 import com.google.gerrit.server.change.ChangeJson;
@@ -146,6 +147,7 @@
 
     install(new BatchGitModule());
     install(new DefaultCacheFactory.Module());
+    install(new ExternalIdModule());
     install(new GroupModule());
     install(new NoteDbModule(cfg));
     install(new PrologModule());
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountCacheImpl.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountCacheImpl.java
index 535f6d0..b2f1bae 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountCacheImpl.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountCacheImpl.java
@@ -27,7 +27,7 @@
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.account.WatchConfig.NotifyType;
 import com.google.gerrit.server.account.WatchConfig.ProjectWatchKey;
-import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.cache.CacheModule;
 import com.google.gerrit.server.index.account.AccountIndexer;
 import com.google.gerrit.server.query.account.InternalAccountQuery;
@@ -150,6 +150,7 @@
     private final GeneralPreferencesLoader loader;
     private final LoadingCache<String, Optional<Account.Id>> byName;
     private final Provider<WatchConfig.Accessor> watchConfig;
+    private final ExternalIds externalIds;
 
     @Inject
     ByIdLoader(
@@ -157,12 +158,14 @@
         GroupCache groupCache,
         GeneralPreferencesLoader loader,
         @Named(BYUSER_NAME) LoadingCache<String, Optional<Account.Id>> byUsername,
-        Provider<WatchConfig.Accessor> watchConfig) {
+        Provider<WatchConfig.Accessor> watchConfig,
+        ExternalIds externalIds) {
       this.schema = sf;
       this.groupCache = groupCache;
       this.loader = loader;
       this.byName = byUsername;
       this.watchConfig = watchConfig;
+      this.externalIds = externalIds;
     }
 
     @Override
@@ -185,9 +188,6 @@
         return missing(who);
       }
 
-      Set<ExternalId> externalIds =
-          ExternalId.from(db.accountExternalIds().byAccount(who).toList());
-
       Set<AccountGroup.UUID> internalGroups = new HashSet<>();
       for (AccountGroupMember g : db.accountGroupMembers().byAccount(who)) {
         final AccountGroup.Id groupId = g.getAccountGroupId();
@@ -206,7 +206,10 @@
       }
 
       return new AccountState(
-          account, internalGroups, externalIds, watchConfig.get().getProjectWatches(who));
+          account,
+          internalGroups,
+          externalIds.byAccount(db, who),
+          watchConfig.get().getProjectWatches(who));
     }
   }
 
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountManager.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountManager.java
index f078a38..944d008 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountManager.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/AccountManager.java
@@ -14,8 +14,6 @@
 
 package com.google.gerrit.server.account;
 
-import static java.util.stream.Collectors.toSet;
-
 import com.google.common.base.Strings;
 import com.google.gerrit.audit.AuditService;
 import com.google.gerrit.common.TimeUtil;
@@ -30,6 +28,7 @@
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.account.externalids.ExternalIdsUpdate;
 import com.google.gerrit.server.project.ProjectCache;
 import com.google.gerrit.server.query.account.InternalAccountQuery;
@@ -62,6 +61,7 @@
   private final AtomicBoolean awaitsFirstAccountCheck;
   private final AuditService auditService;
   private final Provider<InternalAccountQuery> accountQueryProvider;
+  private final ExternalIds externalIds;
   private final ExternalIdsUpdate.Server externalIdsUpdateFactory;
 
   @Inject
@@ -75,6 +75,7 @@
       ProjectCache projectCache,
       AuditService auditService,
       Provider<InternalAccountQuery> accountQueryProvider,
+      ExternalIds externalIds,
       ExternalIdsUpdate.Server externalIdsUpdateFactory) {
     this.schema = schema;
     this.byIdCache = byIdCache;
@@ -86,6 +87,7 @@
     this.awaitsFirstAccountCheck = new AtomicBoolean(true);
     this.auditService = auditService;
     this.accountQueryProvider = accountQueryProvider;
+    this.externalIds = externalIds;
     this.externalIdsUpdateFactory = externalIdsUpdateFactory;
   }
 
@@ -229,8 +231,7 @@
     try {
       db.accounts().upsert(Collections.singleton(account));
 
-      ExternalId existingExtId =
-          ExternalId.from(db.accountExternalIds().get(extId.key().asAccountExternalIdKey()));
+      ExternalId existingExtId = externalIds.get(db, extId.key());
       if (existingExtId != null && !existingExtId.accountId().equals(extId.accountId())) {
         // external ID is assigned to another account, do not overwrite
         db.accounts().delete(Collections.singleton(account));
@@ -406,10 +407,7 @@
       throws OrmException, AccountException, IOException, ConfigInvalidException {
     try (ReviewDb db = schema.open()) {
       Collection<ExternalId> filteredExtIdsByScheme =
-          ExternalId.from(db.accountExternalIds().byAccount(to).toList())
-              .stream()
-              .filter(e -> e.isScheme(who.getExternalIdKey().scheme()))
-              .collect(toSet());
+          externalIds.byAccount(db, to, who.getExternalIdKey().scheme());
 
       if (!filteredExtIdsByScheme.isEmpty()
           && (filteredExtIdsByScheme.size() > 1
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/ChangeUserName.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/ChangeUserName.java
index 1d34e64..1a02ea1 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/ChangeUserName.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/ChangeUserName.java
@@ -15,7 +15,6 @@
 package com.google.gerrit.server.account;
 
 import static com.google.gerrit.server.account.externalids.ExternalId.SCHEME_USERNAME;
-import static java.util.stream.Collectors.toSet;
 
 import com.google.gerrit.common.Nullable;
 import com.google.gerrit.common.errors.NameAlreadyUsedException;
@@ -23,6 +22,7 @@
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.account.externalids.ExternalIdsUpdate;
 import com.google.gerrit.server.ssh.SshKeyCache;
 import com.google.gwtjsonrpc.common.VoidResult;
@@ -49,6 +49,7 @@
 
   private final AccountCache accountCache;
   private final SshKeyCache sshKeyCache;
+  private final ExternalIds externalIds;
   private final ExternalIdsUpdate.Server externalIdsUpdateFactory;
 
   private final ReviewDb db;
@@ -59,12 +60,14 @@
   ChangeUserName(
       AccountCache accountCache,
       SshKeyCache sshKeyCache,
+      ExternalIds externalIds,
       ExternalIdsUpdate.Server externalIdsUpdateFactory,
       @Assisted ReviewDb db,
       @Assisted IdentifiedUser user,
       @Nullable @Assisted String newUsername) {
     this.accountCache = accountCache;
     this.sshKeyCache = sshKeyCache;
+    this.externalIds = externalIds;
     this.externalIdsUpdateFactory = externalIdsUpdateFactory;
     this.db = db;
     this.user = user;
@@ -75,11 +78,7 @@
   public VoidResult call()
       throws OrmException, NameAlreadyUsedException, InvalidUserNameException, IOException,
           ConfigInvalidException {
-    Collection<ExternalId> old =
-        ExternalId.from(db.accountExternalIds().byAccount(user.getAccountId()).toList())
-            .stream()
-            .filter(e -> e.isScheme(SCHEME_USERNAME))
-            .collect(toSet());
+    Collection<ExternalId> old = externalIds.byAccount(db, user.getAccountId(), SCHEME_USERNAME);
     if (!old.isEmpty()) {
       throw new IllegalStateException(USERNAME_CANNOT_BE_CHANGED);
     }
@@ -102,8 +101,7 @@
       } catch (OrmDuplicateKeyException dupeErr) {
         // If we are using this identity, don't report the exception.
         //
-        ExternalId other =
-            ExternalId.from(db.accountExternalIds().get(key.asAccountExternalIdKey()));
+        ExternalId other = externalIds.get(db, key);
         if (other != null && other.accountId().equals(user.getAccountId())) {
           return VoidResult.INSTANCE;
         }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/CreateAccount.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/CreateAccount.java
index 2b73453..a23d882 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/CreateAccount.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/CreateAccount.java
@@ -37,6 +37,7 @@
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.account.externalids.ExternalIdsUpdate;
 import com.google.gerrit.server.api.accounts.AccountExternalIdCreator;
 import com.google.gerrit.server.group.GroupsCollection;
@@ -73,6 +74,7 @@
   private final AccountLoader.Factory infoLoader;
   private final DynamicSet<AccountExternalIdCreator> externalIdCreators;
   private final AuditService auditService;
+  private final ExternalIds externalIds;
   private final ExternalIdsUpdate.User externalIdsUpdateFactory;
   private final String username;
 
@@ -89,6 +91,7 @@
       AccountLoader.Factory infoLoader,
       DynamicSet<AccountExternalIdCreator> externalIdCreators,
       AuditService auditService,
+      ExternalIds externalIds,
       ExternalIdsUpdate.User externalIdsUpdateFactory,
       @Assisted String username) {
     this.db = db;
@@ -102,6 +105,7 @@
     this.infoLoader = infoLoader;
     this.externalIdCreators = externalIdCreators;
     this.auditService = auditService;
+    this.externalIds = externalIds;
     this.externalIdsUpdateFactory = externalIdsUpdateFactory;
     this.username = username;
   }
@@ -127,13 +131,11 @@
     Account.Id id = new Account.Id(db.nextAccountId());
 
     ExternalId extUser = ExternalId.createUsername(username, id, input.httpPassword);
-    if (db.accountExternalIds().get(extUser.key().asAccountExternalIdKey()) != null) {
+    if (externalIds.get(db, extUser.key()) != null) {
       throw new ResourceConflictException("username '" + username + "' already exists");
     }
     if (input.email != null) {
-      if (db.accountExternalIds()
-              .get(ExternalId.Key.create(SCHEME_MAILTO, input.email).asAccountExternalIdKey())
-          != null) {
+      if (externalIds.get(db, ExternalId.Key.create(SCHEME_MAILTO, input.email)) != null) {
         throw new UnprocessableEntityException("email '" + input.email + "' already exists");
       }
       if (!OutgoingEmailValidator.isValid(input.email)) {
@@ -160,7 +162,7 @@
       } catch (OrmDuplicateKeyException duplicateKey) {
         try {
           externalIdsUpdate.delete(db, extUser);
-        } catch (IOException | ConfigInvalidException | OrmException cleanupError) {
+        } catch (IOException | ConfigInvalidException cleanupError) {
           // Ignored
         }
         throw new UnprocessableEntityException("email '" + input.email + "' already exists");
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteEmail.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteEmail.java
index e796ce9..bfdf06c 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteEmail.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteEmail.java
@@ -28,6 +28,7 @@
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.account.DeleteEmail.Input;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
 import com.google.inject.Provider;
@@ -44,17 +45,20 @@
   private final Realm realm;
   private final Provider<ReviewDb> dbProvider;
   private final AccountManager accountManager;
+  private final ExternalIds externalIds;
 
   @Inject
   DeleteEmail(
       Provider<CurrentUser> self,
       Realm realm,
       Provider<ReviewDb> dbProvider,
-      AccountManager accountManager) {
+      AccountManager accountManager,
+      ExternalIds externalIds) {
     this.self = self;
     this.realm = realm;
     this.dbProvider = dbProvider;
     this.accountManager = accountManager;
+    this.externalIds = externalIds;
   }
 
   @Override
@@ -75,13 +79,9 @@
     }
 
     Set<ExternalId> extIds =
-        dbProvider
-            .get()
-            .accountExternalIds()
-            .byAccount(user.getAccountId())
-            .toList()
+        externalIds
+            .byAccount(dbProvider.get(), user.getAccountId())
             .stream()
-            .map(ExternalId::from)
             .filter(e -> email.equals(e.email()))
             .collect(toSet());
     if (extIds.isEmpty()) {
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteExternalIds.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteExternalIds.java
index 251119d..dc7b7ad 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteExternalIds.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/DeleteExternalIds.java
@@ -28,6 +28,7 @@
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.account.externalids.ExternalIdsUpdate;
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
@@ -41,6 +42,7 @@
 public class DeleteExternalIds implements RestModifyView<AccountResource, List<String>> {
   private final AccountByEmailCache accountByEmailCache;
   private final AccountCache accountCache;
+  private final ExternalIds externalIds;
   private final ExternalIdsUpdate.User externalIdsUpdateFactory;
   private final Provider<CurrentUser> self;
   private final Provider<ReviewDb> dbProvider;
@@ -49,41 +51,39 @@
   DeleteExternalIds(
       AccountByEmailCache accountByEmailCache,
       AccountCache accountCache,
+      ExternalIds externalIds,
       ExternalIdsUpdate.User externalIdsUpdateFactory,
       Provider<CurrentUser> self,
       Provider<ReviewDb> dbProvider) {
     this.accountByEmailCache = accountByEmailCache;
     this.accountCache = accountCache;
+    this.externalIds = externalIds;
     this.externalIdsUpdateFactory = externalIdsUpdateFactory;
     this.self = self;
     this.dbProvider = dbProvider;
   }
 
   @Override
-  public Response<?> apply(AccountResource resource, List<String> externalIds)
+  public Response<?> apply(AccountResource resource, List<String> extIds)
       throws RestApiException, IOException, OrmException, ConfigInvalidException {
     if (self.get() != resource.getUser()) {
       throw new AuthException("not allowed to delete external IDs");
     }
 
-    if (externalIds == null || externalIds.size() == 0) {
+    if (extIds == null || extIds.size() == 0) {
       throw new BadRequestException("external IDs are required");
     }
 
     Account.Id accountId = resource.getUser().getAccountId();
     Map<ExternalId.Key, ExternalId> externalIdMap =
-        dbProvider
-            .get()
-            .accountExternalIds()
-            .byAccount(resource.getUser().getAccountId())
-            .toList()
+        externalIds
+            .byAccount(dbProvider.get(), resource.getUser().getAccountId())
             .stream()
-            .map(ExternalId::from)
             .collect(toMap(i -> i.key(), i -> i));
 
     List<ExternalId> toDelete = new ArrayList<>();
     ExternalId.Key last = resource.getUser().getLastLoginExternalIdKey();
-    for (String externalIdStr : externalIds) {
+    for (String externalIdStr : extIds) {
       ExternalId id = externalIdMap.get(ExternalId.Key.parse(externalIdStr));
 
       if (id == null) {
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/GetExternalIds.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/GetExternalIds.java
index 2a45b77..12de82c 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/GetExternalIds.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/GetExternalIds.java
@@ -25,11 +25,13 @@
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.CurrentUser;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.config.AuthConfig;
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
 import com.google.inject.Provider;
 import com.google.inject.Singleton;
+import java.io.IOException;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.List;
@@ -37,26 +39,30 @@
 @Singleton
 public class GetExternalIds implements RestReadView<AccountResource> {
   private final Provider<ReviewDb> db;
+  private final ExternalIds externalIds;
   private final Provider<CurrentUser> self;
   private final AuthConfig authConfig;
 
   @Inject
-  GetExternalIds(Provider<ReviewDb> db, Provider<CurrentUser> self, AuthConfig authConfig) {
+  GetExternalIds(
+      Provider<ReviewDb> db,
+      ExternalIds externalIds,
+      Provider<CurrentUser> self,
+      AuthConfig authConfig) {
     this.db = db;
+    this.externalIds = externalIds;
     this.self = self;
     this.authConfig = authConfig;
   }
 
   @Override
   public List<AccountExternalIdInfo> apply(AccountResource resource)
-      throws RestApiException, OrmException {
+      throws RestApiException, IOException, OrmException {
     if (self.get() != resource.getUser()) {
       throw new AuthException("not allowed to get external IDs");
     }
 
-    Collection<ExternalId> ids =
-        ExternalId.from(
-            db.get().accountExternalIds().byAccount(resource.getUser().getAccountId()).toList());
+    Collection<ExternalId> ids = externalIds.byAccount(db.get(), resource.getUser().getAccountId());
     if (ids.isEmpty()) {
       return ImmutableList.of();
     }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/PutHttpPassword.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/PutHttpPassword.java
index 6f2635a..d8451bf 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/PutHttpPassword.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/PutHttpPassword.java
@@ -27,6 +27,7 @@
 import com.google.gerrit.server.IdentifiedUser;
 import com.google.gerrit.server.account.PutHttpPassword.Input;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.account.externalids.ExternalIdsUpdate;
 import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
@@ -57,6 +58,7 @@
   private final Provider<CurrentUser> self;
   private final Provider<ReviewDb> dbProvider;
   private final AccountCache accountCache;
+  private final ExternalIds externalIds;
   private final ExternalIdsUpdate.User externalIdsUpdate;
 
   @Inject
@@ -64,10 +66,12 @@
       Provider<CurrentUser> self,
       Provider<ReviewDb> dbProvider,
       AccountCache accountCache,
+      ExternalIds externalIds,
       ExternalIdsUpdate.User externalIdsUpdate) {
     this.self = self;
     this.dbProvider = dbProvider;
     this.accountCache = accountCache;
+    this.externalIds = externalIds;
     this.externalIdsUpdate = externalIdsUpdate;
   }
 
@@ -111,13 +115,8 @@
     }
 
     ExternalId extId =
-        ExternalId.from(
-            dbProvider
-                .get()
-                .accountExternalIds()
-                .get(
-                    ExternalId.Key.create(SCHEME_USERNAME, user.getUserName())
-                        .asAccountExternalIdKey()));
+        externalIds.get(
+            dbProvider.get(), ExternalId.Key.create(SCHEME_USERNAME, user.getUserName()));
     if (extId == null) {
       throw new ResourceNotFoundException();
     }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/DisabledExternalIdCache.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/DisabledExternalIdCache.java
new file mode 100644
index 0000000..484c246
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/DisabledExternalIdCache.java
@@ -0,0 +1,76 @@
+// Copyright (C) 2017 The Android Open Source Project
+//
+// Licensed 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 com.google.gerrit.server.account.externalids;
+
+import com.google.gerrit.reviewdb.client.Account;
+import com.google.inject.AbstractModule;
+import com.google.inject.Module;
+import java.util.Set;
+import org.eclipse.jgit.lib.ObjectId;
+
+public class DisabledExternalIdCache implements ExternalIdCache {
+  public static Module module() {
+    return new AbstractModule() {
+
+      @Override
+      protected void configure() {
+        bind(ExternalIdCache.class).to(DisabledExternalIdCache.class);
+      }
+    };
+  }
+
+  @Override
+  public void onCreate(ObjectId newNotesRev, Iterable<ExternalId> extId) {}
+
+  @Override
+  public void onUpdate(ObjectId newNotesRev, Iterable<ExternalId> extId) {}
+
+  @Override
+  public void onReplace(
+      ObjectId newNotesRev,
+      Account.Id accountId,
+      Iterable<ExternalId> toRemove,
+      Iterable<ExternalId> toAdd) {}
+
+  @Override
+  public void onReplaceByKeys(
+      ObjectId newNotesRev,
+      Account.Id accountId,
+      Iterable<ExternalId.Key> toRemove,
+      Iterable<ExternalId> toAdd) {}
+
+  @Override
+  public void onReplaceByKeys(
+      ObjectId newNotesRev, Iterable<ExternalId.Key> toRemove, Iterable<ExternalId> toAdd) {}
+
+  @Override
+  public void onReplace(
+      ObjectId newNotesRev, Iterable<ExternalId> toRemove, Iterable<ExternalId> toAdd) {}
+
+  @Override
+  public void onRemove(ObjectId newNotesRev, Iterable<ExternalId> extId) {}
+
+  @Override
+  public void onRemoveByKeys(
+      ObjectId newNotesRev, Account.Id accountId, Iterable<ExternalId.Key> extIdKeys) {}
+
+  @Override
+  public void onRemoveByKeys(ObjectId newNotesRev, Iterable<ExternalId.Key> extIdKeys) {}
+
+  @Override
+  public Set<ExternalId> byAccount(Account.Id accountId) {
+    throw new UnsupportedOperationException();
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdCache.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdCache.java
new file mode 100644
index 0000000..d8171dd
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdCache.java
@@ -0,0 +1,76 @@
+// Copyright (C) 2016 The Android Open Source Project
+//
+// Licensed 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 com.google.gerrit.server.account.externalids;
+
+import com.google.gerrit.reviewdb.client.Account;
+import java.io.IOException;
+import java.util.Collections;
+import java.util.Set;
+import org.eclipse.jgit.lib.ObjectId;
+
+/** Caches external IDs of all accounts */
+interface ExternalIdCache {
+  void onCreate(ObjectId newNotesRev, Iterable<ExternalId> extId) throws IOException;
+
+  void onUpdate(ObjectId newNotesRev, Iterable<ExternalId> extId) throws IOException;
+
+  void onReplace(
+      ObjectId newNotesRev,
+      Account.Id accountId,
+      Iterable<ExternalId> toRemove,
+      Iterable<ExternalId> toAdd)
+      throws IOException;
+
+  void onReplaceByKeys(
+      ObjectId newNotesRev,
+      Account.Id accountId,
+      Iterable<ExternalId.Key> toRemove,
+      Iterable<ExternalId> toAdd)
+      throws IOException;
+
+  void onReplaceByKeys(
+      ObjectId newNotesRev, Iterable<ExternalId.Key> toRemove, Iterable<ExternalId> toAdd)
+      throws IOException;
+
+  void onReplace(ObjectId newNotesRev, Iterable<ExternalId> toRemove, Iterable<ExternalId> toAdd)
+      throws IOException;
+
+  void onRemove(ObjectId newNotesRev, Iterable<ExternalId> extId) throws IOException;
+
+  void onRemoveByKeys(
+      ObjectId newNotesRev, Account.Id accountId, Iterable<ExternalId.Key> extIdKeys)
+      throws IOException;
+
+  void onRemoveByKeys(ObjectId newNotesRev, Iterable<ExternalId.Key> extIdKeys) throws IOException;
+
+  Set<ExternalId> byAccount(Account.Id accountId) throws IOException;
+
+  default void onCreate(ObjectId newNotesRev, ExternalId extId) throws IOException {
+    onCreate(newNotesRev, Collections.singleton(extId));
+  }
+
+  default void onRemove(ObjectId newNotesRev, ExternalId extId) throws IOException {
+    onRemove(newNotesRev, Collections.singleton(extId));
+  }
+
+  default void onRemoveByKey(ObjectId newNotesRev, Account.Id accountId, ExternalId.Key extIdKey)
+      throws IOException {
+    onRemoveByKeys(newNotesRev, accountId, Collections.singleton(extIdKey));
+  }
+
+  default void onUpdate(ObjectId newNotesRev, ExternalId updatedExtId) throws IOException {
+    onUpdate(newNotesRev, Collections.singleton(updatedExtId));
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdCacheImpl.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdCacheImpl.java
new file mode 100644
index 0000000..7eb29da
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdCacheImpl.java
@@ -0,0 +1,263 @@
+// Copyright (C) 2016 The Android Open Source Project
+//
+// Licensed 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 com.google.gerrit.server.account.externalids;
+
+import com.google.common.cache.CacheLoader;
+import com.google.common.cache.LoadingCache;
+import com.google.common.collect.ImmutableSetMultimap;
+import com.google.common.collect.Iterables;
+import com.google.common.collect.ListMultimap;
+import com.google.common.collect.Multimap;
+import com.google.common.collect.MultimapBuilder;
+import com.google.gerrit.reviewdb.client.Account;
+import com.google.inject.Inject;
+import com.google.inject.Singleton;
+import com.google.inject.name.Named;
+import java.io.IOException;
+import java.util.Collections;
+import java.util.Set;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReentrantLock;
+import java.util.function.Consumer;
+import org.eclipse.jgit.lib.ObjectId;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/** Caches external IDs of all accounts. The external IDs are always loaded from NoteDb. */
+@Singleton
+class ExternalIdCacheImpl implements ExternalIdCache {
+  private static final Logger log = LoggerFactory.getLogger(ExternalIdCacheImpl.class);
+
+  public static final String CACHE_NAME = "external_ids_map";
+
+  private final LoadingCache<ObjectId, ImmutableSetMultimap<Account.Id, ExternalId>>
+      extIdsByAccount;
+  private final ExternalIdReader externalIdReader;
+  private final Lock lock;
+
+  @Inject
+  ExternalIdCacheImpl(
+      @Named(CACHE_NAME)
+          LoadingCache<ObjectId, ImmutableSetMultimap<Account.Id, ExternalId>> extIdsByAccount,
+      ExternalIdReader externalIdReader) {
+    this.extIdsByAccount = extIdsByAccount;
+    this.externalIdReader = externalIdReader;
+    this.lock = new ReentrantLock(true /* fair */);
+  }
+
+  @Override
+  public void onCreate(ObjectId newNotesRev, Iterable<ExternalId> extIds) throws IOException {
+    updateCache(
+        newNotesRev,
+        m -> {
+          for (ExternalId extId : extIds) {
+            m.put(extId.accountId(), extId);
+          }
+        });
+  }
+
+  @Override
+  public void onRemove(ObjectId newNotesRev, Iterable<ExternalId> extIds) throws IOException {
+    updateCache(
+        newNotesRev,
+        m -> {
+          for (ExternalId extId : extIds) {
+            m.remove(extId.accountId(), extId);
+          }
+        });
+  }
+
+  @Override
+  public void onRemoveByKeys(
+      ObjectId newNotesRev, Account.Id accountId, Iterable<ExternalId.Key> extIdKeys)
+      throws IOException {
+    updateCache(
+        newNotesRev,
+        m -> {
+          for (ExternalId extId : m.get(accountId)) {
+            for (ExternalId.Key extIdKey : extIdKeys) {
+              if (extIdKey.equals(extId.key())) {
+                m.remove(accountId, extId);
+                break;
+              }
+            }
+          }
+        });
+  }
+
+  @Override
+  public void onRemoveByKeys(ObjectId newNotesRev, Iterable<ExternalId.Key> extIdKeys)
+      throws IOException {
+    updateCache(
+        newNotesRev,
+        m -> {
+          for (ExternalId extId : m.values()) {
+            for (ExternalId.Key extIdKey : extIdKeys) {
+              if (extIdKey.equals(extId.key())) {
+                m.remove(extId.accountId(), extId);
+                break;
+              }
+            }
+          }
+        });
+  }
+
+  @Override
+  public void onUpdate(ObjectId newNotesRev, Iterable<ExternalId> updatedExtIds)
+      throws IOException {
+    updateCache(
+        newNotesRev,
+        m -> {
+          for (ExternalId updatedExtId : updatedExtIds) {
+            for (ExternalId extId : m.get(updatedExtId.accountId())) {
+              if (updatedExtId.key().equals(extId.key())) {
+                m.remove(updatedExtId.accountId(), extId);
+                break;
+              }
+            }
+            m.put(updatedExtId.accountId(), updatedExtId);
+          }
+        });
+  }
+
+  @Override
+  public void onReplace(
+      ObjectId newNotesRev,
+      Account.Id accountId,
+      Iterable<ExternalId> toRemove,
+      Iterable<ExternalId> toAdd)
+      throws IOException {
+    ExternalIdsUpdate.checkSameAccount(Iterables.concat(toRemove, toAdd), accountId);
+
+    updateCache(
+        newNotesRev,
+        m -> {
+          for (ExternalId extId : toRemove) {
+            m.remove(extId.accountId(), extId);
+          }
+          for (ExternalId extId : toAdd) {
+            m.put(extId.accountId(), extId);
+          }
+        });
+  }
+
+  @Override
+  public void onReplaceByKeys(
+      ObjectId newNotesRev,
+      Account.Id accountId,
+      Iterable<ExternalId.Key> toRemove,
+      Iterable<ExternalId> toAdd)
+      throws IOException {
+    ExternalIdsUpdate.checkSameAccount(toAdd, accountId);
+
+    updateCache(
+        newNotesRev,
+        m -> {
+          for (ExternalId extId : m.get(accountId)) {
+            for (ExternalId.Key extIdKey : toRemove) {
+              if (extIdKey.equals(extId.key())) {
+                m.remove(accountId, extId);
+              }
+            }
+          }
+          for (ExternalId extId : toAdd) {
+            m.put(extId.accountId(), extId);
+          }
+        });
+  }
+
+  @Override
+  public void onReplaceByKeys(
+      ObjectId newNotesRev, Iterable<ExternalId.Key> toRemove, Iterable<ExternalId> toAdd)
+      throws IOException {
+    updateCache(
+        newNotesRev,
+        m -> {
+          for (ExternalId extId : m.values()) {
+            for (ExternalId.Key extIdKey : toRemove) {
+              if (extIdKey.equals(extId.key())) {
+                m.remove(extId.accountId(), extId);
+              }
+            }
+          }
+          for (ExternalId extId : toAdd) {
+            m.put(extId.accountId(), extId);
+          }
+        });
+  }
+
+  @Override
+  public void onReplace(
+      ObjectId newNotesRev, Iterable<ExternalId> toRemove, Iterable<ExternalId> toAdd)
+      throws IOException {
+    updateCache(
+        newNotesRev,
+        m -> {
+          for (ExternalId extId : toRemove) {
+            m.remove(extId.accountId(), extId);
+          }
+          for (ExternalId extId : toAdd) {
+            m.put(extId.accountId(), extId);
+          }
+        });
+  }
+
+  @Override
+  public Set<ExternalId> byAccount(Account.Id accountId) throws IOException {
+    try {
+      return extIdsByAccount.get(externalIdReader.readRevision()).get(accountId);
+    } catch (ExecutionException e) {
+      log.warn("Cannot list external ids", e);
+      return Collections.emptySet();
+    }
+  }
+
+  private void updateCache(ObjectId newNotesRev, Consumer<Multimap<Account.Id, ExternalId>> update)
+      throws IOException {
+    lock.lock();
+    try {
+      ListMultimap<Account.Id, ExternalId> m =
+          MultimapBuilder.hashKeys()
+              .arrayListValues()
+              .build(extIdsByAccount.get(externalIdReader.readRevision()));
+      update.accept(m);
+      extIdsByAccount.put(newNotesRev, ImmutableSetMultimap.copyOf(m));
+    } catch (ExecutionException e) {
+      log.warn("Cannot update external IDs", e);
+    } finally {
+      lock.unlock();
+    }
+  }
+
+  static class Loader extends CacheLoader<ObjectId, ImmutableSetMultimap<Account.Id, ExternalId>> {
+    private final ExternalIdReader externalIdReader;
+
+    @Inject
+    Loader(ExternalIdReader externalIdReader) {
+      this.externalIdReader = externalIdReader;
+    }
+
+    @Override
+    public ImmutableSetMultimap<Account.Id, ExternalId> load(ObjectId notesRev) throws Exception {
+      Multimap<Account.Id, ExternalId> extIdsByAccount =
+          MultimapBuilder.hashKeys().arrayListValues().build();
+      for (ExternalId extId : externalIdReader.all(notesRev)) {
+        extIdsByAccount.put(extId.accountId(), extId);
+      }
+      return ImmutableSetMultimap.copyOf(extIdsByAccount);
+    }
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdModule.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdModule.java
new file mode 100644
index 0000000..3486b4e
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdModule.java
@@ -0,0 +1,52 @@
+// Copyright (C) 2017 The Android Open Source Project
+//
+// Licensed 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 com.google.gerrit.server.account.externalids;
+
+import com.google.common.collect.ImmutableSetMultimap;
+import com.google.gerrit.reviewdb.client.Account;
+import com.google.gerrit.server.account.externalids.ExternalIdCacheImpl.Loader;
+import com.google.gerrit.server.cache.CacheModule;
+import com.google.inject.TypeLiteral;
+import org.eclipse.jgit.lib.ObjectId;
+
+public class ExternalIdModule extends CacheModule {
+  @Override
+  protected void configure() {
+    cache(
+            ExternalIdCacheImpl.CACHE_NAME,
+            ObjectId.class,
+            new TypeLiteral<ImmutableSetMultimap<Account.Id, ExternalId>>() {})
+        // The cached data is potentially pretty large and we are always only interested
+        // in the latest value, hence the maximum cache weight is set to 1.
+        // This can lead to extra cache loads in case of the following race:
+        // 1. thread 1 reads the notes ref at revision A
+        // 2. thread 2 updates the notes ref to revision B and stores the derived value
+        //    for B in the cache
+        // 3. thread 1 attempts to read the data for revision A from the cache, and misses
+        // 4. later threads attempt to read at B
+        // In this race unneeded reloads are done in step 3 (reload from revision A) and
+        // step 4 (reload from revision B, because the value for revision B was lost when the
+        // reload from revision A was done, since the cache can hold only one entry).
+        // These reloads could be avoided by increasing the cache size to 2. However the race
+        // window between reading the ref and looking it up in the cache is small so that
+        // it's rare that this race happens. Therefore it's not worth to double the memory
+        // usage of this cache, just to avoid this.
+        .maximumWeight(1)
+        .loader(Loader.class);
+
+    bind(ExternalIdCacheImpl.class);
+    bind(ExternalIdCache.class).to(ExternalIdCacheImpl.class);
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdReader.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdReader.java
new file mode 100644
index 0000000..7b607dc
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdReader.java
@@ -0,0 +1,184 @@
+// Copyright (C) 2017 The Android Open Source Project
+//
+// Licensed 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 com.google.gerrit.server.account.externalids;
+
+import static org.eclipse.jgit.lib.Constants.OBJ_BLOB;
+
+import com.google.common.collect.ImmutableSet;
+import com.google.gerrit.common.Nullable;
+import com.google.gerrit.reviewdb.client.RefNames;
+import com.google.gerrit.reviewdb.server.ReviewDb;
+import com.google.gerrit.server.config.AllUsersName;
+import com.google.gerrit.server.config.GerritServerConfig;
+import com.google.gerrit.server.git.GitRepositoryManager;
+import com.google.gwtorm.server.OrmException;
+import com.google.inject.Inject;
+import com.google.inject.Singleton;
+import java.io.IOException;
+import java.util.HashSet;
+import java.util.Set;
+import org.eclipse.jgit.errors.ConfigInvalidException;
+import org.eclipse.jgit.lib.Config;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.Ref;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.notes.Note;
+import org.eclipse.jgit.notes.NoteMap;
+import org.eclipse.jgit.revwalk.RevWalk;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * Class to read external IDs from ReviewDb or NoteDb.
+ *
+ * <p>In NoteDb external IDs are stored in the All-Users repository in a Git Notes branch called
+ * refs/meta/external-ids where the sha1 of the external ID is used as note name. Each note content
+ * is a git config file that contains an external ID. It has exactly one externalId subsection with
+ * an accountId and optionally email and password:
+ *
+ * <pre>
+ * [externalId "username:jdoe"]
+ *   accountId = 1003407
+ *   email = jdoe@example.com
+ *   password = bcrypt:4:LCbmSBDivK/hhGVQMfkDpA==:XcWn0pKYSVU/UJgOvhidkEtmqCp6oKB7
+ * </pre>
+ */
+@Singleton
+public class ExternalIdReader {
+  private static final Logger log = LoggerFactory.getLogger(ExternalIdReader.class);
+
+  public static final int MAX_NOTE_SZ = 1 << 19;
+
+  public static ObjectId readRevision(Repository repo) throws IOException {
+    Ref ref = repo.exactRef(RefNames.REFS_EXTERNAL_IDS);
+    return ref != null ? ref.getObjectId() : ObjectId.zeroId();
+  }
+
+  public static NoteMap readNoteMap(RevWalk rw, ObjectId rev) throws IOException {
+    if (!rev.equals(ObjectId.zeroId())) {
+      return NoteMap.read(rw.getObjectReader(), rw.parseCommit(rev));
+    }
+    return NoteMap.newEmptyMap();
+  }
+
+  private final boolean readFromGit;
+  private final GitRepositoryManager repoManager;
+  private final AllUsersName allUsersName;
+
+  @Inject
+  ExternalIdReader(
+      @GerritServerConfig Config cfg, GitRepositoryManager repoManager, AllUsersName allUsersName) {
+    this.readFromGit = cfg.getBoolean("user", null, "readExternalIdsFromGit", false);
+    this.repoManager = repoManager;
+    this.allUsersName = allUsersName;
+  }
+
+  boolean readFromGit() {
+    return readFromGit;
+  }
+
+  ObjectId readRevision() throws IOException {
+    try (Repository repo = repoManager.openRepository(allUsersName)) {
+      return readRevision(repo);
+    }
+  }
+
+  /** Reads and returns all external IDs. */
+  Set<ExternalId> all(ReviewDb db) throws IOException, OrmException {
+    if (readFromGit) {
+      try (Repository repo = repoManager.openRepository(allUsersName)) {
+        return all(repo, readRevision(repo));
+      }
+    }
+
+    return ExternalId.from(db.accountExternalIds().all().toList());
+  }
+
+  /**
+   * Reads and returns all external IDs from the specified revision of the refs/meta/external-ids
+   * branch.
+   */
+  Set<ExternalId> all(ObjectId rev) throws IOException {
+    try (Repository repo = repoManager.openRepository(allUsersName)) {
+      return all(repo, rev);
+    }
+  }
+
+  /** Reads and returns all external IDs. */
+  private static Set<ExternalId> all(Repository repo, ObjectId rev) throws IOException {
+    if (rev.equals(ObjectId.zeroId())) {
+      return ImmutableSet.of();
+    }
+
+    try (RevWalk rw = new RevWalk(repo)) {
+      NoteMap noteMap = readNoteMap(rw, rev);
+      Set<ExternalId> extIds = new HashSet<>();
+      for (Note note : noteMap) {
+        byte[] raw =
+            rw.getObjectReader().open(note.getData(), OBJ_BLOB).getCachedBytes(MAX_NOTE_SZ);
+        try {
+          extIds.add(ExternalId.parse(note.getName(), raw));
+        } catch (ConfigInvalidException e) {
+          log.error(String.format("Ignoring invalid external ID note %s", note.getName()), e);
+        }
+      }
+      return extIds;
+    }
+  }
+
+  /** Reads and returns the specified external ID. */
+  @Nullable
+  ExternalId get(ReviewDb db, ExternalId.Key key)
+      throws IOException, ConfigInvalidException, OrmException {
+    if (readFromGit) {
+      try (Repository repo = repoManager.openRepository(allUsersName);
+          RevWalk rw = new RevWalk(repo)) {
+        ObjectId rev = readRevision(repo);
+        if (rev.equals(ObjectId.zeroId())) {
+          return null;
+        }
+
+        return parse(key, rw, rev);
+      }
+    }
+    return ExternalId.from(db.accountExternalIds().get(key.asAccountExternalIdKey()));
+  }
+
+  /** Reads and returns the specified external ID from the given revision. */
+  @Nullable
+  ExternalId get(ExternalId.Key key, ObjectId rev) throws IOException, ConfigInvalidException {
+    if (rev.equals(ObjectId.zeroId())) {
+      return null;
+    }
+
+    try (Repository repo = repoManager.openRepository(allUsersName);
+        RevWalk rw = new RevWalk(repo)) {
+      return parse(key, rw, rev);
+    }
+  }
+
+  private static ExternalId parse(ExternalId.Key key, RevWalk rw, ObjectId rev)
+      throws IOException, ConfigInvalidException {
+    NoteMap noteMap = readNoteMap(rw, rev);
+    ObjectId noteId = key.sha1();
+    if (!noteMap.contains(noteId)) {
+      return null;
+    }
+
+    byte[] raw =
+        rw.getObjectReader().open(noteMap.get(noteId), OBJ_BLOB).getCachedBytes(MAX_NOTE_SZ);
+    return ExternalId.parse(noteId.name(), raw);
+  }
+}
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIds.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIds.java
index 6f41958..e8fb586 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIds.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIds.java
@@ -14,92 +14,72 @@
 
 package com.google.gerrit.server.account.externalids;
 
-import static org.eclipse.jgit.lib.Constants.OBJ_BLOB;
+import static java.util.stream.Collectors.toSet;
 
 import com.google.gerrit.common.Nullable;
-import com.google.gerrit.reviewdb.client.RefNames;
-import com.google.gerrit.server.config.AllUsersName;
-import com.google.gerrit.server.git.GitRepositoryManager;
+import com.google.gerrit.reviewdb.client.Account;
+import com.google.gerrit.reviewdb.server.ReviewDb;
+import com.google.gwtorm.server.OrmException;
 import com.google.inject.Inject;
 import com.google.inject.Singleton;
 import java.io.IOException;
+import java.util.Set;
 import org.eclipse.jgit.errors.ConfigInvalidException;
 import org.eclipse.jgit.lib.ObjectId;
-import org.eclipse.jgit.lib.Ref;
-import org.eclipse.jgit.lib.Repository;
-import org.eclipse.jgit.notes.NoteMap;
-import org.eclipse.jgit.revwalk.RevWalk;
 
 /**
- * Class to read external IDs from NoteDb.
+ * Class to access external IDs.
  *
- * <p>In NoteDb external IDs are stored in the All-Users repository in a Git Notes branch called
- * refs/meta/external-ids where the sha1 of the external ID is used as note name. Each note content
- * is a git config file that contains an external ID. It has exactly one externalId subsection with
- * an accountId and optionally email and password:
- *
- * <pre>
- * [externalId "username:jdoe"]
- *   accountId = 1003407
- *   email = jdoe@example.com
- *   password = bcrypt:4:LCbmSBDivK/hhGVQMfkDpA==:XcWn0pKYSVU/UJgOvhidkEtmqCp6oKB7
- * </pre>
+ * <p>The external IDs are either read from NoteDb or retrieved from the cache.
  */
 @Singleton
 public class ExternalIds {
-  public static final int MAX_NOTE_SZ = 1 << 19;
-
-  public static ObjectId readRevision(Repository repo) throws IOException {
-    Ref ref = repo.exactRef(RefNames.REFS_EXTERNAL_IDS);
-    return ref != null ? ref.getObjectId() : ObjectId.zeroId();
-  }
-
-  public static NoteMap readNoteMap(RevWalk rw, ObjectId rev) throws IOException {
-    if (!rev.equals(ObjectId.zeroId())) {
-      return NoteMap.read(rw.getObjectReader(), rw.parseCommit(rev));
-    }
-    return NoteMap.newEmptyMap();
-  }
-
-  private final GitRepositoryManager repoManager;
-  private final AllUsersName allUsersName;
+  private final ExternalIdReader externalIdReader;
+  private final ExternalIdCache externalIdCache;
 
   @Inject
-  public ExternalIds(GitRepositoryManager repoManager, AllUsersName allUsersName) {
-    this.repoManager = repoManager;
-    this.allUsersName = allUsersName;
+  public ExternalIds(ExternalIdReader externalIdReader, ExternalIdCache externalIdCache) {
+    this.externalIdReader = externalIdReader;
+    this.externalIdCache = externalIdCache;
   }
 
-  public ObjectId readRevision() throws IOException {
-    try (Repository repo = repoManager.openRepository(allUsersName)) {
-      return readRevision(repo);
-    }
+  /** Returns all external IDs. */
+  public Set<ExternalId> all(ReviewDb db) throws IOException, OrmException {
+    return externalIdReader.all(db);
   }
 
-  /** Reads and returns the specified external ID. */
+  /** Returns all external IDs from the specified revision of the refs/meta/external-ids branch. */
+  public Set<ExternalId> all(ObjectId rev) throws IOException {
+    return externalIdReader.all(rev);
+  }
+
+  /** Returns the specified external ID. */
   @Nullable
-  public ExternalId get(ExternalId.Key key) throws IOException, ConfigInvalidException {
-    try (Repository repo = repoManager.openRepository(allUsersName);
-        RevWalk rw = new RevWalk(repo)) {
-      ObjectId rev = readRevision(repo);
-      if (rev.equals(ObjectId.zeroId())) {
-        return null;
-      }
-
-      return parse(key, rw, rev);
-    }
+  public ExternalId get(ReviewDb db, ExternalId.Key key)
+      throws IOException, ConfigInvalidException, OrmException {
+    return externalIdReader.get(db, key);
   }
 
-  private ExternalId parse(ExternalId.Key key, RevWalk rw, ObjectId rev)
+  /** Returns the specified external ID from the given revision. */
+  @Nullable
+  public ExternalId get(ExternalId.Key key, ObjectId rev)
       throws IOException, ConfigInvalidException {
-    NoteMap noteMap = readNoteMap(rw, rev);
-    ObjectId noteId = key.sha1();
-    if (!noteMap.contains(noteId)) {
-      return null;
+    return externalIdReader.get(key, rev);
+  }
+
+  /** Returns the external IDs of the specified account. */
+  public Set<ExternalId> byAccount(ReviewDb db, Account.Id accountId)
+      throws IOException, OrmException {
+    if (externalIdReader.readFromGit()) {
+      return externalIdCache.byAccount(accountId);
     }
 
-    byte[] raw =
-        rw.getObjectReader().open(noteMap.get(noteId), OBJ_BLOB).getCachedBytes(MAX_NOTE_SZ);
-    return ExternalId.parse(noteId.name(), raw);
+    return ExternalId.from(db.accountExternalIds().byAccount(accountId).toList());
+  }
+
+  /** Returns the external IDs of the specified account that have the given scheme. */
+  public Set<ExternalId> byAccount(ReviewDb db, Account.Id accountId, String scheme)
+      throws IOException, OrmException {
+    return byAccount(db, accountId).stream().filter(e -> e.key().isScheme(scheme)).collect(toSet());
   }
 }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdsBatchUpdate.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdsBatchUpdate.java
index 4bdba76..79e7bb6 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdsBatchUpdate.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdsBatchUpdate.java
@@ -46,6 +46,7 @@
   private final GitRepositoryManager repoManager;
   private final AllUsersName allUsersName;
   private final PersonIdent serverIdent;
+  private final ExternalIdCache externalIdCache;
   private final Set<ExternalId> toAdd = new HashSet<>();
   private final Set<ExternalId> toDelete = new HashSet<>();
 
@@ -53,10 +54,12 @@
   public ExternalIdsBatchUpdate(
       GitRepositoryManager repoManager,
       AllUsersName allUsersName,
-      @GerritPersonIdent PersonIdent serverIdent) {
+      @GerritPersonIdent PersonIdent serverIdent,
+      ExternalIdCache externalIdCache) {
     this.repoManager = repoManager;
     this.allUsersName = allUsersName;
     this.serverIdent = serverIdent;
+    this.externalIdCache = externalIdCache;
   }
 
   /**
@@ -94,9 +97,9 @@
     try (Repository repo = repoManager.openRepository(allUsersName);
         RevWalk rw = new RevWalk(repo);
         ObjectInserter ins = repo.newObjectInserter()) {
-      ObjectId rev = ExternalIds.readRevision(repo);
+      ObjectId rev = ExternalIdReader.readRevision(repo);
 
-      NoteMap noteMap = ExternalIds.readNoteMap(rw, rev);
+      NoteMap noteMap = ExternalIdReader.readNoteMap(rw, rev);
 
       for (ExternalId extId : toDelete) {
         ExternalIdsUpdate.remove(rw, noteMap, extId);
@@ -106,8 +109,10 @@
         ExternalIdsUpdate.insert(rw, ins, noteMap, extId);
       }
 
-      ExternalIdsUpdate.commit(
-          repo, rw, ins, rev, noteMap, commitMessage, serverIdent, serverIdent);
+      ObjectId newRev =
+          ExternalIdsUpdate.commit(
+              repo, rw, ins, rev, noteMap, commitMessage, serverIdent, serverIdent);
+      externalIdCache.onReplace(newRev, toDelete, toAdd);
     }
 
     toAdd.clear();
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdsUpdate.java b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdsUpdate.java
index 1648b4d..561d05e 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdsUpdate.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/account/externalids/ExternalIdsUpdate.java
@@ -18,9 +18,9 @@
 import static com.google.common.base.Preconditions.checkState;
 import static com.google.gerrit.server.account.externalids.ExternalId.Key.toAccountExternalIdKeys;
 import static com.google.gerrit.server.account.externalids.ExternalId.toAccountExternalIds;
-import static com.google.gerrit.server.account.externalids.ExternalIds.MAX_NOTE_SZ;
-import static com.google.gerrit.server.account.externalids.ExternalIds.readNoteMap;
-import static com.google.gerrit.server.account.externalids.ExternalIds.readRevision;
+import static com.google.gerrit.server.account.externalids.ExternalIdReader.MAX_NOTE_SZ;
+import static com.google.gerrit.server.account.externalids.ExternalIdReader.readNoteMap;
+import static com.google.gerrit.server.account.externalids.ExternalIdReader.readRevision;
 import static java.nio.charset.StandardCharsets.UTF_8;
 import static java.util.stream.Collectors.toSet;
 import static org.eclipse.jgit.lib.Constants.OBJ_BLOB;
@@ -98,21 +98,27 @@
   public static class Server {
     private final GitRepositoryManager repoManager;
     private final AllUsersName allUsersName;
+    private final ExternalIds externalIds;
+    private final ExternalIdCache externalIdCache;
     private final Provider<PersonIdent> serverIdent;
 
     @Inject
     public Server(
         GitRepositoryManager repoManager,
         AllUsersName allUsersName,
+        ExternalIds externalIds,
+        ExternalIdCache externalIdCache,
         @GerritPersonIdent Provider<PersonIdent> serverIdent) {
       this.repoManager = repoManager;
       this.allUsersName = allUsersName;
+      this.externalIds = externalIds;
+      this.externalIdCache = externalIdCache;
       this.serverIdent = serverIdent;
     }
 
     public ExternalIdsUpdate create() {
       PersonIdent i = serverIdent.get();
-      return new ExternalIdsUpdate(repoManager, allUsersName, i, i);
+      return new ExternalIdsUpdate(repoManager, allUsersName, externalIds, externalIdCache, i, i);
     }
   }
 
@@ -126,6 +132,8 @@
   public static class User {
     private final GitRepositoryManager repoManager;
     private final AllUsersName allUsersName;
+    private final ExternalIds externalIds;
+    private final ExternalIdCache externalIdCache;
     private final Provider<PersonIdent> serverIdent;
     private final Provider<IdentifiedUser> identifiedUser;
 
@@ -133,10 +141,14 @@
     public User(
         GitRepositoryManager repoManager,
         AllUsersName allUsersName,
+        ExternalIds externalIds,
+        ExternalIdCache externalIdCache,
         @GerritPersonIdent Provider<PersonIdent> serverIdent,
         Provider<IdentifiedUser> identifiedUser) {
       this.repoManager = repoManager;
       this.allUsersName = allUsersName;
+      this.externalIds = externalIds;
+      this.externalIdCache = externalIdCache;
       this.serverIdent = serverIdent;
       this.identifiedUser = identifiedUser;
     }
@@ -144,7 +156,12 @@
     public ExternalIdsUpdate create() {
       PersonIdent i = serverIdent.get();
       return new ExternalIdsUpdate(
-          repoManager, allUsersName, createPersonIdent(i, identifiedUser.get()), i);
+          repoManager,
+          allUsersName,
+          externalIds,
+          externalIdCache,
+          createPersonIdent(i, identifiedUser.get()),
+          i);
     }
 
     private PersonIdent createPersonIdent(PersonIdent ident, IdentifiedUser user) {
@@ -153,8 +170,8 @@
   }
 
   @VisibleForTesting
-  public static RetryerBuilder<Void> retryerBuilder() {
-    return RetryerBuilder.<Void>newBuilder()
+  public static RetryerBuilder<ObjectId> retryerBuilder() {
+    return RetryerBuilder.<ObjectId>newBuilder()
         .retryIfException(e -> e instanceof LockFailureException)
         .withWaitStrategy(
             WaitStrategies.join(
@@ -163,34 +180,50 @@
         .withStopStrategy(StopStrategies.stopAfterDelay(10, TimeUnit.SECONDS));
   }
 
-  private static final Retryer<Void> RETRYER = retryerBuilder().build();
+  private static final Retryer<ObjectId> RETRYER = retryerBuilder().build();
 
   private final GitRepositoryManager repoManager;
   private final AllUsersName allUsersName;
+  private final ExternalIds externalIds;
+  private final ExternalIdCache externalIdCache;
   private final PersonIdent committerIdent;
   private final PersonIdent authorIdent;
   private final Runnable afterReadRevision;
-  private final Retryer<Void> retryer;
+  private final Retryer<ObjectId> retryer;
 
   private ExternalIdsUpdate(
       GitRepositoryManager repoManager,
       AllUsersName allUsersName,
+      ExternalIds externalIds,
+      ExternalIdCache externalIdCache,
       PersonIdent committerIdent,
       PersonIdent authorIdent) {
-    this(repoManager, allUsersName, committerIdent, authorIdent, Runnables.doNothing(), RETRYER);
+    this(
+        repoManager,
+        allUsersName,
+        externalIds,
+        externalIdCache,
+        committerIdent,
+        authorIdent,
+        Runnables.doNothing(),
+        RETRYER);
   }
 
   @VisibleForTesting
   public ExternalIdsUpdate(
       GitRepositoryManager repoManager,
       AllUsersName allUsersName,
+      ExternalIds externalIds,
+      ExternalIdCache externalIdCache,
       PersonIdent committerIdent,
       PersonIdent authorIdent,
       Runnable afterReadRevision,
-      Retryer<Void> retryer) {
+      Retryer<ObjectId> retryer) {
     this.repoManager = checkNotNull(repoManager, "repoManager");
     this.allUsersName = checkNotNull(allUsersName, "allUsersName");
     this.committerIdent = checkNotNull(committerIdent, "committerIdent");
+    this.externalIds = checkNotNull(externalIds, "externalIds");
+    this.externalIdCache = checkNotNull(externalIdCache, "externalIdCache");
     this.authorIdent = checkNotNull(authorIdent, "authorIdent");
     this.afterReadRevision = checkNotNull(afterReadRevision, "afterReadRevision");
     this.retryer = checkNotNull(retryer, "retryer");
@@ -216,12 +249,14 @@
       throws IOException, ConfigInvalidException, OrmException {
     db.accountExternalIds().insert(toAccountExternalIds(extIds));
 
-    updateNoteMap(
-        o -> {
-          for (ExternalId extId : extIds) {
-            insert(o.rw(), o.ins(), o.noteMap(), extId);
-          }
-        });
+    ObjectId newRev =
+        updateNoteMap(
+            o -> {
+              for (ExternalId extId : extIds) {
+                insert(o.rw(), o.ins(), o.noteMap(), extId);
+              }
+            });
+    externalIdCache.onCreate(newRev, extIds);
   }
 
   /**
@@ -243,12 +278,14 @@
       throws IOException, ConfigInvalidException, OrmException {
     db.accountExternalIds().upsert(toAccountExternalIds(extIds));
 
-    updateNoteMap(
-        o -> {
-          for (ExternalId extId : extIds) {
-            upsert(o.rw(), o.ins(), o.noteMap(), extId);
-          }
-        });
+    ObjectId newRev =
+        updateNoteMap(
+            o -> {
+              for (ExternalId extId : extIds) {
+                upsert(o.rw(), o.ins(), o.noteMap(), extId);
+              }
+            });
+    externalIdCache.onUpdate(newRev, extIds);
   }
 
   /**
@@ -273,12 +310,14 @@
       throws IOException, ConfigInvalidException, OrmException {
     db.accountExternalIds().delete(toAccountExternalIds(extIds));
 
-    updateNoteMap(
-        o -> {
-          for (ExternalId extId : extIds) {
-            remove(o.rw(), o.noteMap(), extId);
-          }
-        });
+    ObjectId newRev =
+        updateNoteMap(
+            o -> {
+              for (ExternalId extId : extIds) {
+                remove(o.rw(), o.noteMap(), extId);
+              }
+            });
+    externalIdCache.onRemove(newRev, extIds);
   }
 
   /**
@@ -302,12 +341,14 @@
       throws IOException, ConfigInvalidException, OrmException {
     db.accountExternalIds().deleteKeys(toAccountExternalIdKeys(extIdKeys));
 
-    updateNoteMap(
-        o -> {
-          for (ExternalId.Key extIdKey : extIdKeys) {
-            remove(o.rw(), o.noteMap(), extIdKey, accountId);
-          }
-        });
+    ObjectId newRev =
+        updateNoteMap(
+            o -> {
+              for (ExternalId.Key extIdKey : extIdKeys) {
+                remove(o.rw(), o.noteMap(), extIdKey, accountId);
+              }
+            });
+    externalIdCache.onRemoveByKeys(newRev, accountId, extIdKeys);
   }
 
   /**
@@ -319,18 +360,20 @@
       throws IOException, ConfigInvalidException, OrmException {
     db.accountExternalIds().deleteKeys(toAccountExternalIdKeys(extIdKeys));
 
-    updateNoteMap(
-        o -> {
-          for (ExternalId.Key extIdKey : extIdKeys) {
-            remove(o.rw(), o.noteMap(), extIdKey, null);
-          }
-        });
+    ObjectId newRev =
+        updateNoteMap(
+            o -> {
+              for (ExternalId.Key extIdKey : extIdKeys) {
+                remove(o.rw(), o.noteMap(), extIdKey, null);
+              }
+            });
+    externalIdCache.onRemoveByKeys(newRev, extIdKeys);
   }
 
   /** Deletes all external IDs of the specified account. */
   public void deleteAll(ReviewDb db, Account.Id accountId)
       throws IOException, ConfigInvalidException, OrmException {
-    delete(db, ExternalId.from(db.accountExternalIds().byAccount(accountId).toList()));
+    delete(db, externalIds.byAccount(db, accountId));
   }
 
   /**
@@ -355,16 +398,18 @@
     db.accountExternalIds().deleteKeys(toAccountExternalIdKeys(toDelete));
     db.accountExternalIds().insert(toAccountExternalIds(toAdd));
 
-    updateNoteMap(
-        o -> {
-          for (ExternalId.Key extIdKey : toDelete) {
-            remove(o.rw(), o.noteMap(), extIdKey, accountId);
-          }
+    ObjectId newRev =
+        updateNoteMap(
+            o -> {
+              for (ExternalId.Key extIdKey : toDelete) {
+                remove(o.rw(), o.noteMap(), extIdKey, accountId);
+              }
 
-          for (ExternalId extId : toAdd) {
-            insert(o.rw(), o.ins(), o.noteMap(), extId);
-          }
-        });
+              for (ExternalId extId : toAdd) {
+                insert(o.rw(), o.ins(), o.noteMap(), extId);
+              }
+            });
+    externalIdCache.onReplaceByKeys(newRev, accountId, toDelete, toAdd);
   }
 
   /**
@@ -383,16 +428,18 @@
     db.accountExternalIds().deleteKeys(toAccountExternalIdKeys(toDelete));
     db.accountExternalIds().insert(toAccountExternalIds(toAdd));
 
-    updateNoteMap(
-        o -> {
-          for (ExternalId.Key extIdKey : toDelete) {
-            remove(o.rw(), o.noteMap(), extIdKey, null);
-          }
+    ObjectId newRev =
+        updateNoteMap(
+            o -> {
+              for (ExternalId.Key extIdKey : toDelete) {
+                remove(o.rw(), o.noteMap(), extIdKey, null);
+              }
 
-          for (ExternalId extId : toAdd) {
-            insert(o.rw(), o.ins(), o.noteMap(), extId);
-          }
-        });
+              for (ExternalId extId : toAdd) {
+                insert(o.rw(), o.ins(), o.noteMap(), extId);
+              }
+            });
+    externalIdCache.onReplaceByKeys(newRev, toDelete, toAdd);
   }
 
   /**
@@ -552,12 +599,12 @@
     noteMap.remove(noteId);
   }
 
-  private void updateNoteMap(MyConsumer<OpenRepo> update)
+  private ObjectId updateNoteMap(MyConsumer<OpenRepo> update)
       throws IOException, ConfigInvalidException, OrmException {
     try (Repository repo = repoManager.openRepository(allUsersName);
         RevWalk rw = new RevWalk(repo);
         ObjectInserter ins = repo.newObjectInserter()) {
-      retryer.call(new TryNoteMapUpdate(repo, rw, ins, update));
+      return retryer.call(new TryNoteMapUpdate(repo, rw, ins, update));
     } catch (ExecutionException | RetryException e) {
       if (e.getCause() != null) {
         Throwables.throwIfInstanceOf(e.getCause(), IOException.class);
@@ -568,14 +615,14 @@
     }
   }
 
-  private void commit(
+  private ObjectId commit(
       Repository repo, RevWalk rw, ObjectInserter ins, ObjectId rev, NoteMap noteMap)
       throws IOException {
-    commit(repo, rw, ins, rev, noteMap, COMMIT_MSG, committerIdent, authorIdent);
+    return commit(repo, rw, ins, rev, noteMap, COMMIT_MSG, committerIdent, authorIdent);
   }
 
   /** Commits updates to the external IDs. */
-  public static void commit(
+  public static ObjectId commit(
       Repository repo,
       RevWalk rw,
       ObjectInserter ins,
@@ -628,6 +675,7 @@
       default:
         throw new IOException("Updating external IDs failed with " + res);
     }
+    return commitId;
   }
 
   private static ObjectId emptyTree(ObjectInserter ins) throws IOException {
@@ -654,7 +702,7 @@
     abstract NoteMap noteMap();
   }
 
-  private class TryNoteMapUpdate implements Callable<Void> {
+  private class TryNoteMapUpdate implements Callable<ObjectId> {
     private final Repository repo;
     private final RevWalk rw;
     private final ObjectInserter ins;
@@ -669,7 +717,7 @@
     }
 
     @Override
-    public Void call() throws Exception {
+    public ObjectId call() throws Exception {
       ObjectId rev = readRevision(repo);
 
       afterReadRevision.run();
@@ -677,8 +725,7 @@
       NoteMap noteMap = readNoteMap(rw, rev);
       update.accept(OpenRepo.create(repo, rw, ins, noteMap));
 
-      commit(repo, rw, ins, rev, noteMap);
-      return null;
+      return commit(repo, rw, ins, rev, noteMap);
     }
   }
 }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/api/accounts/AccountApiImpl.java b/gerrit-server/src/main/java/com/google/gerrit/server/api/accounts/AccountApiImpl.java
index 430b6b7..23c6537 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/api/accounts/AccountApiImpl.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/api/accounts/AccountApiImpl.java
@@ -485,7 +485,7 @@
   public List<AccountExternalIdInfo> getExternalIds() throws RestApiException {
     try {
       return getExternalIds.apply(account);
-    } catch (OrmException e) {
+    } catch (IOException | OrmException e) {
       throw new RestApiException("Cannot get external IDs", e);
     }
   }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/auth/ldap/LdapRealm.java b/gerrit-server/src/main/java/com/google/gerrit/server/auth/ldap/LdapRealm.java
index b589b70..9bcf3d6 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/auth/ldap/LdapRealm.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/auth/ldap/LdapRealm.java
@@ -32,6 +32,7 @@
 import com.google.gerrit.server.account.EmailExpander;
 import com.google.gerrit.server.account.GroupBackends;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.auth.AuthenticationUnavailableException;
 import com.google.gerrit.server.config.AuthConfig;
 import com.google.gerrit.server.config.GerritServerConfig;
@@ -319,21 +320,19 @@
 
   static class UserLoader extends CacheLoader<String, Optional<Account.Id>> {
     private final SchemaFactory<ReviewDb> schema;
+    private final ExternalIds externalIds;
 
     @Inject
-    UserLoader(SchemaFactory<ReviewDb> schema) {
+    UserLoader(SchemaFactory<ReviewDb> schema, ExternalIds externalIds) {
       this.schema = schema;
+      this.externalIds = externalIds;
     }
 
     @Override
     public Optional<Account.Id> load(String username) throws Exception {
       try (ReviewDb db = schema.open()) {
         return Optional.ofNullable(
-                ExternalId.from(
-                    db.accountExternalIds()
-                        .get(
-                            ExternalId.Key.create(SCHEME_GERRIT, username)
-                                .asAccountExternalIdKey())))
+                externalIds.get(db, ExternalId.Key.create(SCHEME_GERRIT, username)))
             .map(ExternalId::accountId);
       }
     }
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/config/GerritGlobalModule.java b/gerrit-server/src/main/java/com/google/gerrit/server/config/GerritGlobalModule.java
index 7b110e3..7747437 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/config/GerritGlobalModule.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/config/GerritGlobalModule.java
@@ -92,6 +92,7 @@
 import com.google.gerrit.server.account.GroupIncludeCacheImpl;
 import com.google.gerrit.server.account.GroupMembers;
 import com.google.gerrit.server.account.VersionedAuthorizedKeys;
+import com.google.gerrit.server.account.externalids.ExternalIdModule;
 import com.google.gerrit.server.api.accounts.AccountExternalIdCreator;
 import com.google.gerrit.server.auth.AuthBackend;
 import com.google.gerrit.server.auth.UniversalAuthBackend;
@@ -228,6 +229,7 @@
     install(new AccessControlModule());
     install(new CmdLineParserModule());
     install(new EmailModule());
+    install(new ExternalIdModule());
     install(new GitModule());
     install(new GroupModule());
     install(new NoteDbModule(cfg));
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/schema/SchemaVersion.java b/gerrit-server/src/main/java/com/google/gerrit/server/schema/SchemaVersion.java
index 9e8ea58..f5a4dd6 100644
--- a/gerrit-server/src/main/java/com/google/gerrit/server/schema/SchemaVersion.java
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/schema/SchemaVersion.java
@@ -35,7 +35,7 @@
 /** A version of the database schema. */
 public abstract class SchemaVersion {
   /** The current schema version. */
-  public static final Class<Schema_143> C = Schema_143.class;
+  public static final Class<Schema_144> C = Schema_144.class;
 
   public static int getBinaryVersion() {
     return guessVersion(C);
diff --git a/gerrit-server/src/main/java/com/google/gerrit/server/schema/Schema_144.java b/gerrit-server/src/main/java/com/google/gerrit/server/schema/Schema_144.java
new file mode 100644
index 0000000..70e55cf
--- /dev/null
+++ b/gerrit-server/src/main/java/com/google/gerrit/server/schema/Schema_144.java
@@ -0,0 +1,78 @@
+// Copyright (C) 2016 The Android Open Source Project
+//
+// Licensed 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 com.google.gerrit.server.schema;
+
+import com.google.gerrit.reviewdb.server.ReviewDb;
+import com.google.gerrit.server.GerritPersonIdent;
+import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIdReader;
+import com.google.gerrit.server.account.externalids.ExternalIdsUpdate;
+import com.google.gerrit.server.config.AllUsersName;
+import com.google.gerrit.server.git.GitRepositoryManager;
+import com.google.gwtorm.server.OrmException;
+import com.google.inject.Inject;
+import com.google.inject.Provider;
+import java.io.IOException;
+import java.sql.SQLException;
+import java.util.Set;
+import org.eclipse.jgit.errors.ConfigInvalidException;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectInserter;
+import org.eclipse.jgit.lib.PersonIdent;
+import org.eclipse.jgit.lib.Repository;
+import org.eclipse.jgit.notes.NoteMap;
+import org.eclipse.jgit.revwalk.RevWalk;
+
+public class Schema_144 extends SchemaVersion {
+  private static final String COMMIT_MSG = "Import external IDs from ReviewDb";
+
+  private final GitRepositoryManager repoManager;
+  private final AllUsersName allUsersName;
+  private final PersonIdent serverIdent;
+
+  @Inject
+  Schema_144(
+      Provider<Schema_143> prior,
+      GitRepositoryManager repoManager,
+      AllUsersName allUsersName,
+      @GerritPersonIdent PersonIdent serverIdent) {
+    super(prior);
+    this.repoManager = repoManager;
+    this.allUsersName = allUsersName;
+    this.serverIdent = serverIdent;
+  }
+
+  @Override
+  protected void migrateData(ReviewDb db, UpdateUI ui) throws OrmException, SQLException {
+    Set<ExternalId> toAdd = ExternalId.from(db.accountExternalIds().all().toList());
+    try {
+      try (Repository repo = repoManager.openRepository(allUsersName);
+          RevWalk rw = new RevWalk(repo);
+          ObjectInserter ins = repo.newObjectInserter()) {
+        ObjectId rev = ExternalIdReader.readRevision(repo);
+
+        NoteMap noteMap = ExternalIdReader.readNoteMap(rw, rev);
+
+        for (ExternalId extId : toAdd) {
+          ExternalIdsUpdate.upsert(rw, ins, noteMap, extId);
+        }
+
+        ExternalIdsUpdate.commit(repo, rw, ins, rev, noteMap, COMMIT_MSG, serverIdent, serverIdent);
+      }
+    } catch (IOException | ConfigInvalidException e) {
+      throw new OrmException("Failed to migrate external IDs to NoteDb", e);
+    }
+  }
+}
diff --git a/gerrit-sshd/src/main/java/com/google/gerrit/sshd/SshKeyCacheImpl.java b/gerrit-sshd/src/main/java/com/google/gerrit/sshd/SshKeyCacheImpl.java
index 25cd940..a3cf7c1 100644
--- a/gerrit-sshd/src/main/java/com/google/gerrit/sshd/SshKeyCacheImpl.java
+++ b/gerrit-sshd/src/main/java/com/google/gerrit/sshd/SshKeyCacheImpl.java
@@ -22,6 +22,7 @@
 import com.google.gerrit.reviewdb.server.ReviewDb;
 import com.google.gerrit.server.account.VersionedAuthorizedKeys;
 import com.google.gerrit.server.account.externalids.ExternalId;
+import com.google.gerrit.server.account.externalids.ExternalIds;
 import com.google.gerrit.server.cache.CacheModule;
 import com.google.gerrit.server.ssh.SshKeyCache;
 import com.google.gerrit.server.ssh.SshKeyCreator;
@@ -92,22 +93,23 @@
 
   static class Loader extends CacheLoader<String, Iterable<SshKeyCacheEntry>> {
     private final SchemaFactory<ReviewDb> schema;
+    private final ExternalIds externalIds;
     private final VersionedAuthorizedKeys.Accessor authorizedKeys;
 
     @Inject
-    Loader(SchemaFactory<ReviewDb> schema, VersionedAuthorizedKeys.Accessor authorizedKeys) {
+    Loader(
+        SchemaFactory<ReviewDb> schema,
+        ExternalIds externalIds,
+        VersionedAuthorizedKeys.Accessor authorizedKeys) {
       this.schema = schema;
+      this.externalIds = externalIds;
       this.authorizedKeys = authorizedKeys;
     }
 
     @Override
     public Iterable<SshKeyCacheEntry> load(String username) throws Exception {
       try (ReviewDb db = schema.open()) {
-        ExternalId user =
-            ExternalId.from(
-                db.accountExternalIds()
-                    .get(
-                        ExternalId.Key.create(SCHEME_USERNAME, username).asAccountExternalIdKey()));
+        ExternalId user = externalIds.get(db, ExternalId.Key.create(SCHEME_USERNAME, username));
         if (user == null) {
           return NO_SUCH_USER;
         }