The Wikipedia Keys article shows this ancient Anglo-Viking voided key from circa 900AD:
Unlike a tumbler lock which needs cuts at exact depths on the key to align its barrels, this key looks very different. How did it work?
It looks like it might fit a padlock of a design similar to this:
The padlock is locked by inserting the shackle (u-shaped part) into the body so that the ward springs (arrowhead shaped part of the shackle) clip into it.
The key is used by inserting it into the slot of the body so that the holes in the key align with the shackle and any other pins in the lock. By sliding the key up, the ward springs are pressed down and the shackle can be removed.
The primary mechanism for this key might look something like this:
Behind that there might be a plate with a slot for the bit at the far right of the key:
A similar design: