REST has grown in popularity recently for a variety of reasons. Developers are attracted to the simplicity of the interfaces created. Since HTTP is such a ubiquitous protocol, developers get lightweight interoperability out of the box because most languages and platforms support both client and server interactions with their built-in HTTP support. REST also provides developers with a strong set of architectural guidelines and constraints. As developers explore these techniques, they are finding that their distributed interfaces become more decoupled, usable, and maintainable over time.
It is true that the Web and REST have progressed well without transactions. However, we believe that there are circumstances and particular applications where the use of transactions, or at least atomicity, would be beneficial. As we have evangelized REST, we have found that a frequent question is: how can application developers leverage transactions? As the movement to the Cloud (public or private) gathers momentum, these same questions arise more and more, either when cloud-based applications need to interact with clients or services outside of the Cloud or within the Cloud, where HTTP is often the only guaranteed means of communication.
These questions are often the result of having tried to do without transactions initially and found the resulting systems inadequate. Sometimes those users have come from backgrounds such as Java Enterprise Edition, where they expect such capabilities and have architected for them. Of course it could be that some of these applications were designed inappropriately and the apparent need for transactions would disappear through a careful redesign. However, this cannot account for all of these use cases.
However, you might ask: Why not use Web Services transactions? After all, WS-Transactions defines atomic and compensation based models and has demonstrated interoperability between all of the major transactions vendors. So the obvious question is why not simply use WS-Transactions? There are several reasons for this:
• The typical Web Services stack is often too large and complex. By leveraging HTTP as both a rich protocol and message format we can reduce the footprint at both the client and the server.
• The HTTP protocol already has a rich vocabulary. For instance, we use Links to convey to clients different ways in which they can interact with the transaction manager.
So how do we go about creating a RESTful transaction protocol? Understanding state and how it relates to transactions has influenced our approach to the REST transaction protocol. We have tried to ensure that the protocol embraces HATEOAS principles rather than just using HTTP as a means of conveying message protocols. For instance, if we consider the two-phase commit protocol, one way of instructing a participant to prepare and commit would be through the use of multiple URIs, such as /participant/prepare and /participant/commit, where the root of the URI (/participant) is the actual participant resource on which the protocol is ultimately operating and whose state is ultimately being changed as a result. A POST request on these URIs could then be used to trigger the relevant operation.
However, we took a different approach; one which is intimately tied to state management and which we believe is more in the HATEOAS approach. Rather than define a URI per operation, our protocol requires a single URI for each participant (as well as coordinator) and the invoker (e.g., the coordinator) requests that the participant change its state to the relevant value via PUT, e.g., to prepare a participant the coordinator would PUT the status Prepare to the URI.
As mentioned previously, working with HTTP gives us a lot of flexibility to address transactional and distributed system faults without having to resort to ad hoc approaches. For instance, attempting to DELETE any transaction will return a 403 response code. Requesting that a transaction commit may return either 200 or 202 HTTP codes (OK and Accepted, respectively). In the latter case the Location header should contain a URI upon which a GET may be performed to obtain the asynchronous transaction outcome later. If the operation fails, e.g., because a participant cannot be committed, then the protocol requires that implementations return the 409 code, i.e., Conflict. If the participant is not in the correct state for the requested operation, e.g., it receives a Prepare when it has been already been prepared, then HTTP gives us another convenient code to return: 412, i.e., Precondition Failed.
But just as with WS-Transactions, we believe that ACID semantics and specifically atomic outcomes, are not appropriate for all applications. The use of ACID transactions within a REST application can break REST principles. Fortunately we also believe that there is a solution in what are commonly referred to as extended transactions. If the transaction needs to undo then it instructs the services to perform some compensation work. This means that in a loosely coupled environment there is no retaining of locks or provisional state change for long durations. We have been working on a compensation transaction model for REST based on Sagas. At this stage the compensation protocol is still under development but the goal is to provide something that is not only a good REST citizen but also does not turn a RESTful application that uses it into one that cannot claim to be RESTful.
This is the blog site for the Narayana team. Expect postings on our transaction projects, but also on general transaction issues.
Saturday, March 12, 2011
Friday, March 11, 2011
Uncaging Cassandra
The ongoing debate between proponents of locking and multi-version concurrency control (MVCC) is almost as heated as that between supporters of vi and emacs. There is nothing fundamentally wrong with doing concurrency control in your data store using multiple reader, single writer locking. Except that multi-version concurrency control is often better.
In an MVCC system with ongoing transactions there may be several copies of a given item of data, representing its state at different points in time. A consistent read over multiple data items can be obtained by using the version of each item that most recently pre-dates the start of the transaction. In other words, the read simply ignores updates from others that occur after its transaction began. Using this system, readers never block each other, nor do they block writers.
Compared to locking, an MVCC approach places very little extra latency on reads. Instead of adding distributed communication to manage a global lock, there is just some extra data managed in the read - multiple copies of the value, from which one is selected for use according to the versioning information. Writes are a bit more involved, as they must preserve the old value and timestamp before updating the new one. So, the reduced read cost comes at the price of more storage space and slightly more activity on writes. Which, as it happens, is exactly the design philosophy on which Cassandra is built...
In most systems built using MVCC, the versioning is entirely server side and not exposed to the client. We don't currently have that luxury with Cassandra, but it does have some features we can use to layer MVCC on top of the existing storage engine. Since it's a schemaless environment, we can simply inline the versions as additional Columns in the existing row, rather than requiring distinct storage. A get becomes a get_slice and the client uses the timestamps to decide which value to use. Of course we may need to consider a more involved approach to storage if we're sharing the store with clients that are not MVCC aware, but that kind of problem is true of external locking solutions too. With the new expiring columns support in 0.7 we can also avoid doing explicit garbage collection of older values - just set the expiry to an interval longer than we expect any transaction to take.
Of course we can't use MVCC as a complete replacement for locking on Cassandra, as there is no CAS support. We're stuck with locking on write to avoid lost updates. Nevertheless, the mixed approach has got some interesting possibilities to explore. Now I just need a few extra hours in each day so that I have time to actually try it...
In an MVCC system with ongoing transactions there may be several copies of a given item of data, representing its state at different points in time. A consistent read over multiple data items can be obtained by using the version of each item that most recently pre-dates the start of the transaction. In other words, the read simply ignores updates from others that occur after its transaction began. Using this system, readers never block each other, nor do they block writers.
Compared to locking, an MVCC approach places very little extra latency on reads. Instead of adding distributed communication to manage a global lock, there is just some extra data managed in the read - multiple copies of the value, from which one is selected for use according to the versioning information. Writes are a bit more involved, as they must preserve the old value and timestamp before updating the new one. So, the reduced read cost comes at the price of more storage space and slightly more activity on writes. Which, as it happens, is exactly the design philosophy on which Cassandra is built...
In most systems built using MVCC, the versioning is entirely server side and not exposed to the client. We don't currently have that luxury with Cassandra, but it does have some features we can use to layer MVCC on top of the existing storage engine. Since it's a schemaless environment, we can simply inline the versions as additional Columns in the existing row, rather than requiring distinct storage. A get becomes a get_slice and the client uses the timestamps to decide which value to use. Of course we may need to consider a more involved approach to storage if we're sharing the store with clients that are not MVCC aware, but that kind of problem is true of external locking solutions too. With the new expiring columns support in 0.7 we can also avoid doing explicit garbage collection of older values - just set the expiry to an interval longer than we expect any transaction to take.
Of course we can't use MVCC as a complete replacement for locking on Cassandra, as there is no CAS support. We're stuck with locking on write to avoid lost updates. Nevertheless, the mixed approach has got some interesting possibilities to explore. Now I just need a few extra hours in each day so that I have time to actually try it...
Thursday, March 10, 2011
NoSQL != NoTx
The extent of support for transaction concepts in NoSQL systems is almost as diverse as the systems themselves. Some have not only full support for 'native' i.e. local transactions, but also support distributed transactions using XA. Others barely support CAS or durable write, much less any higher level constructs. This is not necessarily a bad thing, but does make life 'interesting' for those of us trying to build consistent abstractions over various systems, or to use them as components in the composition of large, reliable systems.
My current preference in NoSQL is Cassandra, which tends towards the 'no support for transactions' end of the spectrum and therefore presents a more interesting challenge than systems that come with XA already baked in.
Cassandra is architected as a BASE rather than an ACID system. In CAP terms it favours availability and partition tolerance over consistency. That's not to say there is no hope of consistency, just that you have to make some compromises if you want it.
There is durability (but don't forget to switch CommitLogSync from periodic to batch), and atomicity in so far as operations on a single row key are atomic. Batch mutates are non-atomic and there is no locking primitive so you can't do much in the way of consistency over multiple API calls.
Non of which is necessarily a problem if you're aware of it and writing your app from the ground up with those constraints in mind. In which case, lucky you. The rest of us get to endure some degree of pain, particularly when migrating, either mentally or physically, from a SQL environment.
There are several ongoing efforts to put a JPA like abstraction on top of Cassandra, thus making it readily accessible to the hordes of JPA trained Java EE programmers out there. Thus far these focus mainly on the data mapping and indexing considerations for query support, whilst avoiding or deferring the tricky transactional bits. That's not to say there is no appreciation of the looming problem, just that it seems nobody has stepped up and tackled it seriously yet.
In order to build an even semi-credible OGM façade over Cassandra or some other approximately key-value oriented store, we need support for certain transactional characteristics, of which repeatable read is perhaps the most fundamental.
The expectation of repeatable read is that if I retrieve the value for a given key twice in the same transaction, I expect it to have the same value, regardless of other users manipulating the database in the meanwhile. If I perform some form of search or index based query multiple times I expect the result set to be consistent within the transaction. If I update a value and then retrieve it, I expect to see the result of the update within the transaction even before I make a commit.
In an RDBMS it's the database engine's job to deal with this and all of them do, using mechanisms from locking to MVCC. All the ORM layer has to do is delegate the problem to the store. In a NoSQL world where the store has no such support and no plans to add any, the client has to do some additional work.
For simple key lookups the client can cache the result locally and use that copy to serve subsequent reads in the same transaction, effectively doing its own MVCC. Most ORMs do this already for performance, although they'll flush modifications and use the relational db engine to perform queries rather than compute the result over the cached copies, which avoids reimplementing large chunks of a db in the ORM but is not feasible when there is no support for it in the store layer.
The client cache approach is fine for small tx, but becomes a problem when the read size is large. Although they are arguably an anti-pattern, tx on large sets can be supported by using a backing store, perhaps the NoSQL engine itself, to store the cache copies when they overspill the available client RAM. However, the client needs some way of isolating these private copies and for rewriting queries to use them.
Alternatively, it can use an external lock manager to perform read/write locking on keys to prevent them being changed for the duration of the transaction. However, this only works where all access to the stores is going via clients that are lockmanager aware. In siloed deployments where a single app exclusively owns the data that is not unreasonable. In enterprise deployments where a single store is shared by multiple apps, each perhaps using a different client library, potentially in a different language, it gets a bit hairy.
The Cassandra community's best effort in this direction thus far is Cages, written by Dominic Williams. Cages is a Java client solution that uses ZooKeeper as a distributed lock manager. It's not a general purpose solution though, as it assumes the complete list of locks required in known in advance. That's fine for apps written to Cassandra's native usage model, where the assumption is that you've laid out your data based on knowing exactly what queries you're going to be performing.
Where you are trying to use Cassandra to support arbitrary JPA-QL style queries it's going to fall short though. The transaction systems in traditional databases allow for gradual acquisition of locks on demand over the course of multiple operations in the transaction and JPA or any other interface that supports ad-hoc querying is going to assume that support. The locking model used by Cages also assumes relatively low contention and is likely to scale poorly compared to an MVCC based solution. Fair enough - it's written by an end user to scratch their own itch, so it's simpler and less powerful than middleware written for the general case.
Whilst a good locking system allows for the provision of several transactional characteristics, it's not the only piece we need to provide full ACID behaviour. In particular, it's not going to help us with durable atomic updates over multiple keys. Nor does it address the issues of making updates of the NoSQL store atomic with respect to actions in other systems the app may be using, such as a message queue or relational databases. There is an expectation that such components support XA, allowing them to participate in distributed transactions coordinated by a JTA.
We're still a long way from being able to use Cassandra as a full member of the transactional resource ecosystem and it's going to be an interesting journey to get there, even assuming we should try. Sounds like it could be a fun trip for those who like adventures though.
My current preference in NoSQL is Cassandra, which tends towards the 'no support for transactions' end of the spectrum and therefore presents a more interesting challenge than systems that come with XA already baked in.
Cassandra is architected as a BASE rather than an ACID system. In CAP terms it favours availability and partition tolerance over consistency. That's not to say there is no hope of consistency, just that you have to make some compromises if you want it.
There is durability (but don't forget to switch CommitLogSync from periodic to batch), and atomicity in so far as operations on a single row key are atomic. Batch mutates are non-atomic and there is no locking primitive so you can't do much in the way of consistency over multiple API calls.
Non of which is necessarily a problem if you're aware of it and writing your app from the ground up with those constraints in mind. In which case, lucky you. The rest of us get to endure some degree of pain, particularly when migrating, either mentally or physically, from a SQL environment.
There are several ongoing efforts to put a JPA like abstraction on top of Cassandra, thus making it readily accessible to the hordes of JPA trained Java EE programmers out there. Thus far these focus mainly on the data mapping and indexing considerations for query support, whilst avoiding or deferring the tricky transactional bits. That's not to say there is no appreciation of the looming problem, just that it seems nobody has stepped up and tackled it seriously yet.
In order to build an even semi-credible OGM façade over Cassandra or some other approximately key-value oriented store, we need support for certain transactional characteristics, of which repeatable read is perhaps the most fundamental.
The expectation of repeatable read is that if I retrieve the value for a given key twice in the same transaction, I expect it to have the same value, regardless of other users manipulating the database in the meanwhile. If I perform some form of search or index based query multiple times I expect the result set to be consistent within the transaction. If I update a value and then retrieve it, I expect to see the result of the update within the transaction even before I make a commit.
In an RDBMS it's the database engine's job to deal with this and all of them do, using mechanisms from locking to MVCC. All the ORM layer has to do is delegate the problem to the store. In a NoSQL world where the store has no such support and no plans to add any, the client has to do some additional work.
For simple key lookups the client can cache the result locally and use that copy to serve subsequent reads in the same transaction, effectively doing its own MVCC. Most ORMs do this already for performance, although they'll flush modifications and use the relational db engine to perform queries rather than compute the result over the cached copies, which avoids reimplementing large chunks of a db in the ORM but is not feasible when there is no support for it in the store layer.
The client cache approach is fine for small tx, but becomes a problem when the read size is large. Although they are arguably an anti-pattern, tx on large sets can be supported by using a backing store, perhaps the NoSQL engine itself, to store the cache copies when they overspill the available client RAM. However, the client needs some way of isolating these private copies and for rewriting queries to use them.
Alternatively, it can use an external lock manager to perform read/write locking on keys to prevent them being changed for the duration of the transaction. However, this only works where all access to the stores is going via clients that are lockmanager aware. In siloed deployments where a single app exclusively owns the data that is not unreasonable. In enterprise deployments where a single store is shared by multiple apps, each perhaps using a different client library, potentially in a different language, it gets a bit hairy.
The Cassandra community's best effort in this direction thus far is Cages, written by Dominic Williams. Cages is a Java client solution that uses ZooKeeper as a distributed lock manager. It's not a general purpose solution though, as it assumes the complete list of locks required in known in advance. That's fine for apps written to Cassandra's native usage model, where the assumption is that you've laid out your data based on knowing exactly what queries you're going to be performing.
Where you are trying to use Cassandra to support arbitrary JPA-QL style queries it's going to fall short though. The transaction systems in traditional databases allow for gradual acquisition of locks on demand over the course of multiple operations in the transaction and JPA or any other interface that supports ad-hoc querying is going to assume that support. The locking model used by Cages also assumes relatively low contention and is likely to scale poorly compared to an MVCC based solution. Fair enough - it's written by an end user to scratch their own itch, so it's simpler and less powerful than middleware written for the general case.
Whilst a good locking system allows for the provision of several transactional characteristics, it's not the only piece we need to provide full ACID behaviour. In particular, it's not going to help us with durable atomic updates over multiple keys. Nor does it address the issues of making updates of the NoSQL store atomic with respect to actions in other systems the app may be using, such as a message queue or relational databases. There is an expectation that such components support XA, allowing them to participate in distributed transactions coordinated by a JTA.
We're still a long way from being able to use Cassandra as a full member of the transactional resource ecosystem and it's going to be an interesting journey to get there, even assuming we should try. Sounds like it could be a fun trip for those who like adventures though.
SQL != NoSQL
The new menagerie of NoSQL databases do not have the same characteristics as traditional SQL databases, much less each other. Which is kind of the point of using them in the first place.
So why are so many otherwise sane and smart people doing their best to ignore this fact? And why is the middleware community pandering to their delusions?
There is a dangerously seductive attraction in the idea that you can improve an existing system just by swapping out some component implementation for another using the same interface. A java.util.Map may abstract a Hashtable, HashMap, ConcurrentHashMap or distributed, replicated in-memory data grid like Infinispan. Choose wisely and your system works better. Choose poorly and things unravel pretty fast. It is necessary to look beyond the interface to the underlying implementation and understand the details in order to know how to drive the interface in optimal, or even correct, manner.
The JPA may abstract not only one of several ORMs, but one of an even larger number of relational database engines behind them. It may even be implemented using an OGM backed by a key-value store such as Infinispan or Cassandra. The ability to reuse existing JPA code or programming skills when migrating from relational to non-relational storage is attractive to both developers and management. The middleware community responds to this user demand with solutions like Kundera and Hibernate OGM, which developers lap up in ever increasing numbers. Unfortunately they often do this with an inadequate understanding of the underlying implementation details.
As middleware developers we are guilty of doing too good a job of abstracting away the underlying implementation detail. Many users willingly buy into this delusion, being all too keen to believe we can magically shield them from having to understand those details.
There are two approaches to dealing with this problem: Improve the abstraction so it becomes less important to understand the implementation details, and provide material to help the users understand those details in cases where they must.
These tasks are going to occupy a big chunk of my time in the future, as I shift attention towards providing transaction management capability for the new generation of cloud environments, where data is managed and manipulated in both SQL and NoSQL stores. Interesting times ahead I think.
So why are so many otherwise sane and smart people doing their best to ignore this fact? And why is the middleware community pandering to their delusions?
There is a dangerously seductive attraction in the idea that you can improve an existing system just by swapping out some component implementation for another using the same interface. A java.util.Map may abstract a Hashtable, HashMap, ConcurrentHashMap or distributed, replicated in-memory data grid like Infinispan. Choose wisely and your system works better. Choose poorly and things unravel pretty fast. It is necessary to look beyond the interface to the underlying implementation and understand the details in order to know how to drive the interface in optimal, or even correct, manner.
The JPA may abstract not only one of several ORMs, but one of an even larger number of relational database engines behind them. It may even be implemented using an OGM backed by a key-value store such as Infinispan or Cassandra. The ability to reuse existing JPA code or programming skills when migrating from relational to non-relational storage is attractive to both developers and management. The middleware community responds to this user demand with solutions like Kundera and Hibernate OGM, which developers lap up in ever increasing numbers. Unfortunately they often do this with an inadequate understanding of the underlying implementation details.
As middleware developers we are guilty of doing too good a job of abstracting away the underlying implementation detail. Many users willingly buy into this delusion, being all too keen to believe we can magically shield them from having to understand those details.
There are two approaches to dealing with this problem: Improve the abstraction so it becomes less important to understand the implementation details, and provide material to help the users understand those details in cases where they must.
These tasks are going to occupy a big chunk of my time in the future, as I shift attention towards providing transaction management capability for the new generation of cloud environments, where data is managed and manipulated in both SQL and NoSQL stores. Interesting times ahead I think.
Wednesday, March 9, 2011
Is it turned On?
Question #0 on any tech troubleshooting checklist is, as you well know, 'Is it plugged in?'. This is followed closely by question #1, 'Is it turned On?'. Sometimes I have to relearn this the hard way.
Those joining the party late will have missed yesterday's exciting episode, at the end of which the intrepid hero is left scratching his head at the failure of his Shiny New SSD to outperform his clunky HDD. Let's move the incredibly riveting plot forward a bit with some hot command line action scenes:
$ dd if=/dev/zero of=/tmp/ssd/foo bs=4k count=1000000 oflag=direct
32.9 MB/s
This sucks. Let's swap in the noop scheduler, downgrade the journalled ext3 to ext2 and change the mount to noatime:
$ dd if=/dev/zero of=/tmp/ssd/foo bs=4k count=1000000 oflag=direct
35.0 MB/s
Better, but still sucking.
$ dd if=/dev/zero of=/tmp/ssd/foo bs=8k count=500000 oflag=direct
58.2 MB/s
$ dd if=/dev/zero of=/tmp/ssd/foo bs=16k count=250000 oflag=direct
87.6 MB/s
ok, so the performance is a direct factor of the block size. Ramp the block size up high enough and we saturate the drive at over 200MB/s. But what is limiting the number of blocks we can throw at the device? The hardware spec rates it at 50000 x 4k IOPS, which would be 195MB/s . Let's throw a few more processor cores at the problem just for the hell of it:
$ dd if=/dev/zero of=/tmp/ssd/foo1 bs=4k count=1000000 oflag=direct &
$ dd if=/dev/zero of=/tmp/ssd/foo2 bs=4k count=1000000 oflag=direct &
$ dd if=/dev/zero of=/tmp/ssd/foo3 bs=4k count=1000000 oflag=direct &
$ dd if=/dev/zero of=/tmp/ssd/foo4 bs=4k count=1000000 oflag=direct &
10.5 MB/s
10.5 MB/s
10.5 MB/s
10.5 MB/s
Well, 42 > 35, but nowhere near a linear speedup. Something is fishy here. SATA should do NCQ, which would allow all four of those processes (actually up to 32) to have outstanding requests, so we should be soaking up a lot more of that lovely bandwidth.
Unless...
$ lsmod | grep libata
libata 209361 1 piix
umm, oops.
The Intel ICH10R on our P6X58D-E is running in running in legacy IDE mode, because someone didn't check the BIOS settings carefully enough when building the machine. Not that I have any clue who that may have been. No, Sir, not at all.
Ahem. Let's reboot shall we...
$ lsmod | grep libata
libata 209361 1 ahci
Right, that's better. Off we go again:
$ dd if=/dev/zero of=/tmp/ssd/foo bs=4k count=1000000 oflag=direct
76.8 MB/s
Double the speed. Not too bad for five minutes work, even if it did require walking all the way down the hall to the machine room.
$ dd if=/dev/zero of=/tmp/ssd/foo1 bs=4k count=1000000 oflag=direct &
$ dd if=/dev/zero of=/tmp/ssd/foo2 bs=4k count=1000000 oflag=direct &
34.5 MB/s
34.5 MB/s
Huh?
With libata now correctly driving the SSD with all its features supported, those concurrent processes should be getting 70+MB/s each, not sharing it. Grrr.
Oh well, let's see how the transaction system is doing shall we. It's writing a single file at a time anyhow. Since we were already running at over 36k tx/s against a theoretical max of 55k we can't expect a 2x speedup the raw dd numbers would suggest, but we should see some improvement...
30116 tx/second.
Some days it's just not worth getting out of bed.
Change request to Clebert: make the block size in the Journal a config option.
Those joining the party late will have missed yesterday's exciting episode, at the end of which the intrepid hero is left scratching his head at the failure of his Shiny New SSD to outperform his clunky HDD. Let's move the incredibly riveting plot forward a bit with some hot command line action scenes:
$ dd if=/dev/zero of=/tmp/ssd/foo bs=4k count=1000000 oflag=direct
32.9 MB/s
This sucks. Let's swap in the noop scheduler, downgrade the journalled ext3 to ext2 and change the mount to noatime:
$ dd if=/dev/zero of=/tmp/ssd/foo bs=4k count=1000000 oflag=direct
35.0 MB/s
Better, but still sucking.
$ dd if=/dev/zero of=/tmp/ssd/foo bs=8k count=500000 oflag=direct
58.2 MB/s
$ dd if=/dev/zero of=/tmp/ssd/foo bs=16k count=250000 oflag=direct
87.6 MB/s
ok, so the performance is a direct factor of the block size. Ramp the block size up high enough and we saturate the drive at over 200MB/s. But what is limiting the number of blocks we can throw at the device? The hardware spec rates it at 50000 x 4k IOPS, which would be 195MB/s . Let's throw a few more processor cores at the problem just for the hell of it:
$ dd if=/dev/zero of=/tmp/ssd/foo1 bs=4k count=1000000 oflag=direct &
$ dd if=/dev/zero of=/tmp/ssd/foo2 bs=4k count=1000000 oflag=direct &
$ dd if=/dev/zero of=/tmp/ssd/foo3 bs=4k count=1000000 oflag=direct &
$ dd if=/dev/zero of=/tmp/ssd/foo4 bs=4k count=1000000 oflag=direct &
10.5 MB/s
10.5 MB/s
10.5 MB/s
10.5 MB/s
Well, 42 > 35, but nowhere near a linear speedup. Something is fishy here. SATA should do NCQ, which would allow all four of those processes (actually up to 32) to have outstanding requests, so we should be soaking up a lot more of that lovely bandwidth.
Unless...
$ lsmod | grep libata
libata 209361 1 piix
umm, oops.
The Intel ICH10R on our P6X58D-E is running in running in legacy IDE mode, because someone didn't check the BIOS settings carefully enough when building the machine. Not that I have any clue who that may have been. No, Sir, not at all.
Ahem. Let's reboot shall we...
$ lsmod | grep libata
libata 209361 1 ahci
Right, that's better. Off we go again:
$ dd if=/dev/zero of=/tmp/ssd/foo bs=4k count=1000000 oflag=direct
76.8 MB/s
Double the speed. Not too bad for five minutes work, even if it did require walking all the way down the hall to the machine room.
$ dd if=/dev/zero of=/tmp/ssd/foo1 bs=4k count=1000000 oflag=direct &
$ dd if=/dev/zero of=/tmp/ssd/foo2 bs=4k count=1000000 oflag=direct &
34.5 MB/s
34.5 MB/s
Huh?
With libata now correctly driving the SSD with all its features supported, those concurrent processes should be getting 70+MB/s each, not sharing it. Grrr.
Oh well, let's see how the transaction system is doing shall we. It's writing a single file at a time anyhow. Since we were already running at over 36k tx/s against a theoretical max of 55k we can't expect a 2x speedup the raw dd numbers would suggest, but we should see some improvement...
30116 tx/second.
Some days it's just not worth getting out of bed.
Change request to Clebert: make the block size in the Journal a config option.
Tuesday, March 8, 2011
hardware p0rn
Like most geeks I adore shiny new tech toys. I recently built two machines to host additional virtualized slave nodes for our hudson cluster. Thanks to the drop in RAM prices I had enough budget to stuff them full (i7 based workstations, so triple channel RAM on a 6 slot board topping out at 24GB). There was even enough left over for an SSD. yay. So today I fired one up and dumped my infamous XA transaction microbenchmark onto it.
The SSD totally failed to outperform the HDD.
So I checked the disk mount points, ran some diagnostics with dd and was still left scratching my head. The test code is basically write only, that being the nature of the beast when working with transaction recovery logs. Fortunately I'd opted for an SSD with the Sandforce controller, which provides for much more symmetric read/write performance compared to some of the competition. The manufacturer specs are 285MB/s read and 275MB/s write. Let's give it a try:
$dd if=/dev/zero of=/tmp/ssd/foo bs=1M count=4000 oflag=direct
4000+0 records in
4000+0 records out
4194304000 bytes (4.2 GB) copied, 19.0998 seconds, 220 MB/s
ok, close enough. The HDD does not do so well:
$dd if=/dev/zero of=/tmp/hdd/foo bs=1M count=4000 oflag=direct
4000+0 records in
4000+0 records out
4194304000 bytes (4.2 GB) copied, 30.5214 seconds, 137 MB/s
So if I can push around 2x the data onto it, I should be able to log 2x the number of transactions per second, right? cool.
Umm, No.
25106 tx/second to HDD log.
24996 tx/second to SSD log.
hmmm.
A little bit of fiddling around with the ObjectStore provides another useful data point: a single transaction log record for this test case is a little over 600 bytes - basically two Xids (one for each XAResource) plus transaction id and overhead.
So, 25k tx/s * 600 bytes = 15MB/s give or take. Less that 1/10th of what the SSD should handle.
We know the benchmark will run at over 50k tx/s with an in-memory store, so we're definitely bottlenecked on the I/O somewhere, but it's not write bandwidth. With a conventional HDD I'd put my money on the number of physical writes (syncs/forces) a drive head can handle. High performance log stores are designed to do contiguous append to a single file to eliminate head seek latency, so it's something to do with the number of events the device can handle in series. Let's use the filesystem's native block size:
dd if=/dev/zero of=/tmp/hdd/foo bs=4k count=1000000 oflag=direct
1000000+0 records in
1000000+0 records out
4096000000 bytes (4.1 GB) copied, 139.289 seconds, 29.4 MB/s
dd if=/dev/zero of=/tmp/sdd/foo bs=4k count=1000000 oflag=direct
1000000+0 records in
1000000+0 records out
4096000000 bytes (4.1 GB) copied, 158.286 seconds, 25.9 MB/s
and there we have it - the block management is killing us.
Looks like I need to spend some time down in the native code and kernel to understand the I/O paths at work here. My feeling is that SSD technology just invalidated a lot of design assumptions that were probably a bit outdated already. SSDs don't do head seeks. The unit of parallelism is the memory bank, not the drive head. A log store designed for SSDs should probably stripe writes over multiple files for lock concurrency and not care about contiguous blocks. Unless the SSD drive firmware is written to assume and optimise for legacy HDD usage patterns. Not that a modern HDD actually does so much in the way of truly contiguous writes anyhow - there is an awful lot of abstraction between the filesystem blocks and the physical layout these days.
Even setting aside the redesign for SSD optimization it's clear there is still room for improvement here. On the HDD we should be able to trade transaction latency against batch size to reduce the number of write events and drive up the overall throughput until we saturate the drive bandwidth. On the SSD I'm not so sure we can actually saturate a properly tuned drive on this machine - the CPU can run 50k tx/s but that's only ~30MB/s of log data. Naturally a server class machine is going to have more CPU power without necessarily increasing the number of drives, but if we can retain a ratio of say one SSD to between 8-16 cores then we should be firmly in CPU bound territory. Welcome to the new era. Your design assumptions are now invalid and your transaction manager needs redesigning to be more CPU efficient. Have a nice day.
The SSD totally failed to outperform the HDD.
So I checked the disk mount points, ran some diagnostics with dd and was still left scratching my head. The test code is basically write only, that being the nature of the beast when working with transaction recovery logs. Fortunately I'd opted for an SSD with the Sandforce controller, which provides for much more symmetric read/write performance compared to some of the competition. The manufacturer specs are 285MB/s read and 275MB/s write. Let's give it a try:
$dd if=/dev/zero of=/tmp/ssd/foo bs=1M count=4000 oflag=direct
4000+0 records in
4000+0 records out
4194304000 bytes (4.2 GB) copied, 19.0998 seconds, 220 MB/s
ok, close enough. The HDD does not do so well:
$dd if=/dev/zero of=/tmp/hdd/foo bs=1M count=4000 oflag=direct
4000+0 records in
4000+0 records out
4194304000 bytes (4.2 GB) copied, 30.5214 seconds, 137 MB/s
So if I can push around 2x the data onto it, I should be able to log 2x the number of transactions per second, right? cool.
Umm, No.
25106 tx/second to HDD log.
24996 tx/second to SSD log.
hmmm.
A little bit of fiddling around with the ObjectStore provides another useful data point: a single transaction log record for this test case is a little over 600 bytes - basically two Xids (one for each XAResource) plus transaction id and overhead.
So, 25k tx/s * 600 bytes = 15MB/s give or take. Less that 1/10th of what the SSD should handle.
We know the benchmark will run at over 50k tx/s with an in-memory store, so we're definitely bottlenecked on the I/O somewhere, but it's not write bandwidth. With a conventional HDD I'd put my money on the number of physical writes (syncs/forces) a drive head can handle. High performance log stores are designed to do contiguous append to a single file to eliminate head seek latency, so it's something to do with the number of events the device can handle in series. Let's use the filesystem's native block size:
dd if=/dev/zero of=/tmp/hdd/foo bs=4k count=1000000 oflag=direct
1000000+0 records in
1000000+0 records out
4096000000 bytes (4.1 GB) copied, 139.289 seconds, 29.4 MB/s
dd if=/dev/zero of=/tmp/sdd/foo bs=4k count=1000000 oflag=direct
1000000+0 records in
1000000+0 records out
4096000000 bytes (4.1 GB) copied, 158.286 seconds, 25.9 MB/s
and there we have it - the block management is killing us.
Looks like I need to spend some time down in the native code and kernel to understand the I/O paths at work here. My feeling is that SSD technology just invalidated a lot of design assumptions that were probably a bit outdated already. SSDs don't do head seeks. The unit of parallelism is the memory bank, not the drive head. A log store designed for SSDs should probably stripe writes over multiple files for lock concurrency and not care about contiguous blocks. Unless the SSD drive firmware is written to assume and optimise for legacy HDD usage patterns. Not that a modern HDD actually does so much in the way of truly contiguous writes anyhow - there is an awful lot of abstraction between the filesystem blocks and the physical layout these days.
Even setting aside the redesign for SSD optimization it's clear there is still room for improvement here. On the HDD we should be able to trade transaction latency against batch size to reduce the number of write events and drive up the overall throughput until we saturate the drive bandwidth. On the SSD I'm not so sure we can actually saturate a properly tuned drive on this machine - the CPU can run 50k tx/s but that's only ~30MB/s of log data. Naturally a server class machine is going to have more CPU power without necessarily increasing the number of drives, but if we can retain a ratio of say one SSD to between 8-16 cores then we should be firmly in CPU bound territory. Welcome to the new era. Your design assumptions are now invalid and your transaction manager needs redesigning to be more CPU efficient. Have a nice day.
More Speed!
"You don't have to outrun the bear, you just have to outrun the guy next to you."
Nevertheless it's always a good idea to run as fast as possible - there is no telling when the guy next to you may put on a sudden burst of acceleration.
So we did some more performance improvements on JBossTS.
For transactions that involve multiple XAResources, the protocol overhead is divided between network round trips to communicate between the TM and RMs, and disks writes to create a recovery log. There are a limited number of tricks that can be done with the network I/O (issuing the prepares in parallel rather than series springs to mind), but the disk I/O is another matter.
JBossTS writes its log through an abstract storage API called the ObjectStore. There are several ObjectStore implementations, including one that uses a relational database. Most however are filesystem based. The default store is an old, reliable piece of code that has worked well for years, but recent hardware evolution has led us to question some of the design decisions.
For years now multicore chips meant the number of concurrent threads in a typical production app server deployment rising and the processor capability in general outstripping the disk I/O capability. Relatively recently SSD have rebalanced things a bit, but we still see a large number of threads (transactions) contending for relatively limited I/O capability.
Time to break out the profiler again...
For total reliability a transaction log write must be forced to disk before the transaction can proceed. No in-memory fs block buffering by the O/S, thank you. This limits the ability of the O/S and disk to batch and reorder writes for efficiency. Essentially there are a fixed number of syncs() a drive can perform per second and for small data like tx logs it's not bottlenecked on the I/O bandwidth.
The design of the current default store is such that it syncs once for each transaction. This becomes a problem when the number of transactions your CPUs and RMs can handle exceeds the number of syncs your disk array can handle. Which is pretty much what's happened. So, back to the drawing board.
Clearly what we need is some way for multiple transaction log writes to be batched into a single sync. Which in turn means putting the log records in a single file, with all the packing and garbage collection problems that entails. Then you have the thread management problems, making sure individual writes blocks until the shared sync is done. That's a lot of fairly complex code and testing. Nightmare.
So we found someone who has already done it and borrowed their implementation. Got to love this open source thing :-)
The new ObjectStore implementation is based on Clebert's brilliant Journal code from HornetQ. The same bit of code that makes persistent messaging in HornetQ so staggeringly quick.
The Journal API is not a perfect for for what we want, but nothing that can't be fixed with another layer of abstraction. One adaptor layer later and we're ready to run another microbenchmark.
First let us get a baseline by using an in-memory ObjectStore (basically a ConcurrentHashMap). Useless for production use, but helpful to establish the runtime needed to execute a basic transaction with two dummy resources and all the log serialization overhead but no actual disk write.
53843 tx/second using 400 threads.
ok, that will do for starters - thanks to lock reduction and other performance optimizations made earlier we're pretty much saturating the quad core i7 CPU. We could probably improve matters a bit by tweaking the ConcurrentHashMap lock striping, but let's move on and swap in the default ObjectStore:
1650 tx/second using 100 threads.
iowait through the roof, CPU mostly idle. dear oh dear. Look on the bright side: that means we've got a lot of scope for improvement.
Adding more threads just causes more scheduling and locking overhead - we're bottlenecked on the number of disk syncs the 2x HDD RAID-1 can handle.
Let's wheel out the secret weapon and plug in it...
20306 tx/second at 400 threads.
yup, you read that right. Don't get too excited though - you won't see that kind of performance improvement in production. We're running an empty transaction with dummy resources - no business logic and no RM communication overhead. Still, pretty sweet huh? Better buy Clebert a beer next time you see him. And one for me too of course.
And if you thought that was good...
Linux has a nifty little library for doing efficient asynchronous I/O operations. If you are running the One True Operating System and you don't mind polluting your Pure Java with a little bit of native code you can drop a .so file into LD_LIBRARY_PATH and leave the other guy to be eaten by that bear:
36491 tx/second at 400 threads.
Coming Soon to a JBossTS release near you. Enjoy.
Nevertheless it's always a good idea to run as fast as possible - there is no telling when the guy next to you may put on a sudden burst of acceleration.
So we did some more performance improvements on JBossTS.
For transactions that involve multiple XAResources, the protocol overhead is divided between network round trips to communicate between the TM and RMs, and disks writes to create a recovery log. There are a limited number of tricks that can be done with the network I/O (issuing the prepares in parallel rather than series springs to mind), but the disk I/O is another matter.
JBossTS writes its log through an abstract storage API called the ObjectStore. There are several ObjectStore implementations, including one that uses a relational database. Most however are filesystem based. The default store is an old, reliable piece of code that has worked well for years, but recent hardware evolution has led us to question some of the design decisions.
For years now multicore chips meant the number of concurrent threads in a typical production app server deployment rising and the processor capability in general outstripping the disk I/O capability. Relatively recently SSD have rebalanced things a bit, but we still see a large number of threads (transactions) contending for relatively limited I/O capability.
Time to break out the profiler again...
For total reliability a transaction log write must be forced to disk before the transaction can proceed. No in-memory fs block buffering by the O/S, thank you. This limits the ability of the O/S and disk to batch and reorder writes for efficiency. Essentially there are a fixed number of syncs() a drive can perform per second and for small data like tx logs it's not bottlenecked on the I/O bandwidth.
The design of the current default store is such that it syncs once for each transaction. This becomes a problem when the number of transactions your CPUs and RMs can handle exceeds the number of syncs your disk array can handle. Which is pretty much what's happened. So, back to the drawing board.
Clearly what we need is some way for multiple transaction log writes to be batched into a single sync. Which in turn means putting the log records in a single file, with all the packing and garbage collection problems that entails. Then you have the thread management problems, making sure individual writes blocks until the shared sync is done. That's a lot of fairly complex code and testing. Nightmare.
So we found someone who has already done it and borrowed their implementation. Got to love this open source thing :-)
The new ObjectStore implementation is based on Clebert's brilliant Journal code from HornetQ. The same bit of code that makes persistent messaging in HornetQ so staggeringly quick.
The Journal API is not a perfect for for what we want, but nothing that can't be fixed with another layer of abstraction. One adaptor layer later and we're ready to run another microbenchmark.
First let us get a baseline by using an in-memory ObjectStore (basically a ConcurrentHashMap). Useless for production use, but helpful to establish the runtime needed to execute a basic transaction with two dummy resources and all the log serialization overhead but no actual disk write.
53843 tx/second using 400 threads.
ok, that will do for starters - thanks to lock reduction and other performance optimizations made earlier we're pretty much saturating the quad core i7 CPU. We could probably improve matters a bit by tweaking the ConcurrentHashMap lock striping, but let's move on and swap in the default ObjectStore:
1650 tx/second using 100 threads.
iowait through the roof, CPU mostly idle. dear oh dear. Look on the bright side: that means we've got a lot of scope for improvement.
Adding more threads just causes more scheduling and locking overhead - we're bottlenecked on the number of disk syncs the 2x HDD RAID-1 can handle.
Let's wheel out the secret weapon and plug in it...
20306 tx/second at 400 threads.
yup, you read that right. Don't get too excited though - you won't see that kind of performance improvement in production. We're running an empty transaction with dummy resources - no business logic and no RM communication overhead. Still, pretty sweet huh? Better buy Clebert a beer next time you see him. And one for me too of course.
And if you thought that was good...
Linux has a nifty little library for doing efficient asynchronous I/O operations. If you are running the One True Operating System and you don't mind polluting your Pure Java with a little bit of native code you can drop a .so file into LD_LIBRARY_PATH and leave the other guy to be eaten by that bear:
36491 tx/second at 400 threads.
Coming Soon to a JBossTS release near you. Enjoy.
Subscribe to:
Posts (Atom)