DiceDB
[Solves #254] Add support for RANDOMKEY command
Hey @JyotinderSingh @arpitbbhayani,
Sorry if it was not allowed to initiate a pull without getting assigned (Issue #254) (If it was feel free to discard this MR).
I had implemented this some weeks back but did not get a reply so decided to commit and push the changes.
For now I've made it so that it uses the existing KEYS implementation and works in O(n). It took approximately 1ms for 100k key entries and 40ms for 1m entries based on the go test benchmark.
If we need it in O(1) might have to create a separate key slice to keep track of the keys and extract RANDOMKEY in O(1).
Additionally, I have skipped the loop to check if the RANDOMKEY is expired, so it is possible for a non-evicted expired key to be returned, again can make changes as needed for the requirement.
Thanks.
Hi @xanish, Thanks for the changes. Ideally, people work on the issues assigned to them, to avoid duplicate effort. Hopefully, this will answer your question, but if you would like to discuss more, drop a message on the discord community here.
Since the existing owner of the issue did not submit any PRs for a while, let's go ahead with this one. Assigning the issue to you. I'll go through this PR in a bit
If we have to get it done in less than O(0) time complexity, we would have to dive deep into the map implementation of Go.
I found this article which explores random key in O(1) space and O(L * (1 + k/n)) time, where n is the number of elements in the map, k is the "capacity" of the map (how many elements it can hold before being resized), and L is the length of the longest "bucket chain." Since Go maps double in size when they grow, the total time will generally not exceed 2x the normal map lookup time.
Article: https://lukechampine.com/hackmap.html Repo: https://github.com/lukechampine/randmap
We can take inspiration and maybe do something like this if it's possible? I have not understood it completely so not sure if it's production safe.
What do you guys think? @JyotinderSingh @apoorvyadav1111 @arpitbbhayani @soumya-codes @AshwinKul28
If we have to get it done in less than O(0) time complexity, we would have to dive deep into the map implementation of Go.
I found this article which explores random key in
O(1) space and O(L * (1 + k/n)) time, where n is the number of elements in the map, k is the "capacity" of the map (how many elements it can hold before being resized), and L is the length of the longest "bucket chain." Since Go maps double in size when they grow, the total time will generally not exceed 2x the normal map lookup time.Article: https://lukechampine.com/hackmap.html
Repo: https://github.com/lukechampine/randmap
We can take inspiration and maybe do something like this if it's possible?
I have not understood it completely so not sure if it's production safe.
What do you guys think?
@JyotinderSingh @apoorvyadav1111 @arpitbbhayani @soumya-codes @AshwinKul28
This is quite a big task to take up. Maybe we can put this off for later since it is not of the highest priority to have this command run in O(1) time.
Thanks for exploring and diving deep into this @SyedMa3. If someone wants to take up this task independently then that's great. However, the core team is stretched thin across a lot of the different projects which are going on right now and won't be able to provide active support on the initiative to make this run faster.
@JyotinderSingh @SyedMa3 lemme know if there is anything to be changed here.
@xanish thanks for working on this feature.
We are going to make multi-threading the default mode of operation for DiceDB in the coming days. We will need to migrate this command as a part of this change itself.
I'm pulling in @AshwinKul28 to help lead the discussion on that and guide you about it since multithreading support for this command will not be straightforward.
Feel free to take your time on the implementation.
Hey @AshwinKul28 can you direct me on this? i will have free time from this weekend so i can wrap this up.
Hey @JyotinderSingh @AshwinKul28 does everything seem fine here? Can we get it merged?
Hey @JyotinderSingh @AshwinKul28 does everything seem fine here? Can we get it merged?
Will review this soon, thanks for working on this!
Thank you for your submission! We really appreciate it. Like many open source projects, we ask that you sign our Contributor License Agreement before we can accept your contribution.
You have signed the CLA already but the status is still pending? Let us recheck it.
this is obsolete now. Closing the PR to keep things clean. Thanks for working on the patch.
@arpitbbhayani Does this need changes to incorporate for newer updates or is this being scrapped?