Skip to content

Latest commit

 

History

History
768 lines (675 loc) · 33.9 KB

rdb.adoc

File metadata and controls

768 lines (675 loc) · 33.9 KB
Raw

Redis Rdb Dump Structures

Table of Contents

Rdb Dump

The Rdb format as output by the dump command, always has these 5 elements.

Rdb Type

Rdb Length

Body

Rdb Version

CRC64

1 Byte, Range: 0 → 15

Length of Body

Body data

0x09 0x00 = version 9

8 bytes, CRC64(Type, Length, Body, Version)

The Rdb format as output by the save command adds the key and some meta information. The value format is similar to the dump command. The CRC64 and Rdb version are only in the file once. The dump command does not add key and expiry to the data it outputs.

Rdb Meta

Rdb Type

Rdb Length

Key

Rdb Length

Body

Optional key expiry, LRU

1 Byte, Range: 0 → 15

Length of Key

Key data

Length of Body

Body data

These sequences are repeated for each key saved to the Rdb file. The last 8 bytes in the file should be a CRC64 of the entire file. The header of the file, before the data is encoded, contains a magic "REDIS000X" string, and the same kind of Rdb Meta fields that may appear before a key.

Rdb Meta

The info about the database, Redis version, current time, and key expiry is encoded with prefix 0xf7 to 0xff. These do not conflict with the Rdb Type, which would start the data encoding of the key values.

Meta Number Notes

MODULE_AUX

0xf7

Module specific coding

IDLE

0xf8

Length encoding, in seconds

FREQ

0xf9

One byte, a LRU code

AUX

0xfa

Two strings (var = value)

DBRESIZE

0xfb

Two lengths

EXPIRED_MS

0xfc

8 bytes, UTC millisecs, little endian

EXPIRED_SEC

0xfd

4 bytes, UTC seconds, little endian

DBSELECT

0xfe

Length encoding

EOF

0xff

0xff

The length coding in the Notes above, uses Rdb Length type coding, but cannot be an immediate integer, they must use length coding.

An example of Rdb Meta coding

The only key in this example database Rdb file is the one added below, setting the key "k" to the value "string" with an expiration of 5000 secs.

$ redis-cli set k string ex 5000
OK
$ redis-cli save
OK
$ xxd /var/lib/redis/dump.rdb
00000000: 5245 4449 5330 3030 39fa 0972 6564 6973  REDIS0009..redis
          A                     B  C               A         BC
00000010: 2d76 6572 0b39 3939 2e39 3939 2e39 3939  -ver.999.999.999
                    D                                  D
00000020: fa0a 7265 6469 732d 6269 7473 c040 fa05  ..redis-bits.@..
          E                             F    G     E           F G
00000030: 6374 696d 65c2 bb14 495e fa08 7573 6564  ctime...I^..used
                      H            I                    H    I
00000040: 2d6d 656d c278 2e0d 00fa 0c61 6f66 2d70  -mem.x.....aof-p
                    J           K                      J    K
00000050: 7265 616d 626c 65c0 00fe 00fb 0101 fc45  reamble........E
                           L    M    N       O            L M N  O
00000060: 6e11 4e70 0100 0000 016b 0673 7472 696e  n.Np.....k.strin
                           P  Q    R                      PQ R
