dragonfly
dragonfly copied to clipboard
feat(generic_family): implement RANDOMKEY command
Resolves #443.
Redis claims to have O(1)
time complexity because:
- it sets a threshold of 100 tries to get a key, each try it:
- collects 15 entries from a random
dict
then: - gets a random entry from those 15
- if the key is not expire, returns the key, else go back to step 2.
~So for this solution I set a threshold of 15 entries, and loop through all shards in parallel collecting 2 entries per child, then I take one random index of these collection.~
Sometimes the RANDOMKEY
command throws the following error on the std::vector<>::~vector()
:
*** SIGSEGV received at time=1708536096 on cpu 0 ***
PC: @ 0x55a4ffdb89f9 (unknown) mi_free
@ 0x55a5007d8b38 192 absl::lts_20230802::WriteFailureInfo()
@ 0x55a5007d910d 272 absl::lts_20230802::AbslFailureSignalHandler()
@ 0x7fcd9382d420 (unknown) (unknown)
@ 0x55a4fdb9c8d3 48 std::_Destroy<>()
@ 0x55a4fdb9cdda 48 std::_Destroy_aux<>::__destroy<>()
@ 0x55a4fdb9a97c 32 std::_Destroy<>()
@ 0x55a4fdb9ce35 48 std::_Destroy<>()
@ 0x55a4fdb9aad1 48 std::vector<>::~vector()
@ 0x55a4fddda8d7 1056 dfly::GenericFamily::RandomKey()
@ 0x55a4fde57d85 80 fu2::abi_400::detail::invocation::invoke<>()
@ 0x55a4fde54ab2 288 fu2::abi_400::detail::type_erasure::invocation_table::function_trait<>::internal_invoker<>::invoke()
@ 0x55a4ff566494 128 fu2::abi_400::detail::type_erasure::tables::vtable<>::invoke<>()
@ 0x55a4ff5667e0 240 fu2::abi_400::detail::type_erasure::erasure<>::invoke<>()
@ 0x55a4ff5669fd 240 fu2::abi_400::detail::type_erasure::invocation_table::operator_impl<>::operator()()
@ 0x55a4ff55b6d7 240 dfly::CommandId::Invoke()
@ 0x55a4fe2bbfc1 1520 dfly::Service::InvokeCmd()
@ 0x55a4fe2ba2b3 1776 dfly::Service::DispatchCommand()
@ 0x55a4ffbd3fc9 384 facade::Connection::DispatchCommand()
@ 0x55a4ffbd51fe 400 facade::Connection::ParseRedis()
@ 0x55a4ffbdbdc1 1264 facade::Connection::IoLoop()
@ 0x55a4ffbcf4d6 1808 facade::Connection::ConnectionFlow()
@ 0x55a4ffbc645d 1488 facade::Connection::HandleRequests()
@ 0x55a500348c23 1312 util::ListenerInterface::RunSingleConnection()
@ 0x55a500340fbd 48 util::ListenerInterface::RunAcceptLoop()::{lambda()#2}::operator()()
@ 0x55a5003643dc 48 std::__invoke_impl<>()
@ 0x55a500361067 32 std::__invoke<>()
@ 0x55a50035d9bb 32 std::__apply_impl<>()
@ 0x55a50035da32 48 std::apply<>()
@ 0x55a50035dd13 224 util::fb2::detail::WorkerFiberImpl<>::run_()
@ 0x55a50035b786 80 util::fb2::detail::WorkerFiberImpl<>::WorkerFiberImpl<>()::{lambda()#1}::operator()()
@ 0x55a5003703d1 80 std::__invoke_impl<>()
@ 0x55a50036dc03 80 std::__invoke<>()
@ ... and at least 4 more frames
Sorry, I hit the submit button too early: thank you so much for your contribution!
@chakaz the new solution:
- For each shard
a. gets a random Cursor based on the available segments and buckets and if it is empty the iterator is responsible for finding the next available entry (
Seek2Occupied
function). b. Then take 3 entries based on this Cursor (the first entry is random the next two are sequential, is that a problem?). c. If no entry was found, repeat step a and b (3 times). d. If, still, no entry was found, tries to take entries from the start of the shard (trying to garantee that we find something). - Take a random key from every shard collection
@chakaz I did the changes as you suggested