[Architecture] Hub-Spoke model for federation?

XtremeOwnageDotCom commented 1 year ago

Question

One of the biggest issues I am currently seeing with Lemmy, is federation.

Either...

Federation between instances having issues.
Federation is backed up.
Federation / Syncing is not scaling.

Etc.

Currently, federation performs in a full-mesh topology. Instances, all talk to other instances.

Full mesh image:

Why is this a problem?

As the number of instances scales up, this will lead to federation/replication traffic increasing exponentially.

ie- It does not scale well.

It is the reason TCP/IP was originally broken up into separate broadcast domains. It is why we have subnets.

To add some math for clarification- lets say, we have 10,000 instances.

To calculate the number of required connections for a full mesh, the formula is w = n * ( n – 1) / 2

10,000 * (10,000 - 1) / 2 = 49,995,000 required connections.

What if- a hub-spoke topology was adopted for federation?

Instead, of instances talking to each other- instead, instances talk to "hub" servers.

Hub Spoke Image:

The hub servers, would need to be big, beefy servers, and would only run services for content replication, syncing, and federation. They would all replicate amongst each other as well, in a full-mesh.

If implemented, instance -> fediverse replication/federation issues would be greatly minimized.... As, either everything works, or nothing works.

Using the same variables above, lets still assume, there are 10,000 instances.

Using hub-spoke, lets say, each instance only needs to maintain concurrent connectivity to a single hub. (But- keeps a list of backup hubs, in the event the main hub goes down).

This- only requires 10,000 connections. (Plus- NumberOfHubs * (NumberOfHubs - 1) / 2) This is significantly less than the 50 million connections from the current full mesh topology.

In the current example, this is a 99.98% reduction in the number of concurrent connections.

Benefits

Amount of federation/replication traffic would be greatly decreased, as individual instances only needs to sync with a hub server.
Federation/replication issues vastly minimized, as, either everything works, or nothing works.
Barrier to entry vastly reduced as well for new instances.
Potential to allow for a centralized "directory/phonebook" for instances/communities, which can be integrated into the UI, for allowing users to EASILY discover/subscribe to new communities (as opposed to needing to discover the community through google, or other tools)

Potential downsides

Introduction of a new failure domain.
Hub servers would need to be trusted/open.
Hub servers need to be scaled to properly handle load.

Potential Mitigations to downsides-

Instances can OPTIONALLY choose to use hubs, rather then full meshing. This eliminates most of the concerns.
Instance admin capability of decide if individual communities should be directly-connected/federated, or used through a hub.

Alternatives?

Can limit lemmy to only a few handfuls of main instances. This, defeats most of the benefits of this platform, however.
Strictly limiting federation to massively reduce load. This- can work, however, this also ruins many benefits of the platform, and vastly decreases user experience. Would not recommend this.
Optimizations of the current implementation can band-aid this issue, but, only up to a point.

RocketDerp commented 1 year ago

I sarted a community on Lemny for this topic: https://lemmy.ml/c/lemmyfederation

XtremeOwnageDotCom commented 1 year ago

I sarted a community on Lemny for this topic: https://lemmy.ml/c/lemmyfederation

Yea... nothing on lemmy.ml is federating correctly for me. beehaw.org working fine. lemmy.world works.

lemmy.ml is no-go.

│ 2023-06-21T14:16:09.127573Z  WARN activitypub_federation::core::activity_queue: Queueing activity https://lemmyonline.com/activities/follow/d6d4fccb-c1e3-40ea-918b-6426d3080b3f to https://lemmy.world/inbox for retry after failure with status 502 Bad Gateway: <html>       │
│ <head><title>502 Bad Gateway</title></head>
│ <body>              
│ <center><h1>502 Bad Gateway</h1></center>       
│ <hr><center>nginx/1.18.0 (Ubuntu)</center>
│ </body>   
│ </html>

Oh, and I can't exactly sign-up to chat about this on lemmy.ml either.

Signups aren't working either.

As well, the instance instance went down.

@RocketDerp if you wanted to have a discussion forum- I'd recommend moving the community to an instance that is not completely overwhelmed, with broken federation for most other instances.

wont-work commented 1 year ago

This would break ActivityPub compatibility, wouldn't it? Not sure if that's a tradeoff the devs are willing to consider yet.

XtremeOwnageDotCom commented 1 year ago

This would break ActivityPub compatibility, wouldn't it? Not sure if that's a tradeoff the devs are willing to consider yet.

Not at all. Services would just connect to the hub servers, which would be responsible for that piece.

Individual instances can optionally elect to enable or disable it as well, with it enabled by default.

bdonvr commented 1 year ago

Great presentation and write up - but this is just not how any of this works. The whole thing is based on a premise that just isn't true.