00000070: 67ff 28ba 74ac 619d 4539                 g.(.t.a.E9
            S  T                                    ST

  1. "REDIS0009" — The magic string which codes the Rdb version in Ascii.

  2. 0xfa — The code for AUX. These are always variable = value style, with two Rdb Length encoded values, a string variable and an integer or a string value.

  3. 0x09 72 65 …​ — Length 9, the string "redis-ver"

  4. 0x0b 39 39 …​ — Length 11, the string "999.999.999". The 0xfa in {B} coded the two strings "redis-ver" = "999.999.999".

  5. 0xfa 0a 72 65 …​ — AUX, Length 10, the string "redis-bits".

  6. 0xc0 40 — The immediate integer 0x40, or 64, setting "redis-bits" = 64.

  7. 0xfa 05 63 74 69 6d — AUX, Length 5, the string "ctime"

  8. 0xc2 bb 14 49 5e — The immediate integer 0x5e4914bb, or 1581847739, setting "ctime" = 1581847739, which is UTC seconds.

  9. 0xfa 08 75 73 …​ — AUX, Length 8, the string "used-mem"

  10. 0xc2 78 2e 0d 00 — The immediate integer 0xd2e78, or 863864, setting "used-mem" = 863864.

  11. 0xfa 0c 61 6f …​ — AUX, Length 12, the string "aof-preamble"

  12. 0xc0 00 — The immediate integer 0, setting "aof-preamble" = 0.

  13. 0xfe 00 — DBSELECT, the current database = 0.

  14. 0xfb 01 01 — DBRESIZE, resize = { 1, 1 }.

  15. 0xfc 45 6e 11 4e 70 01 00 00 — EXPIRED_MS, set the 8 byte UTC expired stamp in milliseconds to 0x1704e116e45 or 1581857730117. This applies to the key that follows this stamp, which starts at {P}.

  16. 0x00 — The Rdb Type 0, or STRING, the simplest coding.

  17. 0x01 6b — The key length is 1 and the key data is "k" (ascii code 0x6b).

  18. 0x06 73 74 72 69 6e 67 — The value of the key "k" is "string".

  19. 0xff — The EOF marker.

  20. 0x28 ba 74 …​ — The CRC64 of the file up to and including {S}.

Lets examine the output of the dump command.

$ redis-cli dump k | xxd
00000000: 0006 7374 7269 6e67 0900 91ea 2f4c facd  ..string..../L..
00000010: 7a3e 0a                                  z>.

The key data and expiry is not present, but the "string" value is. The tail of the dump is the version and CRC64.

Rdb Type

The type range is 0 to 15 in version 9 of Redis Rdb. Some of the enumerations are no longer used in this version. The number is coded in the first byte of the dump format, it determines how to interpret the rest of the data.

Type Number Notes

STRING

0

A string of bytes *

LIST

1

List of string elements

SET

2

List of string members *

ZSET

3

String and string coded double score

HASH

4

List of strings for each field and value *

ZSET_2

5

String and double binary coded score *

MODULE

6

No description yet

MODULE_2

7

No description yet *

HASH_ZIPMAP

9

Not used, uses ZipList

LIST_ZIPLIST

10

Not used, uses QuickList

SET_INTSET

11

Array of integers, all the same size *

ZSET_ZIPLIST

12

A ZipList of members and scores *

HASH_ZIPLIST

13

A ZipList of fields and values *

LIST_QUICKLIST

14

A List of ZipLists *

STREAM_LISTPACK

15

A Stream that uses ListPack lists *

HASH_LISTPACK

16

A ListPack list of key/value pairs

ZSET_LISTPACK

17

A ListPack list of value/score pairs

LIST_QUICKLIST_2

18

A QuickList encoding that uses ListPack

STREAM_LISTPACKS_2

19

A Stream ListPack with additional fields

  • The only types found in a version 9 dump, are: STRING, SET, HASH, ZSET_2, SET_INTSET, ZSET_ZIPLIST, HASH_ZIPLIST, LIST_QUICKLIST, STREAM_LISTPACK.

Rdb Length

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
A |0 0 . . . . . .|      6 bit length
B |0 1 . . . . . . . . . . . . . .|  14 bit length
C |1 0 0 0 0 0 0 0 . . . 32 bit length . . . . . . . . . . . . ...>
D |1 0 0 0 0 0 0 1 . . . 64 bit length . . . . . . . . . . . . ...>
E |1 1 0 0 0 0 0 0 . . . . . . . .|  8 bit immediate int
F |1 1 0 0 0 0 0 1 . . . 16 bit immediate int  . .|
G |1 1 0 0 0 0 1 0 . . . 32 bit immediate int  . . . . . . . . ...>
H |1 1 0 0 0 0 1 1 . . . LZF <zlen> <len>  . . . . . . . . . . ...>
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

  1. 6 bit length — range 0 → 63 bytes. [ 0x00 → 0x3f ]

  2. 14 bit length — range 0 → 16383 bytes. [ 0x4000 → 0x7fff ]

  3. 32 bit length — range 0 → 4GB bytes. [ 0x80 32bits → 0x80 32bits ]

  4. 64 bit length — range 0 → 2^64-1 bytes. [ 0x81 64bits → 0x81 64bits ]

  5. 8 bit immediate integer — range -128 → 127 int. [ 0xc0 00 → 0xc0 ff ]

  6. 16 bit immediate integer — range -32K → 32K-1 int. [ 0xc1 0000 → 0xc1 ffff ]

  7. 32 bit immediate integer — range -2G → 2G-1 int. [ 0xc2 32bits → 0xc2 32bits ]

  8. LZF compressed data. [ 0xc3 <zlen> <len> ]

The length codes are big endian (msb first: 4321), and the immediate codes are little endian (lsb first: 1234). The Intel archetecture is natively little endian.

The length codes {A,B,C,D} are usually used for determining the end of a stream of bytes, but it can also be used to indicate the number of elements in a ZSET or the number of blobs of items in a STREAM_LISTPACK. Since the length codes have 64 bit unsigned range, they are also used when a large number is encoded and data does not follow. The immediate integer range is limited to 32 bit signed values.

The immediate integers {E,F,G} are the data, there is no stream of bytes or elements that follow. They are all signed values, the lengths are all unsigned values.

Compressed data {H} is like length codes, because data in the stream follows the code, unlike the immediate integer codes. After uncompressing zlen bytes, these are removed and the len bytes are inserted.

The examples in this document are short enough that compression does not help. In normal circumstances, compression will be used a lot in cases where there are more than a couple of elements of data, since it does not take a lot of it for compression to be useful.

Body

In the Body, the Rdb Type selects different codings schemes

An example of STRING coding

$ redis-cli set k string
OK
$ redis-cli dump k | xxd
00000000: 0006 7374 7269 6e67 0900 91ea 2f4c facd  ..string..../L..
          A B  C              D    E
00000010: 7a3e 0a                                  z>.

  1. 0x00 — A STRING Rdb Type.

  2. 0x06 — A Rdb Length, indicating 6 bytes follow.

  3. 0x73 74 72 69 6e 67 — The "string" data.

  4. 0x09 00 — The Rdb version.

  5. 0x91 …​ 0a — The CRC64 checksum, with a newline from redis-cli.

The Rdb Type is the first byte, 0x00, the Rdb Length is the second byte, 0x06, and the data "string" follows. The trailing bytes is the version (0x0900) followed by the CRC64 of the previous 10 bytes.

An example of SET coding

$ redis-cli sadd s string 1 2 3 four
(integer) 5
$ redis-cli dump s | xxd
00000000: 0205 c003 c001 c002 0673 7472 696e 6704  .........string.
          A B  C    D    E    F G              H
00000010: 666f 7572 0900 616f e121 b97c 9a93 0a    four..ao.!.|...
          I         J    K

  1. 0x02 — A SET Rdb Type.

  2. 0x05 — A Rdb Length, indicating 5 members of the set.

  3. 0xc0 03 — A Rdb Length, coding the immediate integer 3.

  4. 0xc0 01 — A Rdb Length, coding the immediate integer 1.

  5. 0xc0 02 — A Rdb Length, coding the immediate integer 2.

  6. 0x06 — A Rdb Length, indicating 6 bytes follow.

  7. 0x73 74 72 69 6e 67 — The "string" data.

  8. 0x04 — A Rdb Length, indicating 4 bytes follow.

  9. 0x66 6f 75 72 — The "four" data.

  10. 0x09 00 — The Rdb version.

  11. 0x61 …​ 0a — The CRC64 checksum, with a newline from redis-cli.

The Rdb Type is 0x02 for a SET type. The rest of the data is coded with 6 Rdb Length values. In this case the first Rdb Length, value 5, is the number of items that are in the set. After the length, there are 5 items coded. Some are coded as lengths, and some are coded as immediate integers. The bytes 0xc0 0x03 are coding the immediate integer 3, this is a member of the set.

Zip List

A Zip List is a list of items that can be traversed forwards and in reverse. The Zip List structure has a header followed by elements with links in both directions between them. It is used by many of the data types in Redis.

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |  zlbytes size, 4 bytes                                        |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |  zltail offset, 4 bytes                                       |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |  zllen entry count, 2 bytes   |    0x00       |    zlnext     |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |  optional data                |    zlprev     |    zlnext     |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |  optional data                |    0xff       |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

  • zlbytes — The 32 bit length in bytes of the list, including header, in little endian.

  • zltail  — The 32 bit offset to the last element in the list for traversing in reverse, in little endian.

  • zllen  — The count of elements in the list, which is valid up to the maximum 16 bit value, little endian.

  • zlnext — An index that can have length with data following or immediate integer data, much like Rdb Length. The opcode prefix expands from 0xc0 to 0xf0, to 0xff. The first three are lengths of various bit widths (0x00, 0x40, 0x80), the rest are immediate integers.

  • zlprev — A length in bytes to skip to the previous list element. This is a simplier coding than zlnext. The 0xff value ends the Zip List, the 0xfe prefixes a 32 bit length, and anything less than 0xfe is a length literal (the code 0x10 would be the length 16).

    1. 0xff  — The end of the zip list

    2. 0xfe  — 32 bits little endian length

    3. 0x00 → 0xfd — 8 bits length, range 0 → 253

The complicated part of a Zip List encoding is the [zlnext] link. It has 9 codes, 3 length codes and 6 immediate integer codes. The length codes are the same as the Rdb Length methods, except that 64 bit lengths are not possible. The immediate integers are expanded with more prefix codes and more bit lengths.

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
A |0 0 . . . . . .|      6 bit length
B |0 1 . . . . . . . . . . . . . .|  14 bit length
C |1 0 0 0 0 0 0 0 . . . 32 bit length . . . . . . . . . . . . ...>
D |1 1 0 0 0 0 0 0 . . . 16 bit immediate int  . .|
E |1 1 0 1 0 0 0 0 . . . 32 bit immediate int  . . . . . . . . ...>
F |1 1 1 0 0 0 0 0 . . . 64 bit immediate int  . . . . . . . . ...>
G |1 1 1 1 0 0 0 0 . . . 24 bit immediate int  . . . . . . . . . .|
H |1 1 1 1 1 1 1 0 . . . . . . . .|  8 bit immediate int
I |1 1 1 1 . . . .|      4 bit immediate int
J |1 1 1 1 1 1 1 1|      List terminator
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

  1. 0x00 — Length encoded in 6 bits, range 0 → 63. [ 0x00 → 0x3f ]

  2. 0x40 — Length encoded in 14 bits, big endian, range 0 → 16383. [ 0x4000 → 0x7fff ]

  3. 0x80 — Length encoded in 32 bits, big endian, range 0 → 4G. [ 0x80 32bits → 0x80 32bits ]

  4. 0xc0 — Immediate integer 16 bits, little endian, range -32K → 32K-1. [ 0xc0 0000 → 0xc0 ffff ]

  5. 0xd0 — Immediate integer 32 bits, little endian, range -2G → 2G-1. [ 0xd0 32bits → 0xd0 32bits ]

  6. 0xe0 — Immediate integer 64 bits, little endian, range -2^63 → 2^63-1. [ 0xe0 64bits → 0xe0 64bits ]

  7. 0xf0 — Immediate integer 24 bits, little endian, range -8M → 8M-1. [ 0xf0 24bits → 0xf0 24bits ]

  8. 0xfe — Immediate integer 8 bits, range -128 → 127. [ 0xfe 00 → 0xfe ff ]

  9. 0xf1 → 0xfd — Immediate int 4 bits, unsigned, subtract 1, range 0 → 12. [ 0xf1 → 0xfd ]

  10. 0xff — Terminates the list.

An example of HASH_ZIPLIST coding

$ redis-cli hset h one 1 two 2
(integer) 2
$ redis-cli dump h | xxd
00000000: 0d19 1900 0000 1600 0000 0400 0003 6f6e  ..............on
          A B  C         D         E    F G
00000010: 6505 f202 0374 776f 05f3 ff09 00fc c2a6  e....two........
            H  I J  K         L M  N O    P
00000020: e0a1 0f9b 650a                           ....e.

  1. 0x0d — A HASH_ZIPLIST Rdb Type.

  2. 0x19 — The Rdb Length is 25, data length from {C} to {O}.

  3. 0x19000000 — The [zlbytes], the 32 bit length of the Zip List data.

  4. 0x16000000 — The [ztail], the 32 bit offset to the trailing element, which is the postion {L} above.

  5. 0x0400 — The [zllen], a 16 bit count of elements in the Zip List.

  6. 0x00 — The first [zlprev] link, always null.

  7. 0x03 6f 6e 65 — The [zlnext] length 3, and the "one" data that follows.

  8. 0x05 — The [zlprev] length 5, which points to {F}.

  9. 0xf2 — The [zlnext] immediate integer 1 (0xf2 - 0xf1 = 1).

  10. 0x02 — The [zlprev] length 2, whiich points to {H}.

  11. 0x03 74 77 6f — The [zlnext] length 3, and the "two" data that follows.

  12. 0x05 — The [zlprev] length 5, which points to {J}.

  13. 0xf3 — The [zlnext] immediate integer 2 (0xf3 - 0xf1 = 2).

  14. 0xff — The [zlprev] field terminating the list.

  15. 0x09 00 — The Rdb version.

  16. 0xfc …​ 0a — The CRC64 checksum, with a newline from redis-cli.

Any Zip List coded type will result in the same structure as above. The only difference would be how the list elements are interpretted. In the HASH_ZIPLIST case the list element pairs are used to construct the fields and values. In the ZSET_ZIPLIST case, the list element pairs are used to construct the members and the scores.

An example of HASH_LISTPACK coding

$ redis-cli hset hash aaa 10 hello world
(integer) 2
$ redis-cli dump hash | xxd
00000000: 101c 1c00 0000 0400 8361 6161 040a 0185  .........aaa....
          A B  C         D    E         F G  H I
00000010: 6865 6c6c 6f06 8577 6f72 6c64 06ff 0a00  hello..world....
                      J  K              L M  N
00000020: 1b70 3086 4304 7d99 0a                   .p0.C.}..
          O

  1. 0x10 — A HASH_LISTPACK Rdb Type.

  2. 0x1c — A Rdb Length, length of the hash from {C} to {N}.

  3. 0x1c000000 — A [lpbytes] 32 bit length of the hash.

  4. 0x0400 — A [lplen], a 16 bit count of elements.

  5. 0x83 61 61 61 — The [lpnext] a string length of 3.

  6. 0x04 — The [lpback] length to start, points to {E}.

  7. 0x0a — The [lpnext] the integer value 10.

  8. 0x01 — The [lpback] length to start points to {G}.

  9. 0x85 68 65 6c 6c 6f — [lpnext] a string length of 5.

  10. 0x06 — The [lpback] length to start, points to {I}.

  11. 0x85 77 6f 72 6c 64 — [lpnext] a string length of 5.

  12. 0x06 — The [lpback] length to start, points to {K}.

  13. 0xff — The [lpnext] list terminator.

  14. 0x0a 00 — The Rdb version.

  15. 0x1b …​ 0a — The CRC64 checksum, with a newline from redis-cli.

