Many Cups of Coffee

Multi-tier application + database deadlock or why databases aren't queues (part1)

2012-01-12T01:41:00.000-06:00

Databases aren't queues.

And despite the ubiquitous presence of queuing technology out there (ActiveMQ, MSMQ, MSSQL Service Broker, Oracle Advanced Queuing) there are plenty of times when we ask our relational brethren to pretend to be queues. This is the story of one such folly, and along the way, we'll delve into some interesting sub-plots of deadlocks, lock escalation, execution plans, and covering indexes, oh my! Hopefully we'll laugh, we'll cry, and get the bad guy in the end (turned out I was the bad guy).

This is part one of a multi-part series describing the whole saga. In this part, I lay out the problem, the initial symptom, and the tools and commands I used to figure out what was going wrong.

And so it starts...

I'm going to set the stage for our discussion, to introduce you to the problem, and establish the characters involved in our tragedy. Let's say that this system organizes music CDs into labeled buckets. A CD can only be in one bucket at a time, and the bucket tracks at an aggregate level how many CDs are contained within it (e.g. bucket "size"). You can visualize having a stack of CDs and two buckets: "good CDs" and "bad CDs". Every once in a while you decide that you don't like your bucket choices, and you want to redistribute the CDs into new buckets--perhaps by decade: "1980s music", "1990s music", "all other (inferior) music". Later you might change your mind again and come up with a new way to organize your CDs, etc. We will call each "set" of buckets a "generation". So at generation zero you had 2 buckets "good CDs" and "bad CDs", at generation one you had "1980s CDs", etc, and so on and so on. The generation always increases over time as you redistribute your CDs from a previous generation's buckets to the next generation's buckets.

Lastly, while I might have my music collection organized in some bucket scheme, perhaps my friend Jerry has his own collection and his own bucket scheme. So entire sets of buckets over generations can be grouped into music collections. Collections are completely independent: Jerry and I don't share CDs nor do we share buckets. We just happen to be able to use the same system to manage our music collections.

So we have:

CDs -- the things which are contained within buckets, that we redistribute for every new generation
Buckets -- the organizational units, grouped by generation, which contain CDs. Each bucket has a sticky note on it with the number of CDs currently in the bucket.
Generation -- the set of buckets at a particular point in time.
Collection -- independent set of CDs and buckets

Even while we're redistributing the CDs from one generation's buckets to the next, a CD is only in one bucket at a time. Visualize physically moving the CD from "good CDs" (generation 0) to "1980s music" (generation 1).

NOTE: Our actual system has nothing to do with CDs and buckets-- I just found it easier to map the system into this easy to visualize metaphor.

In this system we have millions of CDs, thousands of buckets, and lots of CPUs moving CDs from bins in one generation to the next (parallel, but not distributed). The size of each bucket must be consistent at any point in time.

So assume the database model looks something like:

Buckets Table

bucketId (e.g. 1,2,3,4) - PRIMARY KEY CLUSTERED
name (e.g. 80s music, 90s music)
generation (e.g. 0, 1, 2)
size (e.g. 4323, 122)
collectionId (e.g. "Steves Music Collection") - NON-CLUSTERED INDEX

Cds Table

cdId (e.g. 1,2,3,4) - PRIMARY KEY CLUSTERED
name (e.g. "Modest Mouse - Moon and Antarctica", "Interpol - Antics")
bucketId (e.g. 1,2, etc. foreign key to the Bucket table) - NON-CLUSTERED INDEX

Note that both tables are clustered by their primary keys-- this means that the actual record data itself is stored in the leaf nodes of the primary index. I.e. the table itself is an index. In addition, Buckets can be looked up by "music collection" without scanning (see the secondary, non-clustered index on collectionId), and Cds can be looked up by bucketId without scanning (see the secondary, non-clustered index on Cds.bucketId).

The algorithm

So I wrote the redistribution process with a few design goals: (1) it needed to work online. I could concurrently add new CDs into the current generations bins while redistributing. (2) I could always locate a CD-- i.e. I could never falsely report that some CD was missing just because I happen to search during a redistribution phase. (3) if we interrupt the redistribution process, we can resume it later. (4) it needed to be parallel. I wanted to accomplish (1) and (2) with bounded blocking time so whatever blocking work I needed to do, I wanted it to be as short as possible to increase concurrency.

I used a simple concurrency abstraction that hosted a pool of workers who shared a supplier of work. The supplier of work would keep giving "chunks" of items to move from one bucket to another. We only redistribute a single music collection at a time. The supplier was shared by all of the workers, but it was synchronized for safe multi-threaded access.

The algorithm for each worker is like:

(I)   Get next chunk of work
(II)  For each CD decide the new generation bucket in which it belongs
        (accumulating the size deltas for old buckets and new buckets)
(III) Begin database transaction
(IV)   Flush accumulated size deltas for buckets
(V)    Flush foreign key updates for CDs to put them in new buckets
(VI)  Commit database transaction

Each worker would be given a chunk of CDs for the current music collection that was being redistributed (I). The worker would do some work to decide which bucket in the new generation should get the CD (II). The worker would accumulate the deltas for counts: decrementing from the original bucket and incrementing the count for the new bucket. Then the worker would flush (IV) these deltas in a correlated update like UPDATE Buckets SET size = size + 123 WHERE bucketId = 1. After the size updates were flushed, it would then flush (V) all of the individual updates to the foreign key fields to refer to the new generations buckets like UPDATE Cds SET bucketId = 123 WHERE bucketId = 101. These two operations happen in the same database transaction.

The supplier that gives work to the workers is a typical "queue" like SELECT query -- we want to iterate over all of the items in the music collection in the old generation. This happens in a separate connection, separate database transaction from the workers (discussed later). The next chunk will be read using the worker thread (with thread safe synchronization). This separate "reader" connection doesn't have its own thread or anything.

First sign of trouble - complete stand still

So we were doing some large volume testing on not-so-fast hardware, when suddenly...the system just came to a halt. We seemed to be in the middle of moving CDs to new buckets, and they just stopped making progress.

Finding out what the Java application was doing

So first step was to see what the Java application was doing:

c:\>jps
1234 BucketRedistributionMain
3456 jps
c:\>jstack 1234 > threaddump.out

Jps finds the java process id, and then run jstack to output a stacktrace for each of the threads in the java program. Jps and Jstack are included in the JDK.

The resulting stack trace showed that all workers were waiting in socketRead to complete the database update to flush the bucket size updates (step IV above).

Here is the partial stack trace for one of the workers (some uninteresting frames omitted for brevity):

"container-lowpool-3" daemon prio=2 tid=0x0000000007b0e000 nid=0x4fb0 runnable [0x000000000950e000]
   java.lang.Thread.State: RUNNABLE
 at java.net.SocketInputStream.socketRead0(Native Method)
 at java.net.SocketInputStream.read(Unknown Source)
 ...
 at net.sourceforge.jtds.jdbc.SharedSocket.readPacket(Unknown)
 at net.sourceforge.jtds.jdbc.SharedSocket.getNetPacket(Unknown)
 ...
 at org.hibernate.jdbc.BatchingBatcher.doExecuteBatch(Unknown)
 ...
 at org.hibernate.impl.SessionImpl.flush(SessionImpl.java:1216)
 ...
 at com.mycompany.BucketRedistributor$Worker.updateBucketSizeDeltas()
 ...
 at java.util.concurrent.FutureTask$Sync.innerRun(Unknown Source)
 ...
 at java.lang.Thread.run(Unknown Source)

