rowlock.go 9.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368
  1. package storage
  2. import (
  3. "errors"
  4. "strings"
  5. "sync"
  6. "sync/atomic"
  7. "time"
  8. )
  9. // Row-lock contention outcomes. ErrRowLocked is intentionally reported to the
  10. // client as a serialization failure (40001): the optimistic commit model makes
  11. // a conflicting writer retry rather than block.
  12. var (
  13. ErrRowLocked = errors.New("row is locked by another transaction")
  14. ErrLockNotAvailable = errors.New("row lock is not available")
  15. ErrDeadlockDetected = errors.New("deadlock detected")
  16. )
  17. // LockMode is the strength of a locking read.
  18. type LockMode uint8
  19. const (
  20. LockUpdate LockMode = iota
  21. LockShare
  22. )
  23. // LockWait is the contention policy of a locking read.
  24. type LockWait uint8
  25. const (
  26. LockWaitBlock LockWait = iota
  27. LockWaitNoWait
  28. LockWaitSkip
  29. )
  30. type rowLockEntry struct {
  31. mu sync.Mutex
  32. closed bool
  33. owners map[*Session]LockMode
  34. // waiters are signalled when an owner releases. A waiter retries the
  35. // acquisition instead of receiving ownership directly: a release can wake
  36. // several compatible readers.
  37. waiters map[chan struct{}]struct{}
  38. }
  39. func (e *rowLockEntry) ownerList() []*Session {
  40. owners := make([]*Session, 0, len(e.owners))
  41. for owner := range e.owners {
  42. owners = append(owners, owner)
  43. }
  44. return owners
  45. }
  46. // RowLockManager holds in-process row locks. Locking reads create entries;
  47. // ordinary writes do not. A write checks the entries at its durable batch
  48. // boundary and fails with ErrSerialization if another transaction holds one.
  49. //
  50. // gate is a reader/writer gate around lock insertion checks and the write-side
  51. // check. A write holds it for reading from the check through publication, so a
  52. // lock cannot be inserted in the window between "no lock seen" and "committed".
  53. // Waiting for a row lock never holds gate.
  54. type RowLockManager struct {
  55. gate sync.RWMutex
  56. entries sync.Map // string (data key) -> *rowLockEntry
  57. active atomic.Int64
  58. waitMu sync.Mutex
  59. waits map[*Session]*Session
  60. }
  61. func NewRowLockManager() *RowLockManager {
  62. return &RowLockManager{waits: make(map[*Session]*Session)}
  63. }
  64. // Active reports whether any row locks are currently held. Callers use it to
  65. // skip the map scan on the normal, lock-free path.
  66. func (l *RowLockManager) Active() bool {
  67. l.gate.RLock()
  68. defer l.gate.RUnlock()
  69. return l.active.Load() > 0
  70. }
  71. func (l *RowLockManager) entry(key string) (*rowLockEntry, bool) {
  72. value, ok := l.entries.Load(key)
  73. if !ok {
  74. return nil, false
  75. }
  76. return value.(*rowLockEntry), true
  77. }
  78. // tryLock acquires key if it is free or compatible. The caller must hold gate.
  79. func (l *RowLockManager) tryLock(owner *Session, key string, mode LockMode) (bool, *Session) {
  80. e, ok := l.entry(key)
  81. if !ok {
  82. e = &rowLockEntry{owners: make(map[*Session]LockMode), waiters: make(map[chan struct{}]struct{})}
  83. e.owners[owner] = mode
  84. l.entries.Store(key, e)
  85. l.active.Add(1)
  86. return true, nil
  87. }
  88. e.mu.Lock()
  89. if e.closed {
  90. // A concurrent Release deleted this entry after we loaded it. We hold
  91. // gate for writing, so it is safe to replace it with a fresh entry.
  92. e.mu.Unlock()
  93. e = &rowLockEntry{owners: make(map[*Session]LockMode), waiters: make(map[chan struct{}]struct{})}
  94. e.owners[owner] = mode
  95. l.entries.Store(key, e)
  96. l.active.Add(1)
  97. return true, nil
  98. }
  99. defer e.mu.Unlock()
  100. if current, held := e.owners[owner]; held {
  101. if current == LockUpdate || mode == LockShare {
  102. return true, nil
  103. }
  104. // Upgrade FOR SHARE to FOR UPDATE only when no other reader holds one.
  105. if len(e.owners) == 1 {
  106. e.owners[owner] = LockUpdate
  107. return true, nil
  108. }
  109. for other := range e.owners {
  110. return false, other
  111. }
  112. }
  113. if len(e.owners) == 0 {
  114. e.owners[owner] = mode
  115. return true, nil
  116. }
  117. if mode == LockShare {
  118. compatible := true
  119. var other *Session
  120. for holder, held := range e.owners {
  121. if held == LockUpdate {
  122. compatible = false
  123. other = holder
  124. break
  125. }
  126. }
  127. if compatible {
  128. e.owners[owner] = LockShare
  129. return true, nil
  130. }
  131. return false, other
  132. }
  133. for other := range e.owners {
  134. return false, other
  135. }
  136. return false, nil
  137. }
  138. // Acquire obtains a row lock. Skip and NoWait return immediately when the row is
  139. // contended; Block waits until it is free and reports a deadlock as
  140. // ErrDeadlockDetected.
  141. func (l *RowLockManager) Acquire(owner *Session, key string, mode LockMode, wait LockWait) error {
  142. for {
  143. l.gate.Lock()
  144. ok, other := l.tryLock(owner, key, mode)
  145. l.gate.Unlock()
  146. if ok {
  147. return nil
  148. }
  149. switch wait {
  150. case LockWaitNoWait:
  151. return ErrLockNotAvailable
  152. case LockWaitSkip:
  153. return ErrRowLocked
  154. }
  155. if err := l.waitFor(owner, key, other); err != nil {
  156. return err
  157. }
  158. }
  159. }
  160. func (l *RowLockManager) waitFor(owner *Session, key string, other *Session) error {
  161. e, ok := l.entry(key)
  162. if !ok {
  163. return nil
  164. }
  165. ch := make(chan struct{})
  166. e.mu.Lock()
  167. // The owner may have released and removed the entry after tryLock returned
  168. // but before we enqueued. Re-check under the entry lock so we never sleep on
  169. // a detached entry.
  170. current, present := l.entry(key)
  171. if !present || current != e || len(e.owners) == 0 {
  172. e.mu.Unlock()
  173. return nil
  174. }
  175. e.waiters[ch] = struct{}{}
  176. e.mu.Unlock()
  177. l.waitMu.Lock()
  178. l.waits[owner] = other
  179. deadlock := l.hasCycleLocked(owner)
  180. if deadlock {
  181. delete(l.waits, owner)
  182. } else {
  183. l.waits[owner] = other
  184. }
  185. l.waitMu.Unlock()
  186. if deadlock {
  187. e.mu.Lock()
  188. delete(e.waiters, ch)
  189. e.mu.Unlock()
  190. return ErrDeadlockDetected
  191. }
  192. defer func() {
  193. l.waitMu.Lock()
  194. if l.waits[owner] == other {
  195. delete(l.waits, owner)
  196. }
  197. l.waitMu.Unlock()
  198. }()
  199. select {
  200. case <-ch:
  201. return nil
  202. // A genuine cycle is detected by the wait-for graph immediately; this is a
  203. // last-resort guard against a lost wake-up, not a lock timeout.
  204. case <-time.After(5 * time.Minute):
  205. e.mu.Lock()
  206. delete(e.waiters, ch)
  207. e.mu.Unlock()
  208. return ErrDeadlockDetected
  209. }
  210. }
  211. func (l *RowLockManager) hasCycleLocked(start *Session) bool {
  212. seen := map[*Session]bool{}
  213. cur := start
  214. for cur != nil {
  215. if seen[cur] {
  216. return cur == start
  217. }
  218. seen[cur] = true
  219. cur = l.waits[cur]
  220. }
  221. return false
  222. }
  223. // Release drops one owner's hold on key and wakes waiters.
  224. func (l *RowLockManager) Release(owner *Session, key string) {
  225. e, ok := l.entry(key)
  226. if !ok {
  227. return
  228. }
  229. e.mu.Lock()
  230. delete(e.owners, owner)
  231. empty := len(e.owners) == 0
  232. waiters := make([]chan struct{}, 0, len(e.waiters))
  233. if empty || len(e.owners) == 0 {
  234. for ch := range e.waiters {
  235. waiters = append(waiters, ch)
  236. }
  237. e.waiters = make(map[chan struct{}]struct{})
  238. }
  239. if empty {
  240. e.closed = true
  241. l.entries.Delete(key)
  242. l.active.Add(-1)
  243. }
  244. e.mu.Unlock()
  245. for _, ch := range waiters {
  246. close(ch)
  247. }
  248. }
  249. // ReleaseAll drops every lock held by owner. It is used at transaction end,
  250. // rollback, and failed commit. It intentionally does not take gate: releasing a
  251. // lock can never invalidate an in-flight commit, and resetLocked may call it
  252. // while a commit still holds gate for reading.
  253. func (l *RowLockManager) ReleaseAll(owner *Session) {
  254. l.entries.Range(func(key, value interface{}) bool {
  255. e := value.(*rowLockEntry)
  256. e.mu.Lock()
  257. delete(e.owners, owner)
  258. empty := len(e.owners) == 0
  259. var waiters []chan struct{}
  260. if empty {
  261. e.closed = true
  262. waiters = make([]chan struct{}, 0, len(e.waiters))
  263. for ch := range e.waiters {
  264. waiters = append(waiters, ch)
  265. }
  266. e.waiters = make(map[chan struct{}]struct{})
  267. l.entries.Delete(key)
  268. l.active.Add(-1)
  269. }
  270. e.mu.Unlock()
  271. for _, ch := range waiters {
  272. close(ch)
  273. }
  274. return true
  275. })
  276. l.waitMu.Lock()
  277. delete(l.waits, owner)
  278. l.waitMu.Unlock()
  279. }
  280. // BeginWrite holds the commit gate for reading and verifies that no other
  281. // transaction holds any of keys. The returned function must be called after the
  282. // durable batch is published. Holding gate across publication is what makes a
  283. // lock acquisition and a write mutually exclusive.
  284. func (l *RowLockManager) BeginWrite(owner *Session, keys, tablePrefixes []string) (func(), error) {
  285. l.gate.RLock()
  286. if l.active.Load() == 0 {
  287. return l.gate.RUnlock, nil
  288. }
  289. for _, key := range keys {
  290. e, ok := l.entry(key)
  291. if !ok {
  292. continue
  293. }
  294. e.mu.Lock()
  295. conflict := false
  296. for holder := range e.owners {
  297. if holder != owner {
  298. conflict = true
  299. break
  300. }
  301. }
  302. e.mu.Unlock()
  303. if conflict {
  304. l.gate.RUnlock()
  305. return nil, ErrRowLocked
  306. }
  307. }
  308. if len(tablePrefixes) > 0 {
  309. conflict := false
  310. l.entries.Range(func(key, value interface{}) bool {
  311. k := key.(string)
  312. matched := false
  313. for _, prefix := range tablePrefixes {
  314. if strings.HasPrefix(k, prefix) {
  315. matched = true
  316. break
  317. }
  318. }
  319. if !matched {
  320. return true
  321. }
  322. e := value.(*rowLockEntry)
  323. e.mu.Lock()
  324. for holder := range e.owners {
  325. if holder != owner {
  326. conflict = true
  327. break
  328. }
  329. }
  330. e.mu.Unlock()
  331. return !conflict
  332. })
  333. if conflict {
  334. l.gate.RUnlock()
  335. return nil, ErrRowLocked
  336. }
  337. }
  338. return l.gate.RUnlock, nil
  339. }
  340. // BeginTableWrite is the coarse check used by autocommit bulk/DDL operations
  341. // whose exact row keys are not known before the scan. It rejects the write if
  342. // any other transaction holds a row lock in the table.
  343. func (l *RowLockManager) BeginTableWrite(owner *Session, prefix string) (func(), error) {
  344. return l.BeginWrite(owner, nil, []string{prefix})
  345. }