none
live lock and sql server - does it exist?

    Question

  • I had a peculiar question today "what is live lock in SQL Server" that got me digging to see where did term "live lock" in connection to SQL Server came from to begin with. The term is not used in BOL. And the definitions I've seeing are peculiar, they trace down to some blogs so.

    "A Live lock is one, where a request for exclusive lock is denied continuously because a series of overlapping shared locks keeps on interfering each other and to adapt from each other they keep on changing the status which further prevents them to complete the task. In SQL Server Live Lock occurs when read transactions are applied on table which prevents write transaction to wait indefinitely. This is different then deadlock as in deadlock both the processes wait on each other."

    and the example about 2 humans in a corridor moving to let another go keep crawling from one interview question-answer list to another, descriptions when process that issued exclusive locks will wait processes that read indefinitely is there as well.

    That's where I have a problem - database lock schedulers do not work like humans ... well unless there is a locking hierarchy bug in there... but it's a bug and should be treated accordingly.

    The explanations like one I've quoted above pretty much suggest that MS SQL Server lock scheduler is faulty and does not handle convoys (if that would be true, transaction log locks - which is a constant of convoys - would be a disaster, but as we have seeng in practice it is not true for MS SQL Server implementation) returning those high trafick lock requests to the scheduler in proper timely fashion.

    Does this actually exist in SQL Server to begin with? I was looking for any kind of an example that would have a proof that live lock exists in SQL Server and found only claims that it does, but all the follow up requests aka "code/example please" remained unanswered in those blogs.

    Why would one talk about it as a part of interview questions (several interview questions sites mention it, actually that's where most of the google search hits were...)  if it does not exist in SQL Server or is mentioned in it's documentation. That one I find peculiar, I wounder where does this stuff come from and did anyone see live lock in SQL Server to begin with? I did not see one in more than 15 years, what was I missing? did locking hierarchy break in any SQL Server version and I missed that one? Intent locks would catch that kind of case and SQL Server severs 4 such lock requests denies if the convoy type of a behavior is there and does not grant any more shared locks to that convoy. Where is "exclusive lock is waiting indefinitely" here, I'm missing the indefinitely part, I'm seeing "working slow" and "wasting some resources" part. Locks will be released when transactions-readers commit/rollback. But that's normal well known lock wait.

     

     

    Wednesday, January 26, 2011 9:50 PM

Answers

  • Let me give some background and then a few comments:

    A long time ago, with some new version of SQL Server, I recall reading something along the lines of "livelocks no longer occurs", being an improvement in this new version. Now, this was a long long time ago, possibly somewhere about version 6.0 (1995 timeframe).

    So, for a long time now, SQL Server avoids livelocks using queuing. This is even visible nowadays using one with X loxc and two waiting with S locks (a classic demo). Activity Monitor etc will show one of the S loc requestor waiting for the X lock (as expected), but the other S lock requestor will wait for the first S lock requestor. So, not only is this queuing implemented in the engine, it is nowadays visible to us as well (when this externally visibility was introduced I don't recall). So, we've had queuing for a long time now to avoid dlivelocks, and a bit more recently it is also pretty visible to us. Here's a repro to show a "classic" livelock (avoidance). Execute below from different query windows (in pubs database):

    --1
    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
    BEGIN TRAN
    SELECT * FROM authors
    
    --2
    UPDATE authors 
    SET au_lname = 'X'
    WHERE au_id = '238-95-7766'
    
    --3
    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
    BEGIN TRAN
    SELECT * FROM authors
    
    --4
    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
    BEGIN TRAN
    SELECT * FROM authors
    
    --5
    EXEC sp_who2
    
    You will see that 2 is blocked by 1, 3 is blocked by 2 and 4 is blocked by 3. Theoretically, 3 and 4 could execute (there's only a shared lock), but queuing makes 3 and 4 to wait. This is how livelocks are avoided: queuing.
    Tibor Karaszi, SQL Server MVP | web | blog
    Thursday, January 27, 2011 8:24 AM
    Moderator

All replies

  • to the best of my knowledge, locks queue in order in SQL Server so that scenario should never occur.  at least not regarding "locks".  it is possible that some other resource exists in SQL Server which does not queue, but as (again, to the best of my knowledge) all tasks in SQL Server run at the same priority and are scheduled round-robin, even there it would seem difficult if not impossible to have someone jump the queue to create the livelock situation.

    I'll Google this a bit and see if anything more pops up that seems worth a comment.

    I would presume that if you see it on interview question lists, that it probably leaked in from some other system where livelocks do occur, onto someone's interview question list, and from there it simply got cloned all over the internet the way stuff does.

    --

    huh, yes you certainly can Google to a bunch of places it's mentioned, but I still don't really know that it ever happens.

    Josh

     

    Wednesday, January 26, 2011 11:14 PM
  • Hi,

    The best explination I have seen is from Tibor Karaszi and reads "A has shared lock on resource X
    B requests exclusive lock. Is blocked.
    C requests shared lock, is granted.
    A releases lock, but C has its shared lock. B is still blocked.
    D requests shared lock, is granted.
    E requests shared lock, is granted.
    C releases lock, but D and E has its shared lock. B is still blocked.
    And so on."

    However...I have just spent quite some time trying to replicate this scenario, and I can not. I have tried numerous permiatations, with loops, with explicit v autocommit transactions, etc, and monitoring the locks with sys.dm_tran_locks, etc, and I can not make a shared lock "skip the queue".

    I suspect (and I'm open to be proven wrong) that this was a situation applied to an early version of SQL, and is no longer an issue.

    Another possibility is that it applies (as Josh says) to resource contention of some nature, but even though I can well believe that it exists without being documented in books on-line, I find it hard to believe that it exists, but there are no forum threads, etc of people pulling their hair out trying to debug it, blog posts from Paul Randal, et all, etc.

    The third possibility is that it is pure fiction. From the research I have done on this tonight, it is a genuine concept, but seems to refer to thread-based programming, where you have multiple threads either fighting for resource, or performing actions that repeatedly cancel out the other.


    Peter Carter-Greenan http://sqlserverdownanddirty.blogspot.com/
    Thursday, January 27, 2011 12:16 AM
  • Do you have a link to Tibor's discussion?

    He generally knows his stuff!

    It's a simple enough scenario.  Of course, one avoids it by queuing requests regardless of type, though that will impact overall throughput - but then so would having livelock occur!

    I don't recall ever having this happen to me, and I'd think by now I would have.  Bunch of SPs that scan a table and one that updates it, would seem a common scenario when a livelock would occur - if it was going to!

    OTOH, I almost never am around anything that deadlocks, and I know that happens to people out in the world - and I can certainly make one happen in a few lines, if I want to see one.  Now if I were a bit more ambitious I'd try to replicate the livelock ... mebbe later. :)

    Josh

    ps - it occurs to me I can *make* one occur if I timeout instead of wait when applying for a locked resource.  I suppose that could be the point of the question.

     

    Thursday, January 27, 2011 12:55 AM
  • Let me give some background and then a few comments:

    A long time ago, with some new version of SQL Server, I recall reading something along the lines of "livelocks no longer occurs", being an improvement in this new version. Now, this was a long long time ago, possibly somewhere about version 6.0 (1995 timeframe).

    So, for a long time now, SQL Server avoids livelocks using queuing. This is even visible nowadays using one with X loxc and two waiting with S locks (a classic demo). Activity Monitor etc will show one of the S loc requestor waiting for the X lock (as expected), but the other S lock requestor will wait for the first S lock requestor. So, not only is this queuing implemented in the engine, it is nowadays visible to us as well (when this externally visibility was introduced I don't recall). So, we've had queuing for a long time now to avoid dlivelocks, and a bit more recently it is also pretty visible to us. Here's a repro to show a "classic" livelock (avoidance). Execute below from different query windows (in pubs database):

    --1
    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
    BEGIN TRAN
    SELECT * FROM authors
    
    --2
    UPDATE authors 
    SET au_lname = 'X'
    WHERE au_id = '238-95-7766'
    
    --3
    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
    BEGIN TRAN
    SELECT * FROM authors
    
    --4
    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
    BEGIN TRAN
    SELECT * FROM authors
    
    --5
    EXEC sp_who2
    
    You will see that 2 is blocked by 1, 3 is blocked by 2 and 4 is blocked by 3. Theoretically, 3 and 4 could execute (there's only a shared lock), but queuing makes 3 and 4 to wait. This is how livelocks are avoided: queuing.
    Tibor Karaszi, SQL Server MVP | web | blog
    Thursday, January 27, 2011 8:24 AM
    Moderator
  • <<The best explination I have seen is from Tibor Karaszi and reads>>

    Being mentioned, perhaps I should comment on this as well... :-)

    I found my old post here http://www.sqlmonster.com/Uwe/Forum.aspx/sql-server-programming/39948/Can-truncate-but-not-delete (although it was probably posted in the newsgroups). If you read on a bit in that post, I said "To the best of my knowledge, SQL Server handles this by queuing the lock requests.". Possibly a bit vague (my meaning was that livelocks doesn't happen in SQL Server), but hopefully I didn't send to many readers on a wild goose chase ... :-)

     


    Tibor Karaszi, SQL Server MVP | web | blog
    Thursday, January 27, 2011 9:01 AM
    Moderator
  • Let me give some background and then a few comments:

    A long time ago, with some new version of SQL Server, I recall reading something along the lines of "livelocks no longer occurs", being an improvement in this new version. Now, this was a long long time ago, possibly somewhere about version 6.0 (1995 timeframe).

    So, for a long time now, SQL Server avoids livelocks using queuing. This is even visible nowadays using one with X loxc and two waiting with S locks (a classic demo). Activity Monitor etc will show one of the S loc requestor waiting for the X lock (as expected), but the other S lock requestor will wait for the first S lock requestor. So, not only is this queuing implemented in the engine, it is nowadays visible to us as well (when this externally visibility was introduced I don't recall). So, we've had queuing for a long time now to avoid dlivelocks, and a bit more recently it is also pretty visible to us. Here's a repro to show a "classic" livelock (avoidance). Execute below from different query windows (in pubs database):

    --1
    
    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
    
    BEGIN TRAN
    
    SELECT * FROM authors
    
    
    
    --2
    
    UPDATE authors 
    
    SET au_lname = 'X'
    
    WHERE au_id = '238-95-7766'
    
    
    
    --3
    
    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
    
    BEGIN TRAN
    
    SELECT * FROM authors
    
    
    
    --4
    
    SET TRANSACTION ISOLATION LEVEL SERIALIZABLE
    
    BEGIN TRAN
    
    SELECT * FROM authors
    
    
    
    --5
    
    EXEC sp_who2
    
    
    You will see that 2 is blocked by 1, 3 is blocked by 2 and 4 is blocked by 3. Theoretically, 3 and 4 could execute (there's only a shared lock), but queuing makes 3 and 4 to wait. This is how livelocks are avoided: queuing.
    Tibor Karaszi, SQL Server MVP | web | blog


    Tibor -

    Good answer thanks. This was driving me mad last night trying to figer it out! I was sure they didn't exist, but it's hard to prove a negative! :)


    Peter Carter-Greenan http://sqlserverdownanddirty.blogspot.com/
    Thursday, January 27, 2011 11:23 AM
  • Peter,

    <<I was sure they didn't exist, but it's hard to prove a negative! :)>>

    Indeed. I want to emphasize that my script only show that SQL Server has logic to avoid livelocks. It doesn't prove that livelocks will never occur. Important distinction... :-)


    Tibor Karaszi, SQL Server MVP | web | blog
    Thursday, January 27, 2011 11:40 AM
    Moderator
  • Tibor,

    Thanks for the clarification - and history lesson!

    ... but what are the odds that that's what an interviewer wants to hear, "Oh yes, livelocks, they pretty much haven't been a problem for fifteen years!"

    As I said above, we can MAKE one happen if we work at it a little, but I think we could then "fix" the problem we forced by using serializable isolation to strengthen the queuing behavior of SQL Server.  I think.

    Actually, I *do* tell people how to use lock_timeout, so in some of my projects I just might accidentally cause a livelock (though I don't see it as much of a problem even so in real life), so this has actually been somewhat informative for me.

    Thanks OP and all.

    Josh

     

    Thursday, January 27, 2011 3:51 PM
  • Hi All,

    I just stumbled upon this post http://blogs.msdn.com/b/psssql/archive/2009/06/02/sql-server-lock-manager-and-relaxed-fifo.aspx which seems to argue that lock queing is no longer strict in SQL Server, which (I think) means that livelocks could be possible. Do you agree?

    Pete


    Peter Carter-Greenan http://sqlserverdownanddirty.blogspot.com/
    Thursday, January 27, 2011 10:48 PM
  • http://blogs.msdn.com/b/psssql/archive/2009/06/02/sql-server-lock-manager-and-relaxed-fifo.aspx which seems to argue that lock queing is no longer strict in SQL Server, which (I think) means that livelocks could be possible. Do you agree?

    Well, I hope not!

    And it doesn't sound to me like they overlooked this:

    preserves desirable properties such as avoiding starvation

    I think that means they are aware of the problem and did not accidentally allow it back in.

    Josh

     

    Thursday, January 27, 2011 11:02 PM
  • What is described is normal lock wait behavior, the queue, do not want to wait - well... commit the transactions and do not run ROLAP type of sql in OLTP environment and expect no concurrency control related fights for the resources (dirty read/nolock overwrite excluded), databases with locking mechanism do not work this way, version based transaction processing will behave differently, but it has different set of phenomenons to deal with...

    It is normal lock wait, well known, process waits and that's it, that what locks supposed to cause after all to prevent transaction rollback (wait is cheaper resources wise).

    can anyone validate one of these claims.

    http://www.techinterviews.com/sql-server-dba-interview-questions

    "

    What is a deadlock and what is a live lock? How will you go about resolving deadlocks?

    • ...A livelock is one, where a request for an exclusive lock is repeatedly denied because a series of overlapping shared locks keeps interfering. SQL Server detects the situation after four denials and refuses further shared locks. A livelock also occurs when read transactions monopolize a table or page, forcing a write transaction to wait indefinitely. Check out SET DEADLOCK_PRIORITY and "Minimizing Deadlocks" in SQL Server books online. Also check out the article Q169960 from Microsoft knowledge base.

    "

    that part: SQL Server detects the situation after four denials and refuses further shared locks.

    That does not exactly match with the locks queue... The guy from India I was talking to was dead sure livelock exists in SQL and was quite surprised that I have never heard of one in SQL Server. Did not see one in 15 years and all I know about SQL Server implementation of transaction processing does contradict to the fact that this behavior may exist in SQL Server implementation. I wounder if there is any popular blogger who preaches that stuff and that's how it did spread to several places. It looks like the same statements were copied.

    SQL Server has lock queue, it has locking hierarchy and it does not have transactions priorities that would give a process some processing advantage above another transaction. The theoretical possibility of live lock in this scenario is highly unlikely unless there is a bug.


    Thursday, January 27, 2011 11:22 PM
  • I do not think with lock_timeout it is possible either, it will affect your last statement, will return the error, now whatever your application is may act accordingly, it did get the database response in for of an error, try-catch goes into the picture. Nothing has happen except of normal database behavior. For what you know your network connection being dead could have caused just the same - sql timed out, handle the error and move on.

    No different that deadlock or any other sql error handling if you ask me. SQL returned the answer (good or bad) - handle it.

    I do not see an issue in this scenario.

    Thursday, January 27, 2011 11:30 PM
  • Also check out the article Q169960 from Microsoft knowledge base.

    There is such an article titled "INF: Analyzing and Avoiding Deadlocks in SQL Server" regarding SQL 6.5, but it does not contain the word "live", a quick look does not seem to show it discussing the issue at all - and I am not so nostalgic for version 6.5 that I want to read the article in detail to see if it comes anywhere close to describing this issue using other terms!

    Josh

    Friday, January 28, 2011 12:07 AM
  • Josh,

    <<... but what are the odds that that's what an interviewer wants to hear, "Oh yes, livelocks, they pretty much haven't been a problem for fifteen years!">>

    LOL! I very much doubt that an interviewer asking about livelocks know much about livelock and livelock handling in SQL Server in the first place... :-)

    <<As I said above, we can MAKE one happen if we work at it a little, but I think we could then "fix" the problem we forced by using serializable isolation to strengthen the queuing behavior of SQL Server.  I think.>>

    Seems reasonable. The fact that SQL Server has logic to protect against livelocks doesn't mean we will never encounter such.


    Tibor Karaszi, SQL Server MVP | web | blog
    Friday, January 28, 2011 8:25 AM
    Moderator
  • I just stumbled upon this post http://blogs.msdn.com/b/psssql/archive/2009/06/02/sql-server-lock-manager-and-relaxed-fifo.aspx which seems to argue that lock queing is no longer strict in SQL Server, which (I think) means that livelocks could be possible. Do you agree?

    Pete,

    No, I do not agree. They way I read the text is that the relaxation introduced in 2005 is only where the FIFO can be relaxed safely (where livelocks will not enounter anyhow). I.e., 2005 is smarter and can allow more overlapping locks, without further risk for livelocks. Here, I think, is the key technical aspect:

    "This relaxation affected requests that are compatible with all held modes and all pending modes. In these cases, the new lock could be granted immediately by passing any pending requests. Because it is compatible with all pending requests, the newly requested mode would not result in starvation."

    :-)


    Tibor Karaszi, SQL Server MVP | web | blog
    Friday, January 28, 2011 8:31 AM
    Moderator
  • <<can anyone validate one of these claims.

    http://www.techinterviews.com/sql-server-dba-interview-questions

    <snip>

    •...A livelock is one, where a request for an exclusive lock is repeatedly denied because a series of overlapping shared locks keeps interfering. SQL Server detects the situation after four denials and refuses further shared locks."

    Above is already proven incorrect, by the script I posted above. It doesn't take 4 overlapping shared locks until the shared locks will have to wait. Even the first shared lock (--3 in my example abloe) after there is a waiting X lock, will be blocked.

    <<SQL Server has lock queue, it has locking hierarchy and it does not have transactions priorities that would give a process some processing advantage above another transaction. The theoretical possibility of live lock in this scenario is highly unlikely unless there is a bug.>>

    I concur (with reservation for Resource Governor, which I can imagine can possibly complicate things...?). And I do think there are plenty of urban legends floating around regarding livelocks/lock starvation. Urban legands tend to be spun around things that we can't see... :-)

     

     


    Tibor Karaszi, SQL Server MVP | web | blog
    Friday, January 28, 2011 10:07 AM
    Moderator
  • I looked over internet a little, and I think one of very possible sources if this urban legend is this blog

    http://blog.sqlauthority.com/2008/03/21/sql-server-introduction-to-live-lock-what-is-live-lock/

    I speculate on the fact that the guy I was talking to was from India. The blog seem to be a popular Indian blog, but it's very hard to judge how popular and what is in it pure "sql evangelist" marketing strategy. Where do "suggested" interview answers come about -hard to tell, I think the one I looked up was straight forward copied. Why? Good question, no idea.

    Resource governor can not complicate things because it does not alter the locking hierarchy, it lives above that part of the engine, I mean can not alter to that extent ...to the extent of breaking the core transaction processing logic. That would be treated as a bug, and should. I'm not saying the bugs do not exist, but no one would introduce one on the architecture of transaction processing engine, not for the system that started playing in enterprise solutions arena, and not in the company that has acquired Jim Gray's brain. That one if existed would show up a long time ago in OLTP's and OLAP's. My bet would be that in most of the cases "live lock" look alike is the forgotten transaction commit/rollback. And it has never being "live lock" like it is described in Gray-Reuter book for example. You see, ms sql server even if it claims transactional hierarchy exists with begin tran {begin tran ... commit/rollback} commit/rollback everything belong to the top level transaction, ms sql does not do partial rollback-restart transaction.

    The sql authority's human example does not apply to ms sql because in the human scenario both of the humans do make a move, in case of sql server transaction processing only one can move, the other one will hang on waiting, ms sql server does not have true asynchronous sql server calls to the engine from the client, an application would have to do multiple threads and do async calls, but that locking behavior would be already on the level of the application itself, not on the level of the engine of the database.

    my 2C.

    Monday, January 31, 2011 4:29 PM
  • I concur (with reservation for Resource Governor, which I can imagine can possibly complicate things...?).

    Hmm.  I get the impression that the SQL Server group understands the issue and is unlikely to accidentally reintroduce the problem.

    http://blogs.msdn.com/b/psssql/archive/2008/01/10/sql-server-2008-resource-governor-questions.aspx

    The importance setting should not be looked at as a thread or process priority setting.  For example a pool using 0:10 CPU with a group of high importance may not get resources ahead of a pool using 0:100 CPU and a normal importance.   The resource governor is designed to avoid live and deadlock scenarios while attempting to maintain a high level of concurrency.   There are times when other decisions will outweigh the importance decision.

    -

    It looks to me like the resource governor is almost invisible by the time you get down to the lock management level - after all, locks have to work *across* all workgroups!

    Josh

     

    Monday, January 31, 2011 6:50 PM