Implement a persistently ordered list of info hashes to be consumed by the index/API (for DashMap torrent repository)

[mickvandijke]

[josecelano]

Relates to: #565

The new tracker repository implementation does not keep order for torrents so the API would return random torrents. We need to keep the order in a different (new) data structure.

[mickvandijke]

I think we need to revisit if we actually need the tracker API to have the api/v1/torrents endpoint.

In the last meeting we decided that we didn't want a breaking change by merging this PR that implements the new DashMap torrent repository. As it would break the ordering of torrents, which was supposedly needed for the Torrust index when it calls this api endpoint with pagination and such.

Why do we need it

After looking into the index. I could actually not find any place where the tracker api endpoint api/v1/torrents is called. I also do not remember ever needing it when I worked on the index. I can only recall the index keeping track of its own torrents and then occasionally trying to fetch seeders/leechers information from the tracker per info hash.

Am I missing something? Do you know when the index would have to go through all the tracker torrents @josecelano ?

If the feature is not used by the tracker nor the index, shouldn't we just drop it?

How it currently works

Currently we keep all torrents in a BTreeMap, so that the torrents are ordered by key (info hash). When someone calls the get torrents api endpoint, they can specify a page limit and page number to retrieve all torrents using multiple calls.

However, even in the current implementation the torrent order is not always the same in between calls to the get torrents endpoint. If remove_peerless_torrents is enabled, empty torrents will automatically be dropped from the BTreeMap. So this will break the pagination.

How it should work

If we somehow still need this feature for anything (could actually still be useful for testing), I think we should just return the entire detailed torrents map in one go. Yes it will be a big response if the torrent map is huge, but I don't see any other way to safely return all torrents. Meaning without any missing ones. The torrent map is just too dynamic. Even without sharding.

Thoughts @josecelano @da2ce7 ?

[josecelano]

I think we need to revisit if we actually need the tracker API to have the api/v1/torrents endpoint.

In the last meeting we decided that we didn't want a breaking change by merging this PR that implements the new DashMap torrent repository. As it would break the ordering of torrents, which was supposedly needed for the Torrust index when it calls this api endpoint with pagination and such.

Why do we need it

After looking into the index. I could actually not find any place where the tracker api endpoint api/v1/torrents is called. I also do not remember ever needing it when I worked on the index. I can only recall the index keeping track of its own torrents and then occasionally trying to fetch seeders/leechers information from the tracker per info hash.

Am I missing something? Do you know when the index would have to go through all the tracker torrents @josecelano ?

If the feature is not used by the tracker nor the index, shouldn't we just drop it?

How it currently works

Currently we keep all torrents in a BTreeMap, so that the torrents are ordered by key (info hash). When someone calls the get torrents api endpoint, they can specify a page limit and page number to retrieve all torrents using multiple calls.

However, even in the current implementation the torrent order is not always the same in between calls to the get torrents endpoint. If remove_peerless_torrents is enabled, empty torrents will automatically be dropped from the BTreeMap. So this will break the pagination.

How it should work

If we somehow still need this feature for anything (could actually still be useful for testing), I think we should just return the entire detailed torrents map in one go. Yes it will be a big response if the torrent map is huge, but I don't see any other way to safely return all torrents. Meaning without any missing ones. The torrent map is just too dynamic. Even without sharding.

Thoughts @josecelano @da2ce7 ?

Hi @WarmBeer I think you are right. That endpoint is not used in the Index for the time being.
We loop over all torrents in the Index and then we use the endpoint to fetch a single torrent info. In fact, that's a process I would like to review.

However, I think it's a pretty useful endpoint for testing. I use it a lot. Besides, the API is supposed to be generic (for purposes we don't even know), not only consumed by the Index. So it should be designed to fulfill most of the requirements other users might have. And I think that's an important endpoint. I don't see any problem in returning a partial view of the data. I guess that's what always happens when you do pagination. If you want we could add a snapshot endpoint or something like that which can give you the full data, but probably that should be an asynchronous task. I mean, you have to ask for that "report" and then you receive a notification when it's ready and finally you download it.

