Tribler: content popularity community: performance evaluation

[synctext]

@arvidn indicated: tracking popularity is known to be a hard problem.

I spent some time on this (or a similar) problem at BitTorrent many years ago. We eventually gave
up once we realized how hard the problem was. (specifically, we tried to pass around, via gossip,
which swarms are the most popular. Since the full set of torrents is too large to pass around,
we ended up with feedback loops because the ones that were considered popular early on got
disproportional reach).

Anyway, one interesting aspect that we were aiming for was to create a "weighted" popularity,
based on what your peers in the swarms you participated in thought was popular. in a sense,
"what is popular in your cohort".

We deployed the first version into Tribler #3649 , after prior Master thesis research #2783. However, we lack documentation or specification of the deployed protocol.

Key research questions:

• What is the real deployed system behavior?
• What is the resource consumption?
• What is the accuracy and quality in general of the information?
• How can we attack or defend this IPv8 community?

Concrete graphs from a single crawl:

• messages and bandwidth in time
• hashes discovery and duplicates
• distribution of discovered popularity of swarms
• conduct swarm popularity check and compare results in real-time
• behavior of pub/sub mechanism for popularity feed
• dynamics of trust-based pub/sub auto-subscribe

Implementation of on_torrent_health_response(self, source_address, data)
ToDo @xoriole : document deployed algorithm in 20+ lines (swarm check algorithm, pub/sub, hash selection algorithm,handshakes, search integration, etc.).

[xoriole]

Popularity Community
Introduction
Popularity community is a dedicated community to disseminate popular/live contents across the network. The content could be anything for eg. health of a torrent, a list of popular torrents or even search results. The way of dissemination of the content follows the publish-subscribe model. Each peer in the community is both a publisher and a subscriber. A peer subscribes to a set of neighboring peers to receive their content updates while it publishes its content updates to the peers subscribing it.

Every peer maintains a list of subscribing and publishing peers with whom it exchanges content. All contents from non-subscribed publishers are basically refused. Selection of peers to subscribe or to publish greatly influences the dissemination of the content both genuine and spam. Therefore, we try to select based on a simple trust score. Trust score indicates the number of times we have interacted with the node as indicated by the number of mutual Trustchain blocks. Higher the trust score better the chance of being selected (as publisher or subscriber).

Research questions
...

[synctext]

ToDo:
describe the simplified top-N algorithm that is more light-weight (no pub/sub).
As-simple-as-possible gossip. Measure and plot 4 graphs listed above

• messages and bandwidth in time
• hashes discovery and duplicates
• distribution of discovered popularity of swarms
• conduct swarm popularity check and compare results in real-time

[synctext]

Bumping this issue. The key selling point of Tribler 7.6 is popularity community maturing (good enough for coming 2 years) and superior keyword search using relevance ranking. goal: 100k swarm tracking.

This has priority on channel improvements. Our process is to bump each critical features to a superior design and move to the next. Key lesson within distributed systems is: you can't get it perfect the first time (unless you have 20 years of failure experience). iteration and relentless improving deployed code is key.

After we this close performance evaluation issue we can build upon it. We need to know how well it performs and tweak it for 100k swarm tracking. _We can do 1st version of real-time relevance ranking_. Read our 2010 work for background: Improving P2P keyword search by combining .torrent metadata and user preference in a semantic overlay

• Item popularity and recommendation accuracy
• Rank and relevance in novelty and diversity metrics for recommender systems

Repeating key research questions from above (@ichorid):

• What is the real deployed system behavior?
• What is the resource consumption?
• What is the accuracy and quality in general of the information?
• How can we attack or defend this IPv8 community?

Concrete graphs from a single crawl:

• messages and bandwidth in time
• hashes discovery and duplicates
• distribution of discovered popularity of swarms
• conduct swarm popularity check and compare results in real-time
• behavior of pub/sub mechanism for popularity feed
• dynamics of trust-based pub/sub auto-subscribe

[synctext]

See also #4256 for BEP33 measurements&discussion

[synctext]

Please check out @grimadas tool for crawling+analysing Trustchain and enhance this for the popularity community:
https://github.com/Tribler/trustchain_etl

[synctext]

Hopefully we can soon add the health of the ContentPopularity Community to our overall dashboard.

[xoriole]

• PEERS_CONNECTED : Number of currently connected peers
• PEERS_UNIQUE: Number of unique peers encountered during the measurement period (10 mins)
• TORRENTS: Number of torrents received
• SEEDERS_MAX: Seeder count of the most popular torrent received
• SEEDERS_AVG: Avg seeder count of the received torrents. (Higher the better; how to increase this?)
• SEEDERS_ZERO: Number of torrents received with zero seeders

