Random 503 on creating merge requests (Gitlab::Git::CommandError (4:Deadline Exceeded))

Summary

Gitlab, upon creating a merge request, randomly generates 503s because of Gitlab::Git::CommandError (4:Deadline Exceeded).

Steps to reproduce

Try to create a merge request.

What is the current bug behavior?

Randomly, a 503 error appears after a timeout (50s).

What is the expected correct behavior?

Always create the merge request; when no error shows up, the merge request is created in a matter of seconds.

Relevant logs and/or screenshots

Gitlab::Git::CommandError (4:Deadline Exceeded):
  lib/gitlab/git/wraps_gitaly_errors.rb:13:in `rescue in wrapped_gitaly_errors'
  lib/gitlab/git/wraps_gitaly_errors.rb:6:in `wrapped_gitaly_errors'
  lib/gitlab/metrics/instrumentation.rb:161:in `block in wrapped_gitaly_errors'
  lib/gitlab/metrics/method_call.rb:36:in `measure'
  lib/gitlab/metrics/instrumentation.rb:161:in `wrapped_gitaly_errors'
  lib/gitlab/git/repository.rb:714:in `fetch_source_branch!'
  lib/gitlab/git/repository.rb:722:in `compare_source_branch'
  app/models/repository.rb:958:in `compare_source_branch'
  lib/gitlab/metrics/instrumentation.rb:161:in `block in compare_source_branch'
  lib/gitlab/metrics/method_call.rb:36:in `measure'
  lib/gitlab/metrics/instrumentation.rb:161:in `compare_source_branch'
  app/services/compare_service.rb:16:in `execute'
  app/services/merge_requests/build_service.rb:91:in `compare_branches'
  lib/gitlab/metrics/instrumentation.rb:161:in `block in compare_branches'
  lib/gitlab/metrics/method_call.rb:36:in `measure'
  lib/gitlab/metrics/instrumentation.rb:161:in `compare_branches'
  app/services/merge_requests/build_service.rb:26:in `execute'
  lib/gitlab/metrics/instrumentation.rb:161:in `block in execute'
  lib/gitlab/metrics/method_call.rb:36:in `measure'
  lib/gitlab/metrics/instrumentation.rb:161:in `execute'
  app/controllers/projects/merge_requests/creations_controller.rb:92:in `build_merge_request'
  lib/gitlab/i18n.rb:55:in `with_locale'
  lib/gitlab/i18n.rb:61:in `with_user_locale'
  app/controllers/application_controller.rb:423:in `set_locale'
  lib/gitlab/middleware/rails_queue_duration.rb:24:in `call'
  lib/gitlab/metrics/rack_middleware.rb:17:in `block in call'
  lib/gitlab/metrics/transaction.rb:55:in `run'
  lib/gitlab/metrics/rack_middleware.rb:17:in `call'
  lib/gitlab/middleware/multipart.rb:103:in `call'
  lib/gitlab/request_profiler/middleware.rb:16:in `call'
  ee/lib/gitlab/jira/middleware.rb:17:in `call'
  lib/gitlab/middleware/go.rb:20:in `call'
  lib/gitlab/etag_caching/middleware.rb:13:in `call'
  lib/gitlab/middleware/correlation_id.rb:16:in `block in call'
  lib/gitlab/correlation_id.rb:15:in `use_id'
  lib/gitlab/middleware/correlation_id.rb:15:in `call'
  lib/gitlab/middleware/read_only/controller.rb:42:in `call'
  lib/gitlab/middleware/read_only.rb:18:in `call'
  lib/gitlab/middleware/basic_health_check.rb:25:in `call'
  lib/gitlab/request_context.rb:20:in `call'
  lib/gitlab/metrics/requests_rack_middleware.rb:29:in `call'
  lib/gitlab/middleware/release_env.rb:13:in `call'

Results of GitLab environment info

System information
System:         Debian 9.8
Proxy:          no
Current User:   git
Using RVM:      no
Ruby Version:   2.5.3p105
Gem Version:    2.7.6
Bundler Version:1.16.6
Rake Version:   12.3.2
Redis Version:  3.2.12
Git Version:    2.18.1
Sidekiq Version:5.2.5
Go Version:     unknown

GitLab information
Version:        11.8.0-ee
Revision:       002a282
Directory:      /opt/gitlab/embedded/service/gitlab-rails
DB Adapter:     postgresql
DB Version:     9.6.11
URL:            https://******.com
HTTP Clone URL: https://******.com/some-group/some-project.git
SSH Clone URL:  git@******.com:some-group/some-project.git
Elasticsearch:  no
Geo:            no
Using LDAP:     no
Using Omniauth: yes
Omniauth Providers: bitbucket

GitLab Shell
Version:        8.4.4
Repository storage paths:
- default:      /var/opt/gitlab/git-data/repositories
Hooks:          /opt/gitlab/embedded/service/gitlab-shell/hooks
Git:            /opt/gitlab/embedded/bin/git

Results of GitLab application Check

Checking GitLab subtasks ...
              
Checking GitLab Shell ...
             
GitLab Shell: ... GitLab Shell version >= 8.4.4 ? ... OK (8.4.4)
Running /opt/gitlab/embedded/service/gitlab-shell/bin/check
Check GitLab API access: OK
Redis available via internal API: OK
              
Access to /var/opt/gitlab/.ssh/authorized_keys: OK
gitlab-shell self-check successful
             
Checking GitLab Shell ... Finished
                                       
Checking Gitaly ...                     
                                               
Gitaly: ... default ... OK
                                                                        
Checking Gitaly ... Finished
                                
Checking Sidekiq ...
            