Quick List

A Quick List is an array of Zip List. This is only used for coding the LIST_QUICKLIST data type.

An example of LIST_QUICKLIST coding

$ redis-cli rpush l string 2
(integer) 2
$ redis-cli dump l | xxd
00000000: 0e01 1515 0000 0012 0000 0002 0000 0673  ...............s
          A B  C D         E         F    G  H
00000010: 7472 696e 6708 f3ff 0900 5e42 7039 fa1a  tring.....^Bp9..
                      I  J K  L    M
00000020: 7c28 0a                                  |(.

  1. 0xe0 — A LIST_QUICKLIST Rdb Type.

  2. 0x01 — A Rdb Length, indicating an array of one Zip List.

  3. 0x15 — A Rdb Length, the length of the Zip List data from {D} to {L}.

  4. 0x15000000 — The [zlbytes], a 32 bit length data size, little endian.

  5. 0x12000000 — The [zltail], a 32 bit offset to the trailing element, little endian, which points to position 0x15 above, labeled with an I.

  6. 0x0200 — The [zllen], a 16 bit count of elements in the Zip List, little endian.

  7. 0x00 — The first [zlprev] link, always null.

  8. 0x06 73 74 72 69 6e 67 — The [zlnext] field and "string" data.

  9. 0x08 — The [zlprev] length, subtract from current position to go to the previous item.

  10. 0xf3 — The [zlnext] field coding the number 2 (0xf3 - 0xf1 = 2)

  11. 0xff — The [zlprev] field terminating the list.

  12. 0x09 00 — The Rdb version.

  13. 0x5e …​ 0a — The CRC64 checksum, with a newline from redis-cli.

An example of LIST_QUICKLIST_2 coding

$ redis-cli rpush l string 2
(integer) 2
$ redis-cli dump l | xxd
00000000: 1201 0211 1100 0000 0200 8673 7472 696e  ...........strin
          A B  C D  E         F    G
00000010: 6707 0201 ff0a 00d4 c268 a616 e98b 9e0a  g........h......
            H  I J  K L    M

  1. 0x12 — A LIST_QUICKLIST_2 Rdb Type.

  2. 0x01 — A Rdb Length, indincating an array of one.

  3. 0x02 — A Rdb Length, the container type (1 = PLAIN, 2 = PACKED).

  4. 0x11 — A Rdb Length, length of the packed container

  5. 0x11000000 — [lpbytes] 32 bit length of packed container

  6. 0x0200 — [lplen], a 16 bit count of elements

  7. 0x86 73 74 72 69 6e 67 — [lpnext] a string length of 6

  8. 0x07 — [lpback] length to start

  9. 0x02 — [lpnext] immediate value 2

  10. 0x01 — [lpback] length to start

  11. 0xff — [lpnext] list terminator

  12. 0x0a 00 — The Rdb version.

  13. 0xd4 …​ 0a — The CRC64 checksum, with a newline from redis-cli.

List Pack

This structure is a quite similar to Zip List, but has slight tweaks in the coding of the links and slightly different bit prefixes and widths. The List Pack is only used to encode parts of the Redis STREAM data type.

The List Pack header does not have a tail offset like the Zip List does because the linking methods allow the program to determine the back from the size of the data.

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |  lpbytes size, 4 bytes                                        |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |  lplen entry count, 2 bytes   |    lpnext     |    optional ...
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     data         |    lpback     |    lpnext     |    optional ...
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     data         |    lpback     |    0xff       |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

  • lpbytes — The length in bytes of the list, including header, a 32 bit value stored in little endian format.

  • lplen — The count of elements in the list, which is valid up to the maximum 16 bit value, stored in little endian fromat.

  • lpnext — An index that can have length with data following or immediate integer data, much like Rdb Length and Zip List. The opcode prefix expands like those codes do, with different meanings.

  • lpback — An offset to the previous [lpnext] code. This uses big endian format with the 0x80 bit used to signal the end of the code.

The lpback code is used to traverse the list from back to front. The last code has the 0x80 bit clear so that a back to front traversal eats bytes and accumulates the size while the 0x80 bit is set. The forward traversal skips over this coding by calculating the number of 7 bit numbers needed to code the element size, which is the size of the lpnext code and the optional data. For example, the size 500 is represented as 0x03 0xf4 or

0x03f4 : 3 * 128 + 0x74 == 384 + 116 == 500.

The 0x80 bit in 0xf4 is masked to produce 0x74. The size 32000 is represented as 0x1 0xfa 0x80 or

0x01fa80 : 1 * 128 * 128 + 0x7a * 128 + 0 == 16384 + 15616 == 32000.

Like the Zip List, the magic in this coding is the [lpnext] code. One difference with the other codes is that the first code, {A} below, encodes an unsigned immediate integer. All of the other codings for immediate integer are signed, where the most significant bit of the code is sign extended. For example, using the coding method {C} below, the value 0xdffff is decoded as -1; It is the prefix 0xc0 followed by the big endian integer, 0x1fff - 8192 = -1.

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
A |0 . . . . . . .|      7 bit immediate int, unsigned
B |1 0 . . . . . .|      6 bit length
C |1 1 0 . . . . . . . . . . . . .|    13 bit immediate int
D |1 1 1 0 . . . . . . . . . . . .|    12 bit length
E |1 1 1 1 0 0 0 0 . . . 32 bit length . . . . . . . . . . . . ...>
F |1 1 1 1 0 0 0 1 . . . 16 bit immediate int  . .|
G |1 1 1 1 0 0 1 0 . . . 24 bit immediate int  . . . . . . . . . .|
H |1 1 1 1 0 0 1 1 . . . 32 bit immediate int  . . . . . . . . ...>
I |1 1 1 1 0 1 0 0 . . . 64 bit immediate int  . . . . . . . . ...>
J |1 1 1 1 1 1 1 1|      List terminator
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

  1. 0x00 — Immediate unsigned integer in 7 bits, range 0 → 127. [ 0x00 → 0x3f ]

  2. 0x80 — Length encoded in 6 bits, range 0 → 63. [ 0x80 → 0xbf ]

  3. 0xc0 — Immediate integer encoded in 13 bits, big endian, range -4096 → 4095. [ 0xc000 → 0xdfff ]

  4. 0xe0 — Length encoded in 12 bits, big endian, range 0 → 4095. [ 0xe000 → 0xe0fff ]

  5. 0xf0 — Length encoded in 32 bits, big endian, range 0 → 4G-1. [ 0xf0 32bits → 0xf0 32bits ]

  6. 0xf1 — Immediate integer encoded in 16 bits, little endian, range -32K → 32K-1. [ 0xf1 0000 → 0xf1 ffff ]

  7. 0xf2 — Immediate integer encoded in 24 bits, little endian, range -8M → 8M-1. [ 0xf2 24bits → 0xf2 24bits ]

  8. 0xf3 — Immediate integer encoded in 32 bits, little endian. range -2G → 2G-1. [ 0xf3 32bits → 0xf3 32bits ]

  9. 0xf4 — Immediate integer encoded in 64 bits, little endian, range -2^63 → 2^63-1. [ 0xf4 64bits → 0xf4 64bits ]

  10. 0xff — The list terminator.

The prefixes 0xf5 through 0xfe are not used.

An example of STREAM_LISTPACK coding

The structure of a STREAM_LISTPACK contains more than a List Pack container. It also has a list of groups, consumers, and pending entry lists (PELs). To simplify, this example only has the basic stream elements, with two entries encoded.

$ redis-cli xadd str '*' loc mel temp 23
"1581661705262-0"
$ redis-cli xadd str '*' loc sfo temp 10
"1581661738846-0"
$ redis-cli xrange str - +
1) 1) "1581661705262-0"
   2) 1) "loc"
      2) "mel"
      3) "temp"
      4) "23"
