FIP-15: Link Defragmentation

[adityapk00]

Type: Implementation
Author: [Aditya Kulkarni] (@adityapk00 )

Abstract

Link Defragmentation is a new process that can reclaim space in a Link store. A new "CompactStateLinkMessage" is added represent the full state of a Link store for an fid. It will effectively compact the store by pushing out old LinkRemove messages, reducing the storage space required.

Problem

In our CRDT stores, delete messages occupy the same storage space as the add message. Deleting doesn't actually reduce the space used and users will eventually run out of space. When this happens, the CRDT evicts the oldest messages. This is actually reasonable for casts and reactions where the oldest content is less relevant and eventually all the delete messages get cycled out.

It is much more problematic for follows where the oldest follows might be the most relevant. One way to sole this is to re-sign links so that the adds appear after the removes. Warpcast implements this and will periodically resign all LinkAdd messages with a higher timestamp than the LinkRemove, forcing the Removes to get evicted first when limits are reached. The downside of this approach is that it creates a lot of sync thrash.

For some users, thousands of messages are resigned periodically to reclaim a few slots of storage space. This is creating issues where users are seeing their data get out of sync because the high volume of message changes is triggering rate limits and creating other problems.

Specification

A user can create a new type of message called CompactStateLinkMessage which contains the full state of the Link store. State here refers to all the users being followed, so it is simply a list of all fids that the user should be following. It "defragments" the Link store by cleaning up all old LinkRemove references.

message CompactStateLinkMessageBody {
  string type = 1; // Type of link <= 8 chars
  repeated uint32 target_fids = 2;
}

If the user's store is filled with a lot of removes, they can simply issue a new CompactStateLinkMessage with a list of all the fids they want to be following. When the hub receives this message it will:

1. Drop any previous CompactStateLink message.
2. Check that the the number of target_fids <= 10 * STORAGE_UNITS * LINKS_PER_STORAGE_UNIT (currently: 250,000)
3. Prune any LinkRemove messages where linkRemove.timestamp < compactStateMessage.timestamp
4. Prune any LinkAdd messages where linkAdd.timestamp < compactStateMessage.timestamp && linkAdd.targetFid NOT IN compactStateMessage.targetFids.

This enables users to issue a single message which cleans up their state instead of having to resign and re-issue every LinkAdd message. A bonus side effect is that CompactStateLinkMessages can be used to discover missing LinkAdds that can be proactively synced.

If a user's Link set has no CompactStateLinkMessage there is no change to the set rules. But if a message is currently present in the set, the following rules apply:

1. If the message is a LinkAdd and msg.timestamp < compactStateMessage.timestamp, it is merged only if msg.targetFid IS IN compactStateMessage.targetFids.
2. If the message is a LinkRemove and If msg.timestamp < compactStateMessage.timestamp, it is ignored.
3. If msg.timestamp > compactStateMessage.timestamp normal rules apply

Storage Considerations

The CompactStateLinkMessage will be large since it includes a list of fids. For a full link store this can be 2,500 fids and the message would roughly be 10 kB in size. Assuming that all users have a single storage unit this would roughly increase storage space by ~ 3% for compacted fids. A CompactStateLinkMessage cannot exceed 250,000 fids or 10 storage units.

Release

The target release for this proposal is protocol version 5/1/2024.

Backwards compatibility for hubs

Older hubs will ignore the CompactStateMessages, and will temporarily fall out of sync from the network, so upgrading is recommended.

Backwards compatibility for consumers

APIs

If you have downstream apps, you don't need to specifically store a CompactStateMessage if you are handling all the LinkAdd / LinkRemoves. You can query the getLinksByFid or getLinksByTarget and that will return the full set of all valid LinkAdd messages.

Events

When the hub merges a CompactStateMessage, it will generate a hub event like it does for all messages. The event will contain the CompactStateMessage as the mergedMessage, along with any conflicted out messages in the deletedMessages field. This will include any previous CompactStateMessage, all LinkRemoves and LinkAdds that were removed as a part of the compaction

[vrypan]

It is not clear to me: Do we give Warpcast the power to re-define the Links of all FIDs?

