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;
         }