Follow lists don't scale

[alexgleason]

This has been discussed many times but it remains a problem. Follow lists have:

• Race conditions. https://github.com/nostr-protocol/nips/pull/349
• Terrible database performance. Follow lists often exceed the maximum size for entries in the database, and indexing so many tags is problematic. https://github.com/nostr-protocol/nips/discussions/1104

A few people advocated for keeping kind 3 as they are. But I never really understood it. Every new developer I work with on Nostr asks me we tolerate this.

This impacts users. It's a terrible UX.

At some point somebody is going to build a very popular Nostr app and not care about the existing follow lists and steamroll over it, because it's objectively bad. And I wouldn't blame them for doing it.

I'm thinking maybe we should just be brave now and do it on our terms.

[mikedilger]

Keep in mind that we need to preserve some mechanism for people to derive web-of-trust scores. So if we replace them, we need to replace them with some sort of similar functionality and not just discard them.

I'm uncomfortable with creating a slew of little following events. What is my client supposed to do, download all of them from all relays every time it starts up? If not, there is no way for it to 'catch up' with one of these events that it missed from a month ago on some obscure relay. If so, it's a hell of a lot of traffic every time the client starts. I totally get how they would do with @staab says and prevent race conditions, but given the decenralized nature of nostr you'll never find your whole list which is just trading one problem for another.

EDIT: or maybe I should think about the outbox model.

[vitorpamplona]

you'll never find your whole list

I would argue this is a feature, not a bug. Different relays SHOULD have different follow lists. On the outbox model, it doesn't make any sense to send a copy of the WHOLE list, at every time it changes, to each of my follow's inbox relays, even to those whose presence in the list hasn't changed. Clients SHOULD send only the information pertinent to that p-tag. Individual Follow events would have been much better.

Also, a single follow list for all Nostr apps doesn't make any sense. Your Twitter Follows and your Spotify Follows are not the same.

[staab]

or maybe I should think about the outbox model.

I recently realized that a big part of making outbox work is supporting migrations from one relay to another. This would help a lot with user-local consistency.

I obviously agree with @alexgleason that this is one of the biggest problems with nostr, but I don't know how to solve it. Maybe if we could introduce a new concept (like how facebook friends are distinct from twitter follows) that creates new affordances that people really want, we could engineer it properly and get people to use it. I just don't know what either of those would be.

[fiatjaf]

It's not a big deal.

• Race conditions are a client bug. Other schemas might be less prone to bugs, but ultimately we can't fix bugs with specs, only with code.
• If contact lists are hard to index relays can just opt to not index them. In fact it wouldn't be hard to have a rule to not index tags when there are more than whatever number.

I agree they are not the ideal magic thing with no issues we all want, but if this is one of the biggest problems of Nostr then Nostr might be way too close to perfection, because to me it doesn't sound like such a big problem.

[mleku]

as i discovered today, it's also a problem that collides with websocket implementation limitations, the websocket libraries you use - @fiatjaf wsutil and fasthttp/websocket in combination seem to lead to a hard limit of 128kb/message which means no more than about 1000 entries in a follow list, and you should see how many times the relay is choking on these relay lists, websocket reports exceeded read limit and ping goes the connection and try again

in my opinion, follow events should be made that are just an add/remove and pubkey only

the clients have to simply make the requests for them, and the relays have to consider them as a unit of data in any garbage collection scheme, and give them special treatment such as pruning out any follow events that are now out of date, keeping only the head and a few at most behind it

as for the question about web of trust calculations, again, sorry, javascript programmers, you are gonna have to face some actual algorithms and garbage collection type programming in your future

because i have limited time to do things, i'm just throwing out the baby with the bathwater, any event over 128kb is being rejected now, because my websockets can't hack it and i am pretty sure a lot of implementations can't either

[mterenzio]

A month or so ago I lost my whole follow list through some client bug. Insanity.

In the least there should be an event that is a backup follow list. I get that the list was probably present somewhere else but it would have been difficult for me to find it.

[arthurfranca]

