moby: Problem with "deep" multistage builds: `layer does not exist` error

Description

We are having a problem with the multistage builds where on first run we have the layer does not exist error, but if we run the build again it works. So on a clean system (with no cache) it fails, but not on a dirty system with cache.

I have first reported this problem in issue #33974 (see comment https://github.com/moby/moby/issues/33974#issuecomment-399445187). But it looks to be distinct, so I took the advice of @thaJeztah and created a new issue.

Steps to reproduce the issue: I have setup a GitHub repo with all the code to reproduce the problem: https://github.com/jcberthon/multistage-fails

In the readme, there are the instructions (step-by-step to reproduce the bug). You can find also all Dockerfiles. The Dockerfile for which the multistage build fails is under the level3 directory.

Of course you can build every images locally (it fails at level3), or you can directly try to build level3 as I have pushed to Docker Hub the intermediate images.

Describe the results you received:

The first time one runs the above example project, he gets the following result: When building level3 it fails with the error layer does not exist (see the GitHub project above for more details).

Describe the results you expected:

When running it a second time, it works as I expect it. Albeit, it should run like that on the first try already.

Additional information you deem important (e.g. issue happens only occasionally):

The bug is triggered always on a clean system, never when running a 2nd time. So docker system prune -a helps to trigger the bug again.

Output of docker version:

Client:
 Version:      18.05.0-ce
 API version:  1.37
 Go version:   go1.9.5
 Git commit:   f150324
 Built:        Wed May  9 22:16:04 2018
 OS/Arch:      linux/amd64
 Experimental: false
 Orchestrator: swarm

Server:
 Engine:
  Version:      18.05.0-ce
  API version:  1.37 (minimum version 1.12)
  Go version:   go1.9.5
  Git commit:   f150324
  Built:        Wed May  9 22:19:55 2018
  OS/Arch:      linux/amd64
  Experimental: false

Output of docker info:

Containers: 0
 Running: 0
 Paused: 0
 Stopped: 0
Images: 0
Server Version: 18.05.0-ce
Storage Driver: btrfs
 Build Version: Btrfs v4.15.1
 Library Version: 102
Logging Driver: json-file
Cgroup Driver: cgroupfs
Plugins:
 Volume: local
 Network: bridge host macvlan null overlay
 Log: awslogs fluentd gcplogs gelf journald json-file logentries splunk syslog
Swarm: inactive
Runtimes: runc
Default Runtime: runc
Init Binary: docker-init
containerd version: 773c489c9c1b21a6d78b5c538cd395416ec50f88
runc version: 4fc53a81fb7c994640722ac585fa9ca548971871
init version: 949e6fa
Security Options:
 seccomp
  Profile: default
Kernel Version: 4.16.13-300.fc28.x86_64
Operating System: Fedora 28 (Workstation Edition)
OSType: linux
Architecture: x86_64
CPUs: 2
Total Memory: 3.852GiB
Name: spcbo-jcb-fedora.vcs.de
ID: 7ENM:NU5S:7XAB:K2MJ:CVKB:6BUO:HIMM:NW3M:QZ35:KNL6:VCOT:KBRM
Docker Root Dir: /var/lib/docker
Debug Mode (client): false
Debug Mode (server): false
Registry: https://index.docker.io/v1/
Labels:
Experimental: false
Insecure Registries:
 127.0.0.0/8
Live Restore Enabled: false

Additional environment details (AWS, VirtualBox, physical, etc.):

I have tested this behaviour on 3 different platforms:

• VM VBox: Fedora 28 (Kernel 4.16.13-300.fc28.x86_64) with Docker CE 18.05.0-ce - btrfs
• Bare metal: CentOS 7.5 (Kernel 3.10.0-862.3.2.el7.x86_64) with Docker CE 18.03.1-ce - devicemapper
• Bare metal: Ubuntu 16.04.4 (Kernel 4.13.0-45-generic) with Docker CE 18.03.1-ce - btrfs