Skip to main content

turnloop_redis/
routing.rs

1//! Cluster and Sentinel discovery helpers. The host owns per-node connections;
2//! redirects describe exactly where to retry and whether ASKING is required.
3use crate::{Error, resp::Value};
4#[derive(Debug, Clone, PartialEq, Eq)]
5pub struct Endpoint {
6    pub host: String,
7    pub port: u16,
8}
9#[derive(Debug, Clone, PartialEq, Eq)]
10pub struct Redirect {
11    pub slot: u16,
12    pub endpoint: Endpoint,
13    pub asking: bool,
14}
15impl Redirect {
16    pub fn parse(error: &Error) -> Option<Self> {
17        let mut parts = error.message.split_whitespace();
18        let asking = match parts.next()? {
19            "MOVED" => false,
20            "ASK" => true,
21            _ => return None,
22        };
23        let slot = parts.next()?.parse::<u16>().ok().filter(|n| *n < 16384)?;
24        let (host, port) = parts.next()?.rsplit_once(':')?;
25        if parts.next().is_some() {
26            return None;
27        }
28        Some(Self {
29            slot,
30            endpoint: Endpoint {
31                host: host.trim_matches(['[', ']']).into(),
32                port: port.parse().ok()?,
33            },
34            asking,
35        })
36    }
37}
38/// CRC16/XMODEM with Redis's first non-empty {...} hash tag rules.
39pub fn key_slot(mut key: &[u8]) -> u16 {
40    if let Some(open) = key.iter().position(|b| *b == b'{')
41        && let Some(close) = key[open + 1..].iter().position(|b| *b == b'}')
42        && close != 0
43    {
44        key = &key[open + 1..open + 1 + close];
45    }
46    let mut crc = 0u16;
47    for byte in key {
48        crc ^= u16::from(*byte) << 8;
49        for _ in 0..8 {
50            crc = if crc & 0x8000 != 0 {
51                (crc << 1) ^ 0x1021
52            } else {
53                crc << 1
54            };
55        }
56    }
57    crc % 16384
58}
59#[derive(Debug, Default)]
60pub struct SlotMap {
61    nodes: Vec<Endpoint>,
62    slots: Vec<Option<usize>>,
63}
64impl SlotMap {
65    pub fn new() -> Self {
66        Self {
67            nodes: Vec::new(),
68            slots: vec![None; 16384],
69        }
70    }
71    pub fn endpoint(&self, slot: u16) -> Option<&Endpoint> {
72        self.slots
73            .get(usize::from(slot))
74            .copied()
75            .flatten()
76            .and_then(|i| self.nodes.get(i))
77    }
78    fn assign(&mut self, start: u16, end: u16, node: Endpoint) -> Result<(), Error> {
79        if start > end || end >= 16384 {
80            return Err(Error::new("Invalid slot range"));
81        }
82        if self.slots.is_empty() {
83            self.slots.resize(16384, None);
84        }
85        let index = self
86            .nodes
87            .iter()
88            .position(|n| *n == node)
89            .unwrap_or_else(|| {
90                self.nodes.push(node);
91                self.nodes.len() - 1
92            });
93        self.slots[usize::from(start)..=usize::from(end)].fill(Some(index));
94        Ok(())
95    }
96    /// Atomic refresh: malformed maps never destroy the existing topology.
97    pub fn update_slots(&mut self, reply: &Value, fallback_host: &str) -> Result<(), Error> {
98        let mut next = Self::new();
99        for range in items(reply)? {
100            let range = items(range)?;
101            if range.len() < 3 {
102                return Err(Error::new("Invalid CLUSTER SLOTS"));
103            }
104            let node = items(&range[2])?;
105            if node.len() < 2 {
106                return Err(Error::new("Invalid cluster node"));
107            }
108            let host = node[0]
109                .text()
110                .filter(|s| !s.is_empty())
111                .map(|s| s.into_owned())
112                .unwrap_or_else(|| fallback_host.into());
113            next.assign(
114                integer(&range[0])?,
115                integer(&range[1])?,
116                Endpoint {
117                    host,
118                    port: integer(&node[1])?,
119                },
120            )?;
121        }
122        *self = next;
123        Ok(())
124    }
125    pub fn update_shards(&mut self, reply: &Value, fallback_host: &str) -> Result<(), Error> {
126        let mut next = Self::new();
127        for shard in items(reply)? {
128            let ranges = items(field(shard, b"slots")?)?;
129            if ranges.len() % 2 != 0 {
130                return Err(Error::new("Invalid shard slots"));
131            }
132            let nodes = items(field(shard, b"nodes")?)?;
133            let master = nodes
134                .iter()
135                .find(|n| field(n, b"role").ok().and_then(Value::bytes) == Some(b"master"))
136                .ok_or_else(|| Error::new("Shard has no master"))?;
137            let host = field(master, b"endpoint")
138                .ok()
139                .and_then(Value::text)
140                .filter(|s| !s.is_empty())
141                .map(|s| s.into_owned())
142                .unwrap_or_else(|| fallback_host.into());
143            let node = Endpoint {
144                host,
145                port: integer(field(master, b"port")?)?,
146            };
147            for pair in ranges.as_chunks::<2>().0 {
148                next.assign(integer(&pair[0])?, integer(&pair[1])?, node.clone())?;
149            }
150        }
151        *self = next;
152        Ok(())
153    }
154    pub fn apply_redirect(&mut self, redirect: &Redirect) -> Result<(), Error> {
155        if !redirect.asking {
156            self.assign(redirect.slot, redirect.slot, redirect.endpoint.clone())?;
157        }
158        Ok(())
159    }
160    /// All explicitly supplied keys must share one slot, even if different slots
161    /// currently reside on the same node. Empty keys select the caller's seed.
162    pub fn route_keys(&self, keys: &[&[u8]]) -> Result<Option<&Endpoint>, Error> {
163        let Some(first) = keys.first() else {
164            return Ok(None);
165        };
166        let slot = key_slot(first);
167        if keys.iter().any(|k| key_slot(k) != slot) {
168            return Err(Error {
169                name: "ReplyError",
170                message: "CROSSSLOT Keys in request don't hash to the same slot".into(),
171            });
172        }
173        self.endpoint(slot)
174            .map(Some)
175            .ok_or_else(|| Error::new("Cluster slots cache is empty"))
176    }
177    /// Known command key layouts. Unknown/module commands require explicit keys
178    /// via route_keys, avoiding unsafe guesses. Transactions pin their slot in
179    /// the host for MULTI through EXEC/DISCARD.
180    pub fn route_command(&self, args: &[&[u8]]) -> Result<Option<&Endpoint>, Error> {
181        let name = *args.first().ok_or_else(|| Error::new("Empty command"))?;
182        let is = |names: &[&[u8]]| names.iter().any(|n| name.eq_ignore_ascii_case(n));
183        if is(&[
184            b"PING", b"INFO", b"CLUSTER", b"AUTH", b"HELLO", b"QUIT", b"MULTI", b"EXEC",
185            b"DISCARD", b"UNWATCH",
186        ]) {
187            return Ok(None);
188        }
189        if is(&[b"MGET", b"DEL", b"EXISTS", b"UNLINK", b"TOUCH", b"WATCH"]) {
190            return self.route_keys(&args[1..]);
191        }
192        if is(&[
193            b"RENAME",
194            b"RENAMENX",
195            b"RPOPLPUSH",
196            b"LMOVE",
197            b"SMOVE",
198            b"BRPOPLPUSH",
199            b"BLMOVE",
200        ]) {
201            return self.route_keys(args.get(1..3).ok_or_else(|| Error::new("Missing keys"))?);
202        }
203        if is(&[b"BLPOP", b"BRPOP", b"BZPOPMIN", b"BZPOPMAX"]) {
204            if args.len() < 3 {
205                return Err(Error::new("Missing blocking keys"));
206            }
207            return self.route_keys(&args[1..args.len() - 1]);
208        }
209        if is(&[b"MSET", b"MSETNX"]) {
210            if args.len() < 3 || args.len() % 2 != 1 {
211                return Err(Error::new("Invalid MSET arguments"));
212            }
213            let slot = key_slot(args[1]);
214            if args[1..].iter().step_by(2).any(|key| key_slot(key) != slot) {
215                return Err(Error::new(
216                    "CROSSSLOT Keys in request don't hash to the same slot",
217                ));
218            }
219            return self.route_keys(&args[1..2]);
220        }
221        if is(&[b"EVAL", b"EVALSHA", b"FCALL", b"FCALL_RO"]) {
222            let count = args
223                .get(2)
224                .and_then(|b| std::str::from_utf8(b).ok())
225                .and_then(|s| s.parse::<usize>().ok())
226                .ok_or_else(|| Error::new("Invalid numkeys"))?;
227            return self.route_keys(
228                args.get(
229                    3..3usize
230                        .checked_add(count)
231                        .ok_or_else(|| Error::new("Invalid numkeys"))?,
232                )
233                .ok_or_else(|| Error::new("Missing script keys"))?,
234            );
235        }
236        if is(&[
237            b"GET",
238            b"SET",
239            b"SETEX",
240            b"PSETEX",
241            b"INCR",
242            b"DECR",
243            b"INCRBY",
244            b"EXPIRE",
245            b"TTL",
246            b"PTTL",
247            b"TYPE",
248            b"HGET",
249            b"HSET",
250            b"HGETALL",
251            b"HDEL",
252            b"HLEN",
253            b"LPUSH",
254            b"RPUSH",
255            b"LPOP",
256            b"RPOP",
257            b"LRANGE",
258            b"SADD",
259            b"SMEMBERS",
260            b"ZADD",
261            b"ZRANGE",
262        ]) {
263            return self.route_keys(args.get(1..2).ok_or_else(|| Error::new("Missing key"))?);
264        }
265        Err(Error::new(
266            "Unknown command key layout; supply explicit keys",
267        ))
268    }
269}
270fn items(value: &Value) -> Result<&[Value], Error> {
271    value.items().ok_or_else(|| Error::new("Expected array"))
272}
273fn integer(value: &Value) -> Result<u16, Error> {
274    value
275        .integer()
276        .and_then(|n| u16::try_from(n).ok())
277        .or_else(|| value.text()?.parse().ok())
278        .ok_or_else(|| Error::new("Invalid port/slot"))
279}
280fn field<'a>(value: &'a Value, key: &[u8]) -> Result<&'a Value, Error> {
281    match value {
282        Value::Map(entries) => entries
283            .iter()
284            .find(|(k, _)| k.bytes() == Some(key))
285            .map(|(_, v)| v),
286        Value::Array(entries) => entries
287            .as_chunks::<2>()
288            .0
289            .iter()
290            .find(|p| p[0].bytes() == Some(key))
291            .map(|p| &p[1]),
292        _ => None,
293    }
294    .ok_or_else(|| Error::new("Missing discovery field"))
295}
296/// Reply to SENTINEL get-master-addr-by-name. Null means this Sentinel does not
297/// know the group; the discovery driver should try its next configured seed.
298pub fn sentinel_master(value: &Value) -> Result<Option<Endpoint>, Error> {
299    if *value == Value::Null {
300        return Ok(None);
301    }
302    let values = items(value)?;
303    if values.len() != 2 {
304        return Err(Error::new("Invalid Sentinel address"));
305    }
306    Ok(Some(Endpoint {
307        host: values[0]
308            .text()
309            .ok_or_else(|| Error::new("Invalid Sentinel host"))?
310            .into_owned(),
311        port: integer(&values[1])?,
312    }))
313}
314
315/// One per logical cluster request. Reuse with `reset` when its terminal event
316/// is consumed. ASK never mutates the stable slot owner; MOVED does.
317#[derive(Debug)]
318pub struct RedirectTracker {
319    remaining: u32,
320}
321impl Default for RedirectTracker {
322    fn default() -> Self {
323        Self::new(16)
324    }
325}
326impl RedirectTracker {
327    pub fn new(max_redirects: u32) -> Self {
328        Self {
329            remaining: max_redirects,
330        }
331    }
332    pub fn reset(&mut self, max_redirects: u32) {
333        self.remaining = max_redirects;
334    }
335    /// None is an ordinary ReplyError. On Some, retry on the supplied endpoint,
336    /// prepending ASKING on that SAME connection when asking=true. The host
337    /// suppresses intermediate redirect replies and preserves the logical token.
338    pub fn follow(&mut self, error: &Error, map: &mut SlotMap) -> Result<Option<Redirect>, Error> {
339        let Some(redirect) = Redirect::parse(error) else {
340            return Ok(None);
341        };
342        if self.remaining == 0 {
343            return Err(Error::new(
344                "Too many Cluster redirections. Last error: MOVED/ASK",
345            ));
346        }
347        self.remaining -= 1;
348        map.apply_redirect(&redirect)?;
349        Ok(Some(redirect))
350    }
351}
352
353use std::time::{Duration, Instant};
354#[derive(Debug, Clone, PartialEq, Eq)]
355pub enum DiscoveryAction {
356    /// Run SENTINEL get-master-addr-by-name on this Sentinel connection.
357    QueryMaster {
358        sentinel: Endpoint,
359        name: String,
360    },
361    /// Run ROLE against this candidate before publishing it to callers.
362    VerifyRole {
363        candidate: Endpoint,
364    },
365    Discovered(Endpoint),
366    /// All seeds exhausted: evaluate sentinelRetryStrategy in the host.
367    Retry {
368        attempt: u32,
369    },
370    Stopped,
371}
372#[derive(Debug, Clone, Copy, PartialEq, Eq)]
373enum DiscoveryState {
374    Master,
375    Role,
376    Retry,
377    Waiting,
378    Done,
379}
380/// Stateful Sentinel seed iteration and stale-master validation. Sentinel and
381/// data-node credentials/TLS can differ; the host selects a Connection config
382/// for QueryMaster versus VerifyRole. Transport failures call `failed`.
383pub struct SentinelDiscovery {
384    seeds: Vec<Endpoint>,
385    name: String,
386    index: usize,
387    attempt: u32,
388    candidate: Option<Endpoint>,
389    state: DiscoveryState,
390    action: Option<DiscoveryAction>,
391    deadline: Option<Instant>,
392}
393impl SentinelDiscovery {
394    pub fn new(seeds: Vec<Endpoint>, name: String) -> Result<Self, Error> {
395        if seeds.is_empty() || name.is_empty() {
396            return Err(Error::new("Sentinel seeds and name are required"));
397        }
398        let action = Some(DiscoveryAction::QueryMaster {
399            sentinel: seeds[0].clone(),
400            name: name.clone(),
401        });
402        Ok(Self {
403            seeds,
404            name,
405            index: 0,
406            attempt: 0,
407            candidate: None,
408            state: DiscoveryState::Master,
409            action,
410            deadline: None,
411        })
412    }
413    pub fn poll_action(&mut self) -> Option<DiscoveryAction> {
414        self.action.take()
415    }
416    pub fn reply(&mut self, value: &Value) -> Result<(), Error> {
417        if self.action.is_some() {
418            return Err(Error::new(
419                "Consume discovery action before supplying reply",
420            ));
421        }
422        match self.state {
423            DiscoveryState::Master => match sentinel_master(value) {
424                Ok(Some(candidate)) => {
425                    self.candidate = Some(candidate.clone());
426                    self.state = DiscoveryState::Role;
427                    self.action = Some(DiscoveryAction::VerifyRole { candidate });
428                }
429                _ => self.failed(),
430            },
431            DiscoveryState::Role => {
432                if value.items().and_then(|v| v.first()).and_then(Value::bytes) == Some(b"master") {
433                    self.state = DiscoveryState::Done;
434                    self.action = Some(DiscoveryAction::Discovered(self.candidate.take().unwrap()));
435                } else {
436                    self.failed();
437                }
438            }
439            _ => return Err(Error::new("Unexpected Sentinel discovery reply")),
440        }
441        Ok(())
442    }
443    pub fn failed(&mut self) {
444        if !matches!(self.state, DiscoveryState::Master | DiscoveryState::Role) {
445            return;
446        }
447        self.candidate = None;
448        self.index += 1;
449        if self.index == self.seeds.len() {
450            self.state = DiscoveryState::Retry;
451            self.attempt = self.attempt.saturating_add(1);
452            self.action = Some(DiscoveryAction::Retry {
453                attempt: self.attempt,
454            });
455        } else {
456            self.query();
457        }
458    }
459    fn query(&mut self) {
460        self.state = DiscoveryState::Master;
461        self.action = Some(DiscoveryAction::QueryMaster {
462            sentinel: self.seeds[self.index].clone(),
463            name: self.name.clone(),
464        });
465    }
466    pub fn retry(&mut self, now: Instant, delay: Option<Duration>) -> Result<(), Error> {
467        if self.state != DiscoveryState::Retry || self.action.is_some() {
468            return Err(Error::new("No Sentinel retry decision requested"));
469        }
470        if let Some(delay) = delay {
471            self.deadline = now.checked_add(delay);
472            self.state = DiscoveryState::Waiting;
473        } else {
474            self.state = DiscoveryState::Done;
475            self.action = Some(DiscoveryAction::Stopped);
476        }
477        Ok(())
478    }
479    pub fn next_timeout(&self) -> Option<Instant> {
480        self.deadline
481    }
482    pub fn handle_timeout(&mut self, now: Instant) {
483        if self.deadline.is_some_and(|d| d <= now) {
484            self.deadline = None;
485            self.index = 0;
486            self.query();
487        }
488    }
489}