I worked at another music streaming company, we had to do the same. That was hugely frustrating, but we would get user reports of the random button being buggy

I worked at another music streaming company, we had to do the same. That was hugely frustrating, but we would get user reports of the random button being buggy when e.g. the user gets 2 tracks of the same album/artist one after the other. Of course that can happen if we truly randomize your content ! So we switched to a pseudo random algorithm that tries to have consecutive tracks from different album/artists.