Gitlab::Git::CommandError: 4:Deadline Exceeded

https://sentry.gitlap.com/gitlab/gitlabcom/issues/137616/

GRPC::DeadlineExceeded: 4:Deadline Exceeded
  lib/gitlab/gitaly_client.rb:127:in `call'
    stub(service, storage).__send__(rpc, request, kwargs) # rubocop:disable GitlabSecurity/PublicSend
  lib/gitlab/gitaly_client/repository_service.rb:74:in `has_local_branches?'
    response = GitalyClient.call(@storage, :repository_service, :has_local_branches, request, timeout: GitalyClient.fast_timeout)
  lib/gitlab/git/repository.rb:233:in `block in has_local_branches?'
    gitaly_repository_client.has_local_branches?
  lib/gitlab/gitaly_client.rb:232:in `block (2 levels) in migrate'
    yield is_enabled
  lib/gitlab/gitaly_client.rb:274:in `allow_n_plus_1_calls'
    yield
...
(248 additional frame(s) were not displayed)

Gitlab::Git::CommandError: 4:Deadline Exceeded
  lib/gitlab/git/repository.rb:1344:in `rescue in gitaly_migrate'
    raise CommandError.new(e)
  lib/gitlab/git/repository.rb:1337:in `gitaly_migrate'
    def gitaly_migrate(method, status: Gitlab::GitalyClient::MigrationStatus::OPT_IN, &block)
  lib/gitlab/git/repository.rb:231:in `has_local_branches?'
    gitaly_migrate(:has_local_branches) do |is_enabled|
  lib/gitlab/git/repository.rb:1136:in `empty?'
    !has_visible_content?
  lib/gitlab/git/remote_repository.rb:32:in `empty?'
    !@repository.exists? || @repository.empty?
...
(234 additional frame(s) were not displayed)

Gitlab::Git::CommandError: 4:Deadline Exceeded

It seems to be something new since 12 Feb - latest version deployment presumably. Created by @grzesiek