1. If this is the case, this breaks the whole concept of decentralization, censorship resistance and having a permissionless protocol.
2. Who will sign compactStateMessage? Is this a normal signer?

It seems to me that the problem is not at the protocol level (add/remove messages), but on the implementation level (removed messages occupy more space in the db than they should/could). Why would this be fixed by a protocol change and not an implementation change?

I may be missing something, please explain if I got everything wrong :-)

[vrypan]

I think you are right about trust assumptions.

However, there is important information pruned.

• When did I follow/unfollow this account? This can't be answered any more.
• Who were my first 10 followers?
• How many people unfollowed me after I casted X?
• I think there is a signer that is acting maliciously, and removes my Links to accounts that support Y. I'm sure I followed that account, who signed the unfollow? Or is it a supercast bug? How can I check?

Side note: I think that the naming is part of my original confusion. You name the message CompactStateMessage because this is what you want to achieve, but if I understand correctly, what it describes is more like LinkRemoveBulk. Is this correct?

[vrypan]

I'm thinking of a case where I use multiple farcaster apps: Some typical apps like Warpcast, Supercast and some bots that for example unfollow accounts that have not casted for very long, or auto-follow accounts that fit certain criteria (high engagement in a channel, or specific onchain actions like holding more than X from an ERC20, or buying my NFT). At some point I realize that something does not seem right with the accounts I follow. How can I check which signer sent each follow/unfollow message? This information is lost after compacting takes place.

Or maybe I want to analyze hub activity to identify accounts that follow/unfollow just to attract attention, or send some other social signal. Can I do this?

I guess my point is that signer, signature, etc.. fields seem to have more value to me than you. Especially if you look at the network from Warpcast's pov, and you say "it's the same thing repeating, a Warpcast signer". But are we designing the protocol with the assumption that the major client will always be Warpcast, and the rest are outliers?

[adityapk00]

However, there is important information pruned.
Pruning will happen irrespective of whether there are CompactStateMessages (messages are being pruned right now every 2 hours for fids that have hit their storage limits). A compactstatemessage won't change that.

But your larger point is a good one - It does make sense to have a service that can "archive" old/pruned messages to answer questions like you have. I'd even pay for such a service. It could be easily built with existing hub + shuttle + postgres

[adityapk00]

Also note that the "repeating" signers aren't necessarily warpcast - Supercast can sign and merge a CompactStateMessage just fine (and I expect they will). My point was that instead of supercast repeating the signature + signer field on 2500 messages, they put it on 1 message. Also note that the signature on the CompactStateMessage doesn't change the signatures or signer on the existing LinkAdd messages of the targetFids - They will continue to exist and be queryable as they are now (and not get pruned or anything)

[vrypan]

Yes, but a) I can pay for more storage and b) it happens to the oldest messages.

[vrypan]

But your larger point is a good one - It does make sense to have a service that can "archive" old/pruned messages to answer questions like you have. I'd even pay for such a service. It could be easily built with existing hub + shuttle + postgres

There is no guarantee that such a service will actually archive all messages. Any connectivity issue with Warpcast hubs (or any other hub that receives a lot of original messages, like neynar) would result in messages being pruned (compacted) before they even reach my archiving hub. This is not the case today. If I run a replicator today, it will store everything that's posted on the network, even if there are long periods of hub connectivity issues.

[adityapk00]

If I run a replicator today, it will store everything that's posted on the network, even if there are long periods of hub connectivity issues.

This will continue to be true even after CompactStateMessages. Any LinkAdds / LinkRemoves removed as a part of the CompactStateMessage are "pruned", so they will be stored in the replicator

[vrypan]

They are stored on the replicator connected to the hub that received them. For the rest, there is no guarantee.

Example: My hub+replicator is offline for 24h. I may never receive these messages, because by the time I reconnect, the rest of the hubs have already pruned them (due to Compacting).

[varunsrin]

I answered this in the other thread

[vrypan]

Maybe I'm missing something. Let's say this FIP is implemented.

