Skip to content

Hash Field Expiration - listpack support #13209

Merged
tezc merged 34 commits intoredis:hash-field-expiry-integfrom
tezc:hfe-listpack-v1
May 8, 2024
Merged

Hash Field Expiration - listpack support #13209
tezc merged 34 commits intoredis:hash-field-expiry-integfrom
tezc:hfe-listpack-v1

Conversation

@tezc
Copy link
Copy Markdown
Collaborator

@tezc tezc commented Apr 15, 2024

Changes:

  • Adds listpack support to hash field expiration
  • Implements hgetf/hsetf commands

Listpack support for hash field expiration

We keep field name and value pairs in listpack for the hash type. With this PR, if one of hash field expiration command is called on the key for the first time, it converts listpack layout to triplets to hold field name, value and ttl per field. If a field does not have a TTL, we store zero as the ttl value. Zero is encoded as two bytes in the listpack. So, once we convert listpack to hold triplets, for the fields that don't have a TTL, it will be consuming those extra 2 bytes per item. Fields are ordered by ttl in the listpack to find the field with minimum expiry time efficiently.

New command implementations as part of this PR:

  • HGETF command

    For each specified field get its value and optionally set the field's expiration time in sec/msec /unix-sec/unix-msec:

    HGETF key 
      [NX | XX | GT | LT]
      [EX seconds | PX milliseconds | EXAT unix-time-seconds | PXAT unix-time-milliseconds | PERSIST] 
      <FIELDS count field [field ...]>
    
  • HSETF command

    For each specified field value pair: set field to value and optionally set the field's expiration time in sec/msec /unix-sec/unix-msec:

    HSETF key 
      [DC] 
      [DCF | DOF] 
      [NX | XX | GT | LT] 
      [GETNEW | GETOLD] 
      [EX seconds | PX milliseconds | EXAT unix-time-seconds | PXAT unix-time-milliseconds | KEEPTTL] 
      <FVS count field value [field value …]>
    

Todo:

  • Performance improvement.
  • rdb load/save
  • aof
  • defrag

@tezc tezc requested review from moticless and sundb April 15, 2024 03:45
Comment thread src/t_hash.c
Comment thread src/t_hash.c
if (val != HASH_LP_NO_TTL && (uint64_t) val < minExpire)
minExpire = val;

fptr = lpNext(lpt->lp, fptr);
Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

sun: here could be a bottleneck, maybe we can add lpForEach with a callback method and use lpSkip to traverse lp internally, it will be much faster than three lpNext().

Comment thread src/listpack.h
@@ -0,0 +1,629 @@
######## HEXPIRE family commands
Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Github got confused and shows a huge diff for my commit here. Maybe looking it on git might help. It is better there.

Comment thread src/t_hash.c
@tezc tezc force-pushed the hfe-listpack-v1 branch from 83ba789 to b0be597 Compare April 20, 2024 00:34
Comment thread src/t_hash.c Outdated
Comment thread src/t_hash.c Outdated
Comment thread src/t_hash.c Outdated
Comment thread src/server.h Outdated
Comment thread src/object.c Outdated
Comment thread src/t_hash.c Outdated
Comment thread src/db.c Outdated
Comment thread src/listpack.h Outdated
Comment thread src/listpack.c Outdated
@tezc tezc force-pushed the hfe-listpack-v1 branch from c36381c to 5fe4b02 Compare April 26, 2024 09:05
@tezc tezc requested a review from ronen-kalish April 26, 2024 09:45
@tezc
Copy link
Copy Markdown
Collaborator Author

tezc commented Apr 27, 2024

@moticless I'm stuck adding hsetf to new setex api. It becomes too complex. I just realized I got setex api impl wrong for listpack even without hsetf (lost track of return values etc.). I started to feel like we would do better without an unified api (maybe it'd better to have some other smaller abstractions).

I pushed hgetf, I'll prepare and add hsetf without using setex api. There will be duplicated code for these but otherwise I cannot make progress. After that, maybe we'll find a way to reuse some code or you may have a better idea how to combine it to setex api. Meanwhile, please feel free to push changes to integration branch. I won't be able to do my work quickly anyway.

Comment thread src/db.c Outdated
Comment thread src/db.c Outdated
Comment thread src/db.c Outdated
Comment thread src/listpack.h
Comment thread src/t_hash.c Outdated
Copy link
Copy Markdown
Collaborator

@moticless moticless left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Impressive job.

Comment thread src/listpack.c Outdated
Comment thread src/listpack.c Outdated
Comment thread src/server.h Outdated
Comment thread src/server.h Outdated
Comment thread src/server.h Outdated
Comment thread src/t_hash.c
Comment thread src/t_hash.c Outdated
Comment thread src/t_hash.c
Comment thread src/t_hash.c
Comment thread src/t_hash.c
@tezc
Copy link
Copy Markdown
Collaborator Author

tezc commented May 8, 2024

As we discussed, I think we can address rioWriteHashIteratorCursor() and dismissHashObject() when we are dealing with AOF and RDB save.

