diff --git a/changelogs/unreleased/repository-set-cache-races.yml b/changelogs/unreleased/repository-set-cache-races.yml
new file mode 100644
index 0000000000000000000000000000000000000000..e3365ab7c2c4f03728b7a9e07dc7666f53052f2b
--- /dev/null
+++ b/changelogs/unreleased/repository-set-cache-races.yml
@@ -0,0 +1,5 @@
+---
+title: Fix two data races in the branch names cache
+merge_request: 57607
+author:
+type: fixed
diff --git a/lib/gitlab/repository_cache_adapter.rb b/lib/gitlab/repository_cache_adapter.rb
index eb7c9bccf96c94a288392e326dfc53e28b0b2fe9..d0230c035cc1d72c4aa748d146c2536a45d66255 100644
--- a/lib/gitlab/repository_cache_adapter.rb
+++ b/lib/gitlab/repository_cache_adapter.rb
@@ -60,14 +60,17 @@ def cache_method_as_redis_set(name, fallback: nil)
         define_method("#{name}_include?") do |value|
           ivar = "@#{name}_include"
           memoized = instance_variable_get(ivar) || {}
+          lookup = proc { __send__(name).include?(value) } # rubocop:disable GitlabSecurity/PublicSend
 
           next memoized[value] if memoized.key?(value)
 
           memoized[value] =
-            if strong_memoized?(name) || !redis_set_cache.exist?(name)
-              __send__(name).include?(value) # rubocop:disable GitlabSecurity/PublicSend
+            if strong_memoized?(name)
+              lookup.call
             else
-              redis_set_cache.include?(name, value)
+              result, exists = redis_set_cache.try_include?(name, value)
+
+              exists ? result : lookup.call
             end
 
           instance_variable_set(ivar, memoized)[value]
diff --git a/lib/gitlab/repository_set_cache.rb b/lib/gitlab/repository_set_cache.rb
index 69c1688767c0711497086e2875c94e5c7ebec99e..def7b58a8528269e130556b3eb6c607aad082aed 100644
--- a/lib/gitlab/repository_set_cache.rb
+++ b/lib/gitlab/repository_set_cache.rb
@@ -36,11 +36,18 @@ def write(key, value)
     end
 
     def fetch(key, &block)
-      if exist?(key)
-        read(key)
-      else
-        write(key, yield)
+      full_key = cache_key(key)
+
+      smembers, exists = with do |redis|
+        redis.multi do
+          redis.smembers(full_key)
+          redis.exists(full_key)
+        end
       end
+
+      return smembers if exists
+
+      write(key, yield)
     end
   end
 end
diff --git a/lib/gitlab/set_cache.rb b/lib/gitlab/set_cache.rb
index 591265d014ed34c7bca82116af258fda47aef02c..0f2b7b194c9f517fdad7263ecac08c4fb3eb5162 100644
--- a/lib/gitlab/set_cache.rb
+++ b/lib/gitlab/set_cache.rb
@@ -51,6 +51,19 @@ def include?(key, value)
       with { |redis| redis.sismember(cache_key(key), value) }
     end
 
+    # Like include?, but also tells us if the cache was populated when it ran
+    # by returning two booleans: [member_exists, set_exists]
+    def try_include?(key, value)
+      full_key = cache_key(key)
+
+      with do |redis|
+        redis.multi do
+          redis.sismember(full_key, value)
+          redis.exists(full_key)
+        end
+      end
+    end
+
     def ttl(key)
       with { |redis| redis.ttl(cache_key(key)) }
     end
diff --git a/spec/lib/gitlab/repository_cache_adapter_spec.rb b/spec/lib/gitlab/repository_cache_adapter_spec.rb
index 625dcf115466e1a099dd73b3ca410b53f6caf1cd..d14c3f44c6fe78cd929923483b899740baec39bd 100644
--- a/spec/lib/gitlab/repository_cache_adapter_spec.rb
+++ b/spec/lib/gitlab/repository_cache_adapter_spec.rb
@@ -29,10 +29,19 @@ def full_path
 
         def project
         end
