dragonfly icon indicating copy to clipboard operation
dragonfly copied to clipboard

feat(generic_family): implement RANDOMKEY command

Open lsvmello opened this issue 1 year ago • 3 comments

Resolves #443.

Redis claims to have O(1) time complexity because:

  1. it sets a threshold of 100 tries to get a key, each try it:
  2. collects 15 entries from a random dict then:
  3. gets a random entry from those 15
  4. 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

lsvmello avatar Feb 21 '24 18:02 lsvmello

Sorry, I hit the submit button too early: thank you so much for your contribution!

chakaz avatar Feb 21 '24 18:02 chakaz

@chakaz the new solution:

  1. 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).
  2. Take a random key from every shard collection

lsvmello avatar Feb 23 '24 13:02 lsvmello

@chakaz I did the changes as you suggested

lsvmello avatar Feb 26 '24 20:02 lsvmello