diff --git a/app/assets/javascripts/editor/schema/ci.json b/app/assets/javascripts/editor/schema/ci.json
index 1fb6f606b6b865398c14ee42bd56491efdd41513..d240ad7353ab1501f9a11d6f5bf45ffedbef1a4c 100644
--- a/app/assets/javascripts/editor/schema/ci.json
+++ b/app/assets/javascripts/editor/schema/ci.json
@@ -1092,6 +1092,14 @@
             "on_failure",
             "always"
           ]
+        },
+        "fallback_keys": {
+          "type": "array",
+          "markdownDescription": "List of keys to download cache from if no cache hit occurred for key",
+          "items": {
+            "type": "string"
+          },
+          "maxItems": 5
         }
       }
     },
diff --git a/app/models/ci/build.rb b/app/models/ci/build.rb
index 5680cd2181e23ffcd1f9b4aca1c6f448de10d83d..61585de4ff70128c7a40cc6b895d37d87fd1f401 100644
--- a/app/models/ci/build.rb
+++ b/app/models/ci/build.rb
@@ -25,7 +25,8 @@ class Build < Ci::Processable
       refspecs: -> (build) { build.merge_request_ref? },
       artifacts_exclude: -> (build) { build.supports_artifacts_exclude? },
       multi_build_steps: -> (build) { build.multi_build_steps? },
-      return_exit_code: -> (build) { build.exit_codes_defined? }
+      return_exit_code: -> (build) { build.exit_codes_defined? },
+      fallback_cache_keys: -> (build) { build.fallback_cache_keys_defined? }
     }.freeze
 
     DEGRADATION_THRESHOLD_VARIABLE_NAME = 'DEGRADATION_THRESHOLD'
@@ -919,9 +920,15 @@ def services
     def cache
       cache = Array.wrap(options[:cache])
 
+      cache.each do |single_cache|
+        single_cache[:fallback_keys] = [] unless single_cache.key?(:fallback_keys)
+      end
+
       if project.jobs_cache_index
         cache = cache.map do |single_cache|
-          single_cache.merge(key: "#{single_cache[:key]}-#{project.jobs_cache_index}")
+          cache = single_cache.merge(key: "#{single_cache[:key]}-#{project.jobs_cache_index}")
+          fallback = cache.slice(:fallback_keys).transform_values { |keys| keys.map { |key| "#{key}-#{project.jobs_cache_index}" } }
+          cache.merge(fallback.compact)
         end
       end
 
@@ -930,10 +937,16 @@ def cache
       cache.map do |entry|
         type_suffix = !entry[:unprotect] && pipeline.protected_ref? ? 'protected' : 'non_protected'
 
-        entry.merge(key: "#{entry[:key]}-#{type_suffix}")
+        cache = entry.merge(key: "#{entry[:key]}-#{type_suffix}")
+        fallback = cache.slice(:fallback_keys).transform_values { |keys| keys.map { |key| "#{key}-#{type_suffix}" } }
+        cache.merge(fallback.compact)
       end
     end
 
+    def fallback_cache_keys_defined?
+      Array.wrap(options[:cache]).any? { |cache| cache[:fallback_keys].present? }
+    end
+
     def credentials
       Gitlab::Ci::Build::Credentials::Factory.new(self).create!
     end
diff --git a/doc/ci/caching/index.md b/doc/ci/caching/index.md
index b87f34aa63387cef37a48536fd1f0b792ea242c6..ff776784e73fd56629f36dba11431f0e587212bb 100644
--- a/doc/ci/caching/index.md
+++ b/doc/ci/caching/index.md
@@ -91,10 +91,37 @@ test-job:
 ```
 
 If multiple caches are combined with a fallback cache key,
-the fallback cache is fetched every time a cache is not found.
+the global fallback cache is fetched every time a cache is not found.
 
 ## Use a fallback cache key
 
+### Per-cache fallback keys
+
+> [Introduced](https://gitlab.com/gitlab-org/gitlab/-/merge_requests/110467) in GitLab 16.0
+
+Each cache entry supports up-to 5 fallback keys:
+
+```yaml
+test-job:
+  stage: build
+  cache:
+    - key: cache-$CI_COMMIT_REF_SLUG
+      fallback_keys:
+        - cache-$CI_DEFAULT_BRANCH
+        - cache-default
+      paths:
+        - vendor/ruby
+  script:
+    - bundle config set --local path 'vendor/ruby'
+    - bundle install
+    - yarn install --cache-folder .yarn-cache
+    - echo Run tests...
+```
+
+Fallback keys follows the same processing logic as `cache:key`, meaning that the fullname may include a `-$index` (based on cache clearance) and `-protected`/`-non_protected` (if cache separation enabled on protected branches) suffixes.
+
+### Global fallback key
+
 > [Introduced](https://gitlab.com/gitlab-org/gitlab-runner/-/merge_requests/1534) in GitLab Runner 13.4.
 
 You can use the `$CI_COMMIT_REF_SLUG` [predefined variable](../variables/predefined_variables.md)
@@ -120,6 +147,14 @@ job1:
       - binaries/
 ```
 
