Optimization of Lua Global Locks

[i18nsite]

Search before asking

• I had searched in the issues and found no similar issues.

Motivation

Kvrocks 是目前开源磁盘 Redis 里面同时支持 Lua 和事务的选型，同时在命令支持上也是比较完善。为了简化实现复杂度，Lua 和事务相关命令执行时会限制为类似 Redis 的单线程执行。实现方式是在 Lua 和事务相关执行命令加上全局锁，代码如下:

---

我这个感觉其实可以根据redis lua函数的keys来锁定，不需要做全局锁。
为了避免兼容问题，可以加一个配置选项，lua_lock_level = global / keys ，确认可以用键级锁的自己打开

---

redis 规范： https://redis.io/docs/interact/programmability/eval-intro/

重要提示：为了确保脚本的正确执行，无论是在独立部署还是集群部署中，脚本访问的所有键名称都必须显式提供作为输入键参数。该脚本应该只访问其名称作为输入参数给出的键。脚本永远不应访问具有以编程方式生成的名称或基于数据库中存储的数据结构内容的密钥。

---

Kvrocks is an open-source disk-based Redis that simultaneously supports Lua scripts and transactions, and is also quite comprehensive in terms of command support. To simplify the complexity of implementation, the execution of Lua scripts and transaction-related commands is restricted to single-threaded execution similar to Redis. The implementation method involves adding a global lock when executing Lua scripts and transaction-related commands.

I think this approach could potentially be modified to lock based on keys rather than a global lock. To avoid compatibility issues, a configuration option could be added, such as lua_lock_level=global / keys, allowing users to enable key-level locking if they confirm it works as expected.

https://redis.io/docs/interact/programmability/eval-intro/

Important: to ensure the correct execution of scripts, both in standalone and clustered deployments, all names of keys that a script accesses must be explicitly provided as input key arguments. The script should only access keys whose names are given as input arguments. Scripts should never access keys with programmatically-generated names or based on the contents of data structures stored in the database.

[git-hulk]

@i18n-now Thanks for your suggestion.

[i18nsite]

可以参考

https://www.dragonflydb.io/blog/leveraging-power-of-lua-scripting

Leveraging the power of Lua scripting with Dragonfly
利用 Dragonfly 的 Lua 脚本编写能力

This blog post discusses the limitations of Lua scripting in Redis and introduces Dragonfly as a drop-in replacement for Redis. Dragonfly addresses the challenges of long-running scripts and scalability, offering a vertically scalable, multi-threaded, and asynchronous architecture that improves performance and efficiency for Lua scripting in Redis.

这篇博文讨论了 Redis 中 Lua 脚本的局限性，并介绍了 Dragonfly 作为 Redis 的直接替代品。 Dragonfly 解决了长时间运行的脚本和可扩展性的挑战，提供了垂直可扩展、多线程和异步架构，提高了 Redis 中 Lua 脚本的性能和效率。

---

Dragonfly的多线程、异步架构为长时间运行和/或计算量大的脚本提供了更好的性能

Redis 以单线程方式运行，这意味着它一次处理一个操作。当执行长时间运行或计算量大的 Lua 脚本时，这会成为瓶颈，因为它们可能会阻止其他操作直到完成。

另一方面，Dragonfly 是围绕多线程、异步架构构建的。这种方法有几个优点。首先，由于并行处理，它提高了吞吐量。其次，它允许多个脚本执行单元同时运行，这对于计算密集型脚本特别有利，例如那些计算哈希值或聚合值的脚本。

此外，Dragonfly 支持异步性，这意味着只要保留脚本的原子性，常规命令就可以与已运行脚本中的命令混合。这使得 Dragonfly 即使在脚本执行时也可用于传入请求。

[PokIsemaine]

@i18n-now I'm interested in this question, but I don't know much about dragonfly's code at the moment. Do you have any reference materials that can help me quickly understand its overall framework and process?

Currently I found this: https://github.com/dragonflydb/dragonfly/blob/main/docs/transaction.md

[mapleFU]

@PokIsemaine You can refer to Service::EvalInternal for detail

[i18nsite]

大多数的 Redis 兼容服务还是采用了轻量锁的方案，这样比较容易做到兼容，Dragonfly 的实现是参考了《VLL: a lock manager redesign for main memory database systems》[7]里的 VLL 方案。不过从支持的接口[8]列表看，Dragonfly 尚未完全兼容 Redis 的接口。

https://zhuanlan.zhihu.com/p/584485562

为了提供对多键并发操作的原子性保证，我们使用了最近学术研究的进展。我们选择了论文 "VLL: a lock manager redesign for main memory database systems” 来开发Dragonfly的事务框架。无共享式架构和VLL的选择使我们能够在不使用互斥锁或自旋锁的情况下组合原子的多键操作。这是我们 PoC 的一个重要里程碑，它的性能在商业和开源解决方案中脱颖而出。

我们面临的第二个挑战是为新存储设计更高效的数据结构。为了实现这个目标，我们基于论文"Dash: Scalable Hashing on Persistent Memory"构建了核心哈希表结构。这篇论文本身是以持久性内存为中心的，与主存没有直接相关性。
https://github.com/dragonflydb/dragonfly/blob/main/README.zh-CN.md

[PokIsemaine]

之前有提到过 Redis 的事务隔离级别是 Serializable（序列化），那么想做到完全的兼容就必须保持一致。内存数据库和传统基于磁盘的数据库在体系结构上有很大的区别。内存事务不会涉及到 IO 操作，性能瓶颈就从磁盘转移到了 CPU 上。比较成熟的并发协议有：轻量锁、时间戳、多版本、串行等方式。大多数的 Redis 兼容服务还是采用了轻量锁的方案，这样比较容易做到兼容，Dragonfly 的实现是参考了《VLL: a lock manager redesign for main memory database systems》[7]里的 VLL 方案。不过从支持的接口[8]列表看，Dragonfly 尚未完全兼容 Redis 的接口。

• kvrocks 现在使用了 src/common/lock_manager.h 中的 LockManager，这个现在是瓶颈所在吗？因为 kvrocks 并不是 in memory database，我们是否有必要重新设计一个轻量级锁方案？

• 同时我看到参考文献里提到并发引擎的 HashMap 应该支持 「渐进式 rehash」以及「并发修改过程中的无状态扫描」，这两点 kvrocks 现在是支持的吗？或者有必要支持吗？

It was mentioned before that the transaction isolation level of Redis is Serializable (serialization), so it must be consistent if you want to be fully compatible. There is a big architectural difference between in-memory databases and traditional disk-based databases. Memory transactions do not involve IO operations, and the performance bottleneck is transferred from the disk to the CPU. More mature concurrency protocols include: lightweight locks, timestamps, multi-versions, serialization, etc. Most Redis compatible services still use lightweight lock solutions, which are easier to achieve compatibility. The implementation of Dragonfly refers to "VLL: a lock manager redesign for main memory database systems" [7] VLL solution. However, judging from the list of supported interfaces [8], Dragonfly is not yet fully compatible with the Redis interface.

• kvrocks now uses the LockManager in src/common/lock_manager.h. Is this the bottleneck now? Because kvrocks is not in memory database, is it necessary for us to redesign a lightweight lock scheme？

• At the same time, I saw in the reference article that the HashMap of the concurrent engine should support "progressive rehash" and "stateless scanning during concurrent modifications." Are these two points supported by kvrocks now? Or is support necessary?