There is already a solution to this: lists made of the sum of individual events anchored by d tag set to the pubkey and n tag set to the list name (#784 unbound lists). From @vitorpamplona's #761 that uses such lists, here's an example:

{
  "kind": 30382, // This is a kind for public relationship info between the signer and another user
  "pubkey": "<me>",
  "tags": [
    ["d", "<another-user-pubkey>"],
    ["n", "follow"], // A "follow" "n" tag turns this event into a kind 3 equivalent entry
    ["n", "friend"], // He is part of may "Friends" list
    ["n", "close-friend"], // He is also part of my smaller "Close Friends" list
    ["n", "contact"], // My contacts are users to whom I've sent DMs or started an one-to-one audio/video call
    // ...other metadata describing the relationship
    ["T", "3:driver"] // This is using an unreleased spec to rate this user as a great driver
  ],
  "content": ""
  // ...other fields
}

But it would be very hard to make clients migrate from kind:3 to this. Maybe we could use this for new lists such as friends list ("friend" n tag set to kind:30382 events).

[alexgleason]

Very cool @arthurfranca, that seems useful.

However, I liked the atomic follow events in https://github.com/nostr-protocol/nips/pull/349 more, and I am sad that kind kind 10 and 11 got steamrolled by another NIP when a core feature is struggling.

Follows should not be metadata of another event type, but a dedicated event.

[vitorpamplona]

Unbound lists are a lot simpler than kind10,11 to me: the query by n is already the follow list. There is no added benefit to making a 3-kind filter and then merging the incoming kind 10 and 11 into kind 3 to assemble the list.

[mleku]

why can't it just me a simple kind, with a pubkey as the follower, and the followed pubkey is in a tag "follows"

it is not difficult to filter this

{"authors":"youkey","kinds":[#followeventkind]}

every time you want to unfollow, you substitute the tag with "unfollow" and the relay knows it can remove all references from you to the follow

the only problem then is how some people seem to want to follow half of nostr, so how do you work with the limits in requests? make an exception on this one perhaps, to be unlimited, but treat unfollows as delete and remove them from the database maybe?

the size of the events is astounding, i mean over 500kb... a clear argument for what benefit there would be to switch over to base64 instead of hex for everything as well (1/3 less space in messages)

but once a client has cached these, it can segregate these events from the general pool so it never loses them and it only adds them or removes them one by one and not in a blob

i don't think it matters that much if one or two fall out compared to losing a whole change set of several weeks past

i'm pretty sure that some relays are struggling with the size of some users follow lists, and other lists, and actually it's not just kind 3s that are gonna be a problem but all lists in general, which all should be constructed via single addition/removal events, this is more interactive and more resilient and more likely to propagate in any case

i think clients just better get on it, this is not hard stuff to write in code, already requests aggregate by users, by communities, by groups, and by lists in requests that sometimes are pretty ridiculous too, i mean

@arthurfranca i like the general idea of this, i don't think there is any need to specify too much more than list names to attach a pubkey to though

[mikedilger]

There are enough cooks in this kitchen for me to get involved. I will wait for dev consensus and follow.

But as to 128kb limits, I have only run into this in software that is configurable, and was configured to have that low limit. Cameri reported people with >2k followers were losing data at a 128kb cutoff. But tunstenite (rust) has a 64 MB default cutoff, and gossip is configured with a default 1 MB cutoff. The WebSocket spec itself allows a u64, so huge really. Anything cutting off at 128kb can probably be configured to use a larger value. BUT... this is probably moot given a move away from kind-3, which I support in principle. Carry on.

[vitorpamplona]

The case for #761 is quite simple: Every use case can benefit from it's own contact list. However, that contact list is just slightly different than kind 3. If kind3 is heavy and every use case creates its own, then the growth is quadratic.

A reddit follows of a user is different than a twitter follows, which is different from a tiktok follows. The user is still likely to follow largely the same people but remove a few that don't post interesting stuff in that medium. This means that the giant lists of kind3 will be copied and pasted into many NIP-51 lists.

The use of unbound lists or event sets #784 inverts the space use: Don't duplicate the hex keys in every NIP-51 list, just create one event per key and add that key into as many lists as possible by adding an n tag. n tag names are smaller than hex keys. So the space savings are huge.

On top of that, we solve the race condition, the transfer and re-indexing costs of changing a huge list of key-values just to add and remove single keys.

[alexgleason]

@vitorpamplona #761 is definitely good. It's almost the same as Mastodon API's "Relationship" entity: https://docs.joinmastodon.org/entities/Relationship/ So the fact other people have done this shows a clear need for it.

But Nostr is supposed to be a simple protocol. Following somebody is a very basic action. So you should be able to create a follow event without having to think about and understand the concept of a Relationship.

[vitorpamplona]

I don't think they need to understand the concept of a relationship. Clients can start as simple as the d=pubkey and n=follows. No other tags are required.

That would be the default action for the Follow button on Amethyst, for instance.

But the same event is there to handle other lists as well.

[staab]

I think I like follow sets. They are simple, efficient, and support the pattern I originally proposed in #349 They do make migration more difficult, since we'd be ditching not only kind 3, but also ten or so other list kinds.

[mleku]

There are enough cooks in this kitchen for me to get involved. I will wait for dev consensus and follow.

But as to 128kb limits, I have only run into this in software that is configurable, and was configured to have that low limit. Cameri reported people with >2k followers were losing data at a 128kb cutoff. But tunstenite (rust) has a 64 MB default cutoff, and gossip is configured with a default 1 MB cutoff. The WebSocket spec itself allows a u64, so huge really. Anything cutting off at 128kb can probably be configured to use a larger value. BUT... this is probably moot given a move away from kind-3, which I support in principle. Carry on.

yeah, i've set mine to 4mb now, and it's happy, everything goes in... semisol sent me a giant jsonl and it's been invaluable in stress testing and bug catching

also, yes, using the same model for other things is a bad idea... there just is no need for so many things in one event, it interferes with the scheduling of packets when you have a sharp difference in one stream in the multiplex versus the majority, and there just is no reason for it, like i say, client devs, learn how to code

[mikedilger]

As for scaling, I think lots of little events has worse scaling than one big event because there is more total data.

As for race conditions, we could solve them in the following way:

1) Clearly define which relay(s) the user stores their following list on. Clients must fetch the relay list first to make sure they are looking at the right relays.

2) If a client fails to fetch the current following list, instead of creating a new empty one it should ask the user. New users will say "yes I'm new go ahead" and everyone else will say "hang on! don't do that! I'm already following lots of people!" In the latter case the update to "follow this person" will have to be refused "we can't do that right now because we couldn't find your follow list".

As long as a user was not simultaneously operating two clients and actively trying to race-condition against themselves, nobody would experience the clobber situation anymore.

[alexgleason]

As for scaling, I think lots of little events has worse scaling than one big event because there is more total data.

At least we can delete old events to free up space. Big follow lists exceed the page size of databases and have to be broken up on multiple pages, slowing down queries. Some databases have size limitations and make you break it up in your own code.

Kind 3 is basically NIP-95 at this point. Why don't we just base64 encode files and upload them to relays?

[alexgleason]

The scaling issue is the number of users following each other on the network, having increasingly large follow lists. Not the total amount of disk space used by relays.

[vitorpamplona]

Kind 3 is basically NIP-95 at this point. Why don't we just base64 encode files and upload them to relays?

Yeah, why not? :)

