You may want to have a look at Tie::File, which has a read cache and deferred write mode. (It ties an array to lines in the file; you would want to munge it to tie a hash based on the key.) But the caching isn't going to work for you if you really need simultaneous access.

You've constrained your problem so well it becomes hard to solve except with whole-file writes on every change. About the only thing I can think of that would help would be to have a maximum record length, and pad the end of each line out to that length. Then you can update a single line on each STORE. But it makes it easy to mess yourself up when you directly edit the file.