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...
This is the blog site for the Narayana team. Expect postings on our transaction projects, but also on general transaction issues.
Friday, March 11, 2011
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.
Must Go Faster
Transaction management systems, like much other middleware, embody a very simple tradeoff: they make life easier for developers at the cost of a runtime overhead. Maximising the ease of use and minimising the overhead are things we spend a fair bit of time thinking about.
Conventional wisdom in the transaction community is that the runtime cost of a classic ACID transaction is dominated by the disk writing needed to create a log for crash recovery purposes. As with much folklore there is some truth in this, but it's not the whole story. For starters, there are some use cases where we don't need to write a log at all.
In transactions that have only one resource it's easy to optimise the 2PC protocol to a 1PC and avoid much of the overhead. But here is the snag: the design of the transaction API in Java EE does not allow for developers to communicate metadata about number of resource managers expected in the transaction ahead of time. In some cases it's not actually known, as it may depend on runtime data values. However, it's disappointing that you still need some parts of the XA protocol overhead even where the transaction is known at design time to be local (native) to a single RM.
xaresource1.start();
xaresource1.end();
xaresource1.commit();
is still three network rounds trips and one disk sync. That's a huge improvement on the eight trips and three syncs needed for a 2PC, but it's nevertheless more than the single trip and sync in the native case with
connection.commit();
Fortunately there is a workaround: define both XA and non-XA ('local-tx' in JBossAS -ds.xml terminology) datasources in the app server and use the local one wherever you know the transaction won't involve other RMs.
Perhaps one day we'll have a less clunky solution - maybe being able to define a single datasource as supporting both XA and non-XA cases, then annotating transactional methods with e.g. @OneResource or @MultiResource to tell the JCA and TM how to manage the connection. Or even being able to escalate an RM local tx to an XA one on demand rather than having to chose in advance, although that would need RM support as well as changes to the XA protocol and Java APIs. Dream On.
Even where it's running with 1PC optimization for a single RM, the transaction manager still provides benefits over the native connection based transaction management. The most critical is the ability to handle certain lifecycle events, in particular beforeCompletion(), a notification phase that allows in-memory caches such as an ORM session to be flushed to stable store and its companion afterCompletion() which allows for resource cleanup. The TM's ability to manage transaction timeouts is also important to prevent poorly written operations from locking up resources for a protracted period.
As with writing logs for 2PC recovery, the management of timeouts is one of those activities we have to do every time, even though it turns out to be required in only a tiny minority of cases. Efficiently managing the rollback of transactions that have exceeded their allotted lifetime is a seemingly trivial overhead compared to the log write and as a result the code for it received little attention until fairly recently. This is where the folklore came to bite us: conventional wisdom dictated that we should focus the performance tuning effort on the I/O paths and not worry too much about functions that just operated on in-memory structures.
WRONG.
For the reasons outlines above, in a typical app server workload there are an awful lot of transactions containing just a single resource and hence not doing a log write. D'Oh. For those use cases the overhead of the in-memory activity in the TM is actually significant. So we sat down, wrote a highly concurrent 1PC microbenchmark test scenario, put it though a profiler, shuddered and went down the pub.
When we'd recovered a bit we tuned the transaction reaper, a background process responsible for timing out transactions. By deferring much of the work as long as possible it turns out to be possible to skip it entirely for many transactions. A short lived tx does not always need to be inserted into the time ordered reaper queue - it may terminate normally long before the reaper needs to take any action. By being lazy we saved a lot of list sorting and the associated locking overhead.
As a result the recent JBossTS releases substantially outperform their predecessors in the single resource case, particularly when scaling to a large number of threads. Upgrade and Enjoy.
Next time: More Speed! Very fast I/O for 2PC logging.
Conventional wisdom in the transaction community is that the runtime cost of a classic ACID transaction is dominated by the disk writing needed to create a log for crash recovery purposes. As with much folklore there is some truth in this, but it's not the whole story. For starters, there are some use cases where we don't need to write a log at all.
In transactions that have only one resource it's easy to optimise the 2PC protocol to a 1PC and avoid much of the overhead. But here is the snag: the design of the transaction API in Java EE does not allow for developers to communicate metadata about number of resource managers expected in the transaction ahead of time. In some cases it's not actually known, as it may depend on runtime data values. However, it's disappointing that you still need some parts of the XA protocol overhead even where the transaction is known at design time to be local (native) to a single RM.
xaresource1.start();
xaresource1.end();
xaresource1.commit();
is still three network rounds trips and one disk sync. That's a huge improvement on the eight trips and three syncs needed for a 2PC, but it's nevertheless more than the single trip and sync in the native case with
connection.commit();
Fortunately there is a workaround: define both XA and non-XA ('local-tx' in JBossAS -ds.xml terminology) datasources in the app server and use the local one wherever you know the transaction won't involve other RMs.
Perhaps one day we'll have a less clunky solution - maybe being able to define a single datasource as supporting both XA and non-XA cases, then annotating transactional methods with e.g. @OneResource or @MultiResource to tell the JCA and TM how to manage the connection. Or even being able to escalate an RM local tx to an XA one on demand rather than having to chose in advance, although that would need RM support as well as changes to the XA protocol and Java APIs. Dream On.
Even where it's running with 1PC optimization for a single RM, the transaction manager still provides benefits over the native connection based transaction management. The most critical is the ability to handle certain lifecycle events, in particular beforeCompletion(), a notification phase that allows in-memory caches such as an ORM session to be flushed to stable store and its companion afterCompletion() which allows for resource cleanup. The TM's ability to manage transaction timeouts is also important to prevent poorly written operations from locking up resources for a protracted period.
As with writing logs for 2PC recovery, the management of timeouts is one of those activities we have to do every time, even though it turns out to be required in only a tiny minority of cases. Efficiently managing the rollback of transactions that have exceeded their allotted lifetime is a seemingly trivial overhead compared to the log write and as a result the code for it received little attention until fairly recently. This is where the folklore came to bite us: conventional wisdom dictated that we should focus the performance tuning effort on the I/O paths and not worry too much about functions that just operated on in-memory structures.
WRONG.
For the reasons outlines above, in a typical app server workload there are an awful lot of transactions containing just a single resource and hence not doing a log write. D'Oh. For those use cases the overhead of the in-memory activity in the TM is actually significant. So we sat down, wrote a highly concurrent 1PC microbenchmark test scenario, put it though a profiler, shuddered and went down the pub.
When we'd recovered a bit we tuned the transaction reaper, a background process responsible for timing out transactions. By deferring much of the work as long as possible it turns out to be possible to skip it entirely for many transactions. A short lived tx does not always need to be inserted into the time ordered reaper queue - it may terminate normally long before the reaper needs to take any action. By being lazy we saved a lot of list sorting and the associated locking overhead.
As a result the recent JBossTS releases substantially outperform their predecessors in the single resource case, particularly when scaling to a large number of threads. Upgrade and Enjoy.
Next time: More Speed! Very fast I/O for 2PC logging.
Subscribe to:
Posts (Atom)