关于读写锁粒度的思考

在写extendible hashtable的过程中，对于其并发控制中读写锁的粒度选择一事感到困惑。

在数据库事务并发控制中，有三种冲突需要避免（根据隔离级别，可以选择哪些也可以容忍）：

  • unrepeated read（读 -> 写）
  • overwrite（写 -> 写）
  • dirty read（写 -> 读）

但是相比事务而言，数据结构的操作相当于只有一个操作的事务，因此第一种和第三种其实是可以容忍并由事务的并发控制去管理。

但是对于(写->写)这样的操作顺序，却很可能导致出现问题，破坏不变式

比如Insert()在读完direcotory的数据之后，将读锁释放，此时bucket是满的，调用SplitInsert()就需要上对应bucket的写锁（对于bucket都有一个读写锁以减少争用），但是如果上在directory的读锁释放后bucket的写锁前这个时间点就被切出线程到另一个线程也调用Insert()并且key是同一个bucket的，那么就会导致切回来bucket已经不是原来的bucket了（相关的断言也会触发），之后的处理也应视作UB（undefined behavior）。

策略 优点 缺点
细粒度 锁争用（lock contention）的机会减少 由于解锁可能将线程切出去，且其他线程也有写者的话，很可能导致行为不正确
粗粒度 弥补了细粒度锁的缺点，不会莫名出现冲突 锁争用可能比较激烈

同时，对于读操作，我觉得读锁是可以容忍细粒度的，即便此时数据被插入或删除

但是对于extenditble hashtable来说，table_latch和bucket_latch还是不能分离，因为bucket的page id等都是通过directory获取的，如果别的线程调用Remove()，那么这个page id就有无效的可能。

所以我的建议还是，先用粗粒度保证行为正确，之后看是否可以细化，不然都是白搭。