Then I follow a FID. Two days later I unfollow them. What kind of record will hubs have of these two actions, a week later? Will the timestamp and signer (i.e. app used) of my original follow and unfollow exist?

My understanding is that the only onhub record will be a CompactStateMessage that indicates that at some point in time before it was posted, I unfollowed this FID. Am I wrong?

[varunsrin]

There are two cases - one where your storage is full of LinkAdd and LinkRemove messages and one where it isn't.

If you still have space, there is no change from today's behavior. The hub will have a LinkRemove message with the correct timestamp. There will be no trace of the LinkAdd message (this is the current behavior before this FIP is implemented).

If you are out of space, there is still no change. When you issue the LinkRemove your oldest Link* message will be deleted because you are out of space. (this is the current behavior before this FIP is implemented)

The only thing that changes is that you now have two options to solve this, instead of just one:

1. Buy more storage, and keep all the history.
2. Issue a compact message and get rid of the Removes so that you can store more Adds

[vrypan]

Thanks for clarifying.

The only thing that changes is that you now have two options to solve this

But who is "you"? Not me, the user. It's services like warpcast or supercast or neynar can make this decision. And even if I don't want to use the compacting option, and service that has a valid signer from me can do it (just to optimize their hubs for example).

My guess is that I will buy more storage to keep all history, and then one of the signers I have approved will send a CompactStateMessage and.. poof :-)

[vrypan]

I know I sound pedantic... The guy who is trying to find edge cases that don;t even exist in real life, or no one actually cares about.

But I have this feeling that some of the technical decisions made lately are more focused on solving very specific technical issues/challenges in a very specific state of the ecosystem/project/protocol and less focussed on how these decisions will affect the protocol in the future.

So, I'm at least trying to challenge them as much as I can.

[varunsrin]

If enough users want a feature, at least one client will ship it!

[vrypan]

I wanted to comment older FIPs were more principled, and recent ones feel narrower, but the newest version of this FIP is much better 👏

Minor:

I still think that the term CompactStateLink describes your motive and how you intend to technically use this message type, and not the message.

I think that something along the lines of LinkSnapshot or LinkSetState would be a better choice, because they describe what the user sees and not what the engineer wants to do with it. I mean, we could have this message type even if no compacting was taking place in the backend.

[vrypan]

LinkCheckpoint might also be a good term.

[vrypan]

I think there should be a third rule, for Add/Remove messages posted after the CompactStateMessage?

3. If msg.timestamp >= compactStateMessage.timestamp normal rules apply

[adityapk00]

Ah, yes. Thanks for catching this. Fixed

[vrypan]

Oh, one more thing: All rules imply that msg.data.body.type == CompactStateLinkMessageBody.type!

We only use type="follow" right now (as far as I know), but the protocol allows arbitrary Link types.

[vrypan]

And... this means that CompactStateLink messages are unique per type.
My CRDT could have one CompactStateLinkMessage with type="follow", one with type="mute" and one with type="coworker" for example.

[vrypan]

This FIP implies that there is a single type of Link messages (type="follow"). However, the protocol allows for arbitrary Link types that can be used to define various types of relationships between FIDs.

In order for this FIP to be compatible with the current protocol specs, there are a number of alternatives.

I think that both are reasonable and add minimum complexity, with A just being a more explicit version of the current proposal.

A. Narrow the scope of the FIP to Link.type="follow". Changes:

• Check that CompactStateLinkMessageBody.type=="follow". If not, ignore it.
• if a message is currently present in the set, an additional rule applies:
  msg.data.body.type == CompactStateLinkMessageBody.type

This means that CompactLinkMessages will only affect Link.type=="follow" and leave the rest of the LinkMessages unaffected.

B. Extend the scope to support any Link type.

To do so, I propose the following changes:

1. Update the message definition to support multiple Link types:

message CompactStateLinkMessageBody {
  repeated CompactStateLinkType states = 1;
}
message CompactStateLinkType {
  string type = 1; // Type of link <= 8 chars
  repeated uint32 target_fids = 2;
}

2. Update the message validation rule 2 to:
   Check that the the number of SUM(target_fids) <= 10 * STORAGE_UNITS * LINKS_PER_STORAGE_UNIT (currently: 250,000)

