[c++] Resize Value allocation during RmwCopy

[matthewbrookes]

Motivation

We would like to be able to store variable length values in FASTER and use RMW to make them (potentially) bigger. As a motivating example we would like to store a String and then use RMW to modify the String based on the previous value .

Background

We have a set up for supporting variable length values similar to that used in these tests:

• https://github.com/microsoft/FASTER/blob/master/cc/test/in_memory_test.cc#L1319
• https://github.com/microsoft/FASTER/blob/master/cc/test/in_memory_test.cc#L596

Our RmwContext will call a function (defined elsewhere) with the old String to get the new String.

  class RmwContext : public IAsyncContext {
   public:
    typedef Key key_t;
    typedef Value value_t;

    RmwContext(uint64_t key)
      : key_{ key } {
    }

    /// Copy (and deep-copy) constructor.
    RmwContext(const RmwContext& other)
      : key_{ other.key_ } {
    }

    /// The implicit and explicit interfaces require a key() accessor.
    inline const Key& key() const {
      return key_;
    }
    inline uint32_t value_size() const {
      return sizeof(value_t); // This is where insufficient space is allocated
    }

    inline void RmwInitial(Value& value) {
      char* new_string = get_new_string("");
      value.gen_lock_.store(GenLock{});
      value.size_ = sizeof(Value) + sizeof(new_string);
      value.length_ = sizeof(new_string);
      std::memcpy(value.buffer(), new_string, sizeof(new_string));
    }
    inline void RmwCopy(const Value& old_value, Value& value) {
      char* new_string = get_new_string(old_value.buffer());
      value.gen_lock_.store(GenLock{});
      value.size_ = sizeof(Value) + sizeof(new_string);
      value.length_ = sizeof(new_string);
      std::memcpy(value.buffer(), new_string, sizeof(new_string));
    }
    inline bool RmwAtomic(Value& value) {
      bool replaced;
      while(!value.gen_lock_.try_lock(replaced) && !replaced) {
        std::this_thread::yield();
      }
      if(replaced) {
        // Some other thread replaced this record.
        return false;
      }
      char* new_string = get_new_string(value.buffer());
      if(value.size_ < sizeof(Value) + sizeof(new_string)) {
        // Current value is too small for in-place update.
        value.gen_lock_.unlock(true);
        return false;
      }
      // In-place update overwrites length and buffer, but not size.
      value.length_ = sizeof(new_string);
      memcpy(value.buffer(), new_string, sizeof(new_string));
      value.gen_lock_.unlock(false);
      return true;
    }

   protected:
    /// The explicit interface requires a DeepCopy_Internal() implementation.
    Status DeepCopy_Internal(IAsyncContext*& context_copy) {
      return IAsyncContext::DeepCopy_Internal(*this, context_copy);
    }

   private:
    Key key_;
};

Problem

This way of trying to use RMW to modify a String does not work because insufficient space is allocated for the new record. https://github.com/microsoft/FASTER/blob/master/cc/src/core/faster.h#L1076 shows that the new record will be given RmwContext::value_size() bytes for the new Value. In the case of a Value like in this example, we would need to know the size of new_string in order to know how much space to reserve for the new Value.

My Question

Is there a way in which we can resize a Value's allocation on the HybridLog during an RMW operation? With this we could extend the buffer of the new record to fit new_string. To be clear, I'm asking about resizing a record as it is being first written to, not a record already fully-created.

We could of course do a Read request then construct the new String and do an Upsert (given we now would know the required size to allocate) but this would be missing out on the ability to do an RMW in one operation. I guess it would still be possible to take advantage of in-place update during the Upsert?

[badrishc]

FASTER supports variable length values. Can you take a look at the below and see if it meets your requirements?

https://github.com/Microsoft/FASTER/wiki/Variable-length-values#in-c

[matthewbrookes]

Yep, but if the size of the new value is dependent upon the size of the old value then it's not possible to know the new size at the point which FASTER allocates space for the new record (i.e. from calling value_size() in the RmwContext).

So this would probably suggest the use-case I've outlined here isn't possible, right?

[matthewbrookes]

For reference, this is the issue on our side faster-rs/faster-rs#24

[badrishc]

This is fixable. I think we could have a variant of

inline uint32_t value_size()

that takes the existing record as argument, and the RMW op uses that when doing a copy on write. Thoughts?

[matthewbrookes]

I really like this idea and I've put together a PR (#145) with an implementation along those lines. Let me know what you think.