How to run armhf executables on an arm64 system?

I have Ubuntu 16.04.2 LTS installed on an arm64 server:

# uname -a
Linux test 4.9.23-std-1 #1 SMP Mon Apr 24 13:18:14 UTC 2017 aarch64 aarch64 aarch64 GNU/Linux

I ran the following command to enable armhf package installation:

# dpkg --add-architecture armhf

I then installed the traceroute package:

# apt-get install traceroute:armhf
Reading package lists... Done
Building dependency tree
[...]
Preparing to unpack .../traceroute_1%3a2.0.21-1_armhf.deb ...
Unpacking traceroute:armhf (1:2.0.21-1) ...
Processing triggers for man-db (2.7.5-1) ...

However, I cannot launch the executable:

# traceroute
-bash: /usr/sbin/traceroute: cannot execute binary file: Exec format error

Further information:

# file /usr/bin/traceroute.db
/usr/bin/traceroute.db: ELF 32-bit LSB shared object, ARM, EABI5 version 1 (SYSV),
    dynamically linked, interpreter /lib/ld-linux-armhf.so.3, for GNU/Linux
    2.6.32, BuildID[sha1]=0ebd0553e26b163dd848c131fe8ee0a4a2409109, stripped
# ldd /usr/bin/traceroute.db
        not a dynamic executable

I also tried installing binfmt-support and confirming that the binfmt_misc module was loaded.

Isn't arm64 backwards-compatible with armhf? How can I run armhf executables on an arm64 server?

Arm32 support is optional on arm64. In practice, there is only one arm64 CPU that omits legacy arm32 instruction set support - Cavium ThunderX. From the kernel version string, it seems you are using Scaleway armv8 servers. If this is the case, you are out of luck - Scaleway armv8 servers are based on ThunderX. Use the Scaleway C1 instead, which is native arm32.