As you can see our worker was updating the bucket sizes which resulted in a Hibernate "flush" (actually pushes the database query across the wire to the database engine), and then we await the response packet from MSSQL once the statement is complete. Note that we are using the jtds MSSQL driver (as evidenced by the net.sourceforge.jtds in the stack trace.

So the next question is why is the database just hanging out doing nothing?

Finding out what the database was doing...

MSSQL provides a lot of simple ways to get insight into what the database is doing. First let's see the state of all of the connections. Open SQL Server Management Studio (SSMS), click New Query, and type exec sp_who2

This will return output that looks like:

You can see all of the spids for sessions to the database. There should be five that we're are interested in: one for the "work queue" query and four for the workers to perform updates. The sp_who2 output includes a blkBy column which shows the spid that is blocking the given spid in the case that the given spid is SUSPENDED.

We can see that spid 56 is the "work queue" SELECT query (highlighted red). Notice that no one is blocking it... then we see spids 53, 54, 60, and 61 (highlighted in yellow) that are all waiting on 56 (or each other). Disregard 58 - its application source is the management studio as you can see.

So how curious! the reader query is blocking all of the update workers and preventing them from pushing their size updates. The reader "work queue" query looks like:

SELECT c.cdId, c.bucketId FROM Buckets b INNER JOIN Cds c ON b.bucketId = c.bucketId WHERE b.collection = 'Steves Collection' and b.generation = 23

Investing blocking and locking problems...

I see that spid 56 is blocking everyone else. So what locks is 56 holding? In a new query window, I ran exec sp_lock 56 and exec sp_lock 53 to see which locks each was holding and who was waiting on what.

You can see that 56 was holding a S (shared) lock on a key resource (key = row lock on an index) of object 1349579846, which corresponds to the Buckets table.

I wanted to the engine's execution plan for the reader "work queue" query. To get this, I executed a query that I created a while ago to dump as many details about current sessions in the system as possible-- think of it as a "super who2":

select es.session_id, es.host_name, es.status as session_status, sr.blocking_session_id as req_blocked_by,
datediff(ss, es.last_request_start_time, getdate()) as last_req_submit_secs,
st.transaction_id as current_xaction_id, 
datediff(ss, dt.transaction_begin_time, getdate()) as xaction_start_secs,
case dt.transaction_type 
 when 1 then 'read_write' 
 when 2 then 'read_only'
 when 3 then 'system'
 when 4 then 'distributed'
 else 'unknown'
end as trx_type,
sr.status as current_req_status, 
sr.wait_type as current_req_wait, 
sr.wait_time as current_req_wait_time, sr.last_wait_type as current_req_last_wait, 
sr.wait_resource as current_req_wait_rsc, 
es.cpu_time as session_cpu, es.reads as session_reads, es.writes as session_writes, 
es.logical_reads as session_logical_reads, es.memory_usage as session_mem_usage,
es.last_request_start_time, es.last_request_end_time, es.transaction_isolation_level,
sc.text as last_cnx_sql, sr.text as current_sql, sr.query_plan as current_plan
from sys.dm_exec_sessions es
left outer join sys.dm_tran_session_transactions st on es.session_id = st.session_id
left outer join sys.dm_tran_active_transactions dt on st.transaction_id = dt.transaction_id
left outer join 
 (select srr.session_id, srr.start_time, srr.status, srr.blocking_session_id, 
 srr.wait_type, srr.wait_time, srr.last_wait_type, srr.wait_resource, stt.text, qp.query_plan
 from sys.dm_exec_requests srr
 cross apply sys.dm_exec_sql_text(srr.sql_handle) as stt
 cross apply sys.dm_exec_query_plan(srr.plan_handle) as qp) as sr on es.session_id = sr.session_id

left outer join 
 (select scc.session_id, sct.text
 from sys.dm_exec_connections scc
 cross apply sys.dm_exec_sql_text(scc.most_recent_sql_handle) as sct) as sc on sc.session_id = es.session_id

where 
es.session_id >= 50

In the above output, the last column is the SQL XML Execution plan. Viewing that for spid 56, I confirmed my suspicion: The plan to serve the "work queue" query was to seek the "music collection" index on the buckets table for 'Steves collection', then seek to the clustered index to confirm 'generation = 23', then seek into the bucketId index on the Cds table. So to serve the WHERE clause in the "work queue" query, the engine had to use both the non-clustered index on Buckets and the clustered index (for the version predicate).

When joining and reading rows at READ COMMITTED isolation level, the engine will acquire locks as it traverses from index to index in order to ensure consistent reads. Thus, to read the value of the generation in the Buckets table, it must acquire a shared lock. And it has!

The problem comes in when the competing sessions that are trying to update the size on that same record of the Bucket table. It needs an X (exclusive) lock on that row (highlighted in red), and eek! it can't get it, because that reader query has a conflicting S lock already granted (highlighted in green).

Ok so that all makes sense, but why is the S lock being held? At READ COMMITTED you usually only hold the locks while the record is being read (there are exceptions and we'll get to that in Part 2). They are released as soon as the value is read. So if you read 10 rows in a single statement execution, the engine will: acquire lock on row 1, read row 1, release lock on row 1, acquire lock on row 2, read row 2, release lock on row 2, acquire lock on row 3, etc. So none of the four workers are currently reading-- they are writing -- or at least they're trying to if that pesky reader connection wasn't blocking them.

To find this, I was curious why the reader query was in a SUSPENDED state (see original sp_who2 output above). In the above "super who2" output, the current_req_wait value for the "work queue" read query is ASYNC_Network_IO.

ASYNC_Network_IO wait and how databases return results

ASYNC_Network_IO is an interesting wait. Let's discuss how remote applications execute and consume SELECT queries from databases.

That diagram is over-simplified, but within the database there are two chunks of memory to discuss: the buffer cache and the connection network buffer. The buffer cache is a shared chunk of memory, where the actual pages of the tables and indexes are kept to serve queries. So parts of the Buckets and Cds tables will be in memory while this "work queue" query executes. The execution engine executes the plan, it works out of the buffer cache, acquiring locks, and producing output records to send to the client. As it prepares these output records, it puts them in a connection-specific network buffer. When the application reads records from the result set, its actually being served from the network buffer in the database. The application driver typically has its own buffer as well.

When you just execute a simple SQL SELECT query and don't explicitly declare a database cursor, MSSQL gives you what it calls the "default result set" -- which is still a cursor of sorts -- you can think of it as a cursor over a bunch of records that you can only iterate over once in the forward direction. As your application threads iterate over the result set, the driver requests more chunks of rows from the database on your behalf, which in turn depletes the network buffer.

However, with very large result sets, the entire results cannot fit in the connection's network buffer. If the application doesn't read them fast enough, then eventually the network buffer fills up, and the execution engine must stop producing new result records to send to the client application. When this happens the spid must be suspended, and it is suspended with the wait event ASYNC_Network_IO. It's a slightly misleading wait name, because it makes you think there might be a network performance problem, but its more often an application design or performance problem. Note that when the spid is suspended -- just like any other suspension -- the currently held locks will remain held until the spid is resumed.

In our case, we know that we have millions of CDs and we can't fit them all in application memory at one time. We, by design, want to take advantage of the fact that we can stream results from the database and work on them in chunks. Unfortunately, if we happen to be holding a conflicting lock (S lock on Bucket record) when the reader query is suspended, then we create a multi-layer application deadlock, as we observed, and the whole system screeches to a halt.

So what to do for a solution? I will discuss some options and our eventual decision in Parts 2 and 3. Note that I gave one hint at our first attempt when I talked about "covering indexes", and then there is another hint above that we didn't get to in this post about "lock escalation".

Steve

MSSQL non-clustered indexes INCLUDE feature explained

2011-12-22T12:17:00.002-06:00

Today I received a question from someone about the nature of the INCLUDE feature when creating a non-clustered (secondary) index on a table. My response was a bit long, and I haven't posted in a while -- ergo blogpost! Here's the question:

What is your opinion about using the include statement when building your indexes? I’ve never really used the included functionality and I’m curious if there are upsides or downsides to them. My reading lead me to believe that I should use the include when I have a non clustered index and space appears to be a concern. I can use the ‘include’ as part of the index with the columns that may not be used as frequently. We’re using standard datatypes and nothing with very large column widths. So is there a benefit to using include?

A clustered index is stored in a B+-tree data structure and the actual data the whole row of data is in the leaf. So if you think of a b-tree structure (simplified) as something like:

           A
         /   \
        B     C
       / \   / \
      M   N O   P

And you have records like

[ Id =1, FirstName = Steve, LastName = Ash ]
[ Id = 2, FirstName = Neil, LastName=Gafter ]

Then for the clustered index, the id data (id=1 and id=2) will exist at every node (A, B, C, M, N, O, P), but the bytes for “steve” “ash” “neil” “gafter” will only exist in leaf nodes (either M N O or P). The id is used to locate which leaf holds the whole record. (note this is a simplification, see Wikipedia for more info about b+-trees). The noteworthy fact is being a clustered index means that the whole record is in a leaf (i.e. M N O P).

Now let’s think of a non-clustered index on lastName that corresponds to the clustered index above.

In this case the “last name” is used to get to the leaf, and the leaf holds the primary key of the corresponding row in the clustered index. So D E or F will have things like lastName=Ash and lastName=Gafter and the leaves Q and R will have both lastnames and IDs. So an entry in Q or R might look like [lastname=Ash, id=1] (again simplifying).

So if you issue a query like

SELECT firstName FROM ThisTable WHERE lastName = ‘Ash’

(and the optimizer chooses to use the non-clustered index) then the database engine will do something like:

Seek the non-clustered index for ‘Ash’

Look in D to decide which direction to go E or F (lets say E is the right choice)
Look in E to decide which direction to go Q or R (lets say Q is the right choice)

Find the primary key for ‘Ash’

In Q find id for Ash – which is id=1

Seek the clustered index for id = 1

Look in A to decide which direction to go B or C (lets say B is right)
Look in B to decide which direction to go M or N (lets say N is right)

Find the value of firstName for id=1

In N find firstName for id=1 which is ‘Steve’

return ‘Steve’ as the query result

Notice that we created a non-clustered indexed on lastName and we can use that index to quickly locate things by last name, but if we need any additional info, then we have to go back to the clustered index to get the other info in the SELECT list.

The “include” provides a way for you to shove additional information in the leaf nodes of non-clustered indexes (Q and R) to alleviate this "going back" to the clustered index.

So had I created the non-clustered index above on LastName INCLUDE FirstName then the engine would only need to do:

Seek the non-clustered index for ‘Ash’

Look in D to decide which direction to go E or F (lets say E is the right choice)
Look in E to decide which direction to go Q or R (lets say Q is the right choice)

Find the firstName for ‘Ash’

In Q due to the include there is id=1 AND firstName=’Steve’ so we have the first name right here!

return Steve

So you get rid of that entire other seek into the clustered index. This additional seek shows up as a “bookmark lookup” operation in the query plan in MSSQL 2008 & MSSQL 2000 and just another join in MSSQL 2005 query plans. Bookmark lookup is a join -- just with a different name to indicate its semantic role in the query plan.

When you have an index such that they query can be completely served from the index without needing to go back to the clustered index – such an index is called a covering index. The index covers the needs of the query completely. And it’s a performance boost as you don’t need the other join.

So this means a few things:

You can obviously only “include” fields in non-clustered indexes. Clustered indexes already have all the fields in the leaf...so it doesn’t mean anything to include more.
You can only have one clustered-index for a table, but you can simulate have multiple clustered indexes by INCLUDing the rest of the columns on your secondary indexes
By duplicating the data in the secondary index, if you UPDATE firstName – you now have to update both the clustered index and the nonclustered index. (Main trade-off consideration)
- This is also a huge deadlock opportunity if you’re not using read committed snapshot isolation (RCSI) level. Think of two queries: (1)
```
UPDATE MyTable SET firstName = ‘Steve2’ where id = 1
```
  and (2)
```
SELECT shoeSize FROM MyTable WHERE lastName = ‘Ash’
```
  (pretend shoe size is a new field that is in the clustered index but NOT in the non-clustered, i.e. NOT in the INCLUDE). Then the SELECT will seek the non-clustered index, grab shared (S) locks, then (while holding S locks) traverse the clustered index. Whereas (in the opposite order) the UPDATE will seek the clustered index, hold an exclusive (X) lock, then seek the non-clustered index to update firstName. The fact that these two queries are holding incompatible locks in opposite directions, is a deadlock waiting to happen. If I had a dollar for every time I diagnosed this deadlock scenario...
By duplicating the data in the secondary index, each page in the leaf (Q and R) now has fewer rows per page and thus there is a greater memory demand on the buffer cache (and more IO to get the same number of records) (Second trade off consideration)

Some databases (even MSSQL < 2005) don’t support this feature, but you can approximate it by creating non-clustered indexes with compound keys. I.e. if I created the non-clustered index on
```
(lastName, firstName)
```
then the index still covers queries like
```
SELECT firstName FROM myTable WHERE lastName = ‘Ash’
```
Note that this is not as good as the INCLUDE solution (for this particular query) as now the bytes of firstName=’Steve’ take up some space in non-leaf nodes D E F.

So deciding to use an INCLUDE is (like everything) a trade off. If you have a performance critical query that is being executed frequently, then you can usually use INCLUDEs to reduce the number of joins and increase performance. In an environment where CPU is more precious than memory this can be a big win (we can talk about cache locality benefits of includes later). However, if you INCLUDE a column that will be UPDATEd later – then you often are shooting yourself in the foot as the cost can easily outweigh the benefit.

Last tidbit about INCLUDEs that I’ll mention. The sql index analyzer is REALLY aggressive about recommending you add indexes with lots of INCLUDEs. This is because the index analyzer usually doesn’t know how many UPDATEs you’re doing. Usually you just tell it what SELECT you want to speed up and it naively says “oh well of course if you add these three covering indexes, this SELECT will be faster.” And while that’s true it doesn’t take into account the _total_ workload (UPDATEs DELETEs etc) so just be skeptical when you see this if you use the index analyzer.

I can’t give you a hard and fast rule to say INCLUDE is GOOD or EVIL as – like everything with database performance tuning – it depends ;)

Steve

Delegates or interfaces? Functional and OO Dualism

2011-07-31T20:14:00.001-05:00

I have a mixed background: doing C#/.NET for ~4 years then switching to Java (switched jobs). I have been in the Java enterprise ecosystem for the last 4 years. I do mostly Java, but enjoy doing a little C# every now and again. C# is really a nice language. Shame its in such a horrible Microsoft-centric ecosystem.

In any case, I've been writing a little thing in C# and needed a type with a single method to "doWork". So coming from a Java bias I created a:

public interface IWorker {
   void DoWork();
}

Later, however, I wanted to offer the users an API option of just using a lambda to "doWork". Unfortunately, there is no type conversion from a delegate to the matching "single method interface" (at least that I could find, if someone knows the answer, please share!). So as a shim, I created:

public delegate void WorkerDelegate();

public WorkerWrapper : IWorker {
   readonly WorkerDelegate workerDelegate;
   public WorkerWrapper(WorkerDelegate workerDelegate) {
      this.workerDelegate = workerDelegate;
   }

   public void DoWork() {
      workerDelegate();
   }
}

So I wrap the lambda in a little wrapper and don't need to change my entire IWorker-based infrastructure. It works, but I'm not happy with this. I know that in the Java lambda mailing list, they are planning to include a "lambda conversion" so that lambdas can be converted to compatible single abstract method (SAM) types. This would've alleviated my need for the shim above as I could've assigned the lambda directly to an IWorker and all would've been well.

I believe the "C# way" would've been for me to use delegates all the way through to begin with. Had someone come along with an IWorker interface then that would've been assignable to my WorkerDelegate.

But is this the right answer? Conceptually, how should I think of these? What is an IWorker in the above case? Is it really just a chunk of code that should be passed around as such? Or is it a member in the space of collaborating types that make up my system...

This is an example of the conceptual problems reconciling a Functional view of the world with an object oriented view of the world (dualism). I know that many people smarter than me have thought about these problems, and I'm hoping that I can find some good articles discussing them.

It feels like we're describing the same concept: a "chunk of code" that is defined by an interface (call it a delegate or a SAM, same thing). I don't think that I would have any dissonance if both were assignable to each other, and thus can be treated as different expressions of the same concept. If this were the case, then maybe I would view delegates as just SAM types -- so my "world view" is still object oriented, I just have an additional, concise lambda syntax to create SAMs. Actually, if this were the case, then you could probably invoke the Liskov substitution principle and call functional-OO dualism reconciled...

But something still seems amiss. There is more to the identity of an IWorker than the fact that it takes no arguments and returns nothing. I suppose the same questions are true of reconciling structural typing to static typing. Hmm.. I have a lot of reading to do.

I imagine there are a number of philosophical problems between functional and OO. This is just the one I ran across and felt dissonance with C#s implementation. Maybe they truly are different things and should be treated as such. I hope (despite my extremely small readership) to get some links to articles on this topic.

Steve

I <3 Robert C. Martin

2011-07-09T13:59:00.001-05:00

Im reading Clean Code by Uncle Bob. I have read sections of this book before when it came out and actually had the pleasure of watching Robert Martin present it at SDWest in 2008. I've decided to read the whole thing.

A while ago, I read a blog post from someone who was arguing that software wasn't a craft but a trade. I believe the authors intention was to say that we software developers should recognize that the value of the software is the business value and thus we shouldn't wax philosophic about "elegance in design" or software aesthetics as that was all wasting time trying to get to the goal. I may be misrepresenting the author's intention. I couldn't find the post to link it.

In any case, I disagreed entirely with this opinion. While I agree that business value is the motivator-- the craft aspects such as aesthetics, conceptual purity, elegance, etc. All contribute to the solution and its extensibility and maintainability. Maybe we're just arguing over the definition of craft, trade, or art, but in any case I feel there is value in recognizing the challenge of good engineering for today and tomorrow. The masters do it almost effortlessly-- almost accidentally. That feels like art to me and thus should be labelled appropriately as craft.

To this point, clean code is more art than science and Mr. Martin has something to say about it that I really enjoyed:

Every system is built from a domain specific language designed by the programmers to describe their system. Functions are the verbs, classes are the nouns. This is not some throwback to the hideous old notion that the nouns and verbs in a requirements document are the first guess of the classes and functions of a system. Rather, this is a much older truth. The art of programming is, and always has been, the art of language design.

Master programmers think of systems as stories to be told rather than programs to be written. They use facilities of their chosen programming language to construct a much richer and more expressive language that can be used to tell that story. Part of that domain-specific language is the hierarchy of functions that describe all the actions that take place within that system. In an artful act of recursion those actions are written to use the very domain specific language they define to tell their own small part of the story.

So to argue that software is not art is to naively ignore the reality that language is hard and has a dramatic effect on the bottom line of your code base. How many software systems never change or never need to be understood after they are written? Such systems must not be very interesting or do anything important.

Let's recognize the art of good software engineering! It will motivate us to continue to improve if we recognize these things have a value.

Maven -_-

2011-06-27T22:54:00.001-05:00

I have spent the last few days mucking about with POM files. Anyone that has done this understands where I'm going with this. So I'll just leave these two quotes that fit nicely:

But there has to be something fundamentally wrong with any tool that, whenever I use it, seems to have at least a 50% chance of completely fucking up my day.

-Charles Miller

The people who love Maven love the theory. The people who hate Maven hate the reality.

-Zutubi

Frustration.

EDIT: For anyone running across this. Now that I am well over the "learning curve" hump. I <3 maven. Seriously. Yes there are some rough edges-- I really should be able to delete folders simply without having to do ant-runs, etc. But its benefit drastically outweighs its cost in our environment.

OO Reading List

2011-04-13T10:18:00.002-05:00

One of my favorite parts of Pragmatic Thinking is the description of the Dreyfuss model of skills acquisition. This describes the phenomena of how people are frequently distributed along some non-trivial "skill" (like programming), and defines metrics about what differentiates each skill level. Overall, as one moves up to higher skill levels, they are increasing their intuition about the problem space. Intuition is something for which we must train our brain through experience and knowledge. To that end, there are a few books that have helped me in increasing my intuition, which I would like to catalog. If you have others that are missing, please leave a comment! My appetite for the amazon marketplace is insatiable ;-)