3. Update all rules to check that msg.data.body.type == CompactStateLinkMessageBody.state.type

[varunsrin]

cc @adityapk00 i think A is a reasonable approach, and maybe already implicitly in the current implementation

[0x330a]

Wrapping my head around this improvement for my own purposes and trying to document how to work with hub data. Currently it reads that hubs will, upon receiving a compaction message:

Prune any LinkAdd messages where linkAdd.timestamp < compactStateMessage.timestamp && linkAdd.targetFid NOT IN compactStateMessage.targetFids.

Should this be && linkAdd.targetFid IN compactStateMessage.targetFids? It sounds like upon receiving a compact message (representing the user's current followed fids) we would drop the LinkAdd messages that aren't in the list, but preserve the ones that are?

i.e.
[link add: fid 1] -> [link add: fid 2] -> [link add: fid 3] -> [compaction: fids [1,2]]
would end up being merged and containing the link message state:
[link add: fid 1] -> [link add: fid 2] -> [compaction: fids [1,2]]
while dropping the fid 3 follow we previously knew about?

It feels like it should end up pruning the messages that are IN the compaction message so you preserve all link adds / current links?

[vrypan]

You should think of compactStateMessage as "this is all the FIDs I follow" (this is the current state). Then, when a hub receives this message it should:

• Throw away all LinkRemove messages. (with an older timestamp, to make sure that even if the compactStateMessage is stuck in a hub and it propagates later, it does not mess with LinkRemove that were submitted later)
• Keep all LinkAdd messages with FIDs in the compactStateMessage and throw away the rest (again, only apply the rule to older messages, for the same reason as above).

[0x330a]

Just trying to understand if the intention was to keep all the previous link adds, treating the compaction more of a signalling message? Or whether the compaction was supposed to represent all of the linkadd messages while clearing out those messages to make room for more? Seems odd to allow the previous LinkAdd messages when the fid count in the compact link message has a capacity of ~250,000 now where the LinkAdds would only ever contain the 2,500-1 (as of now) but in that case I guess it just allows a buffer of LinkAdds to preserve recent history of timestamps? Just wanted to work out if it was intended behavior or a typo 😄

[vrypan]

Yes, you may consider it more like a signal. Check the Problem statement :-)

Problem example:

• Day 1, I follow my 10 best friends.
• Day 2, I follow 2,490 spam bots.
• Day 10, I realize following spam bots was stupid, and I unfollow them.

Before this FIP, my Link CRDT would look like this, from older to newer:

• 10 LinkAdd messages
• 2490 LinkRemove messages

Suppose that on Day 11, I follow two high quality accounts.

Before this FIP, hubs would append the two new LinkAdd messages and then prune the oldest two LinkAdd messages (2 of my best friends!) because I've crossed the 2,500 storage unit limit and my CRDT would look like:

• 8 LinkAdd
• 2490 LinkRemove
• 2 LinkAdd

After this FIP, if a compactStateMessage was sent on Day 10, my Link CRDT would look like this:

• 10 LinkAdd
• 2 LinkAdd

[0x330a]

Thanks for the extremely detailed response. I think I'll have to read more in the hub storage engine code to get a better understanding of it all

[0x330a]

A follow up question after reading through the hub storage code, it appears that secondary indices are built for tracking the GetLinksByTarget/linksByTargetFid.

index for tracking a link seems to be of the format:
<RootPrefix>:<fid>:<UserPostfix>:<targetKey?>:<type?>

while the secondary index for tracking links by target follows this format:
<RootPrefix>:<target_key>:<fid?>:<tsHash?>

Do these secondary indices get created or maintained during the handling of the compaction event? Could a user with say, 5000 LinkAdds (tracked in a CompactStateLinkMessage, plus 2500 LinkAdds) now have an inaccurate result returned by this secondary / reverse index?

It seems like the hub's age and knowledge of the original LinkAdds which could potentially not exist to a younger hub could lead two different servers returning different results for links by target despite having the same global link state per-fid?

May be a question for @adityapk00 to help me out 😅