Latch is a popular term in the database world. It's used to avoid confusing with the term Lock in a database. Lock in RDBMS usually associates with transaction, data in the tables, data consistence, etc. It has long term semantic and deadlock can be a problem due to user actions. Latch is same as a lock in the traditional CS sense. It's a mutax or semaphore in memory to protect shared data structure in memory, e.g. a paged in index page in memory. The locked duration usually is very short, and deadlock is not a problem due to user actions.
When walking a B+ tree index, the usual code often uses latches to have exclusive access to the index pages being walked from root on the way down so that the pages won't be split due to overflow caused by other threads since the walking thread itself can cause a split and needs to updates the walked pages. Smarter implementation would shorten the list of locked pages when it finds a page with enough room that won't split even if its child pages split. This shortens the scope of the locking of the walk but there are still pages being locked.
This can be a single point of contention when a lot of index walking happen. Pretty much most db operations touch the index. This is especially problematic in modern memory rich systems where most hot data are paged into memory so the locking of the index during walking stuck out like a sore thumb.
A latch-free B+ tree would allow multiple threads to walk the index at the same time, thus removing the single point of contention and allowing massive scaling with more threads added.
Thanks for clarifying! It makes sense to use a different word in the DB community if Lock has some other previous meaning. It's easy to forget that RDBMS terminology has been along longer than most areas of CS.
The terminology clash in this case is unfortunate, because I'd wager that 90% of the people active in the field of concurrent data structures will use 'lock' rather than 'latch'.
Comments
Latch is a popular term in the database world. It's used to avoid confusing with the term Lock in a database. Lock in RDBMS usually associates with transaction, data in the tables, data consistence, etc. It has long term semantic and deadlock can be a problem due to user actions. Latch is same as a lock in the traditional CS sense. It's a mutax or semaphore in memory to protect shared data structure in memory, e.g. a paged in index page in memory. The locked duration usually is very short, and deadlock is not a problem due to user actions.
When walking a B+ tree index, the usual code often uses latches to have exclusive access to the index pages being walked from root on the way down so that the pages won't be split due to overflow caused by other threads since the walking thread itself can cause a split and needs to updates the walked pages. Smarter implementation would shorten the list of locked pages when it finds a page with enough room that won't split even if its child pages split. This shortens the scope of the locking of the walk but there are still pages being locked.
This can be a single point of contention when a lot of index walking happen. Pretty much most db operations touch the index. This is especially problematic in modern memory rich systems where most hot data are paged into memory so the locking of the index during walking stuck out like a sore thumb.
A latch-free B+ tree would allow multiple threads to walk the index at the same time, thus removing the single point of contention and allowing massive scaling with more threads added.
Thanks for clarifying! It makes sense to use a different word in the DB community if Lock has some other previous meaning. It's easy to forget that RDBMS terminology has been along longer than most areas of CS.
The terminology clash in this case is unfortunate, because I'd wager that 90% of the people active in the field of concurrent data structures will use 'lock' rather than 'latch'.