Installing on fresh debian 8 fails on 'Setting up docker-engine (1.9.1-0~jessie)'

I’m trying to install docker-engine on a fresh debian 8 (jessie). I followed the instructions listed here.
Unfortunately, docker-engine fails to install using apt, and after having wasted so many hours trying to solve this I have absolutely no idea what to do next. I also tried to install version 1.9.0-0~jessie, but this generates the same errors.

kernel version: 3.16.0-4-amd64

This is what happens when I try to install:

berten@seven:~$ sudo apt-get install docker-engine
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following extra packages will be installed:
  aufs-tools cgroupfs-mount git git-man libapparmor1 liberror-perl libnih-dbus1 libnih1 makedev mountall patch
  plymouth
Suggested packages:
  git-daemon-run git-daemon-sysvinit git-doc git-el git-email git-gui gitk gitweb git-arch git-cvs git-mediawiki
  git-svn ed diffutils-doc desktop-base plymouth-themes
The following NEW packages will be installed:
  aufs-tools cgroupfs-mount docker-engine git git-man libapparmor1 liberror-perl libnih-dbus1 libnih1 makedev
  mountall patch plymouth
0 upgraded, 13 newly installed, 0 to remove and 3 not upgraded.
Need to get 13.0 MB of archives.
After this operation, 62.6 MB of additional disk space will be used.
Do you want to continue? [Y/n] 
Get:1 http://ftp.belnet.be/debian/ jessie/main makedev all 2.3.1-93 [42.6 kB]
Get:2 http://ftp.belnet.be/debian/ jessie/main plymouth amd64 0.9.0-9 [189 kB]
Get:3 https://apt.dockerproject.org/repo/ debian-jessie/main docker-engine amd64 1.9.1-0~jessie [7,344 kB]
Get:4 http://ftp.belnet.be/debian/ jessie/main libnih1 amd64 1.0.3-4.3 [127 kB]
Get:5 http://ftp.belnet.be/debian/ jessie/main libnih-dbus1 amd64 1.0.3-4.3 [97.1 kB]
Get:6 http://ftp.belnet.be/debian/ jessie/main mountall amd64 2.54 [68.3 kB]
Get:7 http://ftp.belnet.be/debian/ jessie/main patch amd64 2.7.5-1 [109 kB]
Get:8 http://ftp.belnet.be/debian/ jessie/main aufs-tools amd64 1:3.2+20130722-1.1 [92.9 kB]
Get:9 http://ftp.belnet.be/debian/ jessie/main cgroupfs-mount all 1.1 [4,572 B]
Get:10 http://ftp.belnet.be/debian/ jessie/main liberror-perl all 0.17-1.1 [22.4 kB]
Get:11 http://ftp.belnet.be/debian/ jessie/main git-man all 1:2.1.4-2.1 [1,266 kB]
Get:12 http://ftp.belnet.be/debian/ jessie/main git amd64 1:2.1.4-2.1 [3,624 kB]
Get:13 http://ftp.belnet.be/debian/ jessie/main libapparmor1 amd64 2.9.0-3 [60.3 kB]
Fetched 13.0 MB in 1s (7,787 kB/s)        
Selecting previously unselected package makedev.
(Reading database ... 86075 files and directories currently installed.)
Preparing to unpack .../makedev_2.3.1-93_all.deb ...
Unpacking makedev (2.3.1-93) ...
Selecting previously unselected package plymouth.
Preparing to unpack .../plymouth_0.9.0-9_amd64.deb ...
Unpacking plymouth (0.9.0-9) ...
Selecting previously unselected package libnih1.
Preparing to unpack .../libnih1_1.0.3-4.3_amd64.deb ...
Unpacking libnih1 (1.0.3-4.3) ...
Selecting previously unselected package libnih-dbus1.
Preparing to unpack .../libnih-dbus1_1.0.3-4.3_amd64.deb ...
Unpacking libnih-dbus1 (1.0.3-4.3) ...
Selecting previously unselected package mountall.
Preparing to unpack .../mountall_2.54_amd64.deb ...
Unpacking mountall (2.54) ...
Selecting previously unselected package patch.
Preparing to unpack .../patch_2.7.5-1_amd64.deb ...
Unpacking patch (2.7.5-1) ...
Selecting previously unselected package aufs-tools.
Preparing to unpack .../aufs-tools_1%3a3.2+20130722-1.1_amd64.deb ...
Unpacking aufs-tools (1:3.2+20130722-1.1) ...
Selecting previously unselected package cgroupfs-mount.
Preparing to unpack .../cgroupfs-mount_1.1_all.deb ...
Unpacking cgroupfs-mount (1.1) ...
Selecting previously unselected package liberror-perl.
Preparing to unpack .../liberror-perl_0.17-1.1_all.deb ...
Unpacking liberror-perl (0.17-1.1) ...
Selecting previously unselected package git-man.
Preparing to unpack .../git-man_1%3a2.1.4-2.1_all.deb ...
Unpacking git-man (1:2.1.4-2.1) ...
Selecting previously unselected package git.
Preparing to unpack .../git_1%3a2.1.4-2.1_amd64.deb ...
Unpacking git (1:2.1.4-2.1) ...
Selecting previously unselected package libapparmor1:amd64.
Preparing to unpack .../libapparmor1_2.9.0-3_amd64.deb ...
Unpacking libapparmor1:amd64 (2.9.0-3) ...
Selecting previously unselected package docker-engine.
Preparing to unpack .../docker-engine_1.9.1-0~jessie_amd64.deb ...
Unpacking docker-engine (1.9.1-0~jessie) ...
Processing triggers for man-db (2.7.0.2-5) ...
Processing triggers for systemd (215-17+deb8u2) ...
Processing triggers for dbus (1.8.20-0+deb8u1) ...
Setting up makedev (2.3.1-93) ...
/run/udev or .udevdb or .udev presence implies active udev.  Aborting MAKEDEV invocation.
/run/udev or .udevdb or .udev presence implies active udev.  Aborting MAKEDEV invocation.
/run/udev or .udevdb or .udev presence implies active udev.  Aborting MAKEDEV invocation.
/run/udev or .udevdb or .udev presence implies active udev.  Aborting MAKEDEV invocation.
Setting up plymouth (0.9.0-9) ...
update-initramfs: deferring update (trigger activated)
update-rc.d: warning: start and stop actions are no longer supported; falling back to defaults
update-rc.d: warning: start and stop actions are no longer supported; falling back to defaults
Setting up libnih1 (1.0.3-4.3) ...
Setting up libnih-dbus1 (1.0.3-4.3) ...
Setting up mountall (2.54) ...
Setting up patch (2.7.5-1) ...
Setting up aufs-tools (1:3.2+20130722-1.1) ...
Setting up cgroupfs-mount (1.1) ...
Setting up liberror-perl (0.17-1.1) ...
Setting up git-man (1:2.1.4-2.1) ...
Setting up git (1:2.1.4-2.1) ...
Setting up libapparmor1:amd64 (2.9.0-3) ...
Setting up docker-engine (1.9.1-0~jessie) ...
Job for docker.service failed. See 'systemctl status docker.service' and 'journalctl -xn' for details.
invoke-rc.d: initscript docker, action "start" failed.
dpkg: error processing package docker-engine (--configure):
 subprocess installed post-installation script returned error exit status 1