+
+        def cached_methods
+          [:letters]
+        end
+
+        def exists?
+          true
+        end
       end
     end
 
     let(:fake_repository) { klass.new }
+    let(:redis_set_cache) { fake_repository.redis_set_cache }
 
     context 'with an existing repository' do
       it 'caches the output, sorting the results' do
@@ -42,47 +51,43 @@ def project
           expect(fake_repository.letters).to eq(%w(a b c))
         end
 
-        expect(fake_repository.redis_set_cache.exist?(:letters)).to eq(true)
+        expect(redis_set_cache.exist?(:letters)).to eq(true)
         expect(fake_repository.instance_variable_get(:@letters)).to eq(%w(a b c))
       end
 
       context 'membership checks' do
         context 'when the cache key does not exist' do
           it 'calls the original method and populates the cache' do
-            expect(fake_repository.redis_set_cache.exist?(:letters)).to eq(false)
+            expect(redis_set_cache.exist?(:letters)).to eq(false)
             expect(fake_repository).to receive(:_uncached_letters).once.and_call_original
 
             # This populates the cache and memoizes the full result
             expect(fake_repository.letters_include?('a')).to eq(true)
             expect(fake_repository.letters_include?('d')).to eq(false)
-            expect(fake_repository.redis_set_cache.exist?(:letters)).to eq(true)
+            expect(redis_set_cache.exist?(:letters)).to eq(true)
           end
         end
 
         context 'when the cache key exists' do
           before do
-            fake_repository.redis_set_cache.write(:letters, %w(b a c))
+            redis_set_cache.write(:letters, %w(b a c))
           end
 
-          it 'calls #include? on the set cache' do
-            expect(fake_repository.redis_set_cache)
-              .to receive(:include?).with(:letters, 'a').and_call_original
-            expect(fake_repository.redis_set_cache)
-              .to receive(:include?).with(:letters, 'd').and_call_original
+          it 'calls #try_include? on the set cache' do
+            expect(redis_set_cache).to receive(:try_include?).with(:letters, 'a').and_call_original
+            expect(redis_set_cache).to receive(:try_include?).with(:letters, 'd').and_call_original
 
             expect(fake_repository.letters_include?('a')).to eq(true)
             expect(fake_repository.letters_include?('d')).to eq(false)
           end
 
           it 'memoizes the result' do
-            expect(fake_repository.redis_set_cache)
-              .to receive(:include?).once.and_call_original
+            expect(redis_set_cache).to receive(:try_include?).once.and_call_original
 
             expect(fake_repository.letters_include?('a')).to eq(true)
             expect(fake_repository.letters_include?('a')).to eq(true)
 
-            expect(fake_repository.redis_set_cache)
-              .to receive(:include?).once.and_call_original
+            expect(redis_set_cache).to receive(:try_include?).once.and_call_original
 
             expect(fake_repository.letters_include?('d')).to eq(false)
             expect(fake_repository.letters_include?('d')).to eq(false)
diff --git a/spec/lib/gitlab/repository_set_cache_spec.rb b/spec/lib/gitlab/repository_set_cache_spec.rb
index 07f4d7c462da4e87f967e58f5556978c9a216e8a..6bdcc5ea2b76234067aeb83c209deae0151a22cb 100644
--- a/spec/lib/gitlab/repository_set_cache_spec.rb
+++ b/spec/lib/gitlab/repository_set_cache_spec.rb
@@ -132,4 +132,15 @@
       expect(cache.include?(:foo, 'bar')).to be(false)
     end
   end
+
+  describe '#try_include?' do
+    it 'checks existence of the redis set and inclusion' do
+      expect(cache.try_include?(:foo, 'value')).to eq([false, false])
+
+      cache.write(:foo, ['value'])
+
+      expect(cache.try_include?(:foo, 'value')).to eq([true, true])
+      expect(cache.try_include?(:foo, 'bar')).to eq([false, true])
+    end
+  end
 end