OO and Design Patterns

But Uncle Bob Essay on SOLID - This is Robert C Martin's article outlining the principles of Object Oriented Design. If SOLID doesn't ring a bell, then start with this article. Note that the now-famous acronym: SOLID is not actually mentioned in this post, but Robert C Martin is still credited as the inventor.
Agile Software Development Principles, Patterns, and Practices - lovingly referred to as the PPP book (not to be confused with the protocol). This describes much of the why of OOD, and explains the Agile mindset.
Object Design - another often referenced book describing the why and various design decisions that go into object oriented design. Thinking about objects isn't hard-- category theory and abstraction is something that our brain does quite naturally (hence the appeal of this design methodology). However, the ergonomics of OOD can sometimes lead to an undeserved sense of self-confidence in one's design. It may feel like OOD, because "oh look-- there are objects there! inheritance! oh, my!", but within the context of software engineering there are many factors that make some designs good and some bad.
Design Patterns: Elements of Reusable Object Oriented Software - Canonical book by the "gang of four". Has good description of patterns and why they are useful. If you prefer something with prettier pictures, starting with the Head First Design Patterns book is nice too
Essays on OO Software Engineering - Maybe not terribly well-known, but well written theoretical overview of OO, the design forces in OOD, and the motivations behind them. I had the pleasure to work with Ed.
Patterns of Enterprise Application Architecture - Canonical book on patterns by the man himself
Refactoring - Another Fowler book. I haven't read this one cover to cover, but read many chapters. Good examples to get your head around particular refactoring patterns
Domain Driven Design - Eric Evan's now-famous book on how to turn business problems into rich object models. Great read.
Real World Java EE Patterns - while this is a "java" book, the principles and design trade-off analysis that Adam Bien does for each pattern is universal. Good read.

