Closes #3282. Switches to using a struct type for record keys instead of a named slice type, so the implementation is opaque and can be changed in the future.

Changelog: refactor