Currently, a peer shares its most popular 5 and random 5 torrents checked by the peer to its connected neighbors. Since, a peer starts sharing them from the beginning, its not always the case the popular torrents are shared. This results in sharing torrents that doesn't have enough seeders (see SEEDERS_ZERO count), and this does not contribute much in sharing of popular torrents. So, two things that could improve sharing popular torrents seems like:

1. not sharing zero seeder torrents
2. increasing the initial buffer time before sharing is started

https://jenkins-ci.tribler.org/job/Test_tribler_popularity/plot/

[devos50]

Nice work! I assume that this experiment is using the live overlay?

As a piece of advice, I would first try to keep the mechanism simple for now, while analyzing the data from the raw network (as you did right now). Extending the mechanism with (arbitrary) rules might lead to bias results, which I learned the hard way when designing the matchmaking mechanism in our decentralized market. Sharing of the 5 popular and 5 random torrents might look like a naive sharing policy, but it might be a solid starting point to get at least a basic popularity gossip system up and running.

Also, we have a DAS5 experiment where popularity scores are gossiped around (which might actually be broken after some channel changes). This might be helpful to test specific changes to the algorithm before deploying them 👍 .

[xoriole]

@devos50 Yes, it is using live overlay.

Also, we have a DAS5 experiment where popularity scores are gossiped around (which might actually be broken after some channel changes). This might be helpful to test specific changes to the algorithm before deploying them.

Yes, good point. I'll create experiments to test the specific changes.

[synctext]

Thnx @xoriole! We now have our first deployment measurement infrastructure, impressive.

• [X] What is the real deployed system behaviour?

Can we (@kozlovsky @drew2a @xoriole) come up with a dashboard graph to quantify how far we are to our Key Performance Indicator: the goal of tracking 100k swarms? To kickstart the brainstorm:

• [x] Unique hash discovery after joining community for 1 hour (plus duplicates)?
• [x] messages and bandwidth in time
  
  
  
  • For 1 hour measure the amount of messages and type
  
  
  • Indicate their contents (identify ZERO_SEEDERS)
  
  
  • plot bandwidth usage
  
  
• [x] What is the accuracy and quality in general of the information?
  
  
  
  • validate the popularity check results
  
  
  • sample slowly the discovered swarms (DHT hammering will get server blocked)
  
  
  • compare client and our Jenkins re-check result
  
  
  • plot the delta for each swarm and sort by largest difference (Y-Axis delta of popularity, X-Axis: swarms sorted by delta)
  
  
• [ ] distribution of discovered popularity of swarms (dead swarms, suspicious large swarms)

increasing the initial buffer time before sharing is started

As @devos50 indicated, this sort of tuning is best preserved for last. You want to have an unbiased view of your raw data for as long as possible. Viewing raw data improves accurate understanding. {Very unscientific: we design this gossip stuff with intuition. If we have 100+ million users people would be interested in our design principle.}

Repeating long-term key _research questions_ from above (@ichorid):

• What is the resource consumption?
• How can we attack or defend this IPv8 community?
• #3065 Fix for DHT spam using additional deployed service infrastructure

[ichorid]

1. not sharing zero seeder torrents

For every popular torrent, there are a thousand of dead ones. Therefore, information about what is alive is much more precious and scarce then about what is dead. It will be much more efficient to only share torrents that are well seeded.

Though, the biggest questions are:

• should we use the information received from other peers when sending our own gossip packets? (probably not, or to some limited extend)
• should we recheck the torrent health eventually? (probably not, as popular torrents tend to rise quickly and fall slowly)

[ichorid]

• What is the resource consumption?
• #3065 Fix for DHT spam using additional deployed service infrastructure

It would be very nice if we find (or develop) some Python-based Mainline DHT implementation, to precisely control the DHT packets parameters.

• How can we attack or defend this IPv8 community?

| :crossed_swords: attack | :shield: defence |
|--------------------------|---------------------------------------------------------------------------------------------------|
| spam stuff around | pull-based gossip |
| fake data | cross-check data with others |
| biased torrent selection | pseudo-random infohash selection
(e.g. only send infohashes sharing some number of last bytes) |

[drew2a]

We still have no measures for "popularity community".

I will describe a few experiments below.
Maybe they will be helpful for a developing more scientific approach.

Metric 1: how fast a new user can get the list of popular torrents

Experiment 1.1

Given the network of 100 nodes.
Each node has a list of 100K popular torrents.
We add a new node to the network.

Question: how long will it take to deliver a 100K list to the new node?

Experiment 1.2:

The same as 1.1, but 1K nodes.

Metric 2: how fast an empty network will collect 100K popular torrents

Experiment 2.1

