Request times, playback limits, shuffling and the limitations of a server-client architecture

[heyhippari]

I want to make an open and archived design discussion for this, as I think it's important enough that a simple Matrix chat doesn't cut it.

PR #1008 has generated some amount of discussion both publicly and in private, in particular with regards to the imposed limit of 300 items on a request. As such, I wanted to explain the reasoning a bit more, how it also applies to the rest of the client, why it's done and why we can't really do it any other way.

Essentially, "true shuffling" is pretty much impossible in current Jellyfin and may be impossible (or very hard to do) in future Jellyfin.

The main reason why Spotify and other apps that rely on a client-server model do not do "true shuffling" is fairly simple: due to the architecture, you are limited to a set amount of data for transfers to be done quickly. This is the entire reason why websites and web apps paginate data.

Here is an example of two requests for the same data (A music library of around 4046 tracks). The first request doesn't have a limit, second one has a limit of 300 items:

Do not focus too much on the request time here, as network latency and such can very quite a bit. Instead, I would like to focus on the size of the data:

5.75MB vs 0.43MB

This might not seem like a lot, but do remember: we also run on metered and mobile connections. These usually tend to be a lot slower, and every kilobyte of data matters. And for every track you add to your library, this number grows.

This, combined with the server-side time to query items (Jellyfin, as of writing, has a rather slow database) makes one thing obvious: there has to be limits set, for pretty much every query. Otherwise, the client becomes sluggish and annoying to use (Waiting more than around half a second for playback to start is not an acceptable user experience).

Then there is the issue of "true shuffling", which was brought up during discussions about the new playback limit. Here is a thorough answer on Quora from former Spotify engineer Mattias Petter about whether Spotify's shuffle is truly random or not, and why.

Some interesting takeaways from this:

It used to be perfectly random (using the Fisher–Yates shuffle algorithm) but the problem is that to humans, truly random does not feel random, so we got tons of complaints from users about it not being random. Last year, we updated it with a new algorithm, that is intended to feel more random to a human - we outlined it in a blog post.

There is also this answer by Spotify engineer Lukáš Poláček which goes more into the probabilities:

Say you have a playlist with 1000 songs and you listen to it for about 5-6 hours every day, which should be about 100 songs a day. If you then close the application and start playing again the next morning, the shuffling is restarted ignoring what has been played the day before. If you do this every day, you get to hear 100 random songs every day and thus each song has a 10% chance of being played on a particular day.
Each song has therefore a chance of 10% times 10% = 1% of being played two days in a row. Even though you only play 10% of the playlist each day, on average you are going to hear 1000 * 1% = 10 songs two days in a row! What about the probability of a song being played three days in a row? It's 10% times 10% times 10% = 0.1% or about one in a thousand. So on average you are going to hear one song three days in a row, even though you listen to only about 10% of the playlist!

(I believe this may have changed a bit since 2015, but more on that later.)

They also link a very good article from the Spotify R&D blog, written by Lukáš Poláček: https://engineering.atspotify.com/2014/02/28/how-to-shuffle-songs/

tl;dr: Spotify used the Fischer-Yates algorithm to shuffle tracks. This is pretty much what Lodash uses (So what the current master branch of Jellyfin Vue uses, as of 2021-04-17) and, I suspect (but without proof) what the server might use).
Through user feedback, they noticed that true randomness isn't what people actually want (even though they think it is).
They eventually moved on to an algorithm based on dithering algorithms like Floyd-Steinberg. This provides an even distribution of artists and albums throughout the queue, removing the feeling of "non-random randomness" that users felt.

One caveat they mention is that restarting the app essentially re-shuffles the queue, leading to further feeling of non-randomness. I mentioned before that I had a hunch that something changed between the previously cited posts and now, and I believe it relates to that.

My guess is that Spotify stores queues on the server-side, unless the user is playing locally.

When you request playback, it opens a session with Spotify (Much like we do with Jellyfin when starting playback), but the queue is handled on Spotify's side, for the most part.
They shuffle server-side, they send you back a few items to start, and more as you go along or navigate to the queue page.

This solution would fix all our issues, since we could get the speed afforded by paginating items, while also offering longer (potentially limitless) queues, with proper shuffling.

So, here is how I see it:

• As of currently, Jellyfin doesn't support server-side queues.
• Current shuffling is "too random" for its own sake
• We need pagination of some sort to make the client actually useful

With this in mind, here is the game plan that I propose (which would involve the server team, and would likely not be ready until Jellyfin 11):

1. Introduce the limit of 300 songs now, in PR refactor(play): simplify translate items for playback #1008
   This makes the client actually usable, by keeping the "time to start" for playback low
2. Generally adopt more lazy loading around the client
   I'm thinking mainly of the library views. One downside is that this kills @ferferga dream of blazing through library pages at lightning speed. That's essentially impossible due to technical constraints (Even now, it's difficult. The only real way to achieve this is to pre-render everything into DOM, which just isn't viable).
3. Introduce pagination into the playback manager and queue view
   When reaching the last track of the queue (or scrolling down to the end of the queue), we would fetch the next 300 items in the queue.
4. Move part of the queue management server-side (kinda goes along with 3)
   The server is the one who would handle shuffling, paginating the queue, etc. We would just request a session, with an initiator item (An album, playlist, series, collection, library, etc). The server would store the queue on that playback session and we would request pages (This also fixes getting access to queues for remote devices, as well as generally unifies the way clients start playback)
5. Make a bespoke shuffling feature on the server
   Remove the use of true randomness from any shuffle operation. Queues would be shuffled as explained above (though in a way that is adapted to various media types).

This effectively fixes a bunch of issues, both with Vue and the server in general, making us pretty fast, allowing for nicer shuffling of items, unlimited queue lengths, and allowing clients to easily see what the queues for the others are, which is perfect for remote control.

[dkanada]

I think the server already tracks queues on a basic level, but it sounds like what you want already exists in a different form. Rather than track individual queue history on the server (which would impose its own problems) we should add a new sort method called "FakeRandom" or something that takes the user's play history as input. This actually sounds like the better option, because it will account for playback on different devices and thus provide even better non-random randomness.

[heyhippari]

The queue management isn't directly tied to the shuffling, but, from talks with @barronpm , we can't really properly shuffle things while paginating them.

If we shuffle "in batches", you would never get proper shuffling of the playlist, since each page would only shuffle its own content. Shuffling the whole thing, then limiting runs the problem in the other direction: you get X% chances to get the same items in a further page of the queue.

So we need a way to store the shuffled queue in its entirety, while still being able to send pages of the queue to the client. Hence using the server as a central location for managing the queues of all the clients.

We could also use a seed, but that makes it more annoying to use, in my opinion, since you would still have to send the initiator item, the filters and so on with each query for a new page. Though it is doable, I just think storing the whole queue while the session is active makes more sense.

I think the server already tracks queues on a basic level

I've seen this mentioned several time, but I have never found an endpoint that actually does this. Is there an example available?

All I can see is one related to SyncPlay, about queue another item for the group, but that doesn't really do what I'm thinking of, here.

There is something in the sessions, but it seems mostly unused and client-fed, instead of the other way around, which is what we would need for this (And I don't believe the current way is a good way, since it relies on clients reporting their own playlists, while the server should be the source of truth, imo, and provide this for all clients).

[heyhippari]

Rather than track individual queue history on the server (which would impose its own problems) we should add a new sort method called "FakeRandom" or something that takes the user's play history as input.

I also don't think the play history should have any impact on how a set of items are shuffled.