Dining Philosophers January 31, 2009

The Dining Philosophers problem is probably the most famous of the classic synchronization problems. Posed and solved by Edsger Dijkstra in 1965, it became famous not because it is practical, but because it demonstrate in a nicely visual way some of the dangers inherent in careless sharing of resources.

Five philosophers are sitting around a round (oak) table. Each of the five philosophers has a bowl of rice, and between every two bowls there is a single chopstick. As illustrated in the following diagram:

Philosophers never talk to each other. They spend their time thinking. When a philosopher becomes hungry, she attempts to pick up the two chopsticks closest to her (the ones that are shared between her and her left and right neighbors). Each philosopher can only pick up one chopstick at a time. Then she eats, without putting down the chopsticks. When she is done, she puts both chopsticks down and resumes thinking.

We must find a method that will allow the five philosophers to share five chopsticks and eat without letting any philosopher starve from prolonged lack of access to chopsticks.

As I wrote above, this is a very famous and non-practical concurrency problem. Surprisingly, no one demonstrated it in PL/SQL on Oracle database yet.

So, here are three different “solutions” to the dining philosopher’s problem for Oracle.

The code you’ll find in the link contains several sections:

1. Setup code to create the tables with the philosophers and their chopsticks.
2. set_status procedure that allows the philosopher to announce their status (eating, hungry) to us, so we can monitor their progress. This is an autonomous transaction, because we don’t want the philosophers to drop their chopsticks while announcing that they are eating.
3. Three different eating functions, representing the three typical solutions to shared resource problems.
4. add_philosopher code that will allow us to add philosophers to the table and watch them compete for chopsticks.

I also have a nice shell script that runs the five philosophers we need to make the problem interesting.

Now, some explanation about the three eating procedures.

1. The first one is the most trivial one. A philosopher grabs the right chopstick, then the left one and then eat. If any stick is busy, we wait. Note that for some time efficiency (and CPU killing) the philosophers eat very very fast in this version. Run this version and very soon, all philosophers will simultaneously pick up their right sticks and wait for the left to become free. They could wait a long time, but Oracle will soon choose one of them as the deadlock victim and allow the other four to proceed eating in peace.
2. An attempt of avoiding deadlocks – Each philosopher picks up her right stick, and if she sees the left one is taken, she drops her right stick and tries all over again. This will ensure no deadlocks (since waiting philosophers will not hold their sticks), but we are likely to encounter a situation where a philosopher keeps picking up and dropping his right stick without ever getting to eat. It is unlikely that this will continue forever, but it may continue enough to make our philosopher very unhappy with her response times. Since each philosopher should be able to eat on average 400ms every second, if a philosopher did not eat for an entire second we will consider her dead from starvation. If you run this example, you should see at least one philosopher dead from starvation.
3. At last a good solution! We avoid starvation by not dropping the stick we are already holding, and avoid deadlocking by switching the order in which we pick up the sticks. One of our philosophers will pick his left stick first. This solution is also called “partial hierarchy” – we make sure the blocking graph will be a tree and not a cycle. Run this example and see that you encounter no deadlocks and no starving philosophers.

Readers who made it this far – this example will be a part of my HotSos presentation (demonstrating two concurrency sins – deadlocks and starvation). Any comments are appreciated. If you ran my code and had problems, or worse, failed to run into dead philosophers, let me know. If you think my code plain sucks, let me know. If you didn’t understand what I’m trying to say or why I’m trying to say it, also let me know.

Look! I’m an Oracle Ace! January 28, 2009

Thanks to Laurent Schneider and Freek D’Hooge who nominated me, I now joined the prestigious group of Oracle Aces. Oracle actually emailed me last week with the news, but somehow I did not take it that seriously, until I saw the Ace logo next to my name in OTN. This makes me so happy. Few years back when I just started working with databases, I’ve read the OTN forums often and admired the Ace experts who gave such professional answers. Seeing this logo next to my name reminds me how much I learned and advanced in the last few years. Mostly the last year actually. It feels very satisfying to get this recognition. I’m sure this is not the end of the journey for me, but barely the beginning – there is always more to learn, more to test, more to write about and more things that will keep me up until 4am. Rob wondered why I still call myself “Just a Simple DBA” (I’m taking his question out of context a bit). The reason is that, despite being Oracle Ace and all that, I’m actually a  junior DBA at work. I’m working with several DBAs who are more experienced than me, are better troubleshooters, have more creative solutions to production issues, and know much more than me about many database topics. I’m getting an award not because I’m a better DBA, I’m getting an award because I enjoy sharing what I do. Sharing is important, but it is also important to keep things in proper perspective

