Docker service not able to start anymore because of modprobe error

I had the same error today after upgrading docker-ce to version 18.09.0 on Debian 9. I can't give you a solution for that version but going back to version 18.06.1 did make it start again. For Ubuntu this should be:

sudo apt-get install docker-ce=18.06.1~ce~3-0~ubuntu

Did version 18.09.0 ever work for you? My installation crashed right after upgrading.

Edit: There is actually a report on GitHub related to this issue. https://github.com/containerd/containerd/issues/2772

It seems like the new containerd is trying to load the overlay module even when it is already loaded. The overlay module is loaded on my system but I can't find the file in /lib/modules/

Find out if you have the file (you certainly should on stock Ubuntu 16.04):

find /lib/modules -name "*overlay*"

And can you load it yourself?

# modprobe overlay
# echo $?
0

# lsmod | grep overlay
overlay                49152  0

I don't know why docker should fail to load it... but if it's smart, it won't need to load it if you loaded it already. So if you can load it yourself, try adding it to /etc/modules so it's loaded on boot (verify that with lsmod again after reboot).

echo overlay >> /etc/modules