Last I checked, and things might have changed, atuin runs a full posgresql database to store and sync the history, while mcfly is lighter, it also has a narrower feature scope.
On the client, it uses sqlite. As of recently, it also keeps an in-memory Nucleo index to make fuzzy searching much faster