fix(set): fix random in SRANDMEMBER and SPOP commands #3022

BagritsevichStepan · 2024-05-07T15:03:03Z

For IntSet, the time complexity is O(n) (n - number of elements to return/remove). The space complexity is also O(n)
For StrSet, the time complexity is O(m) (m - number of elements in set). The space complexity is O(n)

mapleFU · 2024-05-07T15:54:33Z

src/server/common.h

+
+class NonUniquePicksGenerator : public PicksGenerator {
+ public:
+  NonUniquePicksGenerator(RandomPick max_range);


We can add a comment for max_range is open or closed

mapleFU · 2024-05-07T15:56:41Z

src/server/set_family.cc

@@ -284,19 +284,32 @@ void InterStrSet(const DbContext& db_context, const vector<SetType>& vec, String
  }
 }

-StringVec PopStrSet(const DbContext& db_context, unsigned count, const SetType& st) {
+StringVec RandMemberStrSet(const DbContext& db_context, const SetType& st,
+                           const std::unique_ptr<PicksGenerator>& generator,


Would a virtual function making it even slower?

You can pass just const PicksGenerator&

I don't think the virtual function call adds any mesurable latency 🙂

I agree with @dranikpg, keep the virtual function call as it was

dranikpg

Sorry if this was not ready for review, just strolling by 👣

dranikpg · 2024-05-07T20:19:51Z

src/server/set_family.cc

-      std::copy(result.begin(), result.end(), mapped.begin() + 1);
-      RecordJournal(op_args, "SREM"sv, mapped);
-    }
+  StringVec rand_members = rand_members_result.value();


that's a copy 👮🏻

dranikpg · 2024-05-07T20:21:11Z

src/server/set_family.cc

+  ArgSlice span{members_to_remove.data(), members_to_remove.size()};
+
+  auto rem_members_result = OpRem(op_args, key, span, false);
+  if (!rem_members_result) {
+    return rem_members_result.status();
  }


RETURN_ON_BAD_STATUS(op_args, key, absl::MakeSpan(members), false) 😅

dranikpg · 2024-05-07T20:23:01Z

src/server/set_family.cc

+  int count = 1;
  if (args.size() > 1) {
    string_view arg = ArgS(args, 1);
    if (!absl::SimpleAtoi(arg, &count)) {


This changes what overload of SimpleAtoi is selected

dranikpg · 2024-05-07T20:23:52Z

src/server/set_family_test.cc

+auto ConsistsOf(std::initializer_list<std::string> elements) {
+  return ConsistsOfMatcher(std::unordered_set<std::string>{elements});
+}


Please explain what this means 😀

This means хороший код

хороший кот

dranikpg · 2024-05-07T20:26:38Z

src/server/set_family.cc

+  std::unique_ptr<PicksGenerator> generator =
+      picks_are_unique ? static_cast<std::unique_ptr<PicksGenerator>>(
+                             std::make_unique<UniquePicksGenerator>(picks_count, size))
+                       : std::make_unique<NonUniquePicksGenerator>(size);


ok mabye the function thing was more readable 😆 You can always also just use a declaration and an if after

Ok, I'll fix it in zset_family.cc too

dranikpg · 2024-05-07T20:28:48Z

src/server/set_family.cc

@@ -284,19 +284,32 @@ void InterStrSet(const DbContext& db_context, const vector<SetType>& vec, String
  }
 }

-StringVec PopStrSet(const DbContext& db_context, unsigned count, const SetType& st) {
+StringVec RandMemberStrSet(const DbContext& db_context, const SetType& st,
+                           const std::unique_ptr<PicksGenerator>& generator,


You can pass just const PicksGenerator&

I don't think the virtual function call adds any mesurable latency 🙂

dranikpg · 2024-05-07T20:35:02Z

src/server/set_family.cc

+  std::uint32_t ss_entry_index = 0;
+  for (const sds ptr : *ss) {
+    std::uint32_t t = times_index_is_picked[ss_entry_index++];
+    while (t--) {
+      result.emplace_back(ptr, sdslen(ptr));
    }


you use an unordered_map, but during iteration you'll end up creating every cell up to N because of [ss_entry_index], so better use find()

dranikpg · 2024-05-07T20:36:32Z

src/server/set_family.cc

    }
  }

+  /* Members in result are sorted by scores. So, it is necessary to shuffle them*/


Scores? I think you just mean that equal elements are always succesive and we're limited by the string-set order

dranikpg · 2024-05-07T20:37:57Z

src/server/set_family.cc

+      int64_t value;
+      DCHECK_GT(intsetGet(is, picked_index, &value), std::uint8_t(0));
+


DCHECK it's not called in release builds 🙂

fixes dragonflydb#3018 Signed-off-by: Stepan Bagritsevich <sbagritsevich@quantumbrains.com>

BagritsevichStepan · 2024-05-09T06:37:18Z

Fix a bug where replicas remove other elements during SPOP. Now all the tests are passed. @dranikpg , please take a look.

dranikpg

👍🏻 (Please push separate commits in the future so it's easier to see changes)

mapleFU reviewed May 7, 2024

View reviewed changes

dranikpg reviewed May 7, 2024

View reviewed changes

BagritsevichStepan force-pushed the srandmember_spop_fix branch from 0f19aa7 to 74b498d Compare May 8, 2024 16:33

BagritsevichStepan requested a review from dranikpg May 8, 2024 16:34

BagritsevichStepan force-pushed the srandmember_spop_fix branch from 74b498d to a1162b7 Compare May 8, 2024 17:34

fix(set): fix random in SRANDMEMBER and SPOP commands

1111eb5

fixes dragonflydb#3018 Signed-off-by: Stepan Bagritsevich <sbagritsevich@quantumbrains.com>

BagritsevichStepan force-pushed the srandmember_spop_fix branch from a1162b7 to 1111eb5 Compare May 9, 2024 06:05

dranikpg approved these changes May 9, 2024

View reviewed changes

dranikpg merged commit d3a5851 into dragonflydb:main May 13, 2024
7 checks passed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

fix(set): fix random in SRANDMEMBER and SPOP commands #3022

fix(set): fix random in SRANDMEMBER and SPOP commands #3022

BagritsevichStepan commented May 7, 2024

mapleFU May 7, 2024

BagritsevichStepan May 8, 2024

mapleFU May 7, 2024

dranikpg May 7, 2024

BagritsevichStepan May 8, 2024

dranikpg left a comment

dranikpg May 7, 2024

dranikpg May 7, 2024

dranikpg May 7, 2024

dranikpg May 7, 2024

BagritsevichStepan May 8, 2024

dranikpg May 9, 2024

romange May 9, 2024

dranikpg May 7, 2024 •

edited

BagritsevichStepan May 8, 2024 •

edited

dranikpg May 7, 2024

dranikpg May 7, 2024 •

edited

dranikpg May 7, 2024

dranikpg May 7, 2024

BagritsevichStepan commented May 9, 2024 •

edited

dranikpg left a comment

		int64_t value;
		DCHECK_GT(intsetGet(is, picked_index, &value), std::uint8_t(0));

fix(set): fix random in SRANDMEMBER and SPOP commands #3022

fix(set): fix random in SRANDMEMBER and SPOP commands #3022

Conversation

BagritsevichStepan commented May 7, 2024

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

dranikpg left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

dranikpg May 7, 2024 • edited

Choose a reason for hiding this comment

BagritsevichStepan May 8, 2024 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

dranikpg May 7, 2024 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

BagritsevichStepan commented May 9, 2024 • edited

dranikpg left a comment

Choose a reason for hiding this comment

dranikpg May 7, 2024 •

edited

BagritsevichStepan May 8, 2024 •

edited

dranikpg May 7, 2024 •

edited

BagritsevichStepan commented May 9, 2024 •

edited