Processing triggers for systemd (215-17+deb8u2) ...
Processing triggers for initramfs-tools (0.120) ...
update-initramfs: Generating /boot/initrd.img-3.16.0-4-amd64
Processing triggers for libc-bin (2.19-18+deb8u1) ...
Processing triggers for dbus (1.8.20-0+deb8u1) ...
Errors were encountered while processing:
 docker-engine
E: Sub-process /usr/bin/dpkg returned an error code (1)

systemctl status docker.service

● docker.service - Docker Application Container Engine
   Loaded: loaded (/lib/systemd/system/docker.service; enabled)
   Active: failed (Result: exit-code) since Sat 2015-12-19 17:12:33 CET; 14min ago
     Docs: https://docs.docker.com
  Process: 4770 ExecStart=/usr/bin/docker daemon -H fd:// (code=exited, status=1/FAILURE)
 Main PID: 4770 (code=exited, status=1/FAILURE)

apt-cache policy docker-engine

docker-engine:
  Installed: 1.9.1-0~jessie
  Candidate: 1.9.1-0~jessie
  Version table:
     1.9.1-0~jessie 0
        500 https://apt.dockerproject.org/repo/ debian-jessie/main amd64 Packages
        100 /var/lib/dpkg/status
     1.9.0-0~jessie 0
        500 https://apt.dockerproject.org/repo/ debian-jessie/main amd64 Packages
     1.8.3-0~jessie 0
        500 https://apt.dockerproject.org/repo/ debian-jessie/main amd64 Packages
     1.8.2-0~jessie 0
        500 https://apt.dockerproject.org/repo/ debian-jessie/main amd64 Packages
     1.8.1-0~jessie 0
        500 https://apt.dockerproject.org/repo/ debian-jessie/main amd64 Packages
     1.8.0-0~jessie 0
        500 https://apt.dockerproject.org/repo/ debian-jessie/main amd64 Packages
     1.7.1-0~jessie 0
        500 https://apt.dockerproject.org/repo/ debian-jessie/main amd64 Packages
     1.7.0-0~jessie 0
        500 https://apt.dockerproject.org/repo/ debian-jessie/main amd64 Packages
     1.6.2-0~jessie 0
        500 https://apt.dockerproject.org/repo/ debian-jessie/main amd64 Packages
     1.6.1-0~jessie 0
        500 https://apt.dockerproject.org/repo/ debian-jessie/main amd64 Packages
     1.6.0-0~jessie 0
        500 https://apt.dockerproject.org/repo/ debian-jessie/main amd64 Packages
     1.5.0-0~jessie 0
        500 https://apt.dockerproject.org/repo/ debian-jessie/main amd64 Packages