Reposting my reply from lemmy:

The way federation actually works:

A user on lemmy.ml subscribes to a community on lemmy.world. Say, !funny@lemmy.world

Assume that this user is the first lemmy.ml user to do so - basically what happens is the lemmy.world community sees that a member of a never before seen instance just subscribed. !funny@lemmy.world then adds lemmy.ml to its list of instances it needs to tell whenever something happens in the community.

No matter how many users of lemmy.ml subscribe, this only happens once.

Now when a user of sh.itjust.works upvotes a post on !funny@lemmy.world, the sh.itjust.works instance then tells !funny@lemmy.world of this change. It accepts the change, then tells everyone on its list of instances that have subscribers on them.

So essentially, sh.itjust.works talks to lemmy.world, lemmy.world tells everyone else. There is no “full mesh”. The instance hosting the community is the “hub”, everything else is a spoke.

So if there’s 10,000 instances, and they all just so happen to have at least one subscriber to some community, each change will be sent out 9,999 times. Your “50 million” premise is just completely wrong and I’m not sure where it’s coming from.

XtremeOwnageDotCom commented 1 year ago

Reposting my reply from lemmy:

To... quote my reply, to your comment on lemmy-

Its not wrong- we just have opposite ideas here-

The 50 million, is based on the formula for a full-mesh network. Where all instances talk to each other. In the case of lemmy, this would be an absolute worst-case scenario, where every instance, is subscribed to a community on every other instance.

In your example of only 10,000 messages, you are assuming that of the 10,000 instances in existence, they are ONLY looking at a single community, on a single server.

Lets say, those 10,000 instances all decide to look at a community on another server. Now you have 20,000 connections.

Lets add another community, hosted on yet another instance. That is 30,000 connections.

TLDR;

My example, is based on worst-case scenario.

Your example, is based on best-case scenario.

Realistically, the actual outcome would be somewhere much closer to best-case scenario(As communities seem to lump up on the big servers). However, for planning architecture, you always assume worse-case scenario.

huanga commented 1 year ago

@bdonvr > The problem comes from many many many small instances (i.e.: personal instances) subscribing to larger ones.

As of the time of writing, lemmy.ml is showing 4167 linked server, and lemmy.world is showing 2295 linked server.

Every action on !selfhosted@lemmy.world will need to be propagated out to a substantial portion of those federated server (due to nature of content and likelihood of overlap). So each upvote is to be sent out thousands of times. Someone can easily go into a large thread, and click upvote on a bunch of comments and easily exhaust the 10K federation workers.

Also, I'm willing to wager a portion of those servers are no longer online, or will respond very slowly, which just makes situation even worse.

@XtremeOwnageDotCom > A hub and spoke setup could work, but the hubs needs to be ran by entities that are not going to nilly welly de-federate from each other, or you end up with huge swaths of broken hubs not interconnected. However, we've already seen some large instances pull that trigger, so those hosting the hubs will probably need to be someone else.