Code

Beautiful Code - Essays where programmers reflect on what is beauty in code. As the authors wax philosophic about their "beautiful" examples, you glean insight into their thought process. It's a nice read.
Implementation Patterns - Kent Beck's book about the low-level decisions we make as we actually type the code and create APIs (knowingly or unknowingly). One of my top recommendations. I really love this book.
Clean Code - guide to code readability, writing code at appropriate abstractions, etc. A nice companion to Implementation Patterns. I had the pleasure of meeting Robert C Martin at a conference once. I'm sure I acted appropriately star-struck.

Other "meta" and philosophic musings

Notes on the Synthesis of Form - this is not a computer science book, but deals with the theory of what is design, and describes a methodology for decomposition. It's a quick read, and at least the first half is worth the exploration just to get some ideas in your head about methodologies for design.
Pragmatic Programmer - what list would be complete without this one! Good overview of the pragmatic aspects of becoming a good programmer. From problem solving skills to tools, this is required reading. I think if you read this, then skip or at most skim Productive Programmer
Pragmatic Thinking: Refactoring your wetware - I mentioned this at the front of the post. I enjoyed most of this book-- in particular the front half. Some of the topics towards the end were less interesting, because they were more familiar. In any case at least the first three chapters are a great read.
The Little Schemer - you can run through this in an afternoon. This is an introduction to recursion, via Scheme/LISP. This book is fun, because its a simple and unique format, but takes you through a journey that helps shape your mind to "think" of solutions recursively.
Beautiful Architecture - This one wasn't as successful to me as Beautiful Code, but still worth a read. There are a few chapters you can skip, but a few (especially the first chapter) that are great.
Beautiful Data - I'm only about half way through this one, and need to spend more time with it, as I'm sure there are some gems in there I have yet to run across.

Reading TO-DOs

These are books that are on my shelf to read next (that are relevant to this list at least)

The Design of Design - Fred Brooks (of Mythical Man Month fame) waxes about design philosophies and goes through a few case studies. Im really excited to make time for this.
Masterminds of Programming - interviews with the creators of many of the major languages used over the last 30 years. Looks promising.
Thoughtworks Anthology - I am going to be selective in which essays I read. I will start with those that are most applicable to my world, and then move out to the more "exotic" (relatively). I know that there are essays in here that will be more useful to my current world than others.

I feel like I'm missing some...

Steve

Spring 2011 Reading List

2011-03-06T14:15:00.003-06:00

I gave last Spring's reading list (which was more what I had read in the previous year) in this post. This spring, I am going to write what I am currently reading or hope to finish this Spring.

Seven Languages in Seven Weeks - this book looks interesting, and certainly the challenge of trying to meaningfully cover seven languages and language philosophies in a short book will be interesting if nothing else.
Programming in Scala - I have "played" with Scala, but not done more than toy programs. However, from everything I know about it- I believe I will really enjoy it. I buy into a lot of the functional vs object oriented dualism, and certainly enjoy the terse syntax. I think there are still interesting questions with regards to software development economics (i.e. how do we integrate Scala in a team of mixed skill levels, cost trade offs, etc.)
Thinking Forth - I'm not particularly interested in Forth, but I am interested in language design and problem solving philosophies.
Domain Driven Design - this was recommended by a commenter in the previous post, and I picked it up. I've made it through quite a bit of the book, and have enjoyed it so far. I had always heard this book referenced by Fowler et al, and really I should've read it years ago...
Introduction to Reliable Distributed Programming - its a Springer book, 'nuff said. I've been through a few distributed computing books, and have a fairly broad knowledge of the space. I am hoping to get a more mature, theoretically rigorous view of the problems now.
The Art of Multiprocessor Programming - this book is great. I enjoyed the nice mix of intuitive description and theoretical rigor. It's a nice blend of theory and pragmatics. I really recommend reading this for anyone that wants in depth knowledge of parallel computing.
Introductions to Neural Networks for Java - this was an interesting book to skim I don't really want to recommend it, because most of it is explaining his neural network code base instead of the underlying concepts. In any case, its a nice thing to skim over an afternoon.
Neural Networks and Learning Machines - Great textbook for all the theoretical background and mathematical proofs regarding Neural Nets and machine learning. I've had to crack open my calc books to freshen up while going through this...its dense.
Fuzzy Models and Genetic Algorithms for Data Mining and Exploration - I can't recommend this book (see my Amazon review if you're curious why), but it does provide a decent vocab overview for the topics it covers.

Well that's it for the moment! This spring is a bit more theory heavy than the previous list... that probably reflects my work and school change, which has been more research oriented in the last year. I'm not moving away from the real world just trying to get a more comprehensive grasp on both worlds in the areas which I am interested. I've always thought this was one of my strengths-- knowing enough theory to shape my thinking skills and be knowledgeable-- but continuously, deliberately enriching my implementation and practical skills to actually put the theory to good use! The intersection of the two is the more rewarding area for me, I think.

Steve

Building Derby with Eclipse gotcha

2011-03-05T13:46:00.003-06:00

This is partially a reference for myself and for anyone else trying to build Derby 10 from source using Eclipse. My thesis project involves modifying the on-disk page layout for a database (long story for another post). I am currently using Eclipse for my IDE. I just wanted to document a quick pain point in case anyone else is Googling for the answer:

I wanted to do a clean build of all of Derby. So I set up an ANT External Tool launch configuration:

Launch the build.xml from the root Derby directory
Working directory is the root Derby directory
Refresh resources upon completion
Uncheck the "build before launch
Choose the clobber, all targets (clobber is a total clean)
Defaults for everything else

