SRANDMEMBER RESP3 return should be Array, not Set #8504

hwware · 2021-02-16T20:00:40Z

SRANDMEMBER with negative count (non unique) can return the same member
multiple times, and the order of elements in the returned collection matters.
For these reasons returning a RESP3 Set type is not valid for the negative
count, but also not really valid for the positive (unique) variant either (the
command returns an array of random picks, not a set)

This PR also contains a minor optimization for SRANDMEMBER, HRANDFIELD,
and ZRANDMEMBER, to avoid the temporary dict from being rehashed while it grows.

Fixes #8503

fix typo

madolson · 2021-02-16T22:21:57Z

src/t_set.c

-        addReplySetLen(c,count);
+        /* if the count was negative, return as array type since the reply
+           may contain duplicate element */
+        !uniq ? addReplyArrayLen(c,count) : addReplySetLen(c,count);


Although I don't think this is technically wrong, I think this ternary operator is uncommon usage in C

Suggested change

!uniq ? addReplyArrayLen(c,count) : addReplySetLen(c,count);

if (!uniq)

addReplyArrayLen(c,count);

else

addReplySetLen(c,count)

fixed, thank you

madolson · 2021-02-16T22:33:15Z

hrandfield and zrandmember can also return distinct arrays, should we be returning them as sets? I don't see a conversation on the original PR #8297

oranagra · 2021-02-17T16:23:42Z

the response type for HRANDFIELD etc was discussed here: #8297 (comment)
but it was mainly about not responding with map type (see #8391).
i suppose i haven't noticed that SRANDMEMBER uses set type, and i think this is a bug.
IMHO it's a bug even when the provided COUNT argument is positive.

one would say that It might be too late to fix now due to backwards compatibility, but of course fixing if for a negative COUNT is a must (no debate about that).

note this part of the spec:

Sets are exactly like the Array type, but the first byte is ~ instead of *:
However they are semantically different because the represented items are unordered collections of elements so the client library should return a type that, while not necessarily ordered

in the non-unique (negative count) variant of these RAND* commands we also guarantee random order, not just random selection. so the set type response is invalid both because of repetition and also because of the order.
however, for the positive count we don't currently guarantee random order (some of the code paths just return all the elements of the collection at the order they're placed in the collection)

@redis/core-team please share your thoughts.
specifically: considering that RESP3 is somewhat new, do we feel we can change SRANDMEMBER <count> to always respond with an array rather than a set, or do we want to do that only for the negative count option?

oranagra · 2021-02-17T16:25:13Z

the next question would be if we wanna backport that fix to 6.0?
for the negative variant, i think we do.

madolson · 2021-02-17T22:08:43Z

"Normally Set replies should not contain the same element emitted multiple times, but the protocol does not enforce that: client libraries should try to handle such case, and in case of repeated elements, do some effort to avoid returning duplicated data, at least if some form of hash is used in order to return the reply. Otherwise when returning an array just reading what the protocol contains, duplicated items if present could be passed by client libraries to the caller. Many implementations will find it very natural to avoid duplicates. For instance they'll try to add every read element in some Map or Hash or Set data type, and adding the same element again will either replace the old copy or will fail silently, retaining the old copy."

Also from the spec, which clearly outlines the current negative count behavior is OK, so I don't really trust the spec. Still, the spec doesn't require the items be unordered, so I think the current behavior is fine. It's a little odd we go through the work to order the response and then immediately throw away the ordering.

https://redis.io/commands/srandmember documentation is also wrong. No mention of a set reply in Redis 6, which seems to be a pervasive issue with type changes in the docs.

madolson · 2021-02-17T22:09:20Z

I would vote to fix the negative count, backport it to 6, and do nothing else.

oranagra · 2021-02-18T06:52:45Z

@madolson i'm not sure i understand what you meant with that quote from the spec, and then saying "the current negative count behavior is OK"
it says that the client library should handle repeated elements by throwing them away. so a set reply when count is negative is very wrong.

And again, the spec does say the items in the set are unordered (meaning the client library can store them in a dict and lose the ordering), which makes it a bad fit for the negative count, in which we want to provide random order.
Array is the right type of response here for sure, and the current code is a bug, the only question in my mind is if we wanna change the positive count variant too.
it looks odd that other random commands always return an array, and this one returns either an array or a set depending on the input. i feel that considering RESP3 is relatively new, and not a default, maybe we can afford to fix it.

