Performance optimizations

[josecelano]

I've been thinking and researching how to improve the tracker's performance. I would like to summarize what I've learned so that people who want to contribute to this topic can have a starting point.

First, I will explain what we have right now and why. Then, I will introduce some changes we have been working on and other performance changes that could be implemented following other trackers' implementations, especially the aquatic tracker, which seems to be the fastest.

Structure for torrent repository implementations

In production code we use one torrent repository implementation which is harcoded. Hovewer, we maintain other alternatives for becnhmarking. There are several torrent repository implementations. All of them match a pattern like this:

[STD_RW_LOCK|TOKIO_RW_LOCK] -> OUTER_COLLECTION -> INNER_COLLECTION -> [STD_MUTEX|TOKIO_MUTEX -> [ARC] -> [STD_LOCK|TOKIO_LOCK] -> ENTRY

OUTER_COLLECTION: torrents
INNER_COLLECTION: peer list
[]: optional

Current implementation

UDPDATE: The current implementation has changed. It now uses a SkipMap! But the nested collections structured is still used. The inner collection for peer lists uses a BTreeMap.

Currently, we are using a BtreeMap of torrents where the key is the infohash. For each entry in the BtreeMap, we keep the torrent statistics and another BTreeMap with the peer list. That's all!

In short, it would be something like this:

type TorrentRepository = BTreeMap<InfoHash, TorrentEntry>

struct TorrentEntry {
  peers: BTreeMap<PeerId, Peer>,
  downloaded: u32,
}

The real implementation is more verbose because:

• We are using threads to handle requests so we need to use Arc<Mutex> to safely share the data structures between threads (Arc) and to be able to mutate (Mutex) the state.
• We have implemented several versions of the torrent repository. We use different combinations of locks and mutex:
  • Standard and tokio locks.
  • Standard and tokio mutex.

These are the relevant types:

pub struct Tracker {
    // ...
    pub torrents: Arc<Torrents>,
    // ...
}

pub type Torrents = TorrentsRwLockStdMutexStd;
pub type TorrentsRwLockStdMutexStd = repository::RwLockStd<EntryMutexStd>;

pub struct RwLockStd<T> {
    pub torrents: std::sync::RwLock<std::collections::BTreeMap<InfoHash, T>>,
}

pub type EntryMutexStd = Arc<std::sync::Mutex<entry::Torrent>>;

pub struct Torrent {
    pub(crate) peers: std::collections::BTreeMap<peer::Id, Arc<peer::Peer>>,
    pub(crate) downloaded: u32,
}

pub struct Peer {
    pub peer_id: Id,
    pub peer_addr: SocketAddr,
    pub updated: DurationSinceUnixEpoch,
    pub uploaded: NumberOfBytes,
    pub downloaded: NumberOfBytes,
    pub left: NumberOfBytes,
    pub event: AnnounceEvent,
}

By replacing aliases and generics, you would have something like:

pub struct RwLockStd<Arc<Mutex<entry::Torrent>>> {
    pub torrents: RwLock<std::collections::BTreeMap<InfoHash, Arc<Mutex<entry::Torrent>>>>,
}

That is the torrent repository.

Type of requests

To improve performance, we must know what types of requests we serve with this data structure.

Tracker announce: This is a write-and-read operation into the repository. The peer is inserted or updated in the torrent's peer list. This is the most frequent request and the main one. The main tracker's purpose is to keep a list of peers interested in the same torrent (such as seeders or leechers).

• Tracker scrape: This is a read-only operation.
• API torrent list and torrent details: These are like indirect scrape requests via the REST API.

Why this implementation

RwLock for the outer collection (torrents)

RwLock<std::collections::BTreeMap<InfoHash, Arc<Mutex<entry::Torrent>>>>

It allows us to have "a number of readers or at most one writer at any point in time". All announce requests are simultaneously a write and a read operation. If we only had announce requests, it would not make sense to use a RwLock because all clients would try to lock for writing. But since we also have a scrape request, this allows multiple scrape requests simultaneously. However, announce and scrape requests cannot be handled simultaneously.

BTreeMap for the outer collections (torrents)

RwLock<std::collections::BTreeMap<InfoHash, Arc<Mutex<entry::Torrent>>>>

The torrent repository is a BTreeMap. We use a BTreeMap because we need an ordered list of torrents for the API. Unlike the standard scrape requests, the API allows one to get all torrents without providing a list of infohashes. That means we need to iterate over all torrents to implement the API endpoint (with pagination).

We are considering alternative data structures like DashMap. This structure allows parallel inserts/updates.

NOTICE: With the current implementation, parallel updates are also possible. A thread can acquire the lock for reading and get a tree node. Since the tree node is an Arc<Mutex<entry::Torrent>>> the "reader" could update the torrent entry by acquiring the mutex. In fact, since we are using a Mutex, it does not matter if we are inserting or removing a new peer, updating an existing one, or just reading the peer list; we need to lock the whole peer list. This might not impact announce requests, but it could decrease the total number of requests processed per second because scrape requests have to wait to access the peer list in exclusive mode even if it's unnecessary.

The RwLock is needed for insertion because we add a new node to the tree, not modify a preexisting node.

NOTICE: No other actor can update pre-existing torrents (peer list) when a new torrent is being added. That's the main reason we want to switch to DashMap.

There is an open question: Why do we want the API to include an endpoint to get all torrents, and what does that mean? Currently, the API returns the torrents orderer by infohash (with pagination). Still, if you request the same page after a while, you can get a different result because torrents could be removed. In fact, since the DashMap does not allow iterating over all torrents, we are considering using an alternative structure (BoxCar) to keep all the torrents (including not active torrents) so that the API can return consistent results. That may be a change we will introduce in the future even if, in the end, we don't use the DashMap. See this discussion for details about this topic.

NOTICE: Without the removed torrents, it would be very hard for an API consumer to know if it has imported all torrents from the tracker.

Mutex for the inner collection (peer list)

RwLock<std::collections::BTreeMap<InfoHash, Arc<Mutex<entry::Torrent>>>>

Actors must acquire a lock to read/write a torrent entry. I don't know why a Mutex was used originally, but that does not allow multiple readers. For announce requests, that's OK, but scrape requests don't need to be exclusive.

BTreeMap for the inner collection (peer list)

The peer list is not a list but also a BTreeMap.

std::collections::BTreeMap<peer::Id, Arc<peer::Peer>>

I don't know why a BTreeMap was used originally. I guess it could have been just an array or vector because, as far as I know, we don't need to return an ordered list of peers.

Please comment on this thread if you have some questions (or answers).

cc @da2ce7 @mickvandijke is all that correct? Anything else to add?

Now, I will add some comments with proposals for improvement.

Proposals

1. Replace the inner BTreeMap with another non-ordered structure
2. Replace the outer BTreeMap with a DashMap
3. Split the repository into two repositories for IPv4 and IPv6
4. Preallocate capacity for data structures
5. Sharding for repositories
6. Use crossbeam channels with one thread owning the repository
7. Use crossbeam_skiplist::SkipMap instead of BTreeMap
8. External service for the repository using Use KeyDB
9. Use other lock implementations
10. Use a different web framework

Performace issues

For issues related to optimization, use the label optimization.

This list keeps track of what has been done related to this discussion.

• Use dashmap for torrent in memory storage instead of the std hashmap #565
• Performance optimization: create a new torrent repository using a SkipMap instead of a BTreeMap #777

Resources

• https://marabos.nl/atomics/
• https://www.cl.cam.ac.uk/research/srg/netos/papers/2007-cpwl.pdf
• https://ketansingh.me/posts/lets-talk-skiplist/
• https://www.youtube.com/watch?v=NogIoDZdYqA
• https://mas-bandwidth.com/writing-highly-scalable-backends-in-udp/

[josecelano]

1. Replace the inner BTreeMap with another non-ordered structure

The torrent entry: info stored for each torrent in the tracker:

pub struct Torrent {
    pub(crate) peers: std::collections::BTreeMap<peer::Id, Arc<peer::Peer>>,
    pub(crate) downloaded: u32,
}

A couple of rules would allow us to use a more straightforward and potentially faster data structure for the Peer List:

• The responses don't need an ordered list of peers.
• Although we store an unlimited number of peers, responses only include a maximum of 74 peers.

Maybe a faster alternative could be a fixed array like arrayvec. Aquatic is using them. In fact, aquatic has an enum of peer lists with two sizes: small and large peer lists.

pub enum PeerMap<I: Ip> {
    Small(SmallPeerMap<I>),
    Large(LargePeerMap<I>),
}

See https://github.com/greatest-ape/aquatic/blob/58dc3b0b52a72b460f593661d8dfb25cec1056f6/crates/udp/src/swarm.rs#L327.

Pros:

• It should be faster because we have preallocated memory and allocation, and deallocation is slow.

Cons:

• It consumes more memory because you have empty spots in the array.

[josecelano]

@Power2All, what do you think about this proposal? I see you are also using a BTreeMap for peer lists.

pub struct TorrentTracker {
    // ...
    pub torrents: Arc<SkipMap<InfoHash, TorrentEntryItem>>,
    pub peers: Arc<SkipMap<InfoHash, BTreeMap<PeerId, TorrentPeer>>>,
    // ...
    pub sqlx: DatabaseConnector,
}

[Power2All]

Correct.
Skipmap is basically a "wrapper" for the BTreeMap data.
It makes it so you can change or read data from it, without the need to use mutexes or locks.

[josecelano]

I've opened a PR: #794 to use a SkipMap for the peer list instead of a BTreeMap. The performance is terrible because you must keep the lock for the torrent erny anyway.

On the other hand, regarding this optimization (non-ordered peer list), the order allows a deterministic response, which is useful, at least, for testing. We could try a HashMap.

[josecelano]

I've also tested with the HasMap: #795.
The performance is similar.

[josecelano]

And with FxHashMap too: #796
The performance is similar.

[josecelano]

2. Replace the outer BTreeMap with a DashMap

This is being implemented by @mickvandijke:

#565

It's not merged because DashMap does not allow iteration over all torrents, and the API needs that feature.

On the other hand, it was implemented with a memory consumption limit and the other repositories don't have that feature, so we should:

• Remove the feature.
• Implement the feature in the rest of the repositories.
• Remove the other repositories.
• Remove that feature from the API. Convert the API endpoint into a standard scrape, so that the consumer has to specify all infohashes. That would make it impossible to extract all torrents from external clients, and we would need to refactor tests that are using that feature.

[josecelano]

By the way, I do not know if https://docs.rs/flurry/latest/flurry/ could also be al alternative to DashMap.

[josecelano]

Relates to: #775

[josecelano]

Relates to: #784

I've implemented a DashMap repository without limiting memory consumption. That feature was included in @mickvandijke's PR.

[josecelano]

3. Split the repository into two repositories for IPv4 and IPv6

That's another improvement I've seen in the aquatic repo:

See https://github.com/greatest-ape/aquatic/blob/58dc3b0b52a72b460f593661d8dfb25cec1056f6/crates/udp/src/swarm.rs#L33-L37

#[derive(Clone)]
pub struct TorrentMaps {
    ipv4: TorrentMapShards<Ipv4AddrBytes>,
    ipv6: TorrentMapShards<Ipv6AddrBytes>,
}

Clients only get peers that are using the same IP version, so we have to filter out clients not using the same IP version as the current client making the request. That would be faster for tracker standards requests, but the API endpoints would be slower if we need to merge results from both repositories.

[josecelano]

The Tracker::announce method returns this struct:

pub struct AnnounceData {
    pub peers: Vec<Arc<peer::Peer>>,
    pub stats: SwarmMetadata,
    pub policy: AnnouncePolicy,
}

The peer list contains both IPv4 and IPv6 peers.

The HTTP Tracker handler must split them into two fields (peers and peers6) in the response.

The UDP tracker only includes one type of peer in the response IPv4 or IPv6, so it also must filter out one of the types.

The API is the only service that needs both types of peers simultaneously. The torrent details endpoint shows both of them.

We could add a new method to the Torrent Repository to get the peer list in two different ways:

• One list
• Two lists: one for IPv4 and another for IPv6

This way, the HTTP and UDP tracker handlers would not have to filter the list; they would only convert it to Bencoded format.

Internally the Torrent Repository could have two data structures, whatever the concrete repository trait implementation is using.

I do not know if this is a huge improvement but it's easy to implement, so we could try.

[josecelano]

4. Preallocate capacity for data structures

The BTreeMap does not allow reserve capacity. In general, that would make requests faster because reallocation is expensive.

Pros:

• Faster

Cons:

• More memory consumption

If you change any of the current data structures, consider reserving capacity. For example, the peer list could be a vector with a capacity of 74 peers.

[josecelano]

The SkipMap data structure we use doesn't allow preallocation, but other implementations do. I asked why in the crate repo:

crossbeam-rs/crossbeam#1100

[josecelano]

5. Sharding for repositories

If I'm not wrong, aquatic has:

• Socket Workers
• Swarm Workers

https://github.com/greatest-ape/aquatic/blob/master/documents/aquatic-architecture-2024.svg

I think each "Swarm Worker" has its independent torrent repository. IT's a kind of load-balancer for requests. All requests must stick to the same worker; otherwise, they could get a different peer list. However, I think that should not be a problem.

But I'm not sure if that's the way it works. I have yet to read the code deeply.

Maybe @greatest-ape can confirm.

[Power2All]

I did it like this :) https://github.com/greatest-ape/aquatic/blob/751ef7966e2cb711370ae315997ee8244a807727/crates/udp/src/swarm.rs#L141