Random Thoughts about Queues January 27, 2009

John Brady, wrote a short summary about queue theory and its relevancy to databases. Reading it reminded me of some mistakes I often see when queuing theory is discussed.

Lets start by introducing a concept that John somehow forgot to mention – randomness.

Queue theory is about randomness. The  rate in which requests arrives to your system is random, the amount of time that takes the server to process each request is also random.

When put in terms of randomness, utilization is the probability that at a given point of time the server is busy. Which is a good definition for utilization because we all know that at a point of time, CPU is either busy or not, 0% or 100%. When we talk about utilization we must talk about averages and probabilities.

This is a good place to note that when your average utilization is 50% there is still high probability of extended periods where  the system will be in 100% cpu and will have queues. This is normal result of our planning and cannot really be avoided. You can’t really design a system where the probability for 100% CPU is zero. It doesn’t make sense to do so. Now if only my managers would get that.

So, utilization is the probability that the server is busy, which is identical to the probability that the customer will have to stand in queue. How long will he have to stand? That depends on how many other customers are in the queue and how fast the server can handle them.

There is very little we can say about our queue without knowing something about the rate that work arrives and how fast the server handles them. There are some common assumptions used in queuing theory.

Without assuming those distributions the only thing we know is Little’s Law, which says that the expected number of customers in the system is equal to the rate of arrival multiplied by the average amount of time a customer spends in the system. This law only assumes that the rate of arrivals is not dependent on the queue length (note that even this simple assumption is not always true. Customers may turn away if they notice a queue).

From what I understand (and I may be mistaken here), this law does not translate into queue length and utilization, unless you have additional information about the distribution of arrival rates and service times.

So, we normally assume some standard random distribution, and we talk about average response times, average utilization, average arrival rates (poisson distributed) and average service times (exponentially distributed).

This can work well, but you need to take into account few things:

• There is nothing random or average about the high utilization that occurs at the end of each quarter, just when the users expect better than average response times. “Yes, I know that we agreed for 8 seconds on average, but I’m trying to get the bonuses out on time this month”. You need to account for these events separately.
• The occasional bug that causes a report to take 100% CPU for over 6 hours while everything queues may be random, but is always more frequent than you assume when ordering hardware. Murphy’s law trumps Little’s law every time.
• Almost queuing theory equations assume that when you have multiple servers, they are independent of each other. Service time in one server will not affect service times on others. If you actually plan to use queue theory, TEST THIS ASSUMPTION. You should test all assumptions, but this one is the least likely to be true. Suddenly you discover that your independent storage devices share a switch.
• The best advice about performance predictions is from Cary Millsap – “Measure once – cut twice”. He means that your assumptions are wrong, your estimates which required lots of hard work, are not much better than guesses, and you must build time into the schedule to fix all the sizing mistakes that will come up in the first week the system goes production. As Fredrick Brooks said – “plan to throw one away; you will, anyhow.” He was talking about the first version of a software project, but it seems to apply well to first capacity estimate as well.
• Incidentally, Cary Millsap also gives excellent advice and scripts on how to test that your arrival rates and service rates really match the assumed distributions. You can use his advice (chapter 9 of Oracle Performance book) to make your estimates a bit less of a random guess.
• If you are planning to run 256 concurrent users on 16 CPU system, you cannot test this by running 64 concurrent users on 4 CPU systems.Your system contains a part that doesn’t scale linearly, and the system that performs well in the tiny QA environment will be a disaster in production. This is the kind of catastrophes that you only need to experience once. Since buying another 16 CPU server for QA is out of question, you have two options here.  One is to have 4 completely separate 4-CPU-64-users environments in production. The other is to do load testing in production. It is scary, but it can be done safely if you find someone who knows that he is doing.