I think another solution could be to create hourly/daily/weekly batch of activities (gizpped jsons shouldn't be too huge and can cache very easily by CDNs) for communities on instances exceed a certain threshold (i.e.: >500 linked server, >10K subscribers; arbitrary numbers just to illustrate idea). This will allow individual instances to "catchup" by reviewing parsed messages to exclude, and top up any messages that didn't make the federation window.

XtremeOwnageDotCom commented 1 year ago

So- we have a reasonable discussion occuring on https://lemmyonline.com/post/6367 currently-

And, I have adjusted my idea a bit- Most people seem to agree, the idea of centralized hub servers is a bad thing, and I don't disagree.

So- I am redefining the idea, as a hub/proxy server, leveraging a publish/subscribe method.

Lets use lemmy.ml as an example. It currently has to send all of its updates out to every subscribed server, while also handling all of its local activity.

Lets build a proxy server, and delegate the activity sending to it.

Now. lemmy.ml only needs to send its activity to its proxy server(s). (Lets assume this is a scalable tier)

The proxy server, would subscribe to the updates from the main instance server (lemmy.ml), and it would handle sending those out to the servers subscribed to lemmy.ml, thereby offloading that load from the main instance server.

Now, let's assume that proxy server is overloaded, and unable to keep up with sending messages in a reasonable time. Lets add another proxy server to help distribute the load more.

The action of sending external instance to this proxy server, can be as simple as redirecting the URLs via the reverse proxy sitting in front of lemmy (nginx, by default).

Using the sub/pub method- with guaranteed delivery, with a dead-letter retry limit, should improve the reliability of this piece a bit.

@huanga Your idea is also very feasible too. When subscribing to a new community, I think it absolutely should just send a compressed archive, to quickly get it up to date, rather than sending N number of messages for posts/comments/votes/etc.

lullis commented 1 year ago

I'm wondering if we will end up reinventing BGP here, but here is my off-the-cuff, vaguely-familiar-with-the-subject-but-ignorant-of-the-details idea: if messages are signed and instances keep track of all the keys from the instances/actors, why not use something like a gossip model?

If you have a super popular instance, you can make a network graph, partition in sub-networks that have only your instance in common, and then send the message to only one node on each of these sub-networks.

If you couple that with some (optional) system where (larger) instances can enter in some peering agreement, then you'd mitigate the chattiness of the protocol and wouldn't need any external hub. The system continues fully decentralized and admins would have an incentive to federate, because better connected nodes would have a higher priority in receiving the messages.

XtremeOwnageDotCom commented 1 year ago

gossip model?

I actually was unfamiliar with the gossip model- after digging a bit- here are a few links for others in the same boat as me-

https://en.wikipedia.org/wiki/Gossip_protocol https://arxiv.org/abs/2306.08670 https://www.educative.io/answers/what-is-gossip-protocol https://medium.com/nerd-for-tech/gossip-protocol-in-distributed-systems-e2b0665c7135

Actually sounds similar to what this user was talking about as well: https://lemmyonline.com/comment/35335

After my bit of research- that model sounds like it could be quite feasible too.

jcgurango commented 1 year ago

The gossip model is interesting, and I think I could volunteer to implement it if we can arrive at a good understanding of how to make it work well and if we have @dessalines and @Nutomic's blessings. I think we can poke some holes at it even this early, though, but first allow me to lay out how I think this would work:

This model would come into play whenever an instance would like to disseminate AP activities.
That instance would multicast these activities to several instances and assume they'd continue to disseminate it. Perhaps those instances would also respond back with an OK or something to at least make sure that they've received it and are willing to disseminate them.
These peers would go on to disseminate the information to other peers they know of - perhaps each message can be sent with a list of instances that they are going to be directed to.

These are my initial thoughts:

This would only have to be applicable on the level of an instance hosting a community, disseminating comments and posts to other instances. Because if comments from other instances that don't host that community can use this system to send their comments to an instance, not only is basically anyone allowed to flood the network with activity, but defederation just wouldn't work anymore since comments can still be entered into a community without the main instance that hosts that community's permission.
From what I can see, gossip protocols are usually implemented on a periodical basis and not on a per-event basis. If we implement it that way, will latency be a concern? At the moment, at least for instances not overloaded, comments come in basically immediately so I wonder if people are used to that by now. If we do it on a per-event basis, it'd still introduce latency anyway though, and possibly increase overall network load. Speaking of overall network load...
Won't we be effectively flooding the network with every broadcast? At least, in the case of very large communities with many subscribers. suppose you could say that some instances can opt-out, and they would end up being last on the list, but it seems like an instance can just soft opt-out by saying they'll pass messages on - and then just not sending it out. Point being that there has to be some manner of either trust or verification and I wonder if that would further increase network load.
If peer selection is random then some people might be left out completely. I guess you could do it in a way where if you contact a peer and they've already received the message you can move onto the next one until you reach X amount of peers contacted but for the very last peer in the system that'd end up making as many network requests as there are subscribers.

I also wonder if we could solve this issue just by moving communities off of the larger instances. I feel like an instance can containing however many users as needed, but shouldn't have as many communities as lemmy.world and sh.itjust.works do. The net result for maxing out the federation workers on an instance with many communities is way more devastating than the net result for maxing out the federation workers on an instance with many users. In the first scenario, everybody outside of the instance who is subscribed to at least one community is affected. In the second scenario, only those within the instance are affected.

jrussek commented 1 year ago

It might be worthwhile considering using an existing implementation of gossip for this kind of usecase, for example https://docs.libp2p.io/concepts/pubsub/overview/ which already takes care of a bunch of these concerns (like detecting an dealing with nodes with "poor behavior". pub/sub also seems like an attractive pattern for comments -> community.

RocketDerp commented 1 year ago

I suggest an immediate first step is that federation http activity be moved to an independent project and service for lemmy_server. So that it can be stopped, started, upgraded independently of the core API server. I also think it would be ideal to have routing for federation to be identifiable, perhaps a different hostname, but as I understand it now (correct me please if I'm wrong) nginix distinguishes based on JSON data type in routing connections. I think firewall rules and CDN front-end would want to be different for federation server to server, and it is also another attack surface to consider. I highly suspect major Lemmy servers are denial of servicing each other which also can possibly impact the front-end API resources.

The communication layer between lemmy_server and lemmy_federation service would need to pick a scheme. As newly created local content notifications would need to pass to the outbound sender. Maybe something as simple as disk files being created or a database table or whatever.

yogeshdhamija commented 1 year ago

If my understanding is correct, we're proposing alternative federation models with the purpose of resolving federation scaling issues described in issue #3101?

Although the discussion here is good and laudable, it makes me a little nervous to suggest architectural changes without knowing exactly what the bottlenecks are. I agree, conceptually, having N instances (in the worst case-- all subscribed to each other) means that each action (vote, post, comment) needs to be sent by the home instance N times. Note that, even in the worst case, this scales 1-to-1 with the number of servers. It's not exponential.

Granted, we can probably do better, but I'd prefer to get a better handle on exactly what's causing the current federation issues before making changes which will have tradeoffs (some expected, others unexpected).

jrussek commented 1 year ago

If my understanding is correct, we're proposing alternative federation models with the purpose of resolving federation scaling issues described in issue #3101?

I think the issue describes an architectural concern not an (immediate) solution to that specific issue.

Although the discussion here is good and laudable, it makes me a little nervous to suggest architectural changes without knowing exactly what the bottlenecks are. I agree, conceptually, having N instances (in the worst case-- all subscribed to each other) means that each action (vote, post, comment) needs to be sent by the home instance N times. Note that, even in the worst case, this scales 1-to-1 with the number of servers. It's not exponential.

While for each post the network load scales 1:1 with the number of servers, that's not true for the network as a whole. The total network calls increase at a rate of posts*servers which means whenever either doubles, outgoing RPCs double. I think as a server operator it's easier to reason about doubling the resources for double the users (and posts), than to absorb the total network growth in addition to their instance growth - especially when there are alternatives available.

Granted, we can probably do better, but I'd prefer to get a better handle on exactly what's causing the current federation issues before making changes which will have tradeoffs (some expected, others unexpected).

I agree with that, one is more urgent than the other :) But I think this conversation should be had at the same time.

I'm just a random internet bozo though

jcgurango commented 1 year ago

I believe I may have a solution to this based on some of the ideas in this issue and some cues from how Mastodon relays work: opt-in server confederation.

Two or more small instances can list each other as co-federated (must be opt-in on both instances)
The list of instances that instances cofederate with is federated to other instances
When forwarding activities, a non-cofederated instance will lookup if an instance has cofederators and will no longer send that activity to the other instances the activity is addressed to
The instance will then forward that activity to cofederated instances it is addressed to

This way, many small instances can pool together their userbase. If some instances set themselves up as open cofederation they could even work as relays akin to the hub-spoke model but without a rigid hierarchy. Additionally, if there is some option to forward/accept everything, this could allow new smaller instances to bootstrap their content, much like how Mastodon relays work.

Picking which instance to initially send it to might involve implementing some kind of health check, though, which I think is already planned since there's a lot of just dead instances.

jrussek commented 1 year ago

I believe I may have a solution to this based on some of the ideas in this issue and some cues from how Mastodon relays work: opt-in server confederation.
* Two or more small instances can list each other as co-federated (must be opt-in on both instances)

* The list of instances that instances cofederate with is federated to other instances

* When forwarding activities, a non-cofederated instance will lookup if an instance has cofederators and will no longer send that activity to the other instances the activity is addressed to

* The instance will then forward that activity to cofederated instances it is addressed to
This way, many small instances can pool together their userbase. If some instances set themselves up as open cofederation they could even work as relays akin to the hub-spoke model but without a rigid hierarchy. Additionally, if there is some option to forward/accept everything, this could allow new smaller instances to bootstrap their content, much like how Mastodon relays work.

Picking which instance to initially send it to might involve implementing some kind of health check, though, which I think is already planned since there's a lot of just dead instances.

I agree that a small set of instances "cofederating" is a handy way to encapsulate the problem better and can probably be implemented "easier" - but there's a lot of complexity in dealing with unreliable communication in a network. Many things can fail (what if the instance that gets the activity never forwards it? What if one of them is flaky? How do you keep the list of cofederated instances consistent?).

imho might as well look at an established gossip protocol since they are specifically built to deal with these issues. (And already exist).

But on a more existential note.. are the devs actually interested in these considerations?

RocketDerp commented 1 year ago

But on a more existential note.. are the devs actually interested in these considerations?

I'm often left asking myself that question at the end of each day. Is lossy message delivery considered core to the project values.

WayneSheppard commented 1 year ago

Is lossy message delivery considered core to the project values.

Lossy is fine if we are talking about memes or cat pictures. But lossy would be terrible for support or serious discussion communities.

Nutomic commented 1 year ago

We are working on optimizations to activity sending, that should resolve scaling problems with federation. I dont see any need to make fundamental changes to the way federation works.

LemmyNet / lemmy