Given the network of 100 nodes.
Each node has an empty list of popular torrents.

Question: how long will it take to get a 100K list on each node?

Additional data:  bandwidth consuming over time.
Additional data:  lists filling over time.

Experiment 2.2:

The same as 2.1, but 1K nodes.

Metric 3. how heterogeneous lists are

Experiment 3

Given: the network, after 2.1 experiment.
We calculate the common part of all popular lists (the common part of "100k torrent list" on each node) [hereinafter CommonList]

Question: what size of CommonList (in percent)?

Metric 4: quality of a popular list

Experiment 4

Given: the network after experiment 2.1.
We calculate CommonList.
We somehow receive a reference list (may be it is a static "human-made" list) [hereinafter ReferenceList]
We compare CommonList to the ReferenceList.

Question: Which percentage of the CommonList and ReferenceList is the same?

[devos50]

@drew2a good suggestions, thanks!

Note that many of these experiments can be performed in isolation on our (nation-wide) compute cluster, the DAS5. We have the necessary tools in Gumby to easily create new overlays on this cluster and to connect peers with each other. Gumby also allows plotting of resource consumption. Hopefully, we will soon have a few additional servers operational to conduct experiments.

We already have a basic DAS5 experiment that starts a few Tribler instances and shares popularity vectors. This would be a good starting point for anyone that quickly wants to evaluate the effectiveness of popularity gossip strategies. However, I believe that this issue concerns a performance evaluation of our _live_ network.

[ichorid]

"Experiment 1.1" is basically the experiment @devos50 made for the first implementation of GigaChannels two year ago. The answer is: "very fast, but gets increasingly slower as the list grows".
Also, I doubt there are over 10k popular torrents at any moment in the whole BitTorrent network. Some (dated) insights into the BitTorrent network can be found in @synctext 's seminal works.

There are about 20 popular trackers, each one serving about 0.5-2M torrents. Less than 1% of torrents in any category are "alive". See torrents.csv project. Overall, torrent popularity is pretty transient.

[ichorid]

"Experiment 2" depends on two factors:

• the availability of infohashes
• the maximum allowed rate of DHT checks per ip/port/client id

AFAIK, one can't simply go to a BitTorrent node and ask it for its list of seeded infohashes ( :eye: :ok_hand:). Instead, one must know the infohash and ask the client about it. Maybe there is some BEP-extension that implements querying clients for lists of infohashes, but that would be a great privacy hole (and thus highly unlikely to be accepted by BitTorrent community).

Also, DHT has some flood-protection that already took a toll on our developers.

[synctext]

Great fan of these concrete experiments to collect hard data. We need performance data from emulation. Hence the dashboard idea.

First priority coming sprint weeks: build backwards-compatible PopularityCommunity and all known fix bugs in there, and try to boost performance. Preferably that performance is improved, even with the existing deployed community.

We thus do integration testing, compatibility testing, regression testing, and performance analysis into the Multi-Aspect Sprint Cycles :-)
Big step forward: https://github.com/xoriole/tribler/blob/popularity-helper/src/tribler-core/run_popularity_helper.py

[ichorid]

From this paper

We trace the popularity of those objects by counting the number of requests they receive per week for the entire eight months of our measurement study. Fig. 4 shows that popular objects gain popularity in a relatively short timescale reaching their peak in about 5–10 weeks. The popularity of those objects drops dramatically after that. As the figures show, we observe as much as a sixfold decrease in popularity in a matter of 5–10 weeks.

According to that paper, the content popularity follows Mandelbrot-Zipf distribution.

Unfortunately, I (almost) completely forgot my calculus course, so I can't integrate anymore (except for the simplest stuff). Now, if we would have a mathematician who can integrate the Mandelbrot-Zipf distribution and fit the total number of entries to the already known BitTorrent network stats (see my post above about 40M torrents)... Then we could predict the peak swarm size and tune our experiments accordingly...

@alexander-stannat ?

[xoriole]

Results of popularity community from continuous 1 hour execution.
Plots available in Jenkins

[ichorid]

we ended up with feedback loops because the ones that were considered popular early on got
disproportional reach

I've come up with a simple algorithm on how to solve the feedback problem. The basic idea is to emulate how news spread trough human society:

1. share more important thoughts more often.
2. over the time the urge to share a thought diminishes ("become bored of the idea").
3. if you hear other people repeating your idea, reduce the urge to share it (the "old news" effect).
4. if someone's claim contrasts your thoughts to the point it will change your behaviour, check the fact yourself. If the check fails, reject the claim and notify the claimer.

This list of rules guarantees that information about popular torrents will propagate quickly (1), but will not dominate the gossip (3) and die out naturally (2). Also, it will prevent the spreading of "fake news" (4).