Redis check whether a string is within range

Question

I have a Set named Ranges stored ranged-string, eg: "0-20", "30-50", "60-70", the size of Ranges may be big. If I have two inputs (start, end), how can I performantly check whether they are within any range? For example, with 10 and 15 as inputs, they are within 0-20 range, with 15 and 23 as inputs, they are not within any range.

// brute approach(using smembers)
async function isWithinRangeBrutely(start: number, end: number) {
  const members = await redis.smembers("Ranges");
  return members.some(m => {
    const [redisStart, redisEnd] = m.split("-").map(Number);
    return start >= redisStart && end <= redisEnd;
  });
}
// Then I came across this sscan approach(using sscan)
// ignore the grammer, it's just one of the redis clients in nodejs
function isWithinRangeSmartly(start: number, end: number) {
    return new Promise((resolve, reject) => {
        const stream = redis.sscanStream("Ranges");
        stream.on("data", (ranges: string[]) => {
            const isWithinRange = ranges.some(r => {
                const [redisStart, redisEnd] = r.split("-").map(Number);
                return start >= redisStart && end <= redisEnd;
            });
            if (isWithinRange) {
                resolve(true);
                stream.end();
            }
        });
        stream.on("end", () => resolve(false));
    });
}

However, as I mentioned, Ranges Set may be very big, both smembers and sscan approach are neither perfect(isWithinRange requests are so frequent). I wonder if using lua script is better or is there a better data structure design for this purpose?

Answer 1

You should save your ranges with Sorted Set, instead of set, so that you can do range search, which is must faster than iterating all members of the set.

Add ranges into sorted set, with the end of the range as score, and the range info as member.

ZADD ranges 20 "0-20" 50 "30-50" 70 "60-70"

Search by range, i.e. get the first item whose end is larger or equal to the end of your input:

ZRANGEBYSCORE ranges 15 inf limit 0 1

If it returns empty array reply, the input is not within any range. Otherwise, check the start of the returned range to see if the input is within the range.