News from NoCOUG January 23, 2009

Some updates regarding my favorite user group.

1. Our next conference is at February 12 in Oracle’s location at Redwood Shores. We’ll have keynote and two presentations by Tom Kyte! This doesn’t happen often and I hope you won’t miss it.
   I’ll also give a presentation, but since it is parallel with one of Tom’s sessions, I won’t be surprised to find myself speaking to a very empty room.
2. If you live in North California, enjoy learning about Oracle technologies and did not yet register for next year’s NoCoug membership, you should definitely do so this month. NoCoug membership rates and conference fees will go up starting Feb 1st, so you can save real money by joining now.
3. NoCoug members get special discount at HotSos. The discount is actually higher than the NoCoug membership fee, so if you plan to attend HoSos, it will be absurd not to join NoCoug.
4. I created a facebook group for NoCoug, you can join to recieve updates about our activities.
5. After half year of volunteering at NoCoug, I finally joined the NoCoug board. I was voted the training day coordinator. Wish me luck

Latches, Spinning and Queues January 20, 2009

You know that you care a lot about a topic, if you find yourself thinking about it again and again, each time hoping to gain enough insights to stop this cycle.

Turns out, I care a lot about what my CPUs are doing. Last time I came up with the epiphany that 100% CPU utilization is a bad idea. During the discussion that followed, Jonathan Lewis and Noons took the time to explain to me the difference between waiting and spinning.

The topic came up again as I’m digging for the worse ways concurrency can go wrong.

Concurrency becomes interesting when the concurrent processes attempt to access shared resources, and since Oracle has shared memory, the shared resources tend to be areas in the memory.

We are in 11g now, so we have 3 Oracle ways to protect memory structures – Locks, latches and mutexes (Oracle mutexes, which should not be confused with OS mutexes.). Below, I’ll summarize the main differences between them. Nearly everything I wrote (and a lot more including cool examples) is covered by Tom Kyte’s Expert Oracle Database Architecture book. I’m just summarizing the importnat points below for my (and your) convinience.

When you read about latches, the first thing you hear is that “Latches are lightweight locks”. Lightweight in this case means “Takes less bits in memory”. Why do we care about our locking structures being small? Small memory footprint of the locking mechanism will translate to faster checks and changes to it. Latches are smaller than locks, and the new 10g mutexes are even smaller than latches.

Locks work by queueing. One process holds the lock for a resource, everyone else who tries to access the lock queues up and goes to sleep (i.e. off the CPU). When the current process finishes, the next in line becomes runnable and now owns the lock on the resource. Queuing is nice, because we have a bunch of queueing theory that lets us predict response times, and waits and such. It is also nice, because while Oracle manages the locks and queues it gives us tons of information about who is blocking and who is waiting. And as one last nice, while all those processes are waiting for locks, they are not using CPU, nor represent any cpu scheduling overhead.

Latches work by spinning (mostly). Think of a case when you know a process will need the memory structure for a very short amount of time. Do you really want to maintain queues, waste time on context switching, lose your CPU cache all for just few milliseconds of waiting? Latches exist for this reason. If a process tries to access the latch and its busy, it will keep on retrying for a while, still using the cpu. If during this “retry time” the latch became free, the process can take the latch and we are saved from the need to context switch. If it didn’t get the latch after several retries, the process goes off the CPU.

The important thing to note it that there is no queue. So there is a lot of uncertainty around when your process will finally get its latch. It is entirely possible that processes that started spinning on the latch later will get the latch first due to a fluke of luck. Because there is no queue, it seems that there is no good way to find a list of processes that are waiting for a latch (maybe by looking at statistics and wait tables?). You do have good information about how many requests, misses, spins and sleeps per latch, which is very useful information.

It is interesting to see how Oracle attempts to prevent the situation where a process waits forever for a latch, and keeps missing it because newer processes keep snatching the latch away as soon as it is freed. When reading about “latch free” wait events, the documentation says: ” The wait time increases exponentially and does not include spinning on the latch (active waiting). The maximum wait time also depends on the number of latches that the process is holding. There is an incremental wait of up to 2 seconds.” It is nearly the same mechanism ethernet uses to avoid machines starving for network connections (“truncated binary exponential backoff“) . Incrementally increasing the wait times reduces the probability of collision.