madolson · 2021-02-18T18:34:21Z

@oranagra The spec says that clients should handle set replies with duplicate items. I agree that we should fix the negative count case, I wasn't arguing about that.

The positive count case though, I think changing it is unnecessary backwards breaking change. There is nothing in the spec that says that set replies must be random. Unordered collection does not imply that the order is random. I think the response is fine.

itamarhaber · 2021-02-20T15:23:24Z

Negative fix & backport: aye.
Fix type from set to array: aye (RESP3 is still beta-ish) and backport :)

yossigo · 2021-02-20T18:41:39Z

I think we should always return an array, it's more uniform and better describes what we're returning even if technically a set could fit.

In a more general tone, given the other RESP3 bugs we've seen I think we need to give more weight to fixing for correctness rather than maintaining backwards compatibility.

oranagra · 2021-02-21T07:20:15Z

@oranagra The spec says that clients should handle set replies with duplicate items

@madolson The spec says the client should handle that by removing these duplicate items if found.
I think that unlike SMEMBERS and other set commands, this one should always respond with an array of random items, not a set (it was a mistake the change the type in RESP3).

i'll put it like this:
Imagine that RESP3 would have been added just now (in 6.2), and there are no backwards compatibility concerns. would you think that negative count should reply with an array and positive count with a set?

I agree with Yossi, RESP3 is "beta", and we want to fix these bugs rather than keep them for eternity, and given its low adoption, i hope it won't cause much harm.

the only question in my eyes is if this should be backported to redis 6.0 or not.
I see Itamar was in favor, not sure about Yossi?

yossigo · 2021-02-21T09:22:09Z

@oranagra I think it should be backported, we should accept some RESP3 pain but get things right rather than leave things awkward forever or have fixes diverge across versions.

madolson · 2021-02-22T04:50:33Z

@oranagra I concede that if we started from scratch, I think using arrays for both positive and negative count makes the most sense. I'm against backwards incompatible changes, and I don't think that returning a set type for positive count is so wrong that we should break the contract for that. It looks like there is already a majority in favor of doing that though, so I'm fine with committing to that approach.

@hwware, do you want to update the PR to return an array type for both positive and negative count values?

oranagra · 2021-02-22T10:07:04Z

I strongly feel that we wanna fix this (for positive count too) rather than live with the bug forever.

But we said we're not gonna introduce breaking changes in patch level releases, so this means that in some cases we avoid fixing a bug if it causes compatibility issues, and let that old version remain buggy.
on a major/minor release people should read the release notes and be aware of the compatibility issues.

In retrospect maybe we shouldn't even have fixed #8266 in 6.0.10, and should have let 6.0 keep that bug.
I suppose that if we find a bug that's broken since forever and fixing it introduces compatibility issues, we won't fix it now in a patch level. but if we find a bug in a new mechanism added in 6.0.0 it would be ok to fix it in 6.0.3 (released a few weeks after the bug was released), but not necessarily ok to fix it in 6.0.11 (nearly a year later).

The special consideration in both this PR and the one in #8266, is that we think the bug is in code that's not yet widely used, in which case we want to fix it ASAP before people use it, but i suppose we can take the safe approach and not backport this fix.

oranagra · 2021-02-22T11:49:44Z

turns out changing the response type of CASE2 wasn't so easy since the code redirected the call to sunionDiffGenericCommand.
this was a quick way to code it, but a bit inefficient and non-flexible.
instead i now iterate on the set reply directly.
also, i saw an opportunity to optimize the temporary dict and avoid rehashing in it, so i hogged that PR to do that for other RAND commands too (sorry for hogging).

hwware · 2021-02-23T03:49:44Z

sorry @oranagra @madolson , was late for discussion, but the idea of using array type and the code change of this pr looks good to me..

Harrison88 · 2021-02-24T04:07:02Z

Since it was decided to always return an array, should similar commands like SPOP also be changed to return an array?

oranagra · 2021-02-24T07:05:21Z