[mleku]

wut is nip-95 goddammit

also why can we not just migrate to a single follow per event model?

keeping complete lists is client business not relay

[fiatjaf]

At least we can delete old events to free up space.

You wouldn't be able to delete anything in this case.

Big follow lists exceed the page size of databases and have to be broken up on multiple pages, slowing down queries.

I don't see why, the full event shouldn't be indexed in any reasonable scenario, only the pubkey and kind, and maybe you want a different index entry for each tag but honestly relays should skip doing that for kind:3s.

Kind 3 is basically NIP-95 at this point. Why don't we just base64 encode files and upload them to relays?

All events are NIP-95 free storage relay abuse, if the issue is disk usage then multiple events use more space than a single big event.

[fiatjaf]

keeping complete lists is client business not relay

Makes sense, but you're talking as if the relays were already overburdened and clients were lazy when in fact the opposite is true. Clients are doing way too much work and relays are very simple stupid code. They could be doing more.

[staab]

I had another idea for how to solve this I thought I'd throw out there. What if we adapted follow sets to kind 3 by making kind 3 parameterized replaceable rather than replaceable?

This would be backwards-compatible, since missing d tags on parameterized events should already fall back to empty strings. Old clients could keep doing their thing, but updated clients could publish to a temporary or device-specific follow list as well by using a different d tag.

The difficulty this creates is cleaning up the alternative follow lists when they're no longer useful. But maybe the rule could be "use the latest blank-d-tag kind 3, plus all subsequent non-blank-d-tag kind 3s".

Relay implementations may also have to be updated to support this, which could cause trouble.

[arthurfranca]

@fiatjaf I don't see why, the full (NIP-51) event shouldn't be indexed in any reasonable scenario, only the pubkey and kind, and maybe you want a different index entry for each tag but honestly relays should skip doing that for kind:3s.

This (don't index tags of NIP-51 lists) makes sense. Yet, people wanna know the number of followers.

I came to the conclusion that #784 (Event Sets) may be good, not to replace kind:3 (nor other NIP-51 lists) but to be sent (individual set entry) to the user you've just (un)followed's read relays.

Frankly, #784 brings other problems such as relays deleting old entries and are better as the canonical list JUST IF the list can grow very very big, such as the "contact" set ("mute" seems like a good fit too). For other cases, use event sets just for notification and count purposes.

If this is the way, I think we should add these considerations somehow to NIP-51 and #784.

What do you think?

[arthurfranca]

But maybe the rule could be "use the latest blank-d-tag kind 3, plus all subsequent non-blank-d-tag kind 3s

@staab Yo dawg, I heard you like lists, so we put a list in your list so you can list while you list =D

[arthurfranca]

@mikedilger As for scaling, I think lots of little events has worse scaling than one big event because there is more total data.

It just occurred to me that maybe sets aren't that bad space-wise compared to NIP-51 cause a single event can put the same item in many sets/lists at once. Example of adding a pubkey to 3 sets/lists:

{
  "kind": 30382,
  "pubkey": "<me>",
  "tags": [
    ["d", "<another-user-pubkey>"],
    ["n", "follow"],
    ["n", "friend"],
    ["n", "Best Friends Forever"]
  ],
  // ...other fields
}

[raymonostr]

Puuh, that's a lot to read here. I think from the most outer perspective ... follow lists with > 1000 entries don't make sense. It's something different then and should be named different. Actually that huge lists (like Gigi's) break the bearable traffic of mobile webclients.

[mleku]

Puuh, that's a lot to read here. I think from the most outer perspective ... follow lists with > 1000 entries don't make sense. It's something different then and should be named different. Actually that huge lists (like Gigi's) break the bearable traffic of mobile webclients.

as far as i know, NIP-81 is a spec for creating simple one-by-one CRDTs for relations between one user and another, trying to change the existing lists is probably futile, but adding a new feature that lets users curate all kinds of lists, and giving clients the possibility of designing new more fine grained, semantic relations is probably the way to go