Mutexes are best covered by Tanel Poder.  They are even smaller and faster to take than latches, they also work as a cursor pin (signifying shared or exclusive ownership of a cursor), and they give you even less information about who is waiting for what and for how long. You have information about sleep times, but not number of requests and misses.

First Encounter with Big Corporate January 16, 2009

My friends were teasing me for working in a very large company, and how we have all those “all hands meetings” with hundreds of people participating from all over the world. This reminded me of an old story that I want to share.

This happened over five years ago. I was still an application developer at the time. The customer was a huge telephony company, from an exotic country. The project was to move about 250G of data from our database to their database, and then connect it to an application over in the customer’s data center. I was on the project as the application expert. I would be working with special tools developed for this migration, and with the DBAs on the customer side. The main challenge for this project was that we were working under very tight deadlines.

Obviously the customer was warned about the amounts of data involved. I also explained that we will not be doing direct loading, but bulk inserts. These generate redo, and they must prepare for the amounts of redo generated. I was very proud that although I was not (yet) a DBA, I could already explain about redo

Anyway, we started the project by creating the user, and then ran some scripts to create the empty segments. Later we will load the data into them. Our 250G of data was not uniformly distributed between the 200 tables in the schema. We actually had less than 10 very large tables, and large amount of smaller tables and a significant amount of empty tables. Half way through the object creation our tablespace ran out of space. Anticipating large amounts of data, someone configured HUGE extents. OK, these things happen, lets fix that and try again. We need to get going fast, loading the data was expected to take about 24 hours.

At around 12pm in my timezone, which was around 2am for the customer, their database crashed. Out of space of archive logs. I called their DBAs one after another, leaving messages, but didn’t manage to catch (=wake up) anyone. This was surprising, the DBAs I worked with in my company used to wake up at any hour.
6 hours later, one of the DBAs called me back. I told him that his database is down, was done for the last 6 hours, and this is holding up our urgent data loading project.

His response: “Oh, this is really bad. I must call a meeting to discuss this”.

Two days later the DB was up and running and I could continue the data migration. I love the whooshing sounds deadlines make as they pass by.

At that time I was horrified at their response, becuase I knew that when our servers crash, our DBAs leaped to save it, they did not call any meetings. Now I have some perspective from the DBA side of things and I still don’t get it. We have procedures on how to deal with a DB that ran out of redo space (it is relatively common disaster), and these procedures do not include any meetings.

—————————-

Kevin Closson likes my blog! This makes me very happy, not just because it drives hoards of readers my way (hey everyone! hope you like it here!), but also because Kevin’s blog is the very first Oracle blog I started reading regularly. Kevin is one of the people I most admire in this field. His knowledge of OS, network, storage and hardware is unbelievable. I’ve always been more interested in how stuff actually works than in how to do things and Kevin’s blog is just full of this kind of knowledge.

Copying Schemas? Don’t Forget the Charset! January 13, 2009

As usual on Wednsdays, we refresh the development schemas with data from production. Thursday morning, the users complained that one of their queries fail with:

ORA-600: [kafspa:columnBuffer2], [4001], [4000]

According to our good friends at Metalink, this means that we have 4001 characters in varchar 4000 field. cool! But how did they get in there?

Ah, maybe its a good time to mention that production uses WE8ISO8850P1 charset while the development schema is on a database that uses UTF8. Not brilliant. Even less brilliant is assuming, as I did, that since WE8ISO8850P1 is a subset of UTF8, I can just export and import and everything will be fine.  I assumed that because for the last 2 years we did just that and everything was fine. Turned out that we were lucky.

Oracle support found the segment, file, block and row where the problem occurred from my trace files (unfortunately they did not tell me how they did that). I went through a bit of trial and error to find the correct column (it had to be a table with over 20 varchar 4000 columns). Then I used the primary key of that row to find the right data in production (remember that I couldn’t query that row in development without getting ORA-600), removed few chars and reinserted it into development.

This solved the ORA-600. But what caused it anyway?

