diff --git a/java/com/google/gerrit/lucene/LuceneChangeIndex.java b/java/com/google/gerrit/lucene/LuceneChangeIndex.java
index 032eb01..821719f 100644
--- a/java/com/google/gerrit/lucene/LuceneChangeIndex.java
+++ b/java/com/google/gerrit/lucene/LuceneChangeIndex.java
@@ -131,7 +131,7 @@
   */
 
   static Term idTerm(ChangeData cd) {
-    return idTerm(cd.getId());
+    return idTerm(cd.getVirtualId());
   }
 
   static Term idTerm(Change.Id id) {
diff --git a/java/com/google/gerrit/server/config/GerritImportedServerIdsProvider.java b/java/com/google/gerrit/server/config/GerritImportedServerIdsProvider.java
index f3f7645..2a74833 100644
--- a/java/com/google/gerrit/server/config/GerritImportedServerIdsProvider.java
+++ b/java/com/google/gerrit/server/config/GerritImportedServerIdsProvider.java
@@ -14,24 +14,24 @@
 
 package com.google.gerrit.server.config;
 
-import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableList;
 import com.google.inject.Inject;
 import com.google.inject.Provider;
 import org.eclipse.jgit.lib.Config;
 
-public class GerritImportedServerIdsProvider implements Provider<ImmutableSet<String>> {
+public class GerritImportedServerIdsProvider implements Provider<ImmutableList<String>> {
   public static final String SECTION = "gerrit";
   public static final String KEY = "importedServerId";
 
-  private final ImmutableSet<String> importedIds;
+  private final ImmutableList<String> importedIds;
 
   @Inject
   public GerritImportedServerIdsProvider(@GerritServerConfig Config cfg) {
-    importedIds = ImmutableSet.copyOf(cfg.getStringList(SECTION, null, KEY));
+    importedIds = ImmutableList.copyOf(cfg.getStringList(SECTION, null, KEY));
   }
 
   @Override
-  public ImmutableSet<String> get() {
+  public ImmutableList<String> get() {
     return importedIds;
   }
 }
diff --git a/java/com/google/gerrit/server/index/change/ChangeField.java b/java/com/google/gerrit/server/index/change/ChangeField.java
index 0e066d6..f1b0b96 100644
--- a/java/com/google/gerrit/server/index/change/ChangeField.java
+++ b/java/com/google/gerrit/server/index/change/ChangeField.java
@@ -128,7 +128,7 @@
   // TODO: Rename LEGACY_ID to NUMERIC_ID
   /** Legacy change ID. */
   public static final FieldDef<ChangeData, String> LEGACY_ID_STR =
-      exact("legacy_id_str").stored().build(cd -> String.valueOf(cd.getId().get()));
+      exact("legacy_id_str").stored().build(cd -> String.valueOf(cd.getVirtualId().get()));
 
   /** Newer style Change-Id key. */
   public static final FieldDef<ChangeData, String> ID =
diff --git a/java/com/google/gerrit/server/notedb/AbstractChangeNotes.java b/java/com/google/gerrit/server/notedb/AbstractChangeNotes.java
index 3757244..93f29f6 100644
--- a/java/com/google/gerrit/server/notedb/AbstractChangeNotes.java
+++ b/java/com/google/gerrit/server/notedb/AbstractChangeNotes.java
@@ -17,7 +17,7 @@
 import static java.util.Objects.requireNonNull;
 
 import com.google.common.annotations.VisibleForTesting;
-import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableList;
 import com.google.gerrit.common.Nullable;
 import com.google.gerrit.common.UsedAt;
 import com.google.gerrit.entities.Change;
@@ -53,7 +53,7 @@
     public final AllUsersName allUsers;
     public final NoteDbMetrics metrics;
     public final String serverId;
-    public final ImmutableSet<String> importedServerIds;
+    public final ImmutableList<String> importedServerIds;
 
     // Providers required to avoid dependency cycles.
 
@@ -68,7 +68,7 @@
         NoteDbMetrics metrics,
         Provider<ChangeNotesCache> cache,
         @GerritServerId String serverId,
-        @GerritImportedServerIds ImmutableSet<String> importedServerIds) {
+        @GerritImportedServerIds ImmutableList<String> importedServerIds) {
       this.failOnLoadForTest = new AtomicBoolean();
       this.repoManager = repoManager;
       this.allUsers = allUsers;
diff --git a/java/com/google/gerrit/server/query/change/ChangeData.java b/java/com/google/gerrit/server/query/change/ChangeData.java
index 1349523..8ab9786 100644
--- a/java/com/google/gerrit/server/query/change/ChangeData.java
+++ b/java/com/google/gerrit/server/query/change/ChangeData.java
@@ -74,6 +74,7 @@
 import com.google.gerrit.server.change.MergeabilityCache;
 import com.google.gerrit.server.change.PureRevert;
 import com.google.gerrit.server.config.AllUsersName;
+import com.google.gerrit.server.config.GerritServerId;
 import com.google.gerrit.server.config.TrackingFooters;
 import com.google.gerrit.server.git.GitRepositoryManager;
 import com.google.gerrit.server.git.MergeUtilFactory;
@@ -262,15 +263,65 @@
    * <p>Attempting to lazy load data will fail with NPEs. Callers may consider manually setting
    * fields that can be set.
    *
+   * @param project project name
    * @param id change ID
+   * @param currentPatchSetId current patchset number
+   * @param commitId commit SHA1 of the current patchset
    * @return instance for testing.
    */
   public static ChangeData createForTest(
       Project.NameKey project, Change.Id id, int currentPatchSetId, ObjectId commitId) {
+    return createForTest(project, id, currentPatchSetId, commitId, null, null, null);
+  }
+
+  /**
+   * Create an instance for testing only.
+   *
+   * <p>Attempting to lazy load data will fail with NPEs. Callers may consider manually setting
+   * fields that can be set.
+   *
+   * @param project project name
+   * @param id change ID
+   * @param currentPatchSetId current patchset number
+   * @param commitId commit SHA1 of the current patchset
+   * @param serverId Gerrit server id
+   * @param virtualIdAlgo algorithm for virtualising the Change number
+   * @param changeNotes notes associated with the Change
+   * @return instance for testing.
+   */
+  public static ChangeData createForTest(
+      Project.NameKey project,
+      Change.Id id,
+      int currentPatchSetId,
+      ObjectId commitId,
+      @Nullable String serverId,
+      @Nullable ChangeNumberVirtualIdAlgorithm virtualIdAlgo,
+      @Nullable ChangeNotes changeNotes) {
     ChangeData cd =
         new ChangeData(
-            null, null, null, null, null, null, null, null, null, null, null, null, null, null,
-            null, null, null, project, id, null, null);
+            null,
+            null,
+            null,
+            null,
+            null,
+            null,
+            null,
+            null,
+            null,
+            null,
+            null,
+            null,
+            null,
+            null,
+            null,
+            null,
+            null,
+            serverId,
+            virtualIdAlgo,
+            project,
+            id,
+            null,
+            changeNotes);
     cd.currentPatchSet =
         PatchSet.builder()
             .id(PatchSet.id(id, currentPatchSetId))
@@ -361,6 +412,9 @@
   private Optional<Instant> mergedOn;
   private ImmutableSetMultimap<NameKey, RefState> refStates;
   private ImmutableList<byte[]> refStatePatterns;
+  private String gerritServerId;
+  private String changeServerId;
+  private ChangeNumberVirtualIdAlgorithm virtualIdFunc;
 
   @Inject
   private ChangeData(
@@ -381,6 +435,8 @@
       SubmitRequirementsEvaluator submitRequirementsEvaluator,
       SubmitRequirementsUtil submitRequirementsUtil,
       SubmitRuleEvaluator.Factory submitRuleEvaluatorFactory,
+      @GerritServerId String gerritServerId,
+      ChangeNumberVirtualIdAlgorithm virtualIdFunc,
       @Assisted Project.NameKey project,
       @Assisted Change.Id id,
       @Assisted @Nullable Change change,
@@ -408,6 +464,10 @@
 
     this.change = change;
     this.notes = notes;
+
+    this.changeServerId = notes == null ? null : notes.getServerId();
+    this.gerritServerId = gerritServerId;
+    this.virtualIdFunc = virtualIdFunc;
   }
 
   /**
@@ -528,6 +588,14 @@
     return legacyId;
   }
 
+  public Change.Id getVirtualId() {
+    if (virtualIdFunc == null || changeServerId == null || changeServerId.equals(gerritServerId)) {
+      return legacyId;
+    }
+
+    return Change.id(virtualIdFunc.apply(changeServerId, legacyId.get()));
+  }
+
   public Project.NameKey project() {
     return project;
   }
@@ -558,6 +626,7 @@
       throw new StorageException("Unable to load change " + legacyId, e);
     }
     change = notes.getChange();
+    changeServerId = notes.getServerId();
     setPatchSets(null);
     return change;
   }
diff --git a/java/com/google/gerrit/server/query/change/ChangeNumberBitmapMaskAlgorithm.java b/java/com/google/gerrit/server/query/change/ChangeNumberBitmapMaskAlgorithm.java
new file mode 100644
index 0000000..726a376
--- /dev/null
+++ b/java/com/google/gerrit/server/query/change/ChangeNumberBitmapMaskAlgorithm.java
@@ -0,0 +1,76 @@
+// Copyright (C) 2022 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.query.change;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
+import com.google.gerrit.server.config.GerritImportedServerIds;
+import com.google.inject.Inject;
+import com.google.inject.ProvisionException;
+import com.google.inject.Singleton;
+
+/**
+ * Dictionary-based encoding algorithm for combining a serverId/legacyChangeNum into a virtual
+ * numeric id
+ *
+ * <p>TODO: To be reverted on master and stable-3.8
+ */
+@Singleton
+public class ChangeNumberBitmapMaskAlgorithm implements ChangeNumberVirtualIdAlgorithm {
+  /*
+   * Bit-wise masks for representing the Change's VirtualId as combination of ServerId + ChangeNum:
+   */
+  private static final int CHANGE_NUM_BIT_LEN = 28; // Allows up to 268M changes
+  private static final int LEGACY_ID_BIT_MASK = (1 << CHANGE_NUM_BIT_LEN) - 1;
+  private static final int SERVER_ID_BIT_LEN =
+      Integer.BYTES * 8 - CHANGE_NUM_BIT_LEN; // Allows up to 64 ServerIds
+
+  private final ImmutableMap<String, Integer> serverIdCodes;
+
+  @Inject
+  public ChangeNumberBitmapMaskAlgorithm(
+      @GerritImportedServerIds ImmutableList<String> importedServerIds) {
+    if (importedServerIds.size() >= 1 << SERVER_ID_BIT_LEN) {
+      throw new ProvisionException(
+          String.format(
+              "Too many imported GerritServerIds (%d) to fit into the Change virtual id",
+              importedServerIds.size()));
+    }
+    ImmutableMap.Builder<String, Integer> serverIdCodesBuilder = new ImmutableMap.Builder<>();
+    for (int i = 0; i < importedServerIds.size(); i++) {
+      serverIdCodesBuilder.put(importedServerIds.get(i), i + 1);
+    }
+
+    serverIdCodes = serverIdCodesBuilder.build();
+  }
+
+  @Override
+  public int apply(String changeServerId, int changeNum) {
+    if ((changeNum & LEGACY_ID_BIT_MASK) != changeNum) {
+      throw new IllegalArgumentException(
+          String.format(
+              "Change number %d is too large to be converted into a virtual id", changeNum));
+    }
+
+    Integer encodedServerId = serverIdCodes.get(changeServerId);
+    if (encodedServerId == null) {
+      throw new IllegalArgumentException(
+          String.format("ServerId %s is not part of the GerritImportedServerIds", changeServerId));
+    }
+    int virtualId = (changeNum & LEGACY_ID_BIT_MASK) | (encodedServerId << CHANGE_NUM_BIT_LEN);
+
+    return virtualId;
+  }
+}
diff --git a/java/com/google/gerrit/server/query/change/ChangeNumberVirtualIdAlgorithm.java b/java/com/google/gerrit/server/query/change/ChangeNumberVirtualIdAlgorithm.java
new file mode 100644
index 0000000..ab21705
--- /dev/null
+++ b/java/com/google/gerrit/server/query/change/ChangeNumberVirtualIdAlgorithm.java
@@ -0,0 +1,35 @@
+// Copyright (C) 2022 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.query.change;
+
+import com.google.inject.ImplementedBy;
+
+/**
+ * Algorithm for encoding a serverId/legacyChangeNum into a virtual numeric id
+ *
+ * <p>TODO: To be reverted on master and stable-3.8
+ */
+@ImplementedBy(ChangeNumberBitmapMaskAlgorithm.class)
+public interface ChangeNumberVirtualIdAlgorithm {
+
+  /**
+   * Convert a serverId/legacyChangeNum tuple into a virtual numeric id
+   *
+   * @param serverId Gerrit serverId
+   * @param legacyChangeNum legacy change number
+   * @return virtual id which combines serverId and legacyChangeNum together
+   */
+  int apply(String serverId, int legacyChangeNum);
+}
diff --git a/java/com/google/gerrit/server/schema/SchemaModule.java b/java/com/google/gerrit/server/schema/SchemaModule.java
index e0e64a3..9593522 100644
--- a/java/com/google/gerrit/server/schema/SchemaModule.java
+++ b/java/com/google/gerrit/server/schema/SchemaModule.java
@@ -16,7 +16,7 @@
 
 import static com.google.inject.Scopes.SINGLETON;
 
-import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableList;
 import com.google.gerrit.extensions.config.FactoryModule;
 import com.google.gerrit.server.GerritPersonIdent;
 import com.google.gerrit.server.GerritPersonIdentProvider;
@@ -55,7 +55,7 @@
         .toProvider(GerritServerIdProvider.class)
         .in(SINGLETON);
 
-    bind(new TypeLiteral<ImmutableSet<String>>() {})
+    bind(new TypeLiteral<ImmutableList<String>>() {})
         .annotatedWith(GerritImportedServerIds.class)
         .toProvider(GerritImportedServerIdsProvider.class)
         .in(SINGLETON);
diff --git a/java/com/google/gerrit/testing/InMemoryModule.java b/java/com/google/gerrit/testing/InMemoryModule.java
index b1ab6b1..1afacab 100644
--- a/java/com/google/gerrit/testing/InMemoryModule.java
+++ b/java/com/google/gerrit/testing/InMemoryModule.java
@@ -19,7 +19,7 @@
 import static com.google.inject.Scopes.SINGLETON;
 
 import com.google.common.base.Strings;
-import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.ImmutableList;
 import com.google.common.util.concurrent.ListeningExecutorService;
 import com.google.gerrit.acceptance.testsuite.project.ProjectOperations;
 import com.google.gerrit.acceptance.testsuite.project.ProjectOperationsImpl;
@@ -315,9 +315,9 @@
   @Provides
   @Singleton
   @GerritImportedServerIds
-  public ImmutableSet<String> createImportedServerIds() {
-    ImmutableSet<String> serverIds =
-        ImmutableSet.copyOf(
+  public ImmutableList<String> createImportedServerIds() {
+    ImmutableList<String> serverIds =
+        ImmutableList.copyOf(
             cfg.getStringList(
                 GerritServerIdProvider.SECTION, null, GerritImportedServerIdsProvider.KEY));
     return serverIds;
diff --git a/javatests/com/google/gerrit/server/index/change/ChangeFieldTest.java b/javatests/com/google/gerrit/server/index/change/ChangeFieldTest.java
index 0bdf5cd..e35941c 100644
--- a/javatests/com/google/gerrit/server/index/change/ChangeFieldTest.java
+++ b/javatests/com/google/gerrit/server/index/change/ChangeFieldTest.java
@@ -157,14 +157,16 @@
   @Test
   public void tolerateNullValuesForInsertion() {
     Project.NameKey project = Project.nameKey("project");
-    ChangeData cd = ChangeData.createForTest(project, Change.id(1), 1, ObjectId.zeroId());
+    ChangeData cd =
+        ChangeData.createForTest(project, Change.id(1), 1, ObjectId.zeroId(), null, null, null);
     assertThat(ChangeField.ADDED.setIfPossible(cd, new FakeStoredValue(null))).isTrue();
   }
 
   @Test
   public void tolerateNullValuesForDeletion() {
     Project.NameKey project = Project.nameKey("project");
-    ChangeData cd = ChangeData.createForTest(project, Change.id(1), 1, ObjectId.zeroId());
+    ChangeData cd =
+        ChangeData.createForTest(project, Change.id(1), 1, ObjectId.zeroId(), null, null, null);
     assertThat(ChangeField.DELETED.setIfPossible(cd, new FakeStoredValue(null))).isTrue();
   }
 
diff --git a/javatests/com/google/gerrit/server/notedb/AbstractChangeNotesTest.java b/javatests/com/google/gerrit/server/notedb/AbstractChangeNotesTest.java
index 1b286d1..e8cc6b4 100644
--- a/javatests/com/google/gerrit/server/notedb/AbstractChangeNotesTest.java
+++ b/javatests/com/google/gerrit/server/notedb/AbstractChangeNotesTest.java
@@ -18,7 +18,6 @@
 import static java.util.concurrent.TimeUnit.SECONDS;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
 import com.google.gerrit.entities.Account;
 import com.google.gerrit.entities.Change;
 import com.google.gerrit.entities.Comment;
@@ -179,9 +178,9 @@
             install(NoteDbModule.forTest());
             bind(AllUsersName.class).toProvider(AllUsersNameProvider.class);
             bind(String.class).annotatedWith(GerritServerId.class).toInstance(serverId);
-            bind(new TypeLiteral<ImmutableSet<String>>() {})
+            bind(new TypeLiteral<ImmutableList<String>>() {})
                 .annotatedWith(GerritImportedServerIds.class)
-                .toInstance(new ImmutableSet.Builder<String>().add(importedServerIds).build());
+                .toInstance(new ImmutableList.Builder<String>().add(importedServerIds).build());
             bind(GitRepositoryManager.class).toInstance(repoManager);
             bind(ProjectCache.class).to(NullProjectCache.class);
             bind(Config.class).annotatedWith(GerritServerConfig.class).toInstance(testConfig);
diff --git a/javatests/com/google/gerrit/server/query/change/ChangeDataTest.java b/javatests/com/google/gerrit/server/query/change/ChangeDataTest.java
index e48d4af..5124021 100644
--- a/javatests/com/google/gerrit/server/query/change/ChangeDataTest.java
+++ b/javatests/com/google/gerrit/server/query/change/ChangeDataTest.java
@@ -15,18 +15,29 @@
 package com.google.gerrit.server.query.change;
 
 import static com.google.common.truth.Truth.assertThat;
+import static org.mockito.Mockito.when;
 
 import com.google.common.collect.ImmutableList;
 import com.google.gerrit.entities.Account;
 import com.google.gerrit.entities.Change;
 import com.google.gerrit.entities.PatchSet;
 import com.google.gerrit.entities.Project;
+import com.google.gerrit.server.notedb.ChangeNotes;
 import com.google.gerrit.server.util.time.TimeUtil;
 import com.google.gerrit.testing.TestChanges;
+import java.util.UUID;
 import org.eclipse.jgit.lib.ObjectId;
 import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.mockito.Mock;
+import org.mockito.junit.MockitoJUnitRunner;
 
+@RunWith(MockitoJUnitRunner.class)
 public class ChangeDataTest {
+  private static final String GERRIT_SERVER_ID = UUID.randomUUID().toString();
+
+  @Mock private ChangeNotes changeNotesMock;
+
   @Test
   public void setPatchSetsClearsCurrentPatchSet() throws Exception {
     Project.NameKey project = Project.nameKey("project");
@@ -41,6 +52,26 @@
     assertThat(curr2).isNotSameInstanceAs(curr1);
   }
 
+  @Test
+  public void getChangeVirtualIdUsingAlgorithm() throws Exception {
+    Project.NameKey project = Project.nameKey("project");
+    final int encodedChangeNum = 12345678;
+
+    when(changeNotesMock.getServerId()).thenReturn(UUID.randomUUID().toString());
+
+    ChangeData cd =
+        ChangeData.createForTest(
+            project,
+            Change.id(1),
+            1,
+            ObjectId.zeroId(),
+            GERRIT_SERVER_ID,
+            (s, c) -> encodedChangeNum,
+            changeNotesMock);
+
+    assertThat(cd.getVirtualId().get()).isEqualTo(encodedChangeNum);
+  }
+
   private static PatchSet newPatchSet(Change.Id changeId, int num) {
     return PatchSet.builder()
         .id(PatchSet.id(changeId, num))