java-topology/docs/tickets/rocketchat-0001-send-notifications-mention-ids-array-scan-per-subscriber.md

rocketchat-0001: mentionIds.includes() + usersInThread.includes() O(n) per subscriber in message notification fanout

Target: RocketChat/Rocket.Chat Severity: HIGH CWE: CWE-407 (Inefficient Algorithmic Complexity) File: apps/meteor/app/lib/server/lib/sendNotificationsOnMessage.ts Lines: 79 (mentionIds.includes), 372 (usersInThread?.includes) Status: PATCHED

Description

sendMessageNotifications() iterates over all room subscriptions (up to thousands for large channels) and for each subscriber calls sendNotification() which does mentionIds.includes(subscription.u._id) — an O(M) scan of the mention-IDs array — every iteration. The outer subscriptions.forEach at line 364 also passes usersInThread?.includes(subscription.u._id) inline.

Both mentionIds and usersInThread are plain string[] arrays. For a channel with S subscribers and M mentions / T thread participants the work is O(S × M) and O(S × T) respectively. On a large room (S = 10 000, M = 50, T = 200) that is 500 000 + 2 000 000 = 2.5 M unnecessary comparisons per message.

Pattern	File:Line	Array	Outer loop
mentionIds.includes(subscription.u._id)	sendNotificationsOnMessage.ts:79	string[]	subscriptions.forEach
usersInThread?.includes(subscription.u._id)	sendNotificationsOnMessage.ts:372	string[]	subscriptions.forEach

Root cause

// sendNotificationsOnMessage.ts:364 (outer loop over ALL room subscribers)
subscriptions.forEach(
    (subscription) =>
        void sendNotification({
            ...
            mentionIds,                                    // passed as-is
            hasReplyToThread: usersInThread?.includes(subscription.u._id),  // O(n) per iter
        }),
);

// sendNotificationsOnMessage.ts:79 (inside sendNotification, called per subscriber)
const hasMentionToUser = mentionIds.includes(subscription.u._id);  // O(n) per iter

Fix

Pre-build Set<string> before the loop:

const mentionIdSet = new Set(mentionIds);
const usersInThreadSet = new Set(usersInThread ?? []);

subscriptions.forEach(
    (subscription) =>
        void sendNotification({
            ...
            mentionIdSet,
            hasReplyToThread: usersInThreadSet.has(subscription.u._id),   // O(1)
        }),
);

// inside sendNotification:
const hasMentionToUser = mentionIdSet.has(subscription.u._id);   // O(1)

Complexity

	Before	After
mentionIds check	O(S × M)	O(S)
usersInThread check	O(S × T)	O(S)
Combined	O(S × (M + T))	O(S)

Speedup at S=10 000, M=50, T=200: ~250× on mention check, ~200× on thread check.