Regarding the option remove_peerless_torrents, I would remove that option. I would always remove peerless torrents from memory. See #566 (comment). If we want to store all torrents I would do it similar way to what we do for statistics. We can use the database for that. We should keep in memory only the active torrents.

[mickvandijke]

During our last meeting we discussed a few potential solutions to solve this problem:

Return the full repository of torrents without pagination

Would just return the entire torrent repository on request.

Pros:

• Works with a sharded torrent repository implementation.
• Very easy to implement (just need to remove the pagination and limit in the resource).

Cons:

• Response can get VERY big depending on the size of the torrent repository.

Paginated and limited (current implementation)

Allows users to set a page size and page number during a request. On request it will iterate over the torrent repository and skip over x, x = pageSize * (pageNumber - 1) torrents and then return page size amount of torrents.

Pros:

• Allows for smaller responses depending on page limit.

Cons:

• Does not guarantee that the torrent pages will stay the same in between requests (the torrent repository might update).

Paginated and limited, but with a torrent repository persistency check

Works the same as above, but also returns a unique identifier on request that represents the current state of the torrent repository. The identifier would be held in a RwLock<Option<Identifier>>. It gets updated whenever a user requests the resource and the Option<Identifier> is empty. When the torrent repository state changes in a way that the pagination would be changed as well, the Some(Identifier) would be dropped (if it is not already None).

Pros:

• Allows for smaller responses depending on page limit.
• Informs the user if the torrent pages have changed.

Cons:

• The torrent pages could be changed so often that this method might not be very useful.

Paginated and limited and also persist insertion order of all torrent info hashes in a separate lock free set (the solution we settled on)

Add an additional struct that will keep of the insertion order of all torrents, even removed ones. Use a lock free set like BoxCar for this struct so that we do not force all threads to content for the same write lock after announcing new torrents. Works the same as the current paginated and limited implementation for the rest, except that the order of torrents will come from this new insertion order struct instead of the torrent repository map itself. Removed torrents will be included in the JSON response, but with their value set to null.

Pros:

• Allows for smaller responses depending on page limit.
• Guarantees that all torrent pages stay the same because it follows the insertion order of torrents.

Cons:

• Depending on the internal struct used for the lock free insertion order struct, the last few pages of torrents could change between requests. This is because in a lock free Vec, new items are put into empty spaces near the end of the vec and not perfectly in order. This may result in some empty spots that can later be filled up.
• Uses more memory.

CC @josecelano @da2ce7

[josecelano]

Hi @WarmBeer thank you for the summary. I have a question: doesn't the BoxCar solution always increase the amount of memory consumed? Shouldn't we remove the "removed" torrents from time to time?

[mickvandijke]

Hi @WarmBeer thank you for the summary. I have a question: doesn't the BoxCar solution always increase the amount of memory consumed? Shouldn't we remove the "removed" torrents from time to time?

Hi @josecelano ,

The memory will indeed always increase over time for every newly announced torrent. But we can not remove any info hash because it will change the torrent pagination.

[josecelano]

Hi @WarmBeer thank you for the summary. I have a question: doesn't the BoxCar solution always increase the amount of memory consumed? Shouldn't we remove the "removed" torrents from time to time?

Hi @josecelano ,

The memory will indeed always increase over time for every newly announced torrent. But we can not remove any info hash because it will change the torrent pagination.

:-/ am I missing something? @WarmBeer I guess we should "clean" the data structure from time to time or when we reach a size limit at least. I think it does not make sense to

• Add a configurable memory limit to the torrent repository #567

but introduce a new data structure that can grow indefinitely.

[mickvandijke]

Hi @WarmBeer thank you for the summary. I have a question: doesn't the BoxCar solution always increase the amount of memory consumed? Shouldn't we remove the "removed" torrents from time to time?

Hi @josecelano ,
The memory will indeed always increase over time for every newly announced torrent. But we can not remove any info hash because it will change the torrent pagination.

:-/ am I missing something? @WarmBeer I guess we should "clean" the data structure from time to time or when we reach a size limit at least. I think it does not make sense to