Added support for debug listpack.

Comment thread src/t_hash.c Outdated
Comment thread src/t_hash.c Outdated
Comment thread src/listpack.c Outdated
Comment thread src/listpack.c
Comment thread src/t_hash.c Outdated
Comment thread src/t_hash.c Outdated
Comment thread src/listpack.h Outdated
Comment thread src/object.c
Comment thread src/t_hash.c
Comment thread src/t_hash.c
Comment thread src/t_hash.c
Comment thread src/object.c
break;
}
hashTypeFree(o);
}
Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

What I missed here is that there are flows that might release a hash-fields with TTLs not in the path of dbGenericDelete() and in turn an invalid item will be leftover dangling in global HFE DS. The following sequenece of commands is such example that release a hash and avoid calling dbGenericDelete():

  • HSET mykey f v
  • HEXPIRE mykey 1 1 f
  • SET mykey f

I tried to avoid adding dbid into listpackEx or dictExpireMetadata and placed a hook in dbGenericDelete() instead. But looks like we cannot escape it.

We can fix it on a distinct ticket for hash and listpack, add dbid to metadata and add the logic here.

Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Good catch. Looks like we don't have a test case doing something similar.

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As part of the fix we can add the test as well.

Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

let's handle that in a follow up pr

@tezc
Copy link
Copy Markdown
Collaborator Author

tezc commented May 8, 2024

@sundb @moticless @ronen-kalish Please approve if you don't have any additional comments. I'll merge it if daily run passes fine.

sundb
sundb previously approved these changes May 8, 2024
moticless
moticless previously approved these changes May 8, 2024
@tezc tezc dismissed stale reviews from moticless and sundb via 4bc8ade May 8, 2024 16:46
@tezc tezc merged commit ca4ed48 into redis:hash-field-expiry-integ May 8, 2024
Comment thread src/t_hash.c
Comment on lines +3369 to +3370
h = lpGetValue(tptr, NULL, &expire);
serverAssert(h == NULL);
Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ref #13243 (comment)

this assertiong will never be triggered.
you passed NULL to the second parameter of lpGetValue(), if the field is string, it will crash in *slen = ele_len;.

    vstr = lpGet(p, &ele_len, NULL);
    if (vstr) {
        *slen = ele_len;          <- here
    } else {
        *lval = ele_len;
    }

crash log:

=== REDIS BUG REPORT START: Cut & paste starting from here ===
64716:M 16 May 2024 11:55:33.528 # Redis 255.255.255 crashed by signal: 11, si_code: 1
64716:M 16 May 2024 11:55:33.528 # Accessing address: (nil)
64716:M 16 May 2024 11:55:33.528 # Crashed running the instruction at: 0x55c8922a2fa9

------ STACK TRACE ------
EIP:
./src/redis-server *:6379(lpGetValue+0x54)[0x55c8922a2fa9]

64716 redis-server *
/lib/x86_64-linux-gnu/libc.so.6(+0x45320)[0x701fc8a45320]
./src/redis-server *:6379(lpGetValue+0x54)[0x55c8922a2fa9]
./src/redis-server *:6379(+0x11140f)[0x55c89220b40f]
./src/redis-server *:6379(hgetfCommand+0x1a3)[0x55c89220b987]
./src/redis-server *:6379(call+0x143)[0x55c89219cb67]
./src/redis-server *:6379(processCommand+0xea1)[0x55c89219e6e1]
./src/redis-server *:6379(processCommandAndResetClient+0x39)[0x55c8921bbcc9]
./src/redis-server *:6379(processInputBuffer+0x1a0)[0x55c8921bbf4e]
./src/redis-server *:6379(readQueryFromClient+0x4b5)[0x55c8921bc516]
./src/redis-server *:6379(+0x1b836f)[0x55c8922b236f]
./src/redis-server *:6379(+0x1b8a98)[0x55c8922b2a98]
./src/redis-server *:6379(aeProcessEvents+0x24d)[0x55c892186438]
./src/redis-server *:6379(aeMain+0x2e)[0x55c892186676]
./src/redis-server *:6379(main+0xd5a)[0x55c8921a7ebe]
/lib/x86_64-linux-gnu/libc.so.6(+0x2a1ca)[0x701fc8a2a1ca]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0x8b)[0x701fc8a2a28b]
./src/redis-server *:6379(_start+0x25)[0x55c892180155]

what about adding a new method like int lpGetInteger(unsigned char *lp, long long *lval), return 1 if it's a integer.

Copy link
Copy Markdown
Collaborator Author

@tezc tezc May 16, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

how did you trigger this crash?
Edit: Ok, I see with corrupt restore, it is possible.

lpGetInteger() sounds good.

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

sundb@17b544f
it's easy to reproduce the corrupt by using the patch.
then run ./runtest --single integration/corrupt-dump-fuzzer --accurate
@tezc