I took a long look at all 4000 characters of original data.  One of them was ‘¿’. Its decimal value is 191 in ASCII, but 49855 in UTF8. 49855 takes two bytes while 191 takes only one. I had no idea this could happen – I thought all ASCII chars retained their original value in UTF8. I also learned that when you say varchar (4000 char) it actually means (4000 bytes), so its a bit misleading.

So, import converted one character from one byte to two bytes, in a field that already had 4000 bytes (but should have had 4000 chars), and in the process corrupted my data. Isn’t this a bug?

At this point I did what I should have done few days ago – read what the documentation says about character set migration.  And the doc says:

“The Export and Import utilities can convert character sets from the original database character set to the new database character set. However, character set conversions can sometimes cause data loss or data corruption.”

and also:

“In most cases, a full export and import is recommended to properly convert all data to a new character set. It is important to be aware of data truncation issues, because columns with character datatypes may need to be extended before the import to handle an increase in size.”

Well, I still think that ORA-600 should have not happen, and as the doc says, the field should have been truncuated. However, I can’t complain, I should have been warned that data loss and corruption may happen.

This is a good reminder that things that bite you are the things you think you know when you don’t. I was so sure that moving from ISO8850 to UTF8 is safe, that I didn’t even bother to read the doc.

Save a DB – Practice Restore Today January 9, 2009

Tom Kyte published his new year resolutions, and his first one is “Practice restore every month”. According to Tom, practicing restore on a regular basis is the best way to avoid making mistakes on restore, which is something DBAs can’t afford. I agree, and I have few tips for restore practicers among you.

1. Don’t do it on production. OK, this one is trivial. What I mean is that you can’t really practice restore  on your private “fun and games” DB, because it is likely to be very different than the real ones. Less data usually, and probably it is not connected to the Netapp either.
   We practice our recovery on our staging environment which is a copy of our production, but this means we have to schedule our practices to times that no one is using the staging for their own tests. QA databases are also fun to practice on, in previous workplace QA trashed their DB so often that I practiced recovery on an almost weekly basis.
2. You can design some of the internal procedures so you’ll have to recover all the time. For example, decide that you will create clones of existing DBs by copying files over, without shutting down the DB, and leave out a file or two for the challenge. If you can’t recover from what you made, make sure you understand why and verify that this situation can never ever occur in production. If you (like me) have to clone DBs on a somewhat regular basis, this gives you an opportunity to use the time to practice recovery without having to justify the practice to anyone.
3. Get your manager to watch the practice. This has two great benefits – one is that you get to practice in realistically stressfull situation of having a manager looking over your shoulder. The other is that when you recover in an emergency, the manager will be somewhat familiar with what you do and will ask less questions when you are trying to think.
4. By practicing recovery on realistic environments in advance you will have a good idea how long recovery should take. Try to finish each practice with a nice table saying something like  “For each 20G of lost data files, add 30 minutes to recovery, for each 6 hours of redo to apply add an hour to recover”.  Try to get the business stakeholders to sign off these numbers. If they refuse, maybe its time to think of new strategy. Maybe one involving database flashback or dataguard. In any case, when you are in a real recovery situation these numbers  will allow you to give your business a reasonably accurate estimation of how long the downtime is going to last. This is always a huge win for the DBAs and reduces the stress levels significantly.
5. Recovery is one of these things that are awfully complicated when you memorize a bunch of rules. Do I need the instance up or down? Do I need a backup of the control file? Which redo logs do I need? Do I recover until cancel, until point in time, until now? It  magically becomes very easy when you understand the idea behind those rules. Don’t remember when you need the backup control file, instead take few minutes (hours, days) to understand the idea of SCNs and how they are used in recovery. So, when you practice, make sure you understand why you do each step that you do, don’t just work off a checklist.
6. Don’t throw away the checklist. Either have a bunch of checklists ready for every scenario (my method) or write a checklist and have someone review it before starting recovery (senior DBA does that). Always work with a list. You don’t want to risk forgeting any step.
7. Don’t forget to verify the production backups themselves on a very regular basis. Nothing is worse than discovering that for some reason your backup is useless. I try to always keep a recent full  export on the side of such emergencies. I don’t think we ever had to use it, but we came very close once or twice and it was a comforting thought to know that if we can do nothing else, at least the export is there.