+The order of caches extraction is:
+
+1. Retrieval attempt for `cache:key`
+1. Retrieval attemps for each entry in order in `fallback_keys`
+1. Retrieval attempt for the global fallback key in `CACHE_FALLBACK_KEY`
+
+The cache extraction process stops after the first successful cache is retrieved.
+
 ## Disable cache for specific jobs
 
 If you define the cache globally, each job uses the
diff --git a/doc/ci/yaml/index.md b/doc/ci/yaml/index.md
index 49dbd08c90b3ac33b8abb483f5f8ab91b08b5cf9..ab5226c1c30306cdec4030cf8210115e308026ca 100644
--- a/doc/ci/yaml/index.md
+++ b/doc/ci/yaml/index.md
@@ -1480,6 +1480,33 @@ faster-test-job:
     - echo "Running tests..."
 ```
 
+#### `cache:fallback_keys`
+
+Use `cache:fallback_keys` to specify a list of keys to try to restore cache from
+if there is no cache found for the `cache:key`. Caches are retrieved in the order specified
+in the `fallback_keys` section.
+
+**Keyword type**: Job keyword. You can use it only as part of a job or in the
+[`default` section](#default).
+
+**Possible inputs**:
+
+- An array of cache keys
+
+**Example of `cache:fallback_keys`**:
+
+```yaml
+rspec:
+  script: rspec
+  cache:
+    key: gems-$CI_COMMIT_REF_SLUG
+    paths:
+      - rspec/
+    fallback_keys:
+      - gems
+    when: 'always'
+```
+
 ### `coverage`
 
 Use `coverage` with a custom regular expression to configure how code coverage
diff --git a/lib/api/entities/ci/job_request/cache.rb b/lib/api/entities/ci/job_request/cache.rb
index 9820719b4f03c4bd675c05b7131f68e77b9c785f..9be2b4c34ce1ae08dac2eb146c6009b17e12e98b 100644
--- a/lib/api/entities/ci/job_request/cache.rb
+++ b/lib/api/entities/ci/job_request/cache.rb
@@ -5,7 +5,7 @@ module Entities
     module Ci
       module JobRequest
         class Cache < Grape::Entity
-          expose :key, :untracked, :paths, :policy, :when
+          expose :key, :untracked, :paths, :policy, :when, :fallback_keys
         end
       end
     end
diff --git a/lib/gitlab/ci/config/entry/cache.rb b/lib/gitlab/ci/config/entry/cache.rb
index a635f4091098f2a1c7399a99a02f6512afebccc7..b3ff74c14da6016afc88cf5a6ec7423cb94b3924 100644
--- a/lib/gitlab/ci/config/entry/cache.rb
+++ b/lib/gitlab/ci/config/entry/cache.rb
@@ -9,11 +9,12 @@ class Cache < ::Gitlab::Config::Entry::Node
           include ::Gitlab::Config::Entry::Validatable
           include ::Gitlab::Config::Entry::Attributable
 
-          ALLOWED_KEYS = %i[key untracked paths when policy unprotect].freeze
+          ALLOWED_KEYS = %i[key untracked paths when policy unprotect fallback_keys].freeze
           ALLOWED_POLICY = %w[pull-push push pull].freeze
           DEFAULT_POLICY = 'pull-push'
           ALLOWED_WHEN = %w[on_success on_failure always].freeze
           DEFAULT_WHEN = 'on_success'
+          DEFAULT_FALLBACK_KEYS = [].freeze
 
           validations do
             validates :config, type: Hash, allowed_keys: ALLOWED_KEYS
@@ -27,6 +28,8 @@ class Cache < ::Gitlab::Config::Entry::Node
                 in: ALLOWED_WHEN,
                 message: "should be one of: #{ALLOWED_WHEN.join(', ')}"
               }
+
+              validates :fallback_keys, length: { maximum: 5, too_long: "has to many entries (maximum %{count})" }
             end
           end
 
@@ -42,7 +45,10 @@ class Cache < ::Gitlab::Config::Entry::Node
           entry :paths, Entry::Paths,
             description: 'Specify which paths should be cached across builds.'
 
-          attributes :policy, :when, :unprotect
+          entry :fallback_keys, ::Gitlab::Config::Entry::ArrayOfStrings,
+            description: 'List of keys to download cache from if no cache hit occurred for key'
+
+          attributes :policy, :when, :unprotect, :fallback_keys
 
           def value
             result = super
@@ -52,6 +58,7 @@ def value
             result[:policy] = policy || DEFAULT_POLICY
             # Use self.when to avoid conflict with reserved word
             result[:when] = self.when || DEFAULT_WHEN
+            result[:fallback_keys] = fallback_keys || DEFAULT_FALLBACK_KEYS
 
             result
           end
diff --git a/lib/gitlab/ci/pipeline/seed/build/cache.rb b/lib/gitlab/ci/pipeline/seed/build/cache.rb
index 409b6658cc08934c495a1bf9d75975c79deea17f..936344b9ae8f84679a252b04aa21f4696190a39d 100644
--- a/lib/gitlab/ci/pipeline/seed/build/cache.rb
+++ b/lib/gitlab/ci/pipeline/seed/build/cache.rb
@@ -16,6 +16,7 @@ def initialize(pipeline, cache, custom_key_prefix)
               @when = local_cache.delete(:when)
               @unprotect = local_cache.delete(:unprotect)
               @custom_key_prefix = custom_key_prefix
+              @fallback_keys = local_cache.delete(:fallback_keys)
 
               raise ArgumentError, "unknown cache keys: #{local_cache.keys}" if local_cache.any?
             end
@@ -27,7 +28,8 @@ def attributes
                 policy: @policy,
                 untracked: @untracked,
                 when: @when,
-                unprotect: @unprotect
+                unprotect: @unprotect,
+                fallback_keys: @fallback_keys
               }.compact
             end
 
diff --git a/spec/lib/gitlab/ci/config/entry/cache_spec.rb b/spec/lib/gitlab/ci/config/entry/cache_spec.rb
index 67252eed9380920ac5d1d6434f88de4884cbc9b6..82db116fa0dd064f8da9ec22772eed3070cac835 100644
--- a/spec/lib/gitlab/ci/config/entry/cache_spec.rb
+++ b/spec/lib/gitlab/ci/config/entry/cache_spec.rb
@@ -17,6 +17,7 @@
       let(:key) { 'some key' }
       let(:when_config) { nil }
       let(:unprotect) { false }
+      let(:fallback_keys) { [] }
 
       let(:config) do
         {
@@ -27,13 +28,22 @@
         }.tap do |config|
           config[:policy] = policy if policy
           config[:when] = when_config if when_config
+          config[:fallback_keys] = fallback_keys if fallback_keys
         end
       end
 
       describe '#value' do
         shared_examples 'hash key value' do
           it 'returns hash value' do
-            expect(entry.value).to eq(key: key, untracked: true, paths: ['some/path/'], policy: 'pull-push', when: 'on_success', unprotect: false)
+            expect(entry.value).to eq(
+              key: key,
+              untracked: true,
+              paths: ['some/path/'],
+              policy: 'pull-push',
+              when: 'on_success',
+              unprotect: false,
+              fallback_keys: []
+            )
           end
         end
 
@@ -104,6 +114,20 @@
             expect(entry.value).to include(when: 'on_success')
           end
         end
+
+        context 'with `fallback_keys`' do
+          let(:fallback_keys) { %w[key-1 key-2] }
+
+          it 'matches the list of fallback keys' do
+            expect(entry.value).to match(a_hash_including(fallback_keys: %w[key-1 key-2]))
+          end
+        end
+
+        context 'without `fallback_keys`' do
+          it 'assigns an empty list' do
+            expect(entry.value).to match(a_hash_including(fallback_keys: []))
+          end
+        end
       end
 
       describe '#valid?' do
diff --git a/spec/lib/gitlab/ci/config/entry/job_spec.rb b/spec/lib/gitlab/ci/config/entry/job_spec.rb
index a06fc2d86c7a18ef138339cff890a2c49763d81f..4be7c11fab0c69d72163e585140ca3f416779d92 100644
--- a/spec/lib/gitlab/ci/config/entry/job_spec.rb
+++ b/spec/lib/gitlab/ci/config/entry/job_spec.rb
@@ -664,7 +664,13 @@
 
       it 'overrides default config' do
         expect(entry[:image].value).to eq(name: 'some_image')
-        expect(entry[:cache].value).to eq([key: 'test', policy: 'pull-push', when: 'on_success', unprotect: false])
+        expect(entry[:cache].value).to match_array([
+          key: 'test',
+          policy: 'pull-push',
+          when: 'on_success',
+          unprotect: false,
+          fallback_keys: []
+        ])
       end
     end
 
@@ -679,7 +685,13 @@
 
       it 'uses config from default entry' do
         expect(entry[:image].value).to eq 'specified'
-        expect(entry[:cache].value).to eq([key: 'test', policy: 'pull-push', when: 'on_success', unprotect: false])
+        expect(entry[:cache].value).to match_array([
+          key: 'test',
+          policy: 'pull-push',
+          when: 'on_success',
+          unprotect: false,
+          fallback_keys: []
+        ])
       end
     end
 
diff --git a/spec/lib/gitlab/ci/config/entry/root_spec.rb b/spec/lib/gitlab/ci/config/entry/root_spec.rb
index 9722609aef6df86ae43d2c3a975f88b48d2979e5..5fac5298e8e6521a817a6988f1ef6a3263c1ef4e 100644
--- a/spec/lib/gitlab/ci/config/entry/root_spec.rb
+++ b/spec/lib/gitlab/ci/config/entry/root_spec.rb
@@ -128,7 +128,7 @@
                 services: [{ name: 'postgres:9.1' }, { name: 'mysql:5.5' }],
                 stage: 'test',
                 cache: [{ key: 'k', untracked: true, paths: ['public/'], policy: 'pull-push', when: 'on_success',
-                          unprotect: false }],
+                          unprotect: false, fallback_keys: [] }],
                 job_variables: {},
                 root_variables_inheritance: true,
                 ignore: false,
@@ -144,7 +144,7 @@
                 services: [{ name: 'postgres:9.1' }, { name: 'mysql:5.5' }],
                 stage: 'test',
                 cache: [{ key: 'k', untracked: true, paths: ['public/'], policy: 'pull-push', when: 'on_success',
-                          unprotect: false }],
+                          unprotect: false, fallback_keys: [] }],
                 job_variables: {},
                 root_variables_inheritance: true,
                 ignore: false,
@@ -161,7 +161,7 @@
                 image: { name: "image:1.0" },
                 services: [{ name: "postgres:9.1" }, { name: "mysql:5.5" }],
                 cache: [{ key: "k", untracked: true, paths: ["public/"], policy: "pull-push", when: 'on_success',
-                          unprotect: false }],
+                          unprotect: false, fallback_keys: [] }],
                 only: { refs: %w(branches tags) },
                 job_variables: { 'VAR' => { value: 'job' } },
                 root_variables_inheritance: true,
@@ -209,7 +209,7 @@
                        image: { name: 'image:1.0' },
                        services: [{ name: 'postgres:9.1' }, { name: 'mysql:5.5' }],
                        stage: 'test',
-                       cache: [{ key: 'k', untracked: true, paths: ['public/'], policy: 'pull-push', when: 'on_success', unprotect: false }],
+                       cache: [{ key: 'k', untracked: true, paths: ['public/'], policy: 'pull-push', when: 'on_success', unprotect: false, fallback_keys: [] }],
                        job_variables: {},
                        root_variables_inheritance: true,
                        ignore: false,
@@ -222,7 +222,7 @@
                          image: { name: 'image:1.0' },
                          services: [{ name: 'postgres:9.1' }, { name: 'mysql:5.5' }],
                          stage: 'test',
-                         cache: [{ key: 'k', untracked: true, paths: ['public/'], policy: 'pull-push', when: 'on_success', unprotect: false }],
+                         cache: [{ key: 'k', untracked: true, paths: ['public/'], policy: 'pull-push', when: 'on_success', unprotect: false, fallback_keys: [] }],
                          job_variables: { 'VAR' => { value: 'job' } },
                          root_variables_inheritance: true,
                          ignore: false,
@@ -277,7 +277,13 @@
 
       describe '#cache_value' do
         it 'returns correct cache definition' do
-          expect(root.cache_value).to eq([key: 'a', policy: 'pull-push', when: 'on_success', unprotect: false])
+          expect(root.cache_value).to match_array([
+            key: 'a',
+            policy: 'pull-push',
+            when: 'on_success',
+            unprotect: false,
+            fallback_keys: []
+          ])
         end
       end
     end
diff --git a/spec/lib/gitlab/ci/pipeline/seed/build/cache_spec.rb b/spec/lib/gitlab/ci/pipeline/seed/build/cache_spec.rb
index 49511e14db6fee077b205591c781365e4c376cc8..07e2d6960bfc01f0e671bb98c98489850909e968 100644
--- a/spec/lib/gitlab/ci/pipeline/seed/build/cache_spec.rb
+++ b/spec/lib/gitlab/ci/pipeline/seed/build/cache_spec.rb
@@ -220,6 +220,18 @@
       end
     end
 
+    context 'with cache:fallback_keys' do
+      let(:config) do
+        {
+          key: 'ruby-branch-key',
+          paths: ['vendor/ruby'],
+          fallback_keys: ['ruby-default']
+        }
+      end
+
+      it { is_expected.to include(config) }
+    end
+
     context 'with all cache option keys' do
       let(:config) do
         {
@@ -228,7 +240,8 @@
           untracked: true,
           policy: 'push',
           unprotect: true,
-          when: 'on_success'
+          when: 'on_success',
+          fallback_keys: ['default-ruby']
         }
       end
 
diff --git a/spec/lib/gitlab/ci/yaml_processor_spec.rb b/spec/lib/gitlab/ci/yaml_processor_spec.rb
index f8c2889798fde65f96be15d7ff79ac0894e2cdf2..2c020e76cb66ca50f739eb9494f61b50eaf7a441 100644
--- a/spec/lib/gitlab/ci/yaml_processor_spec.rb
+++ b/spec/lib/gitlab/ci/yaml_processor_spec.rb
@@ -1870,7 +1870,8 @@ module Ci
               key: 'key',
               policy: 'pull-push',
               when: 'on_success',
-              unprotect: false
+              unprotect: false,
+              fallback_keys: []
             ])
         end
 
@@ -1895,7 +1896,8 @@ module Ci
               key: { files: ['file'] },
               policy: 'pull-push',
               when: 'on_success',
-              unprotect: false
+              unprotect: false,
+              fallback_keys: []
             ])
         end
 
@@ -1922,7 +1924,8 @@ module Ci
                 key: 'keya',
                 policy: 'pull-push',
                 when: 'on_success',
-                unprotect: false
+                unprotect: false,
+                fallback_keys: []
               },
               {
                 paths: ['logs/', 'binaries/'],
@@ -1930,7 +1933,8 @@ module Ci
                 key: 'key',
                 policy: 'pull-push',
                 when: 'on_success',
-                unprotect: false
+                unprotect: false,
+                fallback_keys: []
               }
             ]
           )
@@ -1958,7 +1962,8 @@ module Ci
               key: { files: ['file'] },
               policy: 'pull-push',
               when: 'on_success',
-              unprotect: false
+              unprotect: false,
+              fallback_keys: []
             ])
         end
 
@@ -1984,7 +1989,8 @@ module Ci
               key: { files: ['file'], prefix: 'prefix' },
               policy: 'pull-push',
               when: 'on_success',
-              unprotect: false
+              unprotect: false,
+              fallback_keys: []
             ])
         end
 
@@ -2008,7 +2014,8 @@ module Ci
               key: 'local',
               policy: 'pull-push',
               when: 'on_success',
-              unprotect: false
+              unprotect: false,
+              fallback_keys: []
             ])
         end
       end
diff --git a/spec/models/ci/build_spec.rb b/spec/models/ci/build_spec.rb
index 7c32c6d74c8e178255645ab1fa77ebd00812c231..e3e78acb7e544c847ad78238be23bb5b2ee75437 100644
--- a/spec/models/ci/build_spec.rb
+++ b/spec/models/ci/build_spec.rb
@@ -1152,6 +1152,12 @@
       { cache: [{ key: "key", paths: ["public"], policy: "pull-push" }] }
     end
 
+    let(:options_with_fallback_keys) do
+      { cache: [
+        { key: "key", paths: ["public"], policy: "pull-push", fallback_keys: %w(key1 key2) }
+      ] }
+    end
+
     subject { build.cache }
 
     context 'when build has cache' do
@@ -1167,6 +1173,13 @@
           ] }
         end
 
+        let(:options_with_fallback_keys) do
+          { cache: [
+            { key: "key", paths: ["public"], policy: "pull-push", fallback_keys: %w(key3 key4) },
+            { key: "key2", paths: ["public"], policy: "pull-push", fallback_keys: %w(key5 key6) }
+          ] }
+        end
+
         before do
           allow_any_instance_of(Project).to receive(:jobs_cache_index).and_return(1)
         end
@@ -1178,8 +1191,21 @@
             allow(build.pipeline).to receive(:protected_ref?).and_return(true)
           end
 
-          it do
-            is_expected.to all(a_hash_including(key: a_string_matching(/-protected$/)))
+          context 'without the `unprotect` option' do
+            it do
+              is_expected.to all(a_hash_including(key: a_string_matching(/-protected$/)))
+            end
+
+            context 'and the caches have fallback keys' do
+              let(:options) { options_with_fallback_keys }
+
+              it do
+                is_expected.to all(a_hash_including({
+                  key: a_string_matching(/-protected$/),
+                  fallback_keys: array_including(a_string_matching(/-protected$/))
+                }))
+              end
+            end
           end
 
           context 'and the cache has the `unprotect` option' do
@@ -1193,6 +1219,20 @@
             it do
               is_expected.to all(a_hash_including(key: a_string_matching(/-non_protected$/)))
             end
+
+            context 'and the caches have fallback keys' do
+              let(:options) do
+                options_with_fallback_keys[:cache].each { |entry| entry[:unprotect] = true }
+                options_with_fallback_keys
+              end
+
+              it do
+                is_expected.to all(a_hash_including({
+                  key: a_string_matching(/-non_protected$/),
+                  fallback_keys: array_including(a_string_matching(/-non_protected$/))
+                }))
+              end
+            end
           end
         end
 
@@ -1204,6 +1244,17 @@
           it do
             is_expected.to all(a_hash_including(key: a_string_matching(/-non_protected$/)))
           end
+
+          context 'and the caches have fallback keys' do
+            let(:options) { options_with_fallback_keys }
+
+            it do
+              is_expected.to all(a_hash_including({
+                key: a_string_matching(/-non_protected$/),
+                fallback_keys: array_including(a_string_matching(/-non_protected$/))
+              }))
+            end
+          end
         end
 
         context 'when separated caches are disabled' do
@@ -1219,6 +1270,23 @@
             it 'is expected to have no type suffix' do
               is_expected.to match([a_hash_including(key: 'key-1'), a_hash_including(key: 'key2-1')])
             end
+
+            context 'and the caches have fallback keys' do
+              let(:options) { options_with_fallback_keys }
+
+              it do
+                is_expected.to match([
+                  a_hash_including({
+                    key: 'key-1',
+                    fallback_keys: %w(key3-1 key4-1)
+                  }),
+                  a_hash_including({
+                    key: 'key2-1',
+                    fallback_keys: %w(key5-1 key6-1)
+                  })
+                ])
+              end
+            end
           end
 
           context 'running on not protected ref' do
@@ -1229,6 +1297,23 @@
             it 'is expected to have no type suffix' do
               is_expected.to match([a_hash_including(key: 'key-1'), a_hash_including(key: 'key2-1')])
             end
+
+            context 'and the caches have fallback keys' do
+              let(:options) { options_with_fallback_keys }
+
+              it do
+                is_expected.to match([
+                  a_hash_including({
+                    key: 'key-1',
+                    fallback_keys: %w(key3-1 key4-1)
+                  }),
+                  a_hash_including({
+                    key: 'key2-1',
+                    fallback_keys: %w(key5-1 key6-1)
+                  })
+                ])
+              end
+            end
           end
         end
       end
@@ -1239,6 +1324,17 @@
         end
 
         it { is_expected.to be_an(Array).and all(include(key: a_string_matching(/^key-1-(?>protected|non_protected)/))) }
+
+        context 'and the cache have fallback keys' do
+          let(:options) { options_with_fallback_keys }
+
+          it do
+            is_expected.to be_an(Array).and all(include({
+              key: a_string_matching(/^key-1-(?>protected|non_protected)/),
+              fallback_keys: array_including(a_string_matching(/^key\d-1-(?>protected|non_protected)/))
+            }))
+          end
+        end
       end
 
       context 'when project does not have jobs_cache_index' do
@@ -1249,6 +1345,21 @@
         it do
           is_expected.to eq(options[:cache].map { |entry| entry.merge(key: "#{entry[:key]}-non_protected") })
         end
+
+        context 'and the cache have fallback keys' do
+          let(:options) { options_with_fallback_keys }
+
+          it do
+            is_expected.to eq(
+              options[:cache].map do |entry|
+                entry[:key] = "#{entry[:key]}-non_protected"
+                entry[:fallback_keys].map! { |key| "#{key}-non_protected" }
+
+                entry
+              end
+            )
+          end
+        end
       end
     end
 
@@ -1261,6 +1372,29 @@
     end
   end
 
+  describe '#fallback_cache_keys_defined?' do
+    subject { build }
+
+    it 'returns false when fallback keys are not defined' do
+      expect(subject.fallback_cache_keys_defined?).to be false
+    end
+
+    context "with fallbacks keys" do
+      before do
+        allow(build).to receive(:options).and_return({
+          cache: [{
+            key: "key1",
+            fallback_keys: %w(key2)
+          }]
+        })
+      end
+
+      it 'returns true when fallback keys are defined' do
+        expect(subject.fallback_cache_keys_defined?).to be true
+      end
+    end
+  end
+
   describe '#triggered_by?' do
     subject { build.triggered_by?(user) }
 
diff --git a/spec/requests/api/ci/runner/jobs_request_post_spec.rb b/spec/requests/api/ci/runner/jobs_request_post_spec.rb
index 39b8b4890192e3034d3d75eaf5d4f0e8a2564097..0164eda76808ea5994b2620d32bc403c3a7cb43e 100644
--- a/spec/requests/api/ci/runner/jobs_request_post_spec.rb
+++ b/spec/requests/api/ci/runner/jobs_request_post_spec.rb
@@ -230,11 +230,14 @@
           end
 
           let(:expected_cache) do
-            [{ 'key' => a_string_matching(/^cache_key-(?>protected|non_protected)$/),
-               'untracked' => false,
-               'paths' => ['vendor/*'],
-               'policy' => 'pull-push',
-               'when' => 'on_success' }]
+            [{
+              'key' => a_string_matching(/^cache_key-(?>protected|non_protected)$/),
+              'untracked' => false,
+              'paths' => ['vendor/*'],
+              'policy' => 'pull-push',
+              'when' => 'on_success',
+              'fallback_keys' => []
+            }]
           end
 
           let(:expected_features) do
diff --git a/spec/services/ci/create_pipeline_service/cache_spec.rb b/spec/services/ci/create_pipeline_service/cache_spec.rb
index e8d9cec6695ff00b9c7ed62067d7d7f3d5218a8b..2a65f92bfd66c66f67df1ac7f72787f6c418fa9b 100644
--- a/spec/services/ci/create_pipeline_service/cache_spec.rb
+++ b/spec/services/ci/create_pipeline_service/cache_spec.rb
@@ -39,7 +39,8 @@
           policy: 'pull-push',
           untracked: true,
           unprotect: false,
-          when: 'on_success'
+          when: 'on_success',
+          fallback_keys: []
         }
 
         expect(pipeline).to be_persisted
@@ -72,7 +73,8 @@
             paths: ['logs/'],
             policy: 'pull-push',
             when: 'on_success',
-            unprotect: false
+            unprotect: false,
+            fallback_keys: []
           }
 
           expect(pipeline).to be_persisted
@@ -89,7 +91,8 @@
             paths: ['logs/'],
             policy: 'pull-push',
             when: 'on_success',
-            unprotect: false
+            unprotect: false,
+            fallback_keys: []
           }
 
           expect(pipeline).to be_persisted
@@ -123,7 +126,8 @@
             paths: ['logs/'],
             policy: 'pull-push',
             when: 'on_success',
-            unprotect: false
+            unprotect: false,
+            fallback_keys: []
           }
 
           expect(pipeline).to be_persisted
@@ -140,7 +144,8 @@
             paths: ['logs/'],
             policy: 'pull-push',
             when: 'on_success',
-            unprotect: false
+            unprotect: false,
+            fallback_keys: []
           }
 
           expect(pipeline).to be_persisted