sundb added a commit that referenced this pull request May 22, 2024
Add the following validations:
1. Get TTL using the lpGetIntegerValue() method instead of lpGetValue(),
Ref #13209 (comment)
2. The TTL of listpackex is a number in the valid range
(0~EB_EXPIRE_TIME_MAX) and ordered.
3. The TTL fields of listpackex are ordered. 
4. The TTL of hashtable is within the valid range
(0~EB_EXPIRE_TIME_MAX).

Other:
Fix the missing of handling OBJ_ENCODING_LISTPACK_EX in
dismissHashObject().

---------

Co-authored-by: Ozan Tezcan <[email protected]>
sundb added a commit that referenced this pull request May 29, 2024
* For replica sake, rewrite commands `H*EXPIRE*` , `HSETF`, `HGETF` to
have absolute unix time in msec.
* On active-expiration of field, propagate HDEL to replica
(`propagateHashFieldDeletion()`)
* On lazy-expiration, propagate HDEL to replica (`hashTypeGetValue()`
now calls `hashTypeDelete()`. It also takes care to call
`propagateHashFieldDeletion()`).
* Fix `H*EXPIRE*` command such that if it gets flag `LT` and it doesn’t
have any expiration on the field then it will considered as valid
condition.

Note, replicas doesn’t make any active expiration, and should avoid lazy
expiration. On `hashTypeGetValue()` it doesn't check expiration (As long
as the master didn’t request to delete the field, it is valid)

TODO: 
* Attach `dbid` to HASH metadata. See
[here](#13209 (comment))

---------

Co-authored-by: debing.sun <[email protected]>
@tezc tezc deleted the hfe-listpack-v1 branch April 8, 2025 21:07
funny-dog pushed a commit to funny-dog/redis that referenced this pull request Sep 17, 2025
**Changes:**
- Adds listpack support to hash field expiration 
- Implements hgetf/hsetf commands

**Listpack support for hash field expiration**

We keep field name and value pairs in listpack for the hash type. With
this PR, if one of hash field expiration command is called on the key
for the first time, it converts listpack layout to triplets to hold
field name, value and ttl per field. If a field does not have a TTL, we
store zero as the ttl value. Zero is encoded as two bytes in the
listpack. So, once we convert listpack to hold triplets, for the fields
that don't have a TTL, it will be consuming those extra 2 bytes per
item. Fields are ordered by ttl in the listpack to find the field with
minimum expiry time efficiently.

**New command implementations as part of this PR:** 

- HGETF command

For each specified field get its value and optionally set the field's
expiration time in sec/msec /unix-sec/unix-msec:
  ```
  HGETF key 
    [NX | XX | GT | LT]
[EX seconds | PX milliseconds | EXAT unix-time-seconds | PXAT
unix-time-milliseconds | PERSIST]
    <FIELDS count field [field ...]>
  ```

- HSETF command

For each specified field value pair: set field to value and optionally
set the field's expiration time in sec/msec /unix-sec/unix-msec:
  ```
  HSETF key 
    [DC] 
    [DCF | DOF] 
    [NX | XX | GT | LT] 
    [GETNEW | GETOLD] 
[EX seconds | PX milliseconds | EXAT unix-time-seconds | PXAT
unix-time-milliseconds | KEEPTTL]
    <FVS count field value [field value …]>
  ```

Todo:
- Performance improvement.
- rdb load/save
- aof
- defrag
funny-dog pushed a commit to funny-dog/redis that referenced this pull request Sep 17, 2025
Add the following validations:
1. Get TTL using the lpGetIntegerValue() method instead of lpGetValue(),
Ref redis#13209 (comment)
2. The TTL of listpackex is a number in the valid range
(0~EB_EXPIRE_TIME_MAX) and ordered.
3. The TTL fields of listpackex are ordered. 
4. The TTL of hashtable is within the valid range
(0~EB_EXPIRE_TIME_MAX).

Other:
Fix the missing of handling OBJ_ENCODING_LISTPACK_EX in
dismissHashObject().

---------

Co-authored-by: Ozan Tezcan <[email protected]>
funny-dog pushed a commit to funny-dog/redis that referenced this pull request Sep 17, 2025
* For replica sake, rewrite commands `H*EXPIRE*` , `HSETF`, `HGETF` to
have absolute unix time in msec.
* On active-expiration of field, propagate HDEL to replica
(`propagateHashFieldDeletion()`)
* On lazy-expiration, propagate HDEL to replica (`hashTypeGetValue()`
now calls `hashTypeDelete()`. It also takes care to call
`propagateHashFieldDeletion()`).
* Fix `H*EXPIRE*` command such that if it gets flag `LT` and it doesn’t
have any expiration on the field then it will considered as valid
condition.

Note, replicas doesn’t make any active expiration, and should avoid lazy
expiration. On `hashTypeGetValue()` it doesn't check expiration (As long
as the master didn’t request to delete the field, it is valid)

TODO: 
* Attach `dbid` to HASH metadata. See
[here](redis#13209 (comment))

---------

Co-authored-by: debing.sun <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants