[PATCH damus v1] Chunk home filters to avoid hitting max filter item limits

[Daniel D’Aquino]

When a user is following several accounts, they may get a stale feed
caused by the subscription request being rejected by relays (due to max filter item limits).

This commit implements a fix that gets around the issue by
creating several chunked filters for the home feed event and contact
metadata subscriptions.

This is a short to medium-term practical fix, where we get around the
practical limitations imposed by most relays. In the future we should
work on longer-term solutions, which will likely require protocol improvements

Main Test
---------

Procedure:
1. Login with Elsat's npub (Or some account that follows about 2K people)
2. Check the home feed. There should be fresh notes.

REPRO:
Device: iPhone 15 simulator
iOS: 17.4
Damus: 1.9 (3) (0d9954290a674e1520164c08050bcfb9291fdd05)
Results:
- No fresh notes, most recent post is from several hours ago (Feed is stale)

FIX TEST:
Device: iPhone 15 simulator
iOS: 17.4
Damus: This commit
Results:
- Fresh notes appear, most recent post is from a few seconds ago.

Other testing:
--------------

- New automated test passing
- All other automated tests passing
- Tested scrolling down the feed on these conditions:
- Device: iPhone 13 Mini
- iOS: 17.4.1
- Accounts:
- One with about 160 contacts and 10 relays (Daniel D’Aquino)
- One with about 1K+ contacts and 9 relays (Freedom Smuggler)
- One with about 981 contacts and 6 relays (jb55)
- Elsat's account (2K+ accounts and 8 relays)
- Result: None of those were stale

Changelog-Fixed: Fix stale feed issue when follow list is too big
Closes: https://github.com/damus-io/damus/issues/2194
Signed-off-by: Daniel D’Aquino <dan...@daquino.me>
---
damus.xcodeproj/project.pbxproj | 8 ++++
damus/Models/HomeModel.swift | 9 +++-
damus/Nostr/NostrFilter.swift | 64 +++++++++++++++++++++++++
damus/Util/Extensions/Array.swift | 26 +++++++++++
damusTests/NostrFilterTests.swift | 77 +++++++++++++++++++++++++++++++
5 files changed, 182 insertions(+), 2 deletions(-)
create mode 100644 damus/Util/Extensions/Array.swift
create mode 100644 damusTests/NostrFilterTests.swift

