Redis LPOS searches list positions with explicit scan limits

Finding an element's position in a Redis list previously required work outside a dedicated position-search command. Redis 6.0.6 adds LPOS, with controls for selecting an occurrence and limiting the search. The important distinction is between limiting returned matches and limiting examined elements. A query can return one position while still scanning a long list.

The release notes date 6.0.6 to July 20, 2020. The tagged notes identify LPOS as a new feature and rate the release's upgrade urgency moderate. They also list a crash fix for prefix-based client tracking. The command addition is useful on its own, while the fixes remain relevant to applications already using Redis 6.

I have used Redis since its release, and I like commands that express a specific operation directly. LPOS is useful because it gives list searching a defined server-side interface. Its options also make the cost model visible enough to distinguish a bounded search from a small reply.

Rank selects an occurrence

The implementation starts with rank one. A positive rank counts matching elements from the beginning of the list. A negative rank reverses the traversal, so minus one selects the first match encountered from the tail. Rank zero is rejected because it would not identify an occurrence.

The returned position still refers to the list's head-based index. A reverse search changes the direction in which matches are counted, without turning the response into a negative index. The implementation calculates a reverse match's position using the list length and the traversal index.

For a disposable example key, the following commands create a list containing repeated values. The positions of c are two, six and seven.

DEL lpos-example
RPUSH lpos-example a b c 1 2 3 c c
LPOS lpos-example c
LPOS lpos-example c RANK 2
LPOS lpos-example c RANK -1

The three searches return two, six and seven respectively. These cases correspond to the release's list tests, which exercise both positive and negative rank. Selecting an occurrence is different from selecting a particular absolute index. Rank counts matches, and the result reports where the selected match resides.

That difference becomes useful when duplicates have meaning. A caller can ask for a later occurrence without first receiving and inspecting the whole list. The server still performs a traversal to identify that occurrence, so the smaller response should not be mistaken for an indexed lookup.

Count changes the reply form

Without COUNT, LPOS returns a single position when it finds the selected match. Adding COUNT requests an array of matching positions. A count of one therefore differs in reply shape from omitting the option, even when both identify the same first occurrence.

A count of zero means collecting all matches that satisfy the remaining options. It does not mean an empty result request. This convention appears directly in the implementation's loop condition and in the versioned tests.

For the example list, these queries request a limited group and then all matching positions beginning with the second occurrence.

LPOS lpos-example c COUNT 2
LPOS lpos-example c RANK 2 COUNT 0

The first yields positions two and six. The second yields six and seven. Combining count and rank lets the caller skip earlier matches and collect a later group. The selection still follows the chosen traversal direction.

A negative rank can also be combined with a positive count. Searching from the tail with rank minus one and count two returns seven followed by six for this list. The array follows search order, so an application should not assume that every returned position array is sorted in ascending order.

Maximum length limits work examined

The MAXLEN option limits how many list elements the traversal examines. Zero means no such limit. A negative value is rejected. This is the control that bounds the scanned prefix or suffix, depending on the direction selected by rank.

The distinction from count is visible in the loop. The traversal continues while another element exists and the examined index remains below the maximum length. Matches have their own counter, with rank and count controlling which positions enter the response.

For example, searching for c with a maximum length of three can reach index two from the head. A maximum length of one cannot reach that element. Reversing the direction examines the corresponding number of elements from the tail, while returned positions remain relative to the head.

A bounded search that finds no match says nothing about the unexamined portion. This is a semantic consequence of the option. An application using MAXLEN must distinguish searching a chosen region from proving absence throughout the complete list.

The mechanism does not create a secondary index on list values. The implementation iterates through list entries and compares each encountered value with the target. LPOS can avoid transferring those entries to the client, but its server-side work still follows the traversal.

The handler checks the stored value type before beginning traversal. A key containing a different Redis type produces a type error instead of a search through an alternative representation. That preserves the command as a list operation, with its rank and position rules defined for that data structure.

Existing Redis 6 users also get tracking fixes

The tagged notes identify a crash when enabling client tracking with a prefix and a correction to invalidation messages on a flush. Both affect an existing Redis 6 facility that tells clients about changes relevant to cached data. These fixes are independent of whether an application uses LPOS.

The patch also records TLS changes, including ignoring a client certificate when client authentication is disabled and adding session-cache configuration. Those are separate transport behaviours. The release combines a small command addition with corrections to facilities introduced in the major version.

I find the LPOS options useful because their roles can be stated separately. Rank chooses where matching begins, count controls how many positions are requested and maximum length bounds traversal. An application can use those distinctions to ask for a particular result without claiming that a limited scan establishes anything about elements it never examined.