Sidekiq: ... Running? ... yes        
Number of Sidekiq processes ... 1

Checking Sidekiq ... Finished
                  
Checking Incoming Email ...
                  
Incoming Email: ... Reply by email is disabled in config/gitlab.yml
                  
Checking Incoming Email ... Finished
                     
Checking LDAP ...     
                      
LDAP: ... LDAP is disabled in config/gitlab.yml
                      
Checking LDAP ... Finished
                       
Checking GitLab App ...
                  
Git configured correctly? ... yes
Database config exists? ... yes
All migrations up? ... yes                               
Database contains orphaned GroupMembers? ... no
GitLab config exists? ... yes
GitLab config up to date? ... yes      
Log directory writable? ... yes                                    
Tmp directory writable? ... yes                                
Uploads directory exists? ... yes
Uploads directory has correct permissions? ... yes
Uploads directory tmp has correct permissions? ... yes
Init script exists? ... skipped (omnibus-gitlab has no init script)
Init script up-to-date? ... skipped (omnibus-gitlab has no init script)
Projects have namespace: ...
4/1 ... yes   
3/2 ... yes          
5/3 ... yes              
9/4 ... yes                                          
6/5 ... yes                                                    
8/6 ... yes                                 
4/7 ... yes                                                            
3/8 ... yes                 
4/9 ... yes   
3/10 ... yes             
4/11 ... yes 
3/12 ... yes                                                    
4/13 ... yes                                               
3/14 ... yes               
4/15 ... yes                        
6/16 ... yes  
8/17 ... yes                                      
9/18 ... yes                      
9/19 ... yes 
9/20 ... yes                      
9/21 ... yes                           
6/22 ... yes                            
6/23 ... yes                                   
6/24 ... yes              
6/25 ... yes                                                            
3/26 ... yes                
10/27 ... yes                   
4/28 ... yes        
4/29 ... yes
10/30 ... yes                        
5/31 ... yes                     
10/32 ... yes                                               
7/33 ... yes                 
6/34 ... yes      
4/35 ... yes               
6/36 ... yes      
4/37 ... yes                                                       
6/38 ... yes      
4/39 ... yes                        
7/40 ... yes         
7/41 ... yes          
4/42 ... yes          
3/43 ... yes                                   
6/44 ... yes          
4/45 ... yes              
4/46 ... yes           
3/47 ... yes           
13/48 ... yes     
7/49 ... yes                     
7/50 ... yes                   
9/51 ... yes                                             
14/52 ... yes                                  
12/53 ... yes                
13/54 ... yes                          
13/55 ... yes                                                      
13/56 ... yes                                                  
13/57 ... yes                    
12/58 ... yes                                     
3/59 ... yes                                          
12/60 ... yes                                                      
12/61 ... yes                                                          
12/62 ... yes               
9/63 ... yes  
4/64 ... yes         
3/65 ... yes             
7/66 ... yes                                         
8/67 ... yes                                                   
11/68 ... yes                               
13/69 ... yes                                                          
3/71 ... yes                
7/72 ... yes  
6/73 ... yes             
6/74 ... yes 
6/75 ... yes                                                    
11/76 ... yes                                              
11/77 ... yes              
3/78 ... yes                        
14/79 ... yes 
11/80 ... yes                                     
9/81 ... yes                      
4/82 ... yes 
3/83 ... yes                      
9/84 ... yes                           
2/85 ... yes                            
8/86 ... yes                                   
8/87 ... yes              
8/88 ... yes                                                            
8/89 ... yes                
5/90 ... yes                    
5/91 ... yes        
5/92 ... yes
5/93 ... yes                         
5/94 ... yes                     
9/95 ... yes                    
9/96 ... yes                 
9/97 ... yes      
9/98 ... yes               
7/99 ... yes      
5/100 ... yes                                                      
7/101 ... yes     
5/102 ... yes                       
6/103 ... yes        
12/104 ... yes        
11/105 ... yes        
11/106 ... yes                                 
11/107 ... yes        
7/108 ... yes             
12/109 ... yes         
7/110 ... yes          
11/111 ... yes    
8/112 ... yes                    
8/113 ... yes                  
12/114 ... yes                                           
12/115 ... yes                                 
15/116 ... yes               
15/117 ... yes                         
15/118 ... yes                                                     
15/119 ... yes                                                 
15/120 ... yes                   
15/121 ... yes                                    
15/122 ... yes                                        
15/123 ... yes                                                     
8/124 ... yes                                                          
8/125 ... yes               
12/126 ... yes
12/127 ... yes       
12/128 ... yes           
16/129 ... yes                                       
16/130 ... yes                                                 
16/131 ... yes                              
16/132 ... yes                                                         
16/133 ... yes              
16/134 ... yes
16/135 ... yes           
5/136 ... yes
7/137 ... yes                                                   
7/138 ... yes                                              
6/139 ... yes              
7/140 ... yes                       
12/141 ... yes
12/142 ... yes                                    
5/143 ... yes                     
4/145 ... yes
Redis version >= 2.8.0? ... yes   
Ruby version >= 2.3.5 ? ... yes (2.5.3)
Git version >= 2.18.0 ? ... yes (2.18.1)
Git user has default SSH configuration? ... yes
Active users: ... 12      
Elasticsearch version 5.6 - 6.x? ... skipped (elasticsearch is disabled)
                            
Checking GitLab App ... Finished
                    
            
Checking GitLab subtasks ... Finished

What I already tried

Backuping the project before deleting and restoring it from backup; running housekeeping, both before and after restoring it. This did not change the problem; it can be circumvented, though, by retrying to create the merge request. Currently, retrying does not bring up the error again.