@Harrison88 i thought about it too, but i don't think SPOP needs to change.
I know it's very similar in some aspects (random picking), but since they're no chance of repetition, and i don't feel the order matters for the use cases it serves, i think it should return similar type to SMEMBERS.
@itamarhaber maybe you have some input?

SRANDMEMBER with negative count (non unique) can return the same member multiple times, and the order of elements in the returned collection matters. For these reasons returning a RESP3 Set type is not valid for the negative count, but also not really valid for the positive (unique) variant either (the command returns an array of random picks, not a set) This PR also contains a minor optimization for SRANDMEMBER, HRANDFIELD, and ZRANDMEMBER, to avoid the temporary dict from being rehashed while it grows. Co-authored-by: Oran Agra <oran@redislabs.com>

see: * redis/redis#8391 * redis/redis#8504 Co-authored-by: Oran Agra <oran@redislabs.com>

hwware force-pushed the srandmember_res branch from 431c81d to dc9c86d Compare February 16, 2021 20:10

fix SRANDMEMBER negative return type

291e23f

fix typo

hwware force-pushed the srandmember_res branch from dc9c86d to 291e23f Compare February 16, 2021 20:13

madolson reviewed Feb 16, 2021

View reviewed changes

oranagra added state:major-decision Requires core team consensus release-notes indication that this issue needs to be mentioned in the release notes labels Feb 17, 2021

fix review comments

62e42ea

oranagra added 2 commits February 22, 2021 12:15

SRANDMEMBER with COUNT always replies with Array in RESP3

157d89d

SRANDMEMBER case 2, use Array reply in RESP3, and minor optimization

ed383a9

yossigo approved these changes Feb 22, 2021

View reviewed changes

oranagra changed the title ~~Fix SRANDMEMBER return type with negative count~~ Fix SRANDMEMBER RESP3 return should be Array, not Set Feb 22, 2021

oranagra changed the title ~~Fix SRANDMEMBER RESP3 return should be Array, not Set~~ SRANDMEMBER RESP3 return should be Array, not Set Feb 22, 2021

oranagra merged commit f5235b2 into redis:unstable Feb 22, 2021

oranagra mentioned this pull request Feb 22, 2021

Redis 6.2.0 GA #8525

Merged

enjoy-binbin mentioned this pull request Jan 11, 2022

LPOP/RPOP with count against non existing list return null array #10095

Merged

oranagra mentioned this pull request Jan 5, 2023

close #6 - change map to unordered redis/redis-specifications#7

Merged

oranagra added a commit to redis/redis-specifications that referenced this pull request Jan 5, 2023

change map to unordered (#7)

dbee7ab

see: * redis/redis#8391 * redis/redis#8504 Co-authored-by: Oran Agra <oran@redislabs.com>

SRANDMEMBER RESP3 return should be Array, not Set #8504

SRANDMEMBER RESP3 return should be Array, not Set #8504

Uh oh!

Conversation

hwware commented Feb 16, 2021 • edited by oranagra Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

madolson Feb 16, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

hwware Feb 19, 2021

Choose a reason for hiding this comment

Uh oh!

madolson commented Feb 16, 2021

Uh oh!

oranagra commented Feb 17, 2021

Uh oh!

oranagra commented Feb 17, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

madolson commented Feb 17, 2021

Uh oh!

madolson commented Feb 17, 2021

Uh oh!

oranagra commented Feb 18, 2021

Uh oh!

madolson commented Feb 18, 2021

Uh oh!

itamarhaber commented Feb 20, 2021

Uh oh!

yossigo commented Feb 20, 2021

Uh oh!

oranagra commented Feb 21, 2021

Uh oh!

yossigo commented Feb 21, 2021

Uh oh!

madolson commented Feb 22, 2021

Uh oh!

oranagra commented Feb 22, 2021

Uh oh!

oranagra commented Feb 22, 2021

Uh oh!

hwware commented Feb 23, 2021

Uh oh!

Harrison88 commented Feb 24, 2021

Uh oh!

oranagra commented Feb 24, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

hwware commented Feb 16, 2021 •

edited by oranagra

Loading

madolson Feb 16, 2021 •

edited

Loading

oranagra commented Feb 17, 2021 •

edited

Loading