Ah, you used the IP as the "shard" key ?
Not a bad idea, but I use the HASH of the torrent (first byte) as the shard key.
But yah, I'm still learning Rust every time :)

[josecelano]

What's the benefit of using the IP instead of the first byte of the HASH?

By using the IP, clients are equally distributed between shards. With hashes, you could have many clients from different IPs announcing the same torrents, and their requests would not be distributed.

However, with IPs, you could have a small swarm of IPs announcing many torrents (or "big" clients), and the requests would not be distributed.

I guess it depends on what is more common.

Maybe you can try dynamic sharding with two levels of sharding :-)

[greatest-ape]

I don’t use the ip address for sharding, but I maintain separate swarms for ipv4 and ipv6 :-) see https://github.com/greatest-ape/aquatic/blob/751ef7966e2cb711370ae315997ee8244a807727/crates/udp/src/swarm.rs#L305

Sharding swarm state by IP address wouldn’t work properly. SO_REUSEPORT distributes incoming packets to threads by ip address & port though.

[josecelano]

Ok, apparently you also use the first byte of the infohash. I will take a look if I start implementing these improvements I the future.

I knew you were splitting swarms by the IP version. It's one proposal in this discussion I copied from your implementation. I think it's very simple and efficient.

[Power2All]

Yah people nagged to me to implement no dividing IPv4 and IPv6, but people seem to forget that IPv4 and IPv6 cannot talk to each other, however, there is a possibility that an IPv6 network also has IPv4 support, then the client could connect to either IPv4 and IPv6 peers, so that's something to consider.

[josecelano]

6. Use crossbeam channels with one thread owning the repository

https://docs.rs/crossbeam-channel/latest/crossbeam_channel/

Instead of sharing the ownership of the repository between all the threads handling requests, there is only one thread that owns the repository, and it receives requests via a crossbeam_channel

This assumes that:

• Updating a peer list or adding a new torrent is something you have to do sequentially anyway. It could work if we only had announce requests.
• Updating the peer list is only part of the job; the tracker response with the peer list has to be converted to encoded format. Independent threads could do other tasks.

[greatest-ape]

This is essentially the previous aquatic model, except there could be multiple such workers responsible for a shard of the torrents.

[greatest-ape]

That being said, it might still work well for your use case. Nested locks are tricky even without running on top of an async runtime.

[josecelano]

7. Use crossbeam_skiplist::SkipMap instead of BTreeMap

See: crossbeam-skiplist

They are supposed to be faster because:

• "They support safe concurrent access across multiple threads".
• "Methods which mutate the map, such as insert, take &self rather than &mut self. This allows them to be invoked concurrently.".

I think @Power2All is using it in the current Torrust-Actix Tracker implementation.

[josecelano]

I have implemented this one. The performance is only slightly better, at least with our current benchmarking tools.

[josecelano]

I have implemented this one. The performance is only slightly better, at least with our current benchmarking tools.

The ReadWriteLock was already pretty optimized, but down the line, on longer run, the readlocks will become exhausted, and it will completely lock up the application. This is the reason why I went towards a Atomics solution, which does locking on it's own.

Hi @Power2All thank you for your feedback. I think we all benefit from sharing all the things we have tried.

Can you explain it a little bit more. I see you are still using SkipMap for the peer list.

pub struct TorrentTracker {
    pub config: Arc<Configuration>,
    pub torrents: Arc<SkipMap<InfoHash, TorrentEntryItem>>,
    pub peers: Arc<SkipMap<InfoHash, BTreeMap<PeerId, TorrentPeer>>>,
    pub torrents_updates: Arc<SkipMap<InfoHash, i64>>,
    pub torrents_shadow: Arc<SkipMap<InfoHash, i64>>,
    pub stats: Arc<StatsAtomics>,
    pub torrents_whitelist: Arc<SkipMap<InfoHash, i64>>,
    pub torrents_blacklist: Arc<SkipMap<InfoHash, i64>>,
    pub keys: Arc<SkipMap<InfoHash, i64>>,
    pub users: Arc<SkipMap<UserId, UserEntryItem>>,
    pub users_updates: Arc<SkipMap<UserId, UserEntryItem>>,
    pub users_shadow: Arc<SkipMap<UserId, UserEntryItem>>,
    pub sqlx: DatabaseConnector,
}

I guess you mean that you switched to Atomics locks when possible (stats) because they are more lightweight?

[Power2All]

No, it's all Atomics.
Skipmap is based on Atomics, which if you might know, is by itself already a mutex-like system. You don't need to lock anything with Skipmap, since it's Atomics based.

[josecelano]

Oh, cool! I didn't know that. I only knew it was a lock-free implementation that allows concurrent inserts.

[Power2All]

I come back from this, as skipmap is fast, but it doesn't allow you correctly update certain aspects without a other thread dirtying the data.
Instead, I moved away from skipmap, using pure BTreeMap, but made my own implementation of sharding the torrent data in memory, with each shard having their own RWLock. This tremendously speed up performance, but also, parallel threaded work goes much, much faster now.

[josecelano]

8. External service for the repository using Use KeyDB

See #754

The repository could be a wrapper of an external service like KeyDB.

Pros:

• It allows horizontal scaling

Cons:

• Network latency. However, it could be run on the same server which is what we have now.

[josecelano]

9. Use other lock implementations

For example: https://github.com/Amanieu/parking_lot

[josecelano]

I've opened a PR adding a new torrent repo implementation using the parking_lot crate: #800.
Performance looks slightly worse.

[Power2All]

Use parking_lot with the "deadlock scanner".
I use it as well, and helps with finding stuck rwlocks.

[josecelano]

10. Use a different web framework

This is only possible for the HTTP Tracker and the Tracker API.

https://www.techempower.com/benchmarks/#section=data-r16&hw=ph&test=plaintext

[Power2All]

I would suggest, move away from Axum and switch to Actix.
It's easier in use, simpler to apply middleware, and actually applies timeouts properly as expected, that and very customizable.

[josecelano]

Hi @Power2All @greatest-ape I found this challenge https://mas-bandwidth.com/writing-highly-scalable-backends-in-udp/. There are some suggestions to write highly scalable backends in UDP.

[greatest-ape]

I’ve looked a bit at using eBPF to speed up aquatic, but as I don’t have access to hardware with multi-queue NICs, I kind of gave up/lost interest. But it could definitely be good for performance to get interrupts on the proper threads. Designed right, swarm sharding for announce requests could even be done kernel-side.

I’ve looked a little bit at implementing the whole tracker with eBPF too, but since there is no heap access, I don’t see a reasonable way.

[greatest-ape]

That being said, if someone wants to donate two powerful machines with fancy NICs to me, I could probably spend some time on further optimizations 😀

[Power2All]

It's easier then you think.
I already applied threading for UDP data.
recv_from supports threading, so you could have multiple threads awaiting for "recv_from" to hand over a packet to be handled. In this way, the next recv_from can be picked up by a other thread almost directly. UDP is a streaming protocol, so it's serially "pulled" anyway, but after that, you can parallel the workload.

[greatest-ape]

I might also mention, aquatic already does stuff like bind on the same address and port on multiple threads using SO_REUSEPORT. A next step could be what I mentioned in my previous comments, e.g., optimize around how the kernel assigns packets to threads.

[Power2All]

Correct, I use net2 of Rust to use REUSE PORT now.
Currently looking into implementing XDP, AYA crate has support for this.
You can handle raw packets and sent raw packets out again, which could speed up the process drastically too.
https://www.youtube.com/watch?v=NogIoDZdYqA is a good watch :)