How are keys in KV Store locked?

php Editor Zimo will reveal the secret of key locking in KV Store for you. In KV Store, key locking is achieved through a series of complex algorithms and technologies. First, the system generates a unique identifier for each key and stores it with the corresponding value in the database. At the same time, the system will also use a hash function to encrypt the key to ensure its security. In addition, the system also uses access control lists (ACLs) to restrict access to keys so that only authorized users can perform read and write operations. Through these security measures, KV Store ensures the security and reliability of keys and provides users with safe and reliable data storage services.

Question content

I am building a distributed kv store just to learn more about distributed systems and concurrency. The implementation of kv storage I'm building is fully transactional, with an in-memory transaction log. To keep things simple, storage is also entirely in-memory. The api exposes get, insert, update, remove. Note that all endpoints operate on a single key, not a range of keys.

I manage concurrency through locks. However, I have a global lock that locks the entire data store. This sounds very inefficient, because if I want to read the value of k1 while updating k2, I have to wait for k2 to finish updating, although that's irrelevant.

I know some databases use more fine-grained locking. For example, in mysql server there are row level locks. How to implement key-level locking?

I have

type storage struct {
  store map[string]int32
}

Should I add something like this? ：

type Storage struct {
  store map[string]int32
  locks map[string]mutex.Lock
}

If I do this, the problem is that locks must be kept in sync with store. Another option would be to merge the two maps, but even then I would encounter removing entries in the map while locked if the remove request comes before the get The problem.

Solution

Concept part

trade

First of all, strong consistency does not require transaction logs. Transaction logs are useful for maintaining acid properties.

Transactions are also not a strict requirement for strong consistency in a database, but they can be a useful tool for ensuring consistency in many situations.

Strong consistency refers to the property that ensures that all reads from the database will return the most recent write, regardless of where the read operation is performed. In other words, strong consistency guarantees that all clients will see the same data and that the data will be up-to-date and consistent across the system.

You can use consensus algorithms such as paxos or raft to ensure strong consistency. When storing data, you can store a version of the data and use it as an id in paxos.

Lock kv storage

In a key-value (kv) store, keys are usually locked using some kind of locking mechanism, such as a mutex or reader-writer lock (as @paulsm4 suggested). This allows multiple threads or processes to access and modify data in the kv store simultaneously while still ensuring that the data remains consistent and correct.

For example, when a thread or process wants to read or modify a specific key in the kv store, it can acquire a lock on that key. This prevents other threads or processes from modifying the same key at the same time, causing race conditions and other problems. Once a thread or process has finished reading or modifying the key, the lock can be released, allowing other threads or processes to access the key.

The specific details of how keys are locked in kv storage may vary depending on the implementation of kv storage. Some kv stores may use global locks (as you are already doing, which is sometimes inefficient) to lock the entire data store, while other kv stores may use more fine-grained locking mechanisms such as row-level locks or key-level Lock to allow more operations. Concurrent access to data.

So, tldr; conceptually, you're right. The problem lies in the implementation details of locking.

coding

To strictly answer the question about locking, consider reader-writer locks as @paulsm4 suggested. In golang, a similar lock is rwmutex. It is used for sync. map.

Here is a short example:

type Storage struct {
  store sync.Map // a concurrent map
}

// GET retrieves the value for the given key.
func (s *Storage) GET(key string) (int32, error) {
  // Acquire a read lock for the key.
  v, ok := s.store.Load(key)
  if !ok {
    return 0, fmt.Errorf("key not found: %s", key)
  }

  // Return the value.
  return v.(int32), nil
}

// INSERT inserts the given key-value pair into the data store.
func (s *Storage) INSERT(key string, value int32) error {
  // Acquire a write lock for the key.
  s.store.Store(key, value)
  return nil
}

// UPDATE updates the value for the given key.
func (s *Storage) UPDATE(key string, value int32) error {
  // Acquire a write lock for the key.
  s.store.Store(key, value)
  return nil
}

// REMOVE removes the key-value pair for the given key from the data store.
func (s *Storage) REMOVE(key string) error {
  // Acquire a write lock for the key.
  s.store.Delete(key)
  return nil
}

In addition to this, you need paxos to ensure consistency between replicas.

The above is the detailed content of How are keys in KV Store locked?. For more information, please follow other related articles on the PHP Chinese website!