Supporting this, I don't think protobuf is a good format for storing history files. Backward compatibility is tricky with it - I don't think the history format is going to change all that much, but I think there were changes in history of fish shell like adding time field. If the choice would be on a binary format, I would much, much, much more prefer SQLite for that. Also, B-trees are perfectly fine choice for searching history, as they make prefix searches trivial.

TOML is definitely an interesting choice if a text format is deemed necessary however. Array of tables syntax should be a fine syntax choice for storing history.