tuned fails to start with "No library named udev" error

Issue

tuned.service fails to start with error similar to:

Jan 22 08:55:16 -sdc python2: detected unhandled Python exception in '/usr/sbin/tuned'
Jan 22 08:55:17 -sdc abrt-server: Only 2253MiB is available on /var/tmp/abrt
Jan 22 08:55:17 -sdc python2: error sending data to ABRT daemon: 
Jan 22 08:55:17 -sdc tuned: Traceback (most recent call last):
Jan 22 08:55:17 -sdc tuned: File "/usr/sbin/tuned", line 68, in <module>
Jan 22 08:55:17 -sdc tuned: app = tuned.daemon.Application(args.profile, config)
Jan 22 08:55:17 -sdc tuned: File "/usr/lib/python2.7/site-packages/tuned/daemon/application.py", line 33, in __init__
Jan 22 08:55:17 -sdc tuned: hardware_inventory = hardware.Inventory(buffer_size=udev_buffer_size)
Jan 22 08:55:17 -sdc tuned: File "/usr/lib/python2.7/site-packages/tuned/hardware/inventory.py", line 19, in __init__
Jan 22 08:55:17 -sdc tuned: self._udev_context = pyudev.Context()
Jan 22 08:55:17 -sdc tuned: File "/usr/lib/python2.7/site-packages/pyudev/core.py", line 92, in __init__
Jan 22 08:55:17 -sdc tuned: self._libudev = load_udev_library()
Jan 22 08:55:17 -sdc tuned: File "/usr/lib/python2.7/site-packages/pyudev/_libudev.py", line 272, in load_udev_library
Jan 22 08:55:17 -sdc tuned: raise ImportError('No library named udev')
Jan 22 08:55:17 -sdc tuned: ImportError: No library named udev
Jan 22 08:55:17 -sdc tuned: Exception AttributeError: "'Context' object has no attribute '_libudev'" in <bound method Context.__del__ of <pyudev.core.Context object at 0x7f5534c374d0>> ignored
Jan 22 08:55:17 -sdc systemd: tuned.service: main process exited, code=exited, status=1/FAILURE
Jan 22 08:55:17 -sdc systemd: Failed to start Dynamic System Tuning Daemon.
Jan 22 08:55:17 -sdc systemd: Unit tuned.service entered failed state.
Jan 22 08:55:17 -sdc systemd: tuned.service failed.