I started to build and failed with the follow errors (I'm omitting some of the ones in the middle):

[javac] C:\DerbyDev\java\build\org\apache\derbyBuild\javadoc\DiskLayoutTaglet.java:24: package com.sun.tools.doclets does not exist
[javac] import com.sun.tools.doclets.Taglet;
[javac] ^
[javac] C:\DerbyDev\java\build\org\apache\derbyBuild\javadoc\DiskLayoutTaglet.java:25: package com.sun.javadoc does not exist
[javac] import com.sun.javadoc.*;
[javac] ^

...

[javac] C:\DerbyDev\java\build\org\apache\derbyBuild\javadoc\UpgradeTaglet.java:102: cannot find symbol
[javac] symbol : class Taglet
[javac] location: class org.apache.derbyBuild.javadoc.UpgradeTaglet
[javac] Taglet t = (Taglet) tagletMap.get(tag.getName());
[javac] ^
[javac] 40 errors

So as you can see from the first two errors -- its missing the dependency for Javadoc things. As it turns out Derby defines its own Taglet for Javadoc processing. All of these classes are defined in the JDKs tools.jar file, which is in the JDK's/lib directory (not included in the JRE).

Derby's build script includes tools.jar by:
<pathelement path="${java15compile.classpath};${java.home}/../lib/tools.jar"/>

Well I went to my command prompt and looked at my environment variable and java_home was set to the JDKs location. So this should've worked. I added a new launch configuration to execute the showenv target, and added an echo statement to include java.home.

I ran this and low and behold it was pointing to the JRE path, which doesn't have a tools.jar. So the world made sense now. In my eclipse installation, I have both the JDK and JRE installations defined in my preferences. For some reason (subconscious desire to shoot myself in the foot?), the JRE was chosen for this workspace, and thus the launch configuration used that.

So to resolve the problem, you can change the external tools launch configuration for the ANT script. Go to the JRE tab and select separate JRE and choose the JDK. Or change the default JRE for the workspace, and leave the launch configuration set to run in the same JRE as the workspace.

This isn't a tricky problem, but can be a little misleading...plus I haven't posted in a while ;-)

Defender Methods: Neal Gafter is not painting a bike shed

2010-12-01T15:55:00.005-06:00

I follow the lambda-dev mailing list, and there is a discussion going on regarding defender methods and automatic disambiguation. Defender methods are a language feature that allows some interesting things:

Adding methods to existing interfaces without breaking backwards compatability
Multiple inheritance of behavior (but not state-- think interfaces with code)

The second item is profound (well both are), and it will be interesting to see how its usage is adopted by the community. The approach taken with defender methods is described as "declaration-site" extension methods, because it has a syntax present in the interface declaration. For example, imagine adding a "randomElement" method to java.util.Collection. Today, you can't do that without breaking every class that implements Collection. Using a defender method you can do:


interface Collection<T> {
   T randomElement() default Collections.randomElement;
   ...
}

// add the default implementation to Collections
public class Collections {
   ...
   public static <T> randomElement(Collection<T> c) {
      ...
   }
}