diff --git a/damus.xcodeproj/project.pbxproj b/damus.xcodeproj/project.pbxproj
index e7506b62..a32df7d0 100644
--- a/damus.xcodeproj/project.pbxproj
+++ b/damus.xcodeproj/project.pbxproj
@@ -465,6 +465,8 @@
D72A2D022AD9C136002AFF62 /* EventViewTests.swift in Sources */ = {isa = PBXBuildFile; fileRef = D72A2CFF2AD9B66B002AFF62 /* EventViewTests.swift */; };
D72A2D052AD9C1B5002AFF62 /* MockDamusState.swift in Sources */ = {isa = PBXBuildFile; fileRef = D72A2D042AD9C1B5002AFF62 /* MockDamusState.swift */; };
D72A2D072AD9C1FB002AFF62 /* MockProfiles.swift in Sources */ = {isa = PBXBuildFile; fileRef = D72A2D062AD9C1FB002AFF62 /* MockProfiles.swift */; };
+ D72E12782BEED22500F4F781 /* Array.swift in Sources */ = {isa = PBXBuildFile; fileRef = D72E12772BEED22400F4F781 /* Array.swift */; };
+ D72E127A2BEEEED000F4F781 /* NostrFilterTests.swift in Sources */ = {isa = PBXBuildFile; fileRef = D72E12792BEEEED000F4F781 /* NostrFilterTests.swift */; };
D7315A2A2ACDF3B70036E30A /* DamusCacheManager.swift in Sources */ = {isa = PBXBuildFile; fileRef = D7315A292ACDF3B70036E30A /* DamusCacheManager.swift */; };
D7315A2C2ACDF4DA0036E30A /* DamusCacheManagerTests.swift in Sources */ = {isa = PBXBuildFile; fileRef = D7315A2B2ACDF4DA0036E30A /* DamusCacheManagerTests.swift */; };
D7373BA62B688EA300F7783D /* DamusPurpleTranslationSetupView.swift in Sources */ = {isa = PBXBuildFile; fileRef = D7373BA52B688EA200F7783D /* DamusPurpleTranslationSetupView.swift */; };
@@ -1394,6 +1396,8 @@
D72A2CFF2AD9B66B002AFF62 /* EventViewTests.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = EventViewTests.swift; sourceTree = "<group>"; };
D72A2D042AD9C1B5002AFF62 /* MockDamusState.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = MockDamusState.swift; sourceTree = "<group>"; };
D72A2D062AD9C1FB002AFF62 /* MockProfiles.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = MockProfiles.swift; sourceTree = "<group>"; };
+ D72E12772BEED22400F4F781 /* Array.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = Array.swift; sourceTree = "<group>"; };
+ D72E12792BEEEED000F4F781 /* NostrFilterTests.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = NostrFilterTests.swift; sourceTree = "<group>"; };
D7315A292ACDF3B70036E30A /* DamusCacheManager.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = DamusCacheManager.swift; sourceTree = "<group>"; };
D7315A2B2ACDF4DA0036E30A /* DamusCacheManagerTests.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = DamusCacheManagerTests.swift; sourceTree = "<group>"; };
D7373BA52B688EA200F7783D /* DamusPurpleTranslationSetupView.swift */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.swift; path = DamusPurpleTranslationSetupView.swift; sourceTree = "<group>"; };
@@ -2575,6 +2579,7 @@
D72927AC2BAB515C00F93E90 /* RelayURLTests.swift */,
D753CEA92BE9DE04001C3A5D /* MutingTests.swift */,
4C2D34402BDAF1B300F9FB44 /* NIP10Tests.swift */,
+ D72E12792BEEEED000F4F781 /* NostrFilterTests.swift */,
);
path = damusTests;
sourceTree = "<group>";
@@ -2699,6 +2704,7 @@
children = (
7C95CAED299DCEF1009DCB67 /* KFOptionSetter+.swift */,
4C7D09752A0AF19E00943473 /* FillAndStroke.swift */,
+ D72E12772BEED22400F4F781 /* Array.swift */,
);
path = Extensions;
sourceTree = "<group>";
@@ -3255,6 +3261,7 @@
4CE8794829941DA700F758CC /* RelayFilters.swift in Sources */,
4CEE2B02280B39E800AB5EEF /* EventActionBar.swift in Sources */,
4C3BEFE0281DE1ED00B3DE84 /* DamusState.swift in Sources */,
+ D72E12782BEED22500F4F781 /* Array.swift in Sources */,
4C198DF529F88D2E004C165C /* ImageMetadata.swift in Sources */,
4CCEB7AE29B53D260078AA28 /* SearchingEventView.swift in Sources */,
4CF0ABE929844AF100D66079 /* AnyCodable.swift in Sources */,
@@ -3555,6 +3562,7 @@
4C8D00D429E3C5D40036AF10 /* NIP19Tests.swift in Sources */,
3A30410129AB12AA008A0F29 /* EventGroupViewTests.swift in Sources */,
501F8C822A0224EB001AFC1D /* KeychainStorageTests.swift in Sources */,
+ D72E127A2BEEEED000F4F781 /* NostrFilterTests.swift in Sources */,
B5B4D1432B37D47600844320 /* NdbExtensions.swift in Sources */,
3ACBCB78295FE5C70037388A /* TimeAgoTests.swift in Sources */,
D72A2D072AD9C1FB002AFF62 /* MockProfiles.swift in Sources */,
diff --git a/damus/Models/HomeModel.swift b/damus/Models/HomeModel.swift
index 5f040dc6..a4d95946 100644
--- a/damus/Models/HomeModel.swift
+++ b/damus/Models/HomeModel.swift
@@ -42,6 +42,10 @@ enum HomeResubFilter {
}