2) 1) "1581661738846-0"
   2) 1) "loc"
      2) "sfo"
      3) "temp"
      4) "10"
$ redis-cli dump str | xxd
00000000: 0f01 1000 0001 7042 6254 2e00 0000 0000  ......pBbT......
          A B  C D
00000010: 0000 003b 3b00 0000 1200 0201 0001 0201  ...;;...........
                 E  F         G    H    I    J
00000020: 836c 6f63 0484 7465 6d70 0500 0102 0100  .loc..temp......
          K           L              ^    ^    ^
00000030: 0100 0183 6d65 6c04 1701 0501 0201 f230  ....mel........0
            ^    ^            ^    ^    ^    ^
00000040: 8300 0400 0183 7366 6f04 0a01 0501 ff02  ......sfo.......
                 ^    ^            ^    ^    M
00000050: 8100 0001 7042 62d7 5e00 0009 008f ddcc  ....pBb.^.......
00000060: c2a8 a27f 070a                           ......

  1. 0x0f — The Rdb Type STREAM_LISTPACK

  2. 0x01 — A Rdb Length, the length 1, which is the number of blocks that contain a Stream Key and a List Pack.

  3. 0x10 — A Rdb Length, the length 16, which is the size of the Stream Key.

  4. 0x000001704262542e 0x0000000000000000 — The Stream Key, which is composed of a millisecond UTC timestamp and a serial number. This is stored in big-endian format. The value is the first key added to the stream above: "1581661705262-0" The other keys in this ListPack are codes as offsets to this key.

  5. 0x3b — A Rdb Length, the length of the List Pack.

  6. 0x3b000000 — The [lpbytes] field of the List Pack.

  7. 0x1200 — The [lplen] field of the List Pack, the count of items encoded, which is 18 in this case.

  8. 0x02 0x01 — [lpnext] and [lpback], immediate int code 2.

  9. 0x00 0x01 — [lpnext] and [lpback], immediate int code 0.

  10. 0x02 0x01 — [lpnext] and [lpback], immediate int code 2.

  11. 0x83 6c 6f 63 04 — [lpnext] and [lpback], encoding a 3 byte length of the string "loc", the first field in the stream.

  12. 0x84 74 65 6d 70 05 — [lpnext] and [lpback], encoding a 4 byte length of the string "temp", the second field in the stream.

  13. more of the same, 0xff terminates the List Pack.