Other languages implement use-site extension methods (e.g. C#) in which case the owner of Collections doesn't have change anything. You could write (in C#)


namespace SteveCode.Extensions {
   static class MyCollections {
      T randomElement(this ICollection<T> c) {
         ...
      }
   }
}

Then anywhere you state "using SteveCode.Extensions" (i.e. "import" the namespace) then you can invoke someCollection.randomElement() and the compiler will invoke the static method. Ergo, the "user" of the extension method has to indicate that he is using it.

There are some great articles out there discussing the pros/cons of declaration vs use site approaches, so I wont re-hash them. See Remi Forax's post and another.

Java is going with declaration-site style and one of the benefits as now inheritance can still work. I.e. if you augment an interface to add a new method with a "default" and then later in your concrete class you wish to specialize this new method, you can override it and consumers will call the specialized method via polymorphism (as expected). This doesn't work with use-site extension methods as they are just a compiler trick.

So on the lambda-dev list, there has been a discussion over a particular feature in the current specification. Take the following:


public class Impls {
   public static void one(Object o) { ... }
   public static void two(A a) { ... }
   public static void two(B b) { ... }
}

interface A {
   void execute() default Impls.one;
}
interface B {
   void execute() default Impls.one;
}

If you defined a class MyAB implements A,B what would you expect to happen? Well currently the spec allows this "automatic disambiguation" because they both delegate to the same method/overload. Where this becomes a problem is if later the owner of B changes the default of B to something else. Now when you recompile MyAB suddenly it breaks and you must manually disambiguate by implementing execute inside MyAB.

Note that if the interfaces took a different overload of the default, for example:


interface A {
   void execute() default Impls.two;
}
interface B {
   void execute() default Impls.two;
}

Now class MyAB implements A,B would fail right off the bat the first time-- because there is no overload in common. Thus, automatic disambiguation would not work in this case either (nor would you want it). Lastly, imagine having:


public class Impls {
   public static void one(Object o) { ... }
   public static void two(Object o) { ... }
   public static void two(A a) { ... }
   public static void two(B b) { ... }
}

In this case, I think (and someone please correct me if I'm wrong) that normal overload rules will apply and this will compile, invoking two(Object o) in MyAB, but in another class that only extends A, it would call two(A a).

There is also some additional complexity that must be added somewhere (talk of changing the .class file format to include linking information) so that in the presence of changing versions of the interface, the code compiled against the old version will still work (remain binary compatible).

All in all, there is some complexity for doing this "automatic disambiguation". Neal Gafter of Java Puzzlers, Sun Java spec, etc. fame (not in that order) has raised the point of whether this complexity is worth it. One of his proposed solutions is just to use method bodies in the interface itself. This would remove the overload resolution of the "default" entirely, moving the disambiguation to the client at the very beginning instead of making it potentially a source incompatible change to modify the defender's default (probably unexpected). This seems like an entirely reasonable conversation to have on the mailing list as its a language detail that has the potential to have expensive impacts. The discussion was going on for a few days-- and Reinier Zwitserloot (of Project Lambok, etc. fame) chimes in with:

When is the currently proposed "default method is part of the signature" aspect going to result in a problem? If this is about ideological purity, then I vote we stop painting this bikeshed.

If you don't get the bikeshed reference, check here. In classic Neal fashion, he had a precise (ableit somewhat arrogant) retort, which upon reading I had a good chuckle:

An interesting reference to Parkinson's *law of triviality*. The basis of Parkinson's law is that people seem to care less about issues they don't understand, no matter how important those issues might be relative to the issues for which they express a preference. "painting this bikeshed" is an *ad hominem* suggestion that the participants in this discussion are really only commenting on those issues simple enough for them to understand.

In this case, however, you also appear to be saying that you don't fully appreciate the issue, and therefore don't see any point in continuing the discussion. Which ironically reinforces the reference to Parkinson's law.

I like Neal Gafter and Reinier Zwitserloot and am happy that everyone on the dev lists cares enough to take time to discuss these things for the (I believe) betterment of the Java community. Its not to say there should be unbounded discussion, but I personally found Neal's points useful. Automatic disambiguation does seem to require complexity that outweighs its benefit-- and that's worth discussing.

Steve

Notes on the Synthesis of Form

2010-11-19T17:18:00.002-06:00

I just got in Notes on the Synthesis of Form by Christopher Alexander. This is an academic, theoretical treatise on design. It deals with "what is design", etc. It was written in 1962, but the ideas are obviously still relevant today--even though some of the motivating examples seem a little anachronistic. While it has nothing to do with software architecture (the term didn't even exist back then!), it is a fascinating read for those of us who enjoy some philosophical pandering every once in a while.

In the introduction "The Need for Rationality", the author makes clear his opinion of self-proclaimed "artists":

The modern designer relies more and more on his position as an "artist", on catchwords, personal idiom and intuition--for all of these relieve him of some of the burden of decision, and make his cognitive problems manageable. Driven on his own resources, unable to cope with the complicated information he is supposed to organize, he hides his incompetence in a frenzy of artistic individuality. As his capacity to invent clearly conceived, well-fitting forms is exhausted further, the emphasis on intuition and individuality only grows wilder.

In this atmosphere, the designer's greatest gift, his intuitive ability to organize physical form, is being reduced to nothing by the size of the tasks in front of him, and mocked by the efforts of "artists". What is worse, in an era that badly needs designers with the synthetic grasp of organization of the physical world, the real work has to be done by less gifted engineers, because the designers hide their gift in irresponsible pretension to genius.

(pg. 11)

I always enjoy well-written calls to humility. I wonder who in particular the author had in mind when he wrote this? What's funny is this was written in 1962 and seems no less valid in 2010 :-)

Steve

Deadlock two ways (Microsoft SQL Server)

2010-10-26T10:23:00.005-05:00

Think of "Duck two-ways" or some other delicious meal. This is as tasty ;-)

If you have done any development with Microsoft SQL Server with even a moderate amount of concurrent processing, then you have probably witnessed the dreaded:

Transaction (Process ID 42) was deadlocked on lock resources with another process and has been chosen as the deadlock victim

This indicates that Microsoft SQL Server has detected a deadlock and has killed one of the processes to eliminate the stale mate. Let's go through two very different deadlock conditions that have the same central theme. I have found these to be extremely common in production.

Intuitively deadlock is a "deadly embrace" that occurs when two resources are being contended over. Thus, people are often surprised when they get deadlocks and "they weren't touching the same records!". Unfortunately, in traditional pessimistic locking solutions to concurrency control, other records must be locked to guarantee ACID properties. There are other solutions to concurrency control (MVCC is the one everyone reaches for) that avoid most/all of this. However, MSSQL by default employs a pessimistic approach. Also, I don't mean to sound as if I'm picking on MSSQL-- the principles below are true in a number of database implementations. DB/2 is also particularly nasty with pessimistic locking style deadlocks. The two presented below were reported to the JTDS forums, and are from real production.

Deadlock I

This is the common unicode "mismatch" problem. This has been covered on blogs a lot. I am going to use this as a way to describe how to research deadlocks. But if you're already bored, go ahead and skip to Deadlock II
Here is a table definition (slightly changed for brevity):

CREATE TABLE [PM1](
[ID] [bigint] IDENTITY(1,1) NOT NULL,
[KEYNAME] [varchar](50) NOT NULL,
[VALUE] [varchar](255) NULL,
CONSTRAINT [PK_PM1] PRIMARY KEY CLUSTERED
(
[ID] ASC
))
CREATE NONCLUSTERED INDEX [pmkv_idx] ON [PM1]
(
[KEYNAME] ASC,
)

Now we execute multiple, concurrent:

DELETE FROM PM1 WITH (ROWLOCK) WHERE KEYNAME = @P0

And we get a deadlock! Let's familiarize ourselves with some technical details and terms:

Clustered and Non-Clustered Indexes

There are two database structures for this DDL. One primary, clustered index, which has a key [ID]. And a secondary, non-clustered index, which has a key [KEYNAME]. A "clustered" index means that all of the data, the entire record, is stored in the leaf of the index. It is still an index--it is still searchable by [ID], but when it gets to a leaf, the entire data record is physically stored there. This is different from a secondary or non-clustered index in which the leaf of the index contains some kind of reference to the whole data record. In our secondary index, the index is "searchable" by [KEYNAME], but in the leaves of the index, the "reference" is actually the primary key value (ID), which can be used then to "search" the primary, clustered index. This is how databases use secondary indexes-- they find matching data with the index, then do a bookmark lookup, which is a join, into the clustered index to get the rest of the data.

Seeking vs Scanning

There are different actions the engine can perform on these structures: the engine can scan the index, in which case it will start somewhere (often the beginning) and start reading each record in order. As these indexes a B+-Trees, the leaf level is a doubly linked list. Thus, from a single leaf node, you can read sibling records in order without having to go "up and down" the index levels. Scanning is expensive as it is an O(n) operation which degrades as the number of records increases.

The engine can seek the index, in which case it will use a binary search to locate a leaf node (record). This is much preferable as it is a O(log n) operation-- and the base of that log is very high (the number of records per page). Thus seeking is why we put indexes on tables-- to take advantage of the "quick" searching.

Getting Information about your deadlock

In Microsoft SQL Server (2005+) there is a useful report that can give you good details about your deadlock. Without this information, it's very difficult to understand what's really happening. You can get this information two ways

SQL Server Profiler, capturing the Deadlock event
Enable Trace Flag 1222

I find it generally useful to enable T1222 as a startup parameter for SQL Server, so that whenever a deadlock occurs, it dumps the details to the SQL Server error log file. This is great, and incurs negligible performance overhead.

Trace 1222 Output

Let's look at the 1222 output and see what actually happened. There are two sections to the 1222: (1) the processes involved, (2) the wait-for graph, which shows which locks are acquired which are trying to be acquired. Here is an abbreviated 1222 for this deadlock:

<deadlock victim="process3dcab08">
<process-list>
  <process id="process3dcab08" ...>
   <executionStack>
    <frame ... >DELETE FROM PM1 WITH (ROWLOCK) WHERE AND KEYNAME = @P0 </frame>
   </executionStack>
   <inputbuf>(@P0 nvarchar(4000))DELETE FROM PM1 WITH (ROWLOCK) WHERE KEYNAME = @P0 </inputbuf>
  </process>
  <process id="process3de1198" >
   ... (same as previous process) ...
  </process>
</process-list>
<resource-list>
  <keylock ... objectname="DB1.dbo.PM1" indexname="PM_IDidx" ... mode="X" ... >
   <owner-list>
    <owner id="process3de1198" mode="X"/>
   </owner-list>
   <waiter-list>
    <waiter id="process3dcab08" mode="U" requestType="wait"/>
   </waiter-list>
  </keylock>
  <keylock ... objectname="DB1.dbo.PM1" indexname="PM_IDidx" ... mode="X" ... >
   <owner-list>
    <owner id="process3dcab08" mode="X"/>
   </owner-list>
   <waiter-list>
    <waiter id="process3de1198" mode="U" requestType="wait"/>
   </waiter-list>
  </keylock>
</resource-list>
</deadlock>

The process-list section describes all of the processes (concurrent executions) involved. I have colored one blue and one green to help distinguish them. So as we see each is holding an X (exclusive) lock, which the other is trying to get a U (update) lock for.

The database must hold an X lock before actually modifying a record, thus we expect this to be involved. However, a U lock is unexpected. Update locks are an "in between" lock, which are used by the database when scanning for potential records that need to be updated. In this case, a U lock is acquired before checking the value to see if it matches your WHERE clause. If it does, then the U is "upgraded" to an X lock, if not, then it is released. However, our WHERE claue has KEYNAME = @P0, which is indexed. Thus, we shouldn't be scanning anything-- we should be seeking on the index. When seeking-- the database goes exactly to the records which qualify, and thus X locks are requested to begin with. Thus, we expect to see only X locks from the statements above.

So what happened?

The answer is subtle: look at the input buffer for the delete statement:

<inputbuf>(@P0 nvarchar(4000))DELETE FROM PM1 WITH (ROWLOCK) WHERE KEYNAME = @P0 </inputbuf>

The parameter for the delete statement was declared by the driver as nvarchar, but if you look back at the DDL, you will see that the KEYNAME column is declared as varchar.

The NVARCHAR datatype is a unicode text datatype, whereas VARCHAR is non-unicode, 8-bit character datatype. The engine cannot directly compare an nvarchar value to a varchar value-- it must use a conversion. This conversion makes the where clause predicate not sargable, and that disallows the optimizer from seeking on it. Instead it scans the whole index, one record at a time, and for each one, requests a U lock, converts and checks the value, releases the U lock. Thus, for every delete of a single record, every record must be checked with an expensive, conflicting lock. And as seen in our case, two concurrent deletes happen to be checking and ran into each other.

The solution

So why did the driver do that? Well this was a Java application, and in Java strings are unicode by default. By default, the driver binds strings to their unicode counterpart. However, there is a setting on the driver's connection url, which instructs the driver to bind to non-unicode instead. The key is that you want to ensure that the driver is sending parameters the same as the underlying schema is defined. For JTDS the setting is sendStringParametersAsUnicode and it defaults to TRUE. Thus, if your schema is defined with all VARCHARs and you are using them in indexes, then you want to ensure this property is set to FALSE in your connection url. Here is an example of a connection url that forces the driver to send them as varchar instead of nvarchar:

jdbc:jtds:sqlserver://mssql01:1433/DB1;sendStringParametersAsUnicode=false

Deadlock II

This deadlock is a little less common, but interesting, because it also has an "unexpected" wait-for graph in the 1222 output. The schema was jBPM, which may be familiar. I need to see if someone has already fixed this in jBPMs delivered schema.

Trace 1222 Output

First, let's look at the 1222 trace:

<deadlock victim="process3de0868">
<process-list>
  <process id="process3deb08" ...>
   ...
   <inputbuf>(@P0 bigint,@P1 int)delete from JBPM4_SWIMLANE where DBID_= @P0 and DBVERSION_= @P1</inputbuf>
  </process>
  <process id="process3de0868" ...>
   ... same as other process ...
  </process>
</process-list>
<resource-list>
  <keylock ... objectname="dbo.JBPM4_TASK" indexname="PK__JBPM4_TASK__2BFE89A6" mode="X" ...>
   <owner-list>
    <owner id="process3deb08" mode="X"/>
   </owner-list>
   <waiter-list>
    <waiter id="process3de0868" mode="S" requestType="wait"/>
   </waiter-list>
  </keylock>
  <keylock ... objectname="dbo.JBPM4_TASK" indexname="PK__JBPM4_TASK__2BFE89A6" mode="X" ...>
   <owner-list>
    <owner id="process3de0868" mode="X"/>
   </owner-list>
   <waiter-list>
    <waiter id="process3deb08" mode="S" requestType="wait"/>
   </waiter-list>
  </keylock>
</resource-list>
</deadlock>

So we have two workers executing a delete by primary key... and they're deadlocking on S locks!? An S (shared) lock is used when the database needs to get a consistent read on something. Thus, by default, when you execute SELECT statements, shared locks are being issued under the covers to ensure read consistency (w.r.t the isolation level you're running at).

So what happened?

There is a hint in the wait-for graph that shows the problem: Look at the keylock that is being contended-- the indexname is PK__JBPM4_TASK__2BFE89A6. This is an auto-generated name for the primary, clustered index for the JBPM4_TASK table. We're deleting from the SWIMLANE table, so why would there be any locks on the TASK table? The TASK table has a foreign key reference (field swimlane_) to the SWIMLANE table. Thus, when you delete a SWIMLANE record, the database must ensure that there are no records referring to the SWIMLANE record. If there are, then the delete cannot proceed, because it would be a foreign key constraint violation. To do this check, the database needs to find records in the JBPM4_TASK table WHERE swimlane_ = id of swimlane being deleted. This read will be done using S locks to ensure consistency. Unfortunately, the JBPM4_TASK table does NOT have a secondary index on the swimlane_ column. Thus, the only option the database has is to scan the entire table by primary, clustered index. Thus, for each record, a S lock must be acquired, the record evaluated for the WHERE clause, and then the S lock is released. Each one of these is a deadlock opportunity if there are concurrent operations touching the TASK table.

The Solution

Adding an index on the swimlane_ column in the TASK table will reduce the n deadlock opportunities to 1, which is a significant improvement-- not to mention the performance improvement.

The Overall Theme

While these are very different deadlocks, the theme is the same: unintended scans. Scans are not only a performance problem, but a deadlock problem, as you increase the number of times that you request conflicting locks while holding locks. Thus, take care when considering which indexes to create-- its a tricky problem with many factors.

Steve

Some JIRA / GreenHopper Love

2010-10-11T16:39:00.007-05:00

This will be another brief, non-technical, un-informative post to rant..but in a positive way! I actually will post something informative and useful one day ;-)