* [ ]  [Add a configurable memory limit to the torrent repository #567](https://github.com/torrust/torrust-tracker/issues/567)

but introduce a new data structure that can grow indefinitely.

Hi @josecelano ,

Cleaning this data structure would defeat the whole purpose of it. We need this to persist the order of all torrents so that we can offer torrent pagination for this API endpoint v1/torrents without the pages changing all the time.

But yeah, it is a bit cross indeed that we now introduce a new data structure that can keep growing in memory. We could write it to disk/database instead of keeping it in memory, but that will slow down the tracker as such an operation is very slow.

I'm back to thinking that we should just drop the pagination and return the entire torrent map at once 😅. Even though this can make the response very big and slow if you have millions of torrents. I see this as the only way to reliably send all torrents back to the client without sacrificing performance in the tracker.

Perhaps we should think about why people would need this endpoint so that we can think of other solutions that would fit their needs and if returning a in the worst case big and slow response is a problem for them. We already know that it is useful for testing.

Use cases

Testing

It is an easy way to test if a tracker contains all the torrents you would expect it to have.

Scraping

External services could easily scrape all torrents from the tracker. Doing it like this is not standard protocol however.

[josecelano]

Hi @WarmBeer. I think, in the end, the BoxCar vector is like a database table but in memory with all the announced torrents.

Maybe the core tracker should have its own optimized in-memory data structure and that should not be directly connected to anything to avoid performance problems.

The API could be connected only to the persisted data. We could update the database directly from services. When we receive an announce request we update the core tracker but also the DB.

If we use a data structure like this:

#329

or even event sourcing, writes should be fast. There would be only performance problems if there were a lot of request for the API. But you have the option to disable the API.

In the future the API could be a decouple app that listens to events sent by the tracker.

cc @da2ce7

[da2ce7]

@josecelano @WarmBeer
The box-car vector contains only a small amount of data per entry.

BoxCar<sync::Weak<Torrent>>

This is memory efficient.

Yes is it is a forever growing set; however only a small amount of data is kept on the stack per entry.

[josecelano]

@josecelano @WarmBeer The box-car vector contains only a small amount of data per entry.

BoxCar<sync::Weak<Torrent>>

This is memory efficient.

Yes is it is a forever growing set; however only a small amount of data is kept on the stack per entry.

Hi @WarmBeer, @da2ce7 and I were discussing in today and supposing the BoxCar<sync::Weak<Torrent>> size is only 8 bytes.

100_000_000 torrents -> 800_000_000 bytes -> 800 MB

Our current live demo server has 1GB of RAM but 800 MB should not be a problem for a "normal" server. Besides, if you restart the service it starts from zero again.

[mickvandijke]

BoxCar<sync::Weak>

Hi @josecelano , @da2ce7 ,

I just realized there is another perhaps cleaner solution.

This is our current structure:

pub struct RepositoryDashmap {
    pub torrents: DashMap<InfoHash, Entry>,
    pub shard_priority_list: Vec<Mutex<VecDeque<InfoHash>>>,
}

pub struct Entry {
    pub peers: PeersList,
    pub completed: u32,
}

pub type PersistedTorrents = BoxCar<Weak<InfoHash>>;

What if we renamed the current Entry struct to something like TorrentDetails and create a new Entry struct like so:

...

pub struct Entry {
    // Contains the old `Entry` struct.
    pub torrent_details: Option<TorrentDetails>,
    pub time_inserted_in_nanos: u64,
}

pub struct TorrentDetails {
    pub peers: PeersList,
    pub completed: u32,
}

Instead of culling the entire DashMap shard entry of a torrent whenever it is the lowest priority and the TorrentRepository needs extra space because it reached the memory limit. We instead just drop torrent_details of a torrent entry. Only in the case that all the possible torrent_details have been dropped and we still need more space for a new torrent, we will actually drop entire torrent entries from the DashMap shards beginning from the last inserted. This way only the later pages of the torrents response could frequently be updated. And we still adhere to the set memory limit.