Concurrency at Hotsos January 7, 2009

Everyone says that the best way to go to a conference is to be a speaker. For the last 2 years I’ve been trying to go to Hotsos symposium, but I never got the time and budget for this.

So when Hotsos published a call for papers for the 2009 symposium, sending in an abstract or two with my ideas seemed to make sense. Nothing to lose, right?

I did not expect to have my abstract accepted. And now my name is up there in the speakers list, between Cary Millsap  and Chris Date. Somehow, I don’t feel like I fit in. Its been few month since I heard the news and I can still barely believe it.

Of course, now management had no choice, and I’ll get to go to HotSos and listen to terrific technical sessions from very smart people. Yay!

My  session is going to be about concurrency errors. Its a HUGE topic and it was discussed a lot in the past, so I’m working hard to find a unique and interesting angle on this, and to avoid reiterating topics that were discussed to death. My unique take on concurrency is taking classical concurrency problems from OS research, translating them to Oracle and show how they can be used to solve common issues in DB development. There will also be a fair bit of statistics and web servers thrown in because thats what I know, do and love.

I’m planning to talk a lot about testing because concurrency problems are notoriously difficult to test for. I’ll mention some statistical techniques to find concurrency problems, because this is something I didn’t see mentioned before, and I’m very happy whenever I can use my statistics education in real life.

I want to discuss lots of OS theory because so much of it applies directly to Oracle and I want everyone to benefit from the research that was done in a related field. This means talking about queuing and also about process management overheads.

I want to talk about the problems that many application servers inadvertly cause on the database side – such as allowing a user to click refresh on a large report again and again. I see these all the time.

I’ll also talk about starvation a bit, simply because I didn’t hear it discussed yet. And there is a very special case of deadlock that I’d love to talk about, if I could just get a good test case for it.

Thats quite a lot of stuff I want to talk about, and I’ll probably have to make some painfull cuts. This is after I already had to painfully cut a bunch of stuff that I decided not to talk about.

For example, deadlocks are the most well known and well researched concurrency mistake, so I’ll not spend lot of time on it. Why waste time when I can just point to Mark bobak’s presentation from HotSoS few years back (http://www.oaktable.net/userFiles.jsp)?

I’ll also have to skip talking about concurrency problems on RAC. Its a fascinating topic, but its a huge one on its own. Maybe next year? I’ll also have to skip talking about undo+redo overheads caused by many concurrent updates, and latch contentions, and hot blocks… these are all fascinating and relevant aspects that I just could not fit in.

I hope I’ll manage to pull all of these ideas into a good presentation. I hope lots of people will show up and enjoy it. I’m sure HotSoS will be an amazing conference. Its in two month, but I’m already very excited about it.

Thoughts About Management January 5, 2009

Another year gone by. I found out that I learned quite a bit about management this year. Possibly more this year than during the year I was a team lead myself. Which just goes to show that when the student is ready, the teacher appears.

1. Good managers know what is important to them and they make sure the important things are done.
2. Good managers can make performance reviews a positive experience.
3. Good managers are honest. They are straightforward. They say things as they are. Good managers often have a “we got lemons, lets make Limoncello” attitude, but they will not say that the lemons are oranges.
4. Good management is about trust and respect. This is very related to the previous point. Your manager trusts you and respects you, so he is honest, as a result you trust him and respect him, and when he says “I did everything I could for you”, you know he did.
5. Technologists tend to give more trust and respect to managers who get their hands dirty with technical work from time to time. Its not mandatory, but it helps. It is definitely important that you’ll be able to recognize good work and achievements when you see them, and similarly recognize when someone is having trouble. Another thing that helps is when your team overhear you fight for them or praise them to a third party.
6. Good managers know how to make their team members and projects visible. Everyone will talk about the amazing work their team is doing. Being a good manager seems to require some marketing skills.
7. Cool management trick: After your team worked insane hours on a critical project for few days, send them home early or tell them to take a day off. If they say that they have something that need to be done, tell them you’ll do it instead of them. This has three benefits – the team will love you, they will be refreshed and work better after their mini vacation and they’ll feel better about giving extra effort on the next big project.