A team member and I have been using JIRA and recently started using the GreenHopper plug-in. The plug-in advertises that it is "agile" focused. I have always been extremely satisfied with Atlassian products, but this is something special. They really have done a great job in usability with GreenHopper.

The "boards" present a nice, intuitive, usable visualization of a part of the project.
Every aspect of the "boards" visualization (color coding, progress bars, in-place editing) reinforces with high affordance the functionality of that view.
The tools gets out of the way as much as possible in terms of navigation and functionality. Its intuitive. I find that I spend 95% of my time just on the Task board. I never need to leave.
Using the "boards" is fun!

For example, from the "task" board, I can open bugs, assign them to other people, begin progress, etc. This is my "specialized" view that I, a developer, use to see my tasks and at-a-glance get a view of the whole sprint.

Here are some noteworthy features of this visualization:

There are three columns for this sprint: To Do, In Progress, Done. You just drag a card between the columns to start progress or resolve as done. Just as you would with a card on a cork board (intuitive metaphor).
You can switch projects and sprints/versions by clicking the down arrows next in the headers
You can add bugs, features, etc. for this sprint just by clicking the button for that issue (right under the filter icon).
You can add comments to the issue simply or bring up a light box with the entire JIRA issue (see below).
There is a nice progress bar that shows the overall progress for the entire sprint.

When a new sprint comes around you can check out the "planning" board, where you can drag and drop cards to different releases or sprints. Also, there is a "chart" board which summarizes various charts (burndown rate, etc.), and a "released" board which provides metrics on completed sprints and releases.

This is just a little bit of why I like GreenHopper. I have just been so pleased with it that I wanted to share. I have used bugzilla, plain JIRA, and Team Foundation in the past. Team Foundation I know has much of the same (if not more) reporting than GreenHopper, but I never saw a visualization for me, the developer, that was as useful (defined by power/weight ratio) as what GreenHopper provides in the Planning Boards. Its the subtle simplicity and usability that I think makes GreenHopper so great-- not just sheer functionality.

If anyone actually reads this I would be interested to hear others' opinions about tools-- in particular other "killer features" like GreenHoppers planning boards.

Steve

Naming Matters

2010-09-20T19:53:00.004-05:00

This title is kind of a two-for: "Naming matters" as in matters pertaining to naming and naming matters as gee golly-- names really do make a difference! So hurray for homonyms and making a neat opening to what is likely to be a boring post :-) (Have I hooked you to read further? dratz...)

API design "theory" is curious, because it seems to take a back seat in the academic literature, and yet the economic impact of bad API design is so great to the "problem" of software development. I guess the Software Engineering folk are fighting the good fight with code quality metrics, etc., but this is a hard topic, that I had never considered throughout my entire undergraduate career.

Here's an example of an API design mistake in my opinion (albeit a simple one). In Java, there are the following constants defined:

Integer.MIN_VALUE
Long.MIN_VALUE
etc.

These define the lowest value that can be represented by this datatype. Thus, for example, Integer.MIN_VALUE is -2147483648 given that its 4 bytes and uses a 2-s complement representation, etc.

These are used all over the place as sentinels. For example, a typical implementation of Dijkstra's shortest path algorithm initializes every node to a shortest distance of Integer.MAX_VALUE, and as the algorithm progresses, any value will (likely) be less than MAX_VALUE. Thus, it's a natural way to construct the algorithm without having to code a bunch of fragile "special cases" (adding to your cyclomatic complexity).

So what do you think Double.MIN_VALUE returns?

Well as a bug that I coded last week demonstrates, it does *not* return the minimum value of the range of values that can be represented in an instance of the Double data type. That would be ludicrous (this is me being sarcastic).

No, instead it returns the smallest positive value. You need to use Double.NEGATIVE_INFINITY for the smallest, *cough* minimum *cough* value.

Note that in C#/.NET Double.MinValue is the minimum value (i.e. negative number). I wonder what it is in limits.h...

So what's up Java?! I wonder how many man hours of time have been wasted on this pitfall since Java's inception? Can we ask Guy Steel and Bill Joy for a check? Just kidding...

Steve

Save the commentary, please

2010-05-08T21:27:00.003-05:00

I am working on a thesis right now on optimizing data structures and algorithms in database systems. I am doing my implementation for the first part in MySql, and will be augmenting one of the storage engines (maybe InnoDB, maybe something else) to test out some of the ideas in my paper.

Anyways, I picked up Understanding MySql Internals to use as a reference for some of the major components of the software. The technical information is pretty good, and its nice to get a discourse on such a large code base.

However, something bothers me about the book. Riddled throughout the technical details are little dollops of over-embellished praise for Monty Wideneous, the creator of MySql. Now, don't get me wrong-- I go a bit ga-ga for rockstar developers like Monty, Rod Johnson, Crazy Bob Lee, etc., but not in a technical book. It's just awkward to be reading about architectual decisions for the threading model in MySql and then read this:

As far as the programming skills were concerned, they were not lacking at all. Just as a good rider becomes one with the horse, Monty had become one with the computer. It pained him to see system resources wasted. He felt confident enough to be able to write virtually bug-free code.

(p. 109)

Hyperbole such as "Monty had become one with the computer" can be excluded from technical books in my opinion.

Here's another example of the Monty "love-fest":

...perhaps building on his God-given talent, Monty developed a habit and ability to write very efficient code naturally. He also developed, or perhaps was gifted from the start, with an unusually acute vision of what needed to be done to the code to make it useful in future development--without knowing in advance much detail about what that future development would be

(p. 1)

He could've removed this entire paragraph and we would know nothing less, except that the author clearly wants to be on Monty's Christmas card list. So, technical book authors: save the commentary, please. ...or maybe just keep it out of the main text and include an optional, opinion-based companion workbook!

For example, accompanying the section on Threads vs Forked Processes, there could be a multiple choice question:

Why did Monty Widenious choose a thread model instead of a forked process model for MySql?

Large amount of shared data between workers
Greater overhead in context switching processes over threads
Greater overhead in creating a forked process over creating a thread
Monty is a man-god, who is incapable of writing bugs in source code

Steve

Wow...erm...your database is leaking

2010-04-29T22:11:00.003-05:00

It's no secret that some of the traits that go into making good software developers are: problem solving, analytical, and abstraction skills. As we write code and design a software system, we exercise all of these skills -- in particular: abstraction. Abstractions allow us to build larger and more complex systems without needing bigger and bigger brains. We can reason about the interactions of components at various levels, and only focus on the details germane to the topic at the time.

Operating systems provide various abstractions that we use everyday: various models of how to "do work" (processes and threads), how to exchange information (multi-threaded programming primitives, etc.). We leverage complex data structures from libraries. We wouldn't want to re-write a hash table every time we need dictionary lookup semantics, or drop into assembly to write CAS instructions to re-implement mutexes and spinlocks every time we write a multi-threaded program. So *high five* to abstraction-- you're a good friend to us dumb humans.

Yet... there is a problem. In the perfect world in our cerebral cortex, things fit together nicely, and we gloss over real world needs and various "cross-cutting concerns". As such, there is the famous principal of leaky abstraction, which states that there are no perfect abstractions: all abstractions leak-- i.e. all abstractions expose some part of their underlying implementation. The amount of "leakiness" can be a quality metric. I would suspect that "leakiness" is correlated with complexity, and it is certainly correlated with how many resources are involved in the implementation.

