This, the Shuffle function should play every song exactly once, just in a random order. This is what cd players have been supporting since the late '80s.

It is a very simple algorithm but Spotify turned it into something complex that barely works. By default, in large playlists, it will heavily prioritize some songs while others are almost never heard. People have complained about this for years and there is an option in the settings for it now, although I am not yet sure if that setting really disables all of the “smart” algorithms Spotify has associated with shuffle.