1ac3bc07d6
# Redis Array For years, Redis has been missing a real indexed data structure for the use cases where the index and the spatial relationship of elements are semantic. Hashes give you random lookups, but you have to store an index as a key, and have no range visibility. Lists give you appending and trimming, but what is in the middle remains hard to access. Streams give you append-only events, which is another (useful, indeed) beast. None of these is what you want when the *position itself* has business meaning — slot 37, step 4, row 18552, day from 2934 to 2949, file line 11, 12, 15 and so forth. And, all those types, for different reasons, are all suboptimal when you want a **ring buffer** able to store the latest N observed samples of something. Up to now, users found ways (they always do \o/) using the fact that the data structures that are obvious in this universe are also extremely powerful, if well implemented. But this forces compromises. Arrays handle these index-first requirements natively, and usually with much better memory and CPU usage than the workarounds. If the use case is the right one, Arrays often provide much better space, time and usability at the same time. ## Internal encoding 1. When dense, an Array is essentially a more fancy C array. You don't pay anything for storing the index. 2. Yet, instead of going really flat, arrays are sliced into 4096-element slices, and each slice, when it contains just a few elements, uses a special sparse encoding. When a slice is empty it's just a `NULL` stored in the directory. 3. Small ints, floats, and short strings are pointer-tagged, so they cost zero additional memory beyond the pointer slot itself. 4. When very sparse, a super-directory of windowed directories is used. This allows the data type to be safe, instead of exhibiting pathological space or time behavior. This representation is only triggered when there are more than 8 million elements or very high indexes set. ## Use cases Arrays are mostly stateless if not for the fact that each array remembers the index of the latest added item, allowing `ARINSERT` and `ARRING` to work properly. Otherwise it is a set/get at this index game, with solid support for both setting / getting ranges, server-side scanning, returning only populated elements in a time which is proportional not to the range size, but to the population size. A few concrete examples, that may work as mental models for the set of problems that are similar to them (from the POV of the data modeling). **Thermometer.** A sensor reporting once per minute, with gaps: ``` ARSET temp:room12:day7 123 22.3 ARGETRANGE temp:room12:day7 600 660 # the 10:00–11:00 window, with NULLs ARSCAN temp:room12:day7 600 660 # only populated elements AROP temp:room12:day7 0 1439 MAX # peak of the day, server-side ``` Missing minutes cost little to nothing. Numeric aggregation runs inside Redis. Telemetry, IoT, meter readings, KPI rollups. **Calendar.** A clinic with 96 fifteen-minute slots per day: ``` ARSET sched:room12:day 32 booking:991 ARSCAN sched:room12:day 0 95 # only occupied slots ARGETRANGE sched:room12:day 48 63 # the afternoon full view to render ``` The slot number is the business key in this case. Room booking, parking spaces, warehouse bins, lockers, ... **Ring buffer.** ARRING replaces the classic LPUSH+LTRIM pattern. Imagine remote `dmesg`. ``` ARRING machine:123 200 "[141087.430123]: arm_cpu_init(): cpu 14 online" # Capped to 200 entries ARLASTITEMS machine:123 50 REV # 50 newest first ``` Faster than LPUSH+LTRIM, keep indexed access to past elements. Last-N alarms, recent fraud scores, access history, remote logs, device events. Ok here the use cases are mainly the ones of the old pattern: it is just a better fit and allows to access random items in the middle, aggregate server-side, and so forth. **Workflow.** Step number is the index, value is the status. Gaps are meaningful: ``` ARSET claim:99172 0 received ARSET claim:99172 3 waiting:reviewer42 ARSET claim:99172 5 approved ARGETRANGE claim:99172 0 5 # full workflow view, with NULLs for missing steps ARSCAN claim:99172 0 5 # only steps that have a state ARCOUNT claim:99172 # number of recorded steps ARLEN claim:99172 # highest reached step + 1 ``` **Skills knowledge base for agents.** Arrays are good at representing / grepping into Markdown files: ``` ARSET skill:metal_gpu 0 "...." ARSET skill:metal_gpu 1 "...." ARSET skill:metal_gpu 2 "...." ARGREP skill:metal_gpu - + RE "M3|M4" WITHVALUES ``` ARGREP has EXACT, MATCH, GLOB, RE, you can have multiple predicates, can select AND or OR behavior. **Bulk import results.** Sparse row annotations over millions of rows / CSV / ...: ``` ARSET import:job551 18552 ERR:bad_email ARSCAN import:job551 0 1000000 # Provides only rows that have something ``` ## TLDR If the position is part of the meaning, use an Array. If you want to aggregate or grep remotely, use an Array. Feedback welcome :) --------- Co-authored-by: debing.sun <[email protected]> Co-authored-by: Shubham S Taple <[email protected]> Co-authored-by: Yuan Wang <[email protected]> Co-authored-by: Marc Gravell <[email protected]>
9.2 KiB
Introduction
TRE is a lightweight, robust, and efficient POSIX compliant regexp matching library with some exciting features such as approximate (fuzzy) matching.
The matching algorithm used in TRE uses linear worst-case time in the length of the text being searched, and quadratic worst-case time in the length of the used regular expression.
In other words, the time complexity of the algorithm is O(M^2N), where M is the length of the regular expression and N is the length of the text. The used space is also quadratic on the length of the regex, but does not depend on the searched string. This quadratic behaviour occurs only on pathological cases which are probably very rare in practice.
Hacking
Here's how to work with this code.
Prerequisites
You will need the following tools installed on your system:
- autoconf
- automake
- gettext (including autopoint)
- libtool
- zip (optional)
Building
First, prepare the tree. Change to the root of the source directory and run
./utils/autogen.sh
This will regenerate various things using the prerequisite tools so that you end up with a buildable tree.
After this, you can run the configure script and build TRE as usual:
./configure
make
make check
make install
Building a source code package
In a prepared tree, this command creates a source code tarball:
./configure && make dist
Alternatively, you can run
./utils/build-sources.sh
which builds the source code packages and puts them in the dist
subdirectory. This script needs a working zip command.
Features
TRE is not just yet another regexp matcher. TRE has some features which are not there in most free POSIX compatible implementations. Most of these features are not present in non-free implementations either, for that matter.
Approximate matching
Approximate pattern matching allows matches to be approximate, that is, allows the matches to be close to the searched pattern under some measure of closeness. TRE uses the edit-distance measure (also known as the Levenshtein distance) where characters can be inserted, deleted, or substituted in the searched text in order to get an exact match.
Each insertion, deletion, or substitution adds the distance, or cost, of the match. TRE can report the matches which have a cost lower than some given threshold value. TRE can also be used to search for matches with the lowest cost.
TRE includes a version of the agrep (approximate grep) command line tool for approximate regexp matching in the style of grep. Unlike other agrep implementations (like the one by Sun Wu and Udi Manber from University of Arizona) TRE agrep allows full regexps of any length, any number of errors, and non-uniform costs for insertion, deletion and substitution.
Strict standard conformance
POSIX defines the behaviour of regexp functions precisely. TRE attempts to conform to these specifications as strictly as possible. TRE always returns the correct matches for subpatterns, for example. Very few other implementations do this correctly. In fact, the only other implementations besides TRE that I am aware of (free or not) that get it right are Rx by Tom Lord, Regex++ by John Maddock, and the AT&T ast regex by Glenn Fowler and Doug McIlroy.
The standard TRE tries to conform to is the IEEE Std 1003.1-2001, or
Open Group Base Specifications Issue 6, commonly referred to as
“POSIX”. The relevant parts are the base specifications on regular
expressions (and the rationale) and the description of the regcomp()
API.
For an excellent survey on POSIX regexp matchers, see the testregex pages by Glenn Fowler of AT&T Labs Research.
Predictable matching speed
Because of the matching algorithm used in TRE, the maximum time
consumed by any regexec() call is always directly proportional to
the length of the searched string. There is one exception: if back
references are used, the matching may take time that grows
exponentially with the length of the string. This is because matching
back references is an NP complete problem, and almost certainly
requires exponential time to match in the worst case.
Predictable and modest memory consumption
A regexec() call never allocates memory from the heap. TRE allocates
all the memory it needs during a regcomp() call, and some temporary
working space from the stack frame for the duration of the regexec()
call. The amount of temporary space needed is constant during
matching and does not depend on the searched string. For regexps of
reasonable size TRE needs less than 50K of dynamically allocated
memory during the regcomp() call, less than 20K for the compiled
pattern buffer, and less than two kilobytes of temporary working space
from the stack frame during a regexec() call. There is no time /
memory tradeoff. TRE is also small in code size; statically linking
with TRE increases the executable size less than 30K (gcc-3.2, x86,
GNU/Linux).
Wide character and multibyte character set support
TRE supports multibyte character sets. This makes it possible to use regexps seamlessly with, for example, Japanese locales. TRE also provides a wide character API.
Binary pattern and data support
TRE provides APIs which allow binary zero characters both in regexps and searched strings. The standard API cannot be easily used to, for example, search for printable words from binary data (although it is possible with some hacking). Searching for patterns which contain binary zeroes embedded is not possible at all with the standard API.
Completely thread safe
TRE is completely thread safe. All the exported functions are
re-entrant, and a single compiled regexp object can be used
simultaneously in multiple contexts; e.g. in main() and a signal
handler, or in many threads of a multithreaded application.
Portable
TRE is portable across multiple platforms. Below is a table of platforms and compilers used to develop and test TRE:
| Platform | Compiler |
|---|---|
| FreeBSD 14.1 | Clang 18 |
| Ubuntu 22.04 | GCC 11 |
| macOS 14.6 | Clang 14 |
| Windows 11 | Microsoft Visual Studio 2022 |
TRE should compile without changes on most modern POSIX-like platforms, and be easily portable to any platform with a hosted C implementation.
Depending on the platform, you may need to install libutf8 to get wide character and multibyte character set support.
Free
TRE is released under a license which is essentially the same as the “2 clause” BSD-style license used in NetBSD. See the file LICENSE for details.
Roadmap
There are currently two features, both related to collating elements, missing from 100% POSIX compliance. These are:
-
Support for collating elements (e.g.
[[.\<X>.]], where\<X>is a collating element). It is not possible to support multi-character collating elements portably, since POSIX does not define a way to determine whether a character sequence is a multi-character collating element or not. -
Support for equivalence classes, for example
[[=\<X>=]], where\<X>is a collating element. An equivalence class matches any character which has the same primary collation weight as\<X>. Again, POSIX provides no portable mechanism for determining the primary collation weight of a collating element.
Note that other portable regexp implementations don't support collating elements either. The single exception is Regex++, which comes with its own database for collating elements for different locales. Support for collating elements and equivalence classes has not been widely requested and is not very high on the TODO list at the moment.
These are other features I'm planning to implement real soon now:
-
All the missing GNU extensions enabled in GNU regex, such as
[[:<:]]and[[:>:]]. -
A
REG_SHORTESTregexec()flag for returning the shortest match instead of the longest match. -
Perl-compatible syntax:
-
[:^class:]Matches anything but the characters in class. Note that[^[:class:]]works already, this would be just a convenience shorthand. -
\AMatch only at beginning of string. -
\ZMatch only at end of string, or before newline at the end. -
\zMatch only at end of string. -
\lLowercase next char (think vi). -
\uUppercase next char (think vi). -
\LLowercase till\E(think vi). -
\UUppercase till\E(think vi). -
(?=pattern)Zero-width positive look-ahead assertions. -
(?!pattern)Zero-width negative look-ahead assertions. -
(?<=pattern)Zero-width positive look-behind assertions. -
(?<!pattern)Zero-width negative look-behind assertions.
-
Documentation especially for the nonstandard features of TRE, such as
approximate matching, is a work in progress (with “progress” loosely
defined...) If you want to find an extension to use, reading the
include/tre/tre.h header might provide some additional hints if you
are comfortable with C source code.