For example, how leaky are mutex synchronization primitives? On the surface they sound simple! You try to acquire the mutex and get blocked until you get what you want. A nice abstraction, very useful. But then there are these pesky details of lock fairness, thread affinity, etc. that complicate the elegant abstraction. They typically rear their head through "cross-cutting concerns" such as performance. And this is key to the issue-- why can't there be a perfect abstraction? Because at some point there is a *finite* set of resources that are going to give a quick dose of "reality" to these "head in the clouds", "flowers and kittens" abstractions. And where abstract, pure concepts meet reality-- finite constraints start to paint a different picture.

So as developers, we deal with this by straddling the fence: we design in the world of abstractions, but maintain some "implementation" knowledge, and then TEST TEST TEST (for performance and other non-functional requirements). And we pick up little best practices about thread affinity, processor cache coherence, scheduling fairness, IO access patterns, etc. that let us meet these goals.

But in my experience with different teams and colleagues, something funny happens when databases are brought into the pictures. They are almost always treated as a black box. "Oh thats the databases job", "oh well the database just sucks", "databases suck". I have encountered a number of people who choose to write their own little mini-databases instead. They have no problem "breaking the abstraction" to think about file locks, optimizing reads/writes to reduce disk head seeks, etc.-- but they hold database technology to some higher standard; they pretend databases are a perfect abstraction!

So yes, databases are very leaky. They are leakier than many other programming tools, and this seems natural given the complexity. But they bring a slew of features, a slew of research, and a lot of production time with them. Thus, we as developers should be interested in understanding this tool, its leakiness, and how to effectively use it, just as we would anything else (O/S, hard disks, etc.).

Where do databases leak the most? Here's a brief list of various technical nuggets about popular database implementations that are important to at least have in the back of your mind when you're designing something with a database:

Concurrency is hard!

Its multi-threaded programming! Databases aren't magic-- they have to employ the same synchronization as the rest of the world to use a shared memory model of parallelism. Thus read up on isolation levels, read up on optimistic and pessimistic locking, and don't rely on "magic" as an answer for how databases do what they do.

Transactional consistency is hard!

Understand why ACID properties are important, how they make reasoning about complex interactions simple, and why it is almost always economically impossible to create a robust, complex system without some transaction abstraction

Searching for data is hard!

Searching problems in computer science make up a major chunk of the literature for the last thirty years. Oh, you put your data into a table, didn't understand what you should index, and now you blame the database for performing slowly!? Understand the difference in clustered and non-clustered indexes. Understand the concept of selectivity, and learn how to evaluate which queries are sucking the life out of your application.

At some point, I'll actually put something technical on this blog :-)

*kicks soap box to the corner of the room*

Steve

Spring Reading List

2010-01-05T15:35:00.005-06:00

Wow...I really haven't posted regularly, have I? I'd like to catalog some things for my own reference, and to come back in years and chuckle at my musings and naiveté. This leads naturally into a topic: knowledge and learning.

I am an avid reader. I don't really enjoy much fiction, but I love computer science and technology books. I have a bit of an ...erm... addiction (some would say) to Amazon Marketplace. If we take a trip in the 'way back' machine to 2001ish, we will see a younger (still in High School) Steve, delighted to receive his first Amazon Marketplace shipment: Advanced Visual Basic 6: Power Techniques for Everyday Programs and Effective Visual Basic: How to Improve your VB/COM+ Applications. Once you have stopped laughing at the thought of "Effective" or "Advanced" Visual Basic, please continue

Here are two of my bookshelves now. I can't honestly claim that I have read all of them cover to cover, but I always read at least a few chapters of each, and note which sections I want to come back to. Many, though, I have read all the way through-- for example, if you haven't read Brian Goetz's Java Concurrency in Practice, then you are missing out!

Here are some of my favorite books:

Effective Java by Josh Bloch. A collection of pragmatic patterns, and more importantly sound reasoning as to why they are recommended.
Java Concurrency in Practice - excellent overview of the two most important aspects of multi-threaded programming: memory consistency and mutual exclusion. People seem to forget about the first one. Once you finish this book, please go read William Pugh's information on JSR 133. After that if you still don't understand what volatile really is, then repeat.
Implementation Patterns by Kent Beck. He describes the book as a companion to Fowler's canoncial "Refactoring" text. Implementation Patterns focuses on the 'small' decisions that we make every day as it pertains to design, code organization, and getting all of the '-ilities' working for us. Reading this was like re-living the first few years of professional Java development-- Kent just did a good job 'formalizing' a vocubulary with which to discuss and evaluate these various 'design pressures' that enter our mind as we code.
Real World Java EE Patterns by JEE guru Adam Bien. I found this book wonderful. In particular, his trade off analysis that accompanies each pattern is an excellent way to learn how he reasons about design.
The Pragmatic Programmer - this is a famous book and certainly worth the read. I think it's a good litmus test for oneself. I read this once before I started my career and found that I learned a ton. I thought all of the little gems of advice were new and useful. I re-read (or skimmed) this recently, and found myself going "yep, I remember learning that the hard way". I kind of view this as a way to guage the efficiency of the environment within which you work. I have been lucky to work in an environment that properly incentivized writing good software. Thus, I learned these lessons quickly and efficiently as part of my day to day work. If you work in a lazy environment, you may never learn these lessons.
Beautiful Code - this collection of essays is a great read. It's goal (and it succeeds) is imparting how great developers think. These lessons help 'shape' the way in which we approach problem solving. The entire "Beautiful" series is wonderful. I have read them all, except the new "Beautiful Security".
Java Generics - I am not recommending this book, unless you are (a) curious about some of the 'exotic' features of generics, (b) enjoy the theoretical aspects of language design (reification, contra/covariance, etc.) , or (c) want to understand the reasoning behind the design decisions that were made by the expert group.
SQL Server 2008 Query Performance Distilled - this is my favorite pick for SQL Server optimization. Of course Delaney's Inside SQL volume on the matter is great too, but Distilled is a little bit more bang for your buck. I found more useful information crammed into a smaller text. Once you read this (and all of the Inside SQL Server series) then you can graduate to Craig Freedman's Blog

Whew... well I know I am forgetting some. I should probably edit this later after I return home to check any that I may have missed. Another neat fact I learned in doing this is that I have had 137 separate orders with Amazon since 2004... most of which had multiple books :/ I need to seek group help or something...

Steve

Welcome! Do you prefer a bold or mild brew?

2009-09-05T12:36:00.001-05:00

Hello,

My name is Steve. I am currently an enterpise Java developer in a high volume transaction processing oriented domain. We do a lot of 'batch' workloads, and so my day is filled with lots of interesting challenges. I hope to catalogue some of these challenges here, and if I'm lucky, some more learned individuals on the internets will contribute. My current interests are:

High volume, batch oriented, mixed workloads and how such workloads scale using traditional (DBMS) and non-traditional (grid, extreme transaction processing) architectures.

Database technology, specifically implementation with regards to concurrency

Distributed computing including caching and data grids, computing grids, partitioning approaches, etc.

Problem solving, cognitive calisthenics, intelligence and learning. Obviously, these are very important topics in Computer Science. I am interested in these primarily in how they relate to developer productivity, but also am interested in them in the AI domain.

Economics of software engineering. This includes SDLC processes, but currently focused on how teams and processes scale given specialization, project size, etc.

I feel like I am not doing a good job describing my interests. :-( I, like most, have a lot of them!

I know that this is just a metaphorical 'drop in the bucket' of technology blogs, but I am going to try to blog about things that I haven't seen on other blogs. This is spurious from the start, because obviously, I have only read a tiny subset of existing blogs... but I'll give it a go, none the less.

Upcoming topics (these first are very database centric):

- SQL Server deadlock hell (or how I learned to stop worrying and love the lock)
- Fragmentation, Batch Inserts, and Primary Keys...oh my!

Steve

Many Cups of Coffee

Multi-tier application + database deadlock or why databases aren't queues (part1)

And so it starts...

The algorithm

First sign of trouble - complete stand still

Finding out what the Java application was doing

Finding out what the database was doing...

Investing blocking and locking problems...

ASYNC_Network_IO wait and how databases return results

MSSQL non-clustered indexes INCLUDE feature explained

Delegates or interfaces? Functional and OO Dualism

I <3 Robert C. Martin

Maven -_-

OO Reading List

OO and Design Patterns

Code

Other "meta" and philosophic musings

Reading TO-DOs

Spring 2011 Reading List

Building Derby with Eclipse gotcha

Defender Methods: Neal Gafter is *not* painting a bike shed

Notes on the Synthesis of Form

Deadlock two ways (Microsoft SQL Server)

Deadlock I

Clustered and Non-Clustered Indexes

Seeking vs Scanning

Getting Information about your deadlock

Trace 1222 Output

So what happened?

The solution

Deadlock II

Trace 1222 Output

So what happened?

The Solution

The Overall Theme

Some JIRA / GreenHopper Love

Naming Matters

Save the commentary, please

Wow...erm...your database is leaking

Spring Reading List

Welcome! Do you prefer a bold or mild brew?

Defender Methods: Neal Gafter is not painting a bike shed