There are lots of elements in the list which are meta data about the stream rather than the stream field values. The header of the stream contains the fields that are used in the first record of the stream. For each additional entry in the stream, these fields can be referenced and omitted in the record, to avoid repeating the same field names.

The header of this List Pack block contains, starting at {H} above:

  • 2 — Entry count, number of stream entries

  • 0 — Deleted count, number of stream entries deleted

  • 2 — Master field count

  • "loc" — Master field number 1

  • "temp" — Master field number 2

  • 0 — Terminates the back links to allow traversing in reverse.

The entries in the stream follow the header, starting at {T} above:

  • 2 — The flags, 2 means that the master fields in the header are used.

  • 0 — The millisecond offset from the first key, in {D} above "1581661705262-0".

  • 0 — The serial offset from the first key.

  • "mel" — The value of the first field.

  • 23 — The value of the second field.

  • 5 — List back count, number of list elements to skip for this entry.

The second entry, starting at {d} above:

  • 2 — The flags.

  • 33584 — The millisecond offset from the first key, in {D} above, adding this to that arrives at the second key, "1581661738846-0".

  • 0 — The serial offset from the first key.

  • "sfo" — The value of the first field.

  • 10 — The value of the second field.

  • 5 — List back count.

After the end of the List Pack codes, there are more Rdb Length encoded numbers: a count, for the number of stream records, the last id used, and the number of consumer groups. Important Note: These are encoded as lengths since the immediate integers in the Rdb Length method are limited to 32 bits and 64 bits are needed for these. If there are some groups, then all of the groups, consumers, and pending entry lists are appended, but they don’t use the List Pack structure, that is used only by the stream record entries.

00000040: 8300 0400 0183 7366 6f04 0a01 0501 ff02  ......sfo.......
                                               A
00000050: 8100 0001 7042 62d7 5e00 0009 008f ddcc  ....pBb.^.......
          B                     C  D E    F
00000060: c2a8 a27f 070a                           ......

  1. 0x02 — Rdb Length immediate integer 2, the number of stream records

  2. 0x81 00000170 4262d75e — Rdb Length immediate 64 bit UTC milliseconds of the last id used.

  3. 0x00 — Rdb Length immediate serial number of the last id used.

  4. 0x00 — Rdb Length, the number of groups attached to this stream.

  5. 0x09 00 — The Rdb version.

  6. 0x8f …​ 0a — The CRC64 checksum, with a newline from redis-cli.

The version 2 of the STREAM_LISTPACK contains a additial pointers for first and max deleted serial ids.