Are the pre-requisites installed? For installation procedure on Debian refer
https://docs.docker.com/engine/installation/linux/debian/

I have exactly the same output. The main error being:

Errors were encountered while processing:
 docker-engine
E: Sub-process /usr/bin/dpkg returned an error code (1)

Same systemctl output with some more details:

    ● docker.service - Docker Application Container Engine
       Loaded: loaded (/lib/systemd/system/docker.service; enabled)
       Active: failed (Result: exit-code) since Fri 2016-11-04 20:30:39 HKT; 22min ago
         Docs: https://docs.docker.com
      Process: 17699 ExecStart=/usr/bin/dockerd -H fd:// (code=exited, status=1/FAILURE)
     Main PID: 17699 (code=exited, status=1/FAILURE)

    Nov 04 20:30:38 {server} dockerd[17699]: time="2016-11-04T20:30:38.225271018+08:00" level=info msg="libcontainerd: new containerd process, pid: 17703"
    Nov 04 20:30:39 {server} dockerd[17699]: time="2016-11-04T20:30:39.236643722+08:00" level=error msg="'overlay' not found as a supported filesystem on this host. Please ensure kernel is new enough and has overlay support loaded."
    Nov 04 20:30:39 {server} dockerd[17699]: time="2016-11-04T20:30:39.240827002+08:00" level=info msg="Graph migration to content-addressability took 0.00 seconds"
    Nov 04 20:30:39 {server} dockerd[17699]: time="2016-11-04T20:30:39.241598062+08:00" level=warning msg="Your kernel does not support oom control."
    Nov 04 20:30:39 {server} dockerd[17699]: time="2016-11-04T20:30:39.241615302+08:00" level=warning msg="Your kernel does not support memory swappiness."
    Nov 04 20:30:39 {server} dockerd[17699]: time="2016-11-04T20:30:39.241939806+08:00" level=warning msg="Your kernel does not support kernel memory limit."
    Nov 04 20:30:39 {server} dockerd[17699]: time="2016-11-04T20:30:39.241952220+08:00" level=warning msg="Unable to find cpu cgroup in mounts"
    Nov 04 20:30:39 {server} dockerd[17699]: time="2016-11-04T20:30:39.241995762+08:00" level=warning msg="Unable to find cpuset cgroup in mounts"
    Nov 04 20:30:39 {server} dockerd[17699]: time="2016-11-04T20:30:39.242033875+08:00" level=warning msg="mountpoint for pids not found"
    Nov 04 20:30:39 {server} dockerd[17699]: time="2016-11-04T20:30:39.242128925+08:00" level=fatal msg="Error starting daemon: Devices cgroup isn't mounted"

Any clue how to fix this?

  • Fresh install of Debian Jessie
  • Hosted VPS (VZ) with full root
  • Followed the instructions from docs.docker.com
  • A few other posts with the same problem but no workable answers (yet)
  • There is an error that the kernel is not new enough, but the system replies:
uname -r
3.16.0-042stab120.6

This is the latest kernel for the latest Debian (Jessie).