class HomeModel: ContactsDelegate {
+ // The maximum amount of contacts placed on a home feed subscription filter.
+ // If the user has more contacts, chunking or other techniques will be used to avoid sending huge filters
+ let MAX_CONTACTS_ON_FILTER = 500
+
// Don't trigger a user notification for events older than a certain age
static let event_max_age_for_notification: TimeInterval = EVENT_MAX_AGE_FOR_NOTIFICATION

@@ -545,7 +549,8 @@ class HomeModel: ContactsDelegate {
notifications_filter.limit = 500

var notifications_filters = [notifications_filter]
- var contacts_filters = [contacts_filter, our_contacts_filter, our_blocklist_filter, our_old_blocklist_filter]
+ let contacts_filter_chunks = contacts_filter.chunked(on: .authors, into: MAX_CONTACTS_ON_FILTER)
+ var contacts_filters = contacts_filter_chunks + [our_contacts_filter, our_blocklist_filter, our_old_blocklist_filter]
var dms_filters = [dms_filter, our_dms_filter]
let last_of_kind = get_last_of_kind(relay_id: relay_id)

@@ -598,7 +603,7 @@ class HomeModel: ContactsDelegate {
home_filter.authors = friends
home_filter.limit = 500

- var home_filters = [home_filter]
+ var home_filters = home_filter.chunked(on: .authors, into: MAX_CONTACTS_ON_FILTER)

let followed_hashtags = Array(damus_state.contacts.get_followed_hashtags())
if followed_hashtags.count != 0 {
diff --git a/damus/Nostr/NostrFilter.swift b/damus/Nostr/NostrFilter.swift
index 1310defa..4445f2e8 100644
--- a/damus/Nostr/NostrFilter.swift
+++ b/damus/Nostr/NostrFilter.swift
@@ -54,4 +54,68 @@ struct NostrFilter: Codable, Equatable {
public static func filter_hashtag(_ htags: [String]) -> NostrFilter {
NostrFilter(hashtag: htags.map { $0.lowercased() })
}
+
+ /// Splits the filter on a given filter path/axis into chunked filters
+ ///
+ /// - Parameter path: The path where chunking should be done
+ /// - Parameter chunk_size: The maximum size of each chunk.
+ /// - Returns: An array of arrays, where each contained array is a chunk of the original array with up to `size` elements.
+ func chunked(on path: ChunkPath, into chunk_size: Int) -> [Self] {
+ let chunked_slices = self.get_slice(from: path).chunked(into: chunk_size)
+ var chunked_filters: [NostrFilter] = []
+ for chunked_slice in chunked_slices {
+ var chunked_filter = self
+ chunked_filter.apply_slice(chunked_slice)
+ chunked_filters.append(chunked_filter)
+ }
+ return chunked_filters
+ }
+
+ /// Gets a slice from a NostrFilter on a given path/axis
+ ///
+ /// - Parameter path: The path where chunking should be done
+ /// - Parameter chunk_size: The maximum size of each chunk.
+ /// - Returns: An array of arrays, where each contained array is a chunk of the original array with up to `size` elements.
+ func get_slice(from path: ChunkPath) -> Slice {
+ switch path {
+ case .pubkeys:
+ return .pubkeys(self.pubkeys)
+ case .authors:
+ return .authors(self.authors)
+ }
+ }
+
+ /// Overrides one member/axis of a NostrFilter using a specific slice
+ /// - Parameter slice: The slice to be applied on this NostrFilter
+ mutating func apply_slice(_ slice: Slice) {
+ switch slice {
+ case .pubkeys(let pubkeys):
+ self.pubkeys = pubkeys
+ case .authors(let authors):
+ self.authors = authors
+ }
+ }
+
+
+ /// A path to one of the axes of a NostrFilter.
+ enum ChunkPath {
+ case pubkeys
+ case authors
+ // Other paths/axes not supported yet
+ }
+
+ /// Represents the value of a single axis of a NostrFilter
+ enum Slice {
+ case pubkeys([Pubkey]?)
+ case authors([Pubkey]?)
+
+ func chunked(into chunk_size: Int) -> [Slice] {
+ switch self {
+ case .pubkeys(let array):
+ return (array ?? []).chunked(into: chunk_size).map({ .pubkeys($0) })
+ case .authors(let array):
+ return (array ?? []).chunked(into: chunk_size).map({ .authors($0) })
+ }
+ }
+ }
}
diff --git a/damus/Util/Extensions/Array.swift b/damus/Util/Extensions/Array.swift
new file mode 100644
index 00000000..d77bd27a
--- /dev/null
+++ b/damus/Util/Extensions/Array.swift
@@ -0,0 +1,26 @@
+//
+// Array.swift
+// damus
+//
+// Created by Daniel D’Aquino on 2024-05-10.
+//
+
+import Foundation
+
+extension Array {
+ /// Splits the array into chunks of the specified size.
+ /// - Parameter size: The maximum size of each chunk.
+ /// - Returns: An array of arrays, where each contained array is a chunk of the original array with up to `size` elements.
+ func chunked(into size: Int) -> [[Element]] {
+ guard size > 0 else { return [self] }
+ return stride(from: 0, to: count, by: size).map {
+ Array(self[$0..<Swift.min($0 + size, count)])
+ }
+ }
+}
+
+extension Array where Element: Equatable {
+ mutating func removeAll(equalTo item: Element) {
+ self.removeAll(where: { $0 == item })
+ }
+}
diff --git a/damusTests/NostrFilterTests.swift b/damusTests/NostrFilterTests.swift
new file mode 100644
index 00000000..61f1327c
--- /dev/null
+++ b/damusTests/NostrFilterTests.swift
@@ -0,0 +1,77 @@
+//
+// NostrFilterTests.swift
+// damusTests
+//
+// Created by Daniel D’Aquino on 2024-05-10.
+//
+
+import XCTest
+@testable import damus
+
+final class NostrFilterTests: XCTestCase {
+ func testChunkedWithPubKeys() {
+ // Given a NostrFilter with a list of pubkeys
+ let test_pubkey_1 = Pubkey(hex: "760f108754eb415561239d4079e71766d87e23f7e71c8e5b00d759e54dd8d082")!
+ let test_pubkey_2 = Pubkey(hex: "065eab63e939ea2f2f72f2305886b13e5e301302da67b5fe8a18022b278fe872")!
+ let test_pubkey_3 = Pubkey(hex: "aa146d7c6618ebe993702a74c561f54fc046c8a16e388b828cb2f631a1ed9602")!
+ let test_pubkey_4 = Pubkey(hex: "2f7108dcd33fb484be3e09cea24a1e96868fbc0842e691ca19db63781801089e")!
+ let test_pubkey_5 = Pubkey(hex: "1cc7c458e6b565a856d7c3791f4eb5ca5890b1f2433f452ed7a917f9aa0e5250")!
+ let test_pubkey_6 = Pubkey(hex: "2ee1f46a847b6613c33fd766db1e64c7f727c63774fa3ee952261d2c03b81cf2")!
+ let test_pubkey_7 = Pubkey(hex: "214664a7ca3236b9dd5f76550d322f390fd70cc12908a2e3ff2cdf50085d4ef2")!
+ let test_pubkey_8 = Pubkey(hex: "40255b02f3d8ccd6178d50f5ce1c1ac2867b3d919832176957b021c1816fce2f")!
+ let pubkeys: [Pubkey] = [test_pubkey_1, test_pubkey_2, test_pubkey_3, test_pubkey_4]
+ let authors: [Pubkey] = [test_pubkey_5, test_pubkey_6, test_pubkey_7, test_pubkey_8]
+ let filter = NostrFilter(
+ pubkeys: pubkeys,
+ authors: authors
+ )
+
+ let chunked_pubkeys_filters_size_2 = filter.chunked(on: .pubkeys, into: 2)
+ XCTAssertEqual(chunked_pubkeys_filters_size_2.count, 2)
+ XCTAssertEqual(chunked_pubkeys_filters_size_2[0].pubkeys, [test_pubkey_1, test_pubkey_2])
+ XCTAssertEqual(chunked_pubkeys_filters_size_2[1].pubkeys, [test_pubkey_3, test_pubkey_4])
+ XCTAssertEqual(chunked_pubkeys_filters_size_2[0].authors, authors)
+ XCTAssertEqual(chunked_pubkeys_filters_size_2[1].authors, authors)
+
+ let chunked_pubkeys_filters_size_3 = filter.chunked(on: .pubkeys, into: 3)
+ XCTAssertEqual(chunked_pubkeys_filters_size_3.count, 2)
+ XCTAssertEqual(chunked_pubkeys_filters_size_3[0].pubkeys, [test_pubkey_1, test_pubkey_2, test_pubkey_3])
+ XCTAssertEqual(chunked_pubkeys_filters_size_3[1].pubkeys, [test_pubkey_4])
+ XCTAssertEqual(chunked_pubkeys_filters_size_3[0].authors, authors)
+ XCTAssertEqual(chunked_pubkeys_filters_size_3[1].authors, authors)
+
+ let chunked_pubkeys_filters_size_4 = filter.chunked(on: .pubkeys, into: 4)
+ XCTAssertEqual(chunked_pubkeys_filters_size_4.count, 1)
+ XCTAssertEqual(chunked_pubkeys_filters_size_4[0].pubkeys, [test_pubkey_1, test_pubkey_2, test_pubkey_3, test_pubkey_4])
+ XCTAssertEqual(chunked_pubkeys_filters_size_4[0].authors, authors)
+
+ let chunked_pubkeys_filters_size_5 = filter.chunked(on: .pubkeys, into: 5)
+ XCTAssertEqual(chunked_pubkeys_filters_size_5.count, 1)
+ XCTAssertEqual(chunked_pubkeys_filters_size_5[0].pubkeys, [test_pubkey_1, test_pubkey_2, test_pubkey_3, test_pubkey_4])
+ XCTAssertEqual(chunked_pubkeys_filters_size_5[0].authors, authors)
+
+ let chunked_authors_filters_size_2 = filter.chunked(on: .authors, into: 2)
+ XCTAssertEqual(chunked_authors_filters_size_2.count, 2)
+ XCTAssertEqual(chunked_authors_filters_size_2[0].authors, [test_pubkey_5, test_pubkey_6])
+ XCTAssertEqual(chunked_authors_filters_size_2[1].authors, [test_pubkey_7, test_pubkey_8])
+ XCTAssertEqual(chunked_authors_filters_size_2[0].pubkeys, pubkeys)
+ XCTAssertEqual(chunked_authors_filters_size_2[1].pubkeys, pubkeys)
+
+ let chunked_authors_filters_size_3 = filter.chunked(on: .authors, into: 3)
+ XCTAssertEqual(chunked_authors_filters_size_3.count, 2)
+ XCTAssertEqual(chunked_authors_filters_size_3[0].authors, [test_pubkey_5, test_pubkey_6, test_pubkey_7])
+ XCTAssertEqual(chunked_authors_filters_size_3[1].authors, [test_pubkey_8])
+ XCTAssertEqual(chunked_authors_filters_size_3[0].pubkeys, pubkeys)
+ XCTAssertEqual(chunked_authors_filters_size_3[1].pubkeys, pubkeys)
+
+ let chunked_authors_filters_size_4 = filter.chunked(on: .authors, into: 4)
+ XCTAssertEqual(chunked_authors_filters_size_4.count, 1)
+ XCTAssertEqual(chunked_authors_filters_size_4[0].authors, [test_pubkey_5, test_pubkey_6, test_pubkey_7, test_pubkey_8])
+ XCTAssertEqual(chunked_authors_filters_size_4[0].pubkeys, pubkeys)
+
+ let chunked_authors_filters_size_5 = filter.chunked(on: .authors, into: 5)
+ XCTAssertEqual(chunked_authors_filters_size_5.count, 1)
+ XCTAssertEqual(chunked_authors_filters_size_5[0].authors, [test_pubkey_5, test_pubkey_6, test_pubkey_7, test_pubkey_8])
+ XCTAssertEqual(chunked_authors_filters_size_5[0].pubkeys, pubkeys)
+ }
+}

base-commit: 0d9954290a674e1520164c08050bcfb9291fdd05
--
2.44.0

[William Casarin]

On Sat, May 11, 2024 at 01:13:48AM GMT, Daniel D’Aquino wrote:
>When a user is following several accounts, they may get a stale feed
>caused by the subscription request being rejected by relays (due to max filter item limits).
>
>This commit implements a fix that gets around the issue by
>creating several chunked filters for the home feed event and contact
>metadata subscriptions.

Clever solution! I thought about doing this but felt like it might be
too complicated, but this doesn't look too bad. It also feels like it's
kind of hacking around relay limits, but if it works it works!

>This is a short to medium-term practical fix, where we get around the
>practical limitations imposed by most relays. In the future we should
>work on longer-term solutions, which will likely require protocol improvements

definitely!

>Changelog-Fixed: Fix stale feed issue when follow list is too big
>Closes: https://github.com/damus-io/damus/issues/2194
>Signed-off-by: Daniel D’Aquino <dan...@daquino.me>
>---

Code looks great!

Reviewed-by: William Casarin <jb...@jb55.com>

> damus.xcodeproj/project.pbxproj | 8 ++++
> damus/Models/HomeModel.swift | 9 +++-
> damus/Nostr/NostrFilter.swift | 64 +++++++++++++++++++++++++
> damus/Util/Extensions/Array.swift | 26 +++++++++++
> damusTests/NostrFilterTests.swift | 77 +++++++++++++++++++++++++++++++
> 5 files changed, 182 insertions(+), 2 deletions(-)
> create mode 100644 damus/Util/Extensions/Array.swift
> create mode 100644 damusTests/NostrFilterTests.swift
>

[Daniel D'Aquino]

> On May 11, 2024, at 07:24, William Casarin <jb...@jb55.com> wrote:
>
> On Sat, May 11, 2024 at 01:13:48AM GMT, Daniel D’Aquino wrote:
>> When a user is following several accounts, they may get a stale feed
>> caused by the subscription request being rejected by relays (due to max filter item limits).
>>
>> This commit implements a fix that gets around the issue by
>> creating several chunked filters for the home feed event and contact
>> metadata subscriptions.
>
> Clever solution! I thought about doing this but felt like it might be
> too complicated, but this doesn't look too bad. It also feels like it's
> kind of hacking around relay limits, but if it works it works!
>
>> This is a short to medium-term practical fix, where we get around the
>> practical limitations imposed by most relays. In the future we should
>> work on longer-term solutions, which will likely require protocol improvements
>
> definitely!
>
>> Changelog-Fixed: Fix stale feed issue when follow list is too big
>> Closes: https://github.com/damus-io/damus/issues/2194
>> Signed-off-by: Daniel D’Aquino <dan...@daquino.me>
>> ---
>
> Code looks great!
>
> Reviewed-by: William Casarin <jb...@jb55.com>

Thanks! Pushed to `master` (46185c55d1dcc376842ca26e6ba47caa99a55b66)