Vanilla Java

Best practices for Event Sourcing

Peter K Lawrey — Wed, 28 Nov 2018 00:00:00 GMT

David Schmitz presented an excellent talk on what he sees as best practices in using Event Sourcing.

Chronicle Software has two very different event sourcing frameworks Chronicle Microservices Framework (CMF) and Chronicle Decentred. This talk is useful in highlighting how they differ with each other and other Event Sourcing solutions.

CMF is built on Chronicle Queue and is designed for low latency trading systems. Replication is typically asynchronous to minimise latency.

Chronicle Decentred is a framework for building a secure decentralised ledger e.g. a Blockchain. It focuses on high throughput rather than low latency and Byzantine Fault Tolerance.

David’s talk applies to all Event Driven systems, and up to 10 minutes into the talk it applies to Chronicle’s frameworks as well.

Re-Deliveries

He notes that ensuring exactly one delivery is hard.

CMF approach is to assume every input of significance will have an output onto a known queue. This allows the service to restart immediately after the last successfully published message. The benefit of this approach is that:

if the input message is delivered but the service dies before completion, it is reprocessed.
if the input message is processed but the output message is not written successfully, it assumes it should be reprocessed until it does.
it is assumed that any input message which has no output, has no side effects and can be replayed, or if it cannot, a dummy "success" message can be produced.

Chronicle Decentred is checkpointed on a regular basis, e.g. weekly. The state of any individual service can be recovered from this point by replaying all the events.

In both cases, events are not deleted by default and cannot be removed individually (without encryption, see below). The events are stored in files on a rolling basis and are removed when the file(s) are deleted.

Commands vs Queries

CMF and Decentred are designed to execute commands in real time. To support queries you either need to maintain a "live" query you know in advance or for ad hoc queries, maintain an external database of your choice.

Performance

This is one of the ways in which CMF and Decentred differ greatly.

In his talk, David gives an example of a service which performs 100 actions in 66 ms. This is an average latency of 0.66 ms.

CMF is designed for consistently low latency where the focus is on the worst latencies the system sees. A key measure is often the 99.9%ile latency (worst 1 in 1,000) rather than the average or typical latencies.

We recently helped a Tier 1 banking client build an Order Management System with 3 microservices where the wire to wire latency was under 20 micro-seconds 99.9% of the time for a throughput of 20,000 messages per second.

Chronicle Decentred is designed for high throughput. Each chain can process a large number of messages across a cluster of servers e.g. 50K/s to 400K/s depending on the hardware. However, the latency is the time to achieve a consensus, which might be 5 ms to 500 ms depending on the network between them.

Human-readable formats

To support schema changes, David proposes a human-readable format which makes translating different versions of Data Transfer Objects easier as your data model changes. JSON is a common choice for doing this, however, I find that is not as human-readable as YAML.

One downside of human-readable formats is that they are not as fast as binary formats, and for this reason, CMF and Decentred supports both a binary format of YAML, which can be automatically translated to YAML but is 2-3 times faster, and as lower level binary formats which are faster but not as easy to maintain.

Some advantages of YAML over JSON

more concise.
better support for complex data types.
direct support for types and comments.

Downside of YAML

more options for how to write the data.
human readability is in the eye of the beholder, making it harder to code.
a simpler spec with mroe consistent support across languages.
YAML is almost a super set of JSON but not exactlty. e.g after an attribute name you need colon-space in YAML where as a space is not required for JSON.

JSON Example from the talk

{
    "eventType": "MoneyTransfered",
    "aggredateId" : "1234",
    "iban": "DE12",
    "accountNumber": "12312312",
    "amount": 10,
    "currency": "EUR"
}

YAML Example based on the previous example.

!MoneyTransfered: {
    aggredateId : 1234,
    iban: DE12,
    accountNumber: 12312312,
    amount: 10,
    currency: EUR
}

Having a variety of serialization options available, we favour starting with the easiest to work with and optimise later once we have a working system. This allows us to identify the most performance sensitive messages which require optimisation e.g. orders and market data, and leave most messages including the more complex, but less latency sensitive messages easier to maintain e.g. static data and configuration.

Year End Procedure

David discusses Year End Procedure. In trading systems, this is usually performed daily or weekly. This can be achieved by taking a snapshot in the form of events to load at the start of the new time period. Most trading systems have a long downtime window overnight or on the weekend.

Updating events

Event-driven systems are not designed to edit an event once written. Either the event fails, in which case, a new correct event can be added, or the event is successful but incorrect, and one or more events need to be added to correct or reverse the action. There is no easy way to edit an event before it processed, by design.

It is fairly common to have a priority queue for control events, and this could be used to inject delete, cancel or correction events as long as the event modified hasn’t been processed yet.

Great care must be taken to avoid or manage any event which could be executed but cannot be reversed later.

GDPR and encrypting data.

One way to delete data without destroying the whole queue or stream is to encrypt all the data using a key relating to a user with a user-specific key. To "delete" the user you just need to delete the key. Chronicle Queue has support for a plugin to encrypt and decrypt messages as they are written and read which can be integrated with your key management.

Another approach is to anonymize the data so there is nothing the stream which identifies a user, rather this is handled by other systems.

Trying out these solutions.

Chronicle Microservices Framework is a commercial solution for which you can get an evaluation copy, you can also start by using Chronicle Queue

Chronicle Decentred is an opensource projects with some example projects available on github.

Some Java oddities

Peter K Lawrey — Tue, 04 Sep 2018 00:00:00 GMT

I was recently asked for some simple pieces of code which some unusual uses of Java.

Here are some of my favourites ;)

Stateless Singleton implementing an interface

public enum RandomStrategy implements IntSupplier {
    INSTANCE;

    @Override
    public int getAsInt() {
        return ThreadLocalRandom.current().nextInt();
    }
}

This is useful for creating multiple implementations of a strategy pattern which share an interface. E.g. I have TimeProvider with 4 implementations depending on usage.

An example of where I use this is a TimeProvider which is basically

@FunctionalInterface
 public interface TimeProvider {

     long currentTimeMillis();

     default long currentTimeMicros() {
         return currentTimeMillis() * 1000;
     }

This has multiple enum implementations which share an interface so they can be used interchangably

TimeProvider

Usage

SetTimeProvider

a set time for unit testing.

SystemTimeProvider

uses the wall clock.

UniqueMicroTimeProvider

use wall clock except for the micro-second time always increases

LinuxTimeProvider (TBD)

Uses a microsecond resolution system call

Almost final

static final int l = printNM();
static final int n = 10;
static final int m = Math.min(10, 10);
static final int o = printNM();

static int printNM() {
    System.out.println(n + " " + m); // 10 0 then 10 10
    return 5;
}

Before a variable is assigned a value it is 0, false or null unless the value is known at compile time in which case it is also inlined.

Smiley faces

int ⁀‿⁀ = 0, ⁀⁔⁀ = 1, ¢ = 2;

if (⁀‿⁀ != ⁀⁔⁀)
    System.out.println(¢);

As _ and $ are allowed characters so all continuation and currency symbols are allowed.

Getting the top bit whether int or long.

int i = -1;
long l = -1;
System.out.println("sign(i)=" + (i >> -1));
System.out.println("sign(l)=" + (l >> -1));

The shift value is masked by the lower 5 bit for int or 6 bits for long. The upshot is that a shift by -1 is either 31 or 63 depending on the type.

A Throwable for tracing only

/**
 * Throwable created purely for the purposes of reporting a stack trace.
 * 
 * This is not an Error or an Exception and is not expected to be thrown or caught.
 * 
 */
public class StackTrace extends Throwable {
    public StackTrace() {
        this(null);
    }

    public StackTrace(String message) {
        this(message, null);
    }

    public StackTrace(String message, Throwable cause) {
        super(message, cause, false, false);
    }
}

We use this for tracing where resources are allocated and/or closed to reporting on multi-threaded resource management

No ConcurrentModificationException.

The check for iterations == size happens before the modification count for CME.

List ints = new ArrayList() {{
    add(1);
    add(2);
    add(3);
}};
for (int i : ints) // no exception
    if (i == 2)
        ints.remove(i);

Wrapper pooling covers the range -128 to 127 for Byte, Short, Character, Integer and Long. (Possibly higher for Integer depending on command line options.)

Character a1 = 127, a2 = 127;
Character b1 = 128, b2 = 128;
System.out.println(a1 == a2); // true
System.out.println(b1 == b2); // false
Detected assertions are on.
boolean debug = false;
assert debug = true;
if (debug)
   System.out.println("Assertions are on");

This shows you can easily determine is assertions are on for expensive checks. Another simple approach is:

public void method() {
    assert validate();
}

private boolean validate() {
    if (expensiveCheck())
        throw new AssertionError("details");
    return true;
}

Legacy arrays on methods are allowed as easier compilers allowed this.

static int fun(int[] ints)[] { return ints; }

public static void main(String... args) {
    System.out.println(fun(new int[1]).length);
}

char and floating point

The compound assignment operator casts to the wider type and then narrows it implicitly.

char ch = '1';
ch /= 0.9;
System.out.println(ch);

int and float

Wider types don’t always have more precision. A float is wider than an int or long, but has less precision for whole numbers inside the int and long ranges.

int i = Integer.MAX_VALUE;
i += 0.0f;
System.out.println(i == Integer.MAX_VALUE);
i -= 63;
i += 0.0f;
System.out.println(i == Integer.MAX_VALUE);
i -= 64;
i += 0.0f;
System.out.println(i == Integer.MAX_VALUE);

Unknown exit code

One of the threads in your ForkJoinPool.commonPoll() will be the first to call exit.

IntStream.range(0, 128)
        .parallel()
        .forEach(System::exit);

WindowsTF

Windows treats certain file names as special devices, even if a path or file extension is provided.

C:\Users\peter>more > A.java
class Nul { }
class Con { String s = "\nHello World\n"; }
^Z

C:\Users\peter>javac A.java (1)
╩■║╛   4 
           s Ljava/lang/String;  ()V Code LineNumberTable
SourceFile A.java    
Hello World
   Con java/lang/Object                       
   #     *╖ *╡ ▒                
C:\Users\peter>dir
 Volume in drive C is OS
 Volume Serial Number is 3EB6-6BBF

 Directory of C:\Users\peter

04/09/2018  13:51              .
04/09/2018  13:51              ..
04/09/2018  13:51                62 A.java (2)
               1 File(s)             62 bytes
               2 Dir(s)  670,935,572,480 bytes free

1	Compiling the code dumps the `.class` to the screen.
2	Note: no `.class` files are written.

Reducing network latency

Peter K Lawrey — Tue, 28 Aug 2018 00:00:00 GMT

A look down the rabbit hole of reducing network latency. How latency can be measured and what you can do about it in a Java application.

Ping latency

A tool I used regularly when I was a Unix System Administrator was ping

ping -f hostname

This sends a "flood" of packets across the network. It only sends 5 per second, but it gives you an idea of the round trip latency of the network.

I have two servers which are close to each other, so I should be able to get their latencies pretty low. ping reports an average latency of 107 μs (microseconds) which seems reasonable to start with.

All these timings are for round trip time (RTT) which is the time to go from a process in one machine to a process in a second machine and back again.

Java to Java latency with new TCP connections

Creating a new connection each time you want to send a request or a message is relatively expensive, however many applications still work this way so it is useful to get an idea of the latencies this incurs.

Table 1. Using NettyEchoServer and Chronicle’s EchoReconnectingClientMain via 1 Gb line
Throughput, 1 client	Typical	99.9%ile
200/s	290 μs	510 μs
500/s	280 μs	692 μs
1000/s	260 μs	670 μs
2000/s	260 μs	1,700 μs
3500/s	300 μs	6,500 μs

At this point, I found I couldn’t run the test for as long as the machine kept running out of resources. I could have given it more, but as you will see, opening connections each time isn’t efficient even with a bit of tuning.

Using a low latency connection.

One way to improve performance is to use a low latency network card such as the Solarflare 8522-PLUS. It is a 10 Gb card designed for low latency

The ping time for this connection was 26 μs (as you will see, this is still pretty slow)

Table 2. Using NettyEchoServer and Chronicle’s EchoReconnectingClientMain over 10 Gb Solarflare
Throughput, 1 client	Typical	99.9%ile
200/s	160 μs	252 μs
500/s	150 μs	330 μs
1000/s	185 μs	360 μs
2000/s	135 μs	410 μs

This is a significant improvement without having to change the software.

Reusing connections

Reusing connections for streaming messages can achieve much higher throughputs and lower latencies.

Table 3. Using NettyEchoServer and Chronicle’s EchoClientMain via 10 Gb line
Throughput, 1 client	Typical	99.9%ile
20,000/s	21 μs	100 μs
30,000/s	23 μs	260 μs
40,000/s	31 μs	1,600 μs
50,000/s	110 μs	1,700 μs
60,000/s	na	na

The Echo Server using Netty was better than Chronicle Network for thousands of connections, but in this test, we have just one connection.

Table 4. Using Chronicle’s EchoServer2Main and EchoClientMain via 10 Gb line
Throughput, 1 client	Typical	99.9%ile
20,000/s	17 μs	71 μs
30,000/s	18 μs	84 μs
40,000/s	21 μs	110 μs
50,000/s	31 μs	205 μs
60,000/s	na	na

Lastly, to minimise latency, we use Solarflare’s onload which enables a userspace TCP driver, bypassing the kernel without having to change our Java application to use Solarflare’s library.

Table 5. Using Chronicle’s EchoServer2Main and EchoClientMain via 10 Gb line with `onload`
Throughput, 1 client	Typical	99.9%ile
20,000/s	5.6 μs	13 μs
30,000/s	5.6 μs	15 μs
40,000/s	5.6 μs	16 μs
50,000/s	5.6 μs	17 μs
60,000/s	5.6 μs	18 μs
80,000/s	5.6 μs	21 μs
100,000/s	5.6 μs	24 μs
120,000/s	5.9 μs	30 μs
150,000/s	8.9 μs	55 μs

What if the services are on the same machine?

I would recommend using a shared memory ring buffer e.g. Aeron or a durable Chronicle Queue. These solutions have lower latencies again and more consistent high percentile timings as well.

Conclusion

To reduce the latency, and increase the throughput, I suggest

Reuse connections
Use a low latency network card
Use kernel bypass/userspace drivers.
Use our networking library designed for lower latencies

For the same servers, using the same version of Java, the throughput can increase from maybe 5,000 messages per second to 150,000 messages per second, while the round trip latency can drop from 300 μs to less than 6 μs.

Looking at randomness and performance for hash codes

Peter Lawrey — Wed, 15 Aug 2018 00:00:00 GMT

In these articles, String.hashCode() is not even a little unique and Why do I this String.hashCode() is poor, I looked at how String.hashCode() might have been made better with little change at the time it was last updated (in Java 1.2). However, given the current solution has been in place for 20 years, the default behaviour is unlikely to change. Additionally, if we were to consider different a different algorithm I would prefer something much faster and more random than just changing the prime factor from 31 to 109.

How can we evaluate randomness?

One way of looking at randomness is to change the input by one bit and see how many bits change in the resulting hash. The input is first populated with random data and the resulting hashes are compared for a large sample. In this case, I took one million samples and plotted it against what you get for a Random.nextInt() call.

The ideal hash changes half of the bits on average, more than half bits changed is also a bias.

Figure 1. The randomness of the hash code for different strategies for longer inputs compared with Random all have decent outcomes

Harness to estimate the randomness distribution of a hashing strategy.

static double[] randomnessDistribution(ToIntFunction hashCode, int length) {
    double[] dist = new double[33];
    Random random = new Random(length);
    byte[] bytes = new byte[length];
    int tests = 0;
    for (int t = 0; t < 1000000; t += length) {
        for (int i = 0; i < length; i++)
            bytes[i] = (byte) (' ' + random.nextInt(96)); (1)
        int base = hashCode.applyAsInt(bytes);

        for (int i = 0; i < length; i++) {
            for (int j = 0; j < 8; j++) {
                bytes[i] ^= 1 << j;
                int val = hashCode.applyAsInt(bytes);
                int score2 = Integer.bitCount(base ^ val);
                dist[score2]++;
                tests++;
                bytes[i] ^= 1 << j;
            }
        }
    }
    for (int i = 0; i < dist.length; i++)
        dist[i] = Math.round(1000.0 * dist[i] / tests) / 10.0;
    return dist;
}

1	I assume the input is largely ASCII or positive bytes. This doesn’t change the results greatly.

Print the distribution of different strategies for charting.

for(double[] dist: new double[][] {
        randomnessDistribution(HashCodeBenchmarkMain::hashCode31, length),
        randomnessDistribution(Arrays::hashCode, length),
        randomnessDistribution(HashCodeBenchmarkMain::hashCode109, length),
        randomnessDistribution(HashCodeBenchmarkMain::nativeHashCode, length),
        randomnessDistribution(value -> ThreadLocalRandom.current().nextInt(), length)}) {
    System.out.println(Arrays.toString(dist).replaceAll("(\\[|\\])", ""));
}

Modified form of the String.hashCode() using 109 as a prime.

static int hashCode109(byte[] value) {
    if (value.length == 0) return 0;
    int h = value[0]; (1)
    for (int i = 1; i < value.length; i++) {
        h = h * 109 + value[i];
    }
    h *= 109; (2)
    return h;
}

1	On the first iteration don’t need to multiply the previous value.
2	Afterwards, multiply by the factor to improve the outcomes for short inputs.

The differences between hashing strategies are more obvious for shorter inputs.

Figure 2. Most strategies tested do well for 20-byte inputs

Figure 3. For 8-byte inputs, some strategies are not ideal

Figure 4. For 4 byte inputs, String.hashCode() and Arrays.hashCode() are poor

Figure 5. For 2 byte inputs, String.hashCode() and Arrays.hashCode() are not great

Figure 6. For 1 byte inputs, String.hashCode() and Arrays.hashCode() might be fine as the number of possible keys is small.

What is this "native" hashCode?

A technique we use to speed up the processing of bytes is to attempt to process groups of them at once i.e. 4 bytes or 8 bytes at a time. This can speed up processing by 2-4x. We also see a benefit in using a larger prime as we pass through fewer iterations.

Hashing strategy which takes 4 bytes aa time

private static final int M2 = 0x7A646E4D;

// read 4 bytes at a time from a byte[] assuming Java 9+ Compact Strings
private static int getIntFromArray(byte[] value, int i) {
    return UnsafeMemory.INSTANCE.UNSAFE.getInt(value, BYTE_ARRAY_OFFSET + i); (0)
}

public static int nativeHashCode(byte[] value) {
    long h = getIntFromArray(value, 0);
    for (int i = 4; i < value.length; i += 4)
        h = h * M2 + getIntFromArray(value, i); (1)
    h *= M2;
    return (int) h ^ (int) (h >>> 25);
}

1	assess assumes all byte[] have zero byte padding at the end and aligned to a multiple of 4 bytes.
2	in each iteration multiply by a large constant
3	agitate the results using some of the high bits

How can we measure how they perform?

Using JMH, we can benchmark how long each operation takes on average. To have reasonable coverage, the benchmark tried a number of sizes so this is the average for those sizes.

Benchmark comparing the throughput of using String.hashCode with 31 or 109 and the native hashing strategy.

Benchmark                                      Mode  Cnt   Score   Error   Units
HashCodeBenchmarkMain.String_hashCode         thrpt   25  15.586 ± 0.433  ops/us
HashCodeBenchmarkMain.String_hashCode109      thrpt   25  13.480 ± 0.147  ops/us
HashCodeBenchmarkMain.String_hashCode31       thrpt   25  16.173 ± 0.205  ops/us
HashCodeBenchmarkMain.String_native_hashCode  thrpt   25  55.547 ± 2.051  ops/us

The native implementation is around 3-4 times as it processes up to 4 bytes at a time.

The code

A maven module of code exploring how String is hashed is HERE

Conclusion

I believe it is possible to produce a hashing strategy which is both much faster and has a better hash distribution than the 20-year-old solution. Changing the JVM is impractical however having a pluggable hashing strategy for XxxxHashMap might ensure backward compatibility while providing an option for a faster solution.

Why do I think String.hashCode() is poor

Peter Lawrey — Sun, 12 Aug 2018 00:00:00 GMT

In response to an article I wrote HERE, a recent article HERE pointed out a number of things which could have been clearer in my claim that String.hashCode() is poor. What does "poor" mean to me and does it even matter?

What is the purpose of a hashcode?

A hashcode attempts to produce a number for each input, in a somewhat random and unique way. If the input already contains a significant amount of randomness the hashing strategy largely doesn’t matter. Even Integer.hashCode() works well for random (and even sequential numbers) Long strings, for example, are likely to contain a significant amount of randomness so the behaviour for a hash for long strings isn’t a good test of the hash. However, for that use case, it likely it doesn’t matter unless someone has planned a deliberate attack, in which case you have to do more than change the hashing strategy.

How might we test whether a hash code is good or not?

One approach is to score it compared to similar hashcode functions for an assumed use case. In this case, I have used words from the dictionary, selecting words of lengths 1 to 16 and estimated their collision rate in a HashMap with default settings.

HashMap manipulates the hashcode in two ways.

it agitates the hashcode to ensure the higher bits are used
it masks the hashcode by the capacity - 1 where the capacity is the number of buckets and a power of 2. A mask is used as it’s faster than division.

String.hashCode() calculates the hashCode based iterating over the characters in a String and multiplying the hashcode by 31 each time.

Is 31 a good number to use?

It is widely regarded that prime numbers are better to use for hashcodes on balance https://stackoverflow.com/questions/3613102/why-use-a-prime-number-in-hashcode

However, lets test how it compares to other moderately sizes prime numbers. In the following test I look at the percentage of collisions a HashMap is likely to have for words of length 1 to 16. I take into account that HashMap agitates the hashcode and then masks it. The size to mask is based on the default size the HashMap would be for that many keys. I give extra weight for the worst outcome.

public class Main {

    public static void main(String[] args) throws IOException {
        List words = Files.readAllLines(Paths.get("/usr/share/dict/words")); (1)
        Map> scored = IntStream.range(2, 1024).parallel() (2)
                .filter(Main::isPrime)
                .boxed()
                .collect(Collectors.groupingBy(i -> scoreFor(words, i),
                                               TreeMap::new, Collectors.toList())); (3)
        scored.entrySet().stream().forEach(System.out::println);

    }

1	Read all the words from a file.
2	Try all the primes between 2 and 1024 in parallel
3	Build a map of primes sorted by score

    private static int scoreFor(List words, int prime) {
        int score = 0;
        int max = 0;
        for (int length = 1; length < 17; length++) {
            int finalLength = length;
            List words2 = words.stream()
                                       .filter(l -> l.length() == finalLength)
                                      .collect(Collectors.toList()); (1)
            int leading = Integer.numberOfLeadingZeros(words2.size() * 10 / 7);
            int nextPowerOf2 = 1 << -leading; (2)

            Map> collect = words2.stream()
                    .collect(Collectors.groupingBy(s -> hash2(s, nextPowerOf2, prime)));
            int collisions = collect.values().stream()
                                             .mapToInt(l -> l.size() - 1)
                                             .sum(); (3)
            int perc = collisions * 100 / words2.size();
            score += perc; (4)
            max = Math.max(perc, max);
        }
        score += max; (5)
        return score;
    }

1	for all the words of a given length
2	take the next power of two (after considering a load factor of 0.7)
3	count the number of collisions
4	add the percentage
5	add the worst percentage twice.

    static int hash2(String s, int n, int prime) {
        char val[] = s.toCharArray();
        int h = 0;
        for (int i = 0; i < val.length; i++) {
            h = prime * h +  val[i];
        }
        // agitate like HashMap in Java 8.
        h ^= h >>> 16;
        // select a bucket.
        return h & (n - 1);
    }

    static boolean isPrime(long n) {
        if (n > 2 && (n & 1) == 0) return false;
        if (n > 3 && n % 3 == 0) return false;
        if (n > 5 && n % 5 == 0) return false;
        for (int i = 7, max = (int) Math.sqrt(n); i <= max; i++)
            if (n % i == 0)
                return false;
        return true;
    }
}

Not too surprisingly, 2 is the worst prime number to use for this test and has the highest score for collisions. Given that there is 26 letters in the alphabet lets assume we could have ignored prime numbers less than 26. Let’s also assume that numbers over 256 (possible values for a byte) could have been discounted. Primes over 256 don’t find scores outside the range of those we get with 26 to 256. How does each of our prime numbers rank?

297=[109]
301=[103, 173]
302=[223]
304=[29, 73, 167, 179, 211, 251]
305=[79, 101]
308=[41, 83, 151, 199]
309=[37, 47, 67, 89, 139, 239] (1)
310=[43, 97]
311=[149]
312=[163]
314=[53, 193]
316=[197]
317=[31, 131, 233] (2)
318=[61, 71, 137]
319=[107]
320=[59]
322=[229]
323=[181]
324=[113]
330=[191]
331=[241]
343=[157]
364=[227]
374=[127]

1	Median score
2	Score for 31 as a prime factor.

For this test at least, 31 is in the worst half of the possible prime numbers to use. In my initial cut, 31 was the worst number to choose, but I felt the test wouldn’t be general enough.

Isn’t there another implicit factors?

The main computation line could be written like this.

    h = (prime * h +  1 * val[i]) & 0xFFFFFFFF;

How much difference does it make to change one of these factors instead?

Trying different multipliers

Say we make the search of this nature

    h = (31 * h +  prime * val[i]) & 0xFFFFFFFF;

and you get results like this

311=[5]
312=[23, 89]
313=[3]
315=[13, 61]
316=[71, 239]
317=[1, 7, 31, 241]
....

So in this case, using 5 instead of 1 might have been better, however, this adds computational cost. What if we use 109 as the prime

297=[1, 3]
299=[5]
302=[19]
303=[11]
306=[13, 23]

Now, a multiplier of 1 is a good choice.

How about we change the use of an int to a long. This could be slower on some systems, but does it make much difference?

    static int hash2(String s, int n, int prime) {
        char val[] = s.toCharArray();
        long h = 0;
        for (int i = 0; i < val.length; i++) {
            h = prime * h + val[i];
        }
        h ^= h >>> 32;
        // agitate like HashMap in Java 8.
        h ^= h >>> 16;
        // select a bucket.
        return (int) (h & (n - 1));
    }

produces a scores like this

298=[179]
301=[109, 251]
302=[103, 173, 223]
303=[167, 211]
304=[79, 101]
305=[73, 151]
....

I couldn’t say this is any better, but it might be slower, so I would say it is best to leave it with an int calculation.

Comparing the number of collisions for a two character ASCII string

We can generate all the possible two character String and compare the number of collisions using 31 and 109 as the prime number.

public class CollisionsMain {
    public static void main(String[] args) {
        {
            Map> freqMap = IntStream.range(' ', 127)
                    .mapToObj(i -> Character.toString((char) i))
                    .flatMap(c -> IntStream.range(' ', 127)
                            .mapToObj(c2 -> c + (char) c2))
                    .collect(Collectors.groupingBy(String::hashCode));
            long collision = freqMap.values().stream().mapToInt(l -> l.size() - 1).sum();
            System.out.println("with prime = 31, there are " + collision + " collisions");
        }
        {
            Map> freqMap = IntStream.range(' ', 127)
                    .mapToObj(i -> Character.toString((char) i))
                    .flatMap(c -> IntStream.range(' ', 127)
                            .mapToObj(c2 -> c + (char) c2))
                    .collect(Collectors.groupingBy(s -> hash2(s)));
            long collision = freqMap.values().stream().mapToInt(l -> l.size() - 1).sum();
            System.out.println("with prime = 109, there are " + collision + " collisions");
        }
    }

    static int hash2(String s) {
        int h = 0;
        for (int i = 0; i < s.length(); i++) {
            h = h * 109 + s.charAt(i);
        }
        return h;
    }
}

This prints

with prime = 31, there are 5952 collisions
with prime = 109, there are 0 collisions

And for 3 character strings

with prime = 31, there are 755968 collisions
with prime = 109, there are 0 collisions

For this use case, 109 is so much better as the range of ASCII characters I am using is 32 to 126 inclusive which is a range of fewer than 109 values. Using 109 has no collisions for 4 characters either but takes to many resources to run this way.

But because String.hashCode()‘s hash space is small and it runs so fast,

There is plenty of int values to allow every 0 to 4 letter ASCII String to have a unique hashcode.

I have always found (anecdotally) that String.hashCode() manages collisions quite well for Real World Data.

I agree that in general, it does it’s job quite well and HashMap degrading to a tree instead of a list for collisions (in Java 8) mitigates this significantly.

However, let’s say that using 109 instead of 31 is 5% better, imagine how much processing power has been wasted on the millions of devices over the decades for the change of one number.

So what does a “poor” hash function look like? And what does a “good” hash function look like? And where does String.hashCode() fall on that spectrum?

I would say that in terms of prime factors that could have reasonably been chosen, it’s on the "poor" end of the scale.

Conclusion

In conclusion, I feel the String.hashCode() is poor as most prime numbers between 26 and 256 would have been a better choice than 31. The nearest prime 29 is likely to be better and 109 might be even better. A more extensive study of a range of use cases would be needed to settle on one number better in most cases.

I would favour, the hashing strategy for HashMap should be configurable (like Comparator for TreeMap)

Making blockchains simple

Peter Lawrey — Tue, 31 Jul 2018 00:00:00 GMT

One of the challenges of building blockchain solutions is testing it. Chronicle Accelerate has a framework to make adding custom transactions with the state using data-driven tests. i.e. without the need to write code.

Example: Appreciation

The following application allows participants to show appreciation for each other by giving "likes". They have a fixed number of likes to give each other each week on a use or lose it basis. Users with the most likes might get a reward on a monthly basis, which halves their likes.

The data-driven tests are available here Appreciation Give tests

setup.yaml sets up the test, giving it an initial state

openingBalance: {
  publicKey: !!binary RWUHCYzTzADL+4kJ9r90rWHBo6J/Wng5FmlXFjv8bd8=, (1)
  amount: 100.0
}
---
openingBalance: {
  publicKey: !!binary Sq1s3liIh6LkceZYP+qh6MlMRRqCNJ5Dvl9oyAiZHe8=, (2)
  amount: 10.0
}
---

1	Public key of account 1
2	Public key of account 2

in.yaml defines the messages whose outputs are tested

startBatch: {
  batchKey: !!binary RWUHCYzTzADL+4kJ9r90rWHBo6J/Wng5FmlXFjv8bd8=, (1)
  batchTimeUS: "1970-01-01T00:00:00"
}
---
give: { (2)
  publicKey: !!binary Sq1s3liIh6LkceZYP+qh6MlMRRqCNJ5Dvl9oyAiZHe8=, (3)
  amount: 20.0 (4)
}
---
endBatch: ""
---

1	Account 1
2	gives
3	Account 2
4	20.0 likes

produces an output of

output.yaml describes the extends outputs

---
to: !!binary RWUHCYzTzADL+4kJ9r90rWHBo6J/Wng5FmlXFjv8bd8= (1)
onBalance: { (2)
  publicKey: !!binary RWUHCYzTzADL+4kJ9r90rWHBo6J/Wng5FmlXFjv8bd8=,
  amount: 80.0 (3)
}
to: !!binary Sq1s3liIh6LkceZYP+qh6MlMRRqCNJ5Dvl9oyAiZHe8= (4)
onBalance: { (5)
  publicKey: !!binary Sq1s3liIh6LkceZYP+qh6MlMRRqCNJ5Dvl9oyAiZHe8=,
  amount: 30.0 (6)
}
---
---

1	Account 1
2	is notified that it’s balances is now
3	80.0 likes
4	Account 2
5	is notified that it’s balance is now
6	30.0 likes

The two key classes are the gateway class

VanillaAppreciationGateway.java

and the post blockchain class is

VanillaAppreciationTransactionListener.java

lost.town is a domain I use for examples and games I write.

If you would like to get updates on Chronicle Accelerate, join us on Twitter

If you would like to see how our platform can be used to build your blockchain solution Contact us on [email protected]

Publishing tens of millions of messages per second

Peter Lawrey — Mon, 30 Jul 2018 00:00:00 GMT

Welcome to our first newsletter from Chronicle giving you updates on developments at Chronicle Software plus tips and case studies around how Chronicle have helped clients to maximise value from their implementation.

Case Study

We have many examples where we have helped clients who are using our open source software to optimise their solution below is a recent example:-

We helped a client achieve a 12.5x throughput improvement for Chronicle Queue with minimal changes to their solution going from millions of messages per second to tens of millions of events per second.

A large Petrochemical company engaged us to help with performance issues they were seeing writing market data to our Chronicle Queue. The way they were using queue with an older version was limited to about 3.5 million messages per second (per queue). Rather than use more queues they needed to improve the throughput of each one. After tuning their solution and using the last version of Chronicle Queue, they were able to achieve 8.5 million messages per second from Java. What they really needed was a faster, low level way to write from C++ so we produced a bespoke solution for their use case which achieved 44 million messages per second.

This was the throughput just to write the messages and didn’t include their logic.

Commercial Update

Due to ongoing success and growth within the Chronicle business, we have grown our Commercial team recruiting 2 experienced sales and business development professionals Rob Hunt and Andrew Twigg. Rob has over 20 years experience within the financial markets, starting as a hedge fund trader he subsequently moved into software sales successfully selling to both buyside and sellside institutions. Andrew joins us from BGC where he was selling market data to financial institutions across Europe prior to that he worked in various senior sales roles within the financial markets at organisations including Thomson Reuters and Dow Jones.

Rob and Andrew in conjunction with Commercial Director Paul Hienkens are here to help you with any enquiries you may have around consulting or licensing our software solutions.

If you wish to discuss how our Chronicle Software experts can help you or wish to receive ongoing selected updates from Chronicle please contact us [email protected]

Chronicle Software were founded in 2013 by Peter Lawrey the technical architect behind our software stack, as the company has grown Peter has assembled some of the best Java engineers and subject matter experts in the industry. The company’s heritage is firmly rooted in financial services, our business experts and developers are renowned for their proven track records

String.hashCode() is not even a little unique

Peter Lawrey — Thu, 26 Jul 2018 00:00:00 GMT

Some have a misconception that a 32-bit hashCode() can be unique for even complex data. Many realise that String.hashCode() is not unique, but might not realise how bad it is. While it is true that all one character Strings have a unique hashCode, this breaks down for two character Strings.

Two character ASCII strings with common hashCodes

hashCode()

String 1

String 2

String 3

String 4

1149

1180

1211

1242

1273

1304

1335

1366

1397

1428

1459

1490

1521

1552

1583

1614

1645

1676

1707

1738

1769

1800

1831

1862

1893

1924

1955

1986

2017

2048

2079

2110

2141

2172

2203

2234

2265

2296

2327

2358

2389

2420

2451

2482

2513

2544

2575

2606

2637

2668

2699

2730

2761

2792

2823

2854

2885

2916

2947

2978

3009

3040

3071

3102

3133

3164

3195

3226

3257

3288

3319

3350

3381

3412

3443

3474

3505

3536

3567

3598

3629

3660

3691

3722

3753

3784

3815

3846

3877

3908

3939

When strings have the same hashCode and combination of them, of the same length appended together also have the same hashCode.

Three character strings with the most common hashCodes

35652

!{~

!|_

!}@

!~!

"\~

"]_

"^@

"_!

#=~

#>_

#?@

#@!

$!!

35683

!|~

!}_

!~@

"]~

"^_

"_@

"`!

#>~

#?_

#@@

#A!

$!@

$"!

35714

!}~

!~_

"^~

"__

"`@

"a!

#?~

#@_

#A@

#B!

$!_

$"@

$#!

35745

!~~

"_~

"`_

"a@

"b!

#@~

#A_

#B@

#C!

$!~

$"_

$#@

$$!

36613

"{~

"|_

"}@

"~!

#\~

#]_

#^@

#_!

$=~

$>_

$?@

$@!

%!!

36644

"|~

"}_

"~@

#]~

#^_

#_@

#`!

$>~

$?_

$@@

$A!

%!@

%"!

36675

"}~

"~_

#^~

#__

#`@

#a!

$?~

$@_

$A@

$B!

%!_

%"@

%#!

36706

"~~

#_~

#`_

#a@

#b!

$@~

$A_

$B@

$C!

%!~

%"_

%#@

%$!

37574

#{~

#|_

#}@

#~!

$\~

$]_

$^@

$_!

%=~

%>_

%?@

%@!

&!!

37605

#|~

#}_

#~@

$]~

$^_

$_@

$`!

%>~

%?_

%@@

%A!

&!@

&"!

37636

#}~

#~_

$^~

$__

$`@

$a!

%?~

%@_

%A@

%B!

&!_

&"@

&#!

37667

#~~

$_~

$`_

$a@

$b!

%@~

%A_

%B@

%C!

&!~

&"_

&#@

&$!

38535

${~

$|_

$}@

$~!

%\~

%]_

%^@

%_!

&=~

&>_

&?@

&@!

'!!

38566

$|~

$}_

$~@

%]~

%^_

%_@

%`!

&>~

&?_

&@@

&A!

'!@

'"!

38597

$}~

$~_

%^~

%__

%`@

%a!

&?~

&@_

&A@

&B!

'!_

'"@

'#!

38628

$~~

%_~

%`_

%a@

%b!

&@~

&A_

&B@

&C!

'!~

'"_

'#@

'$!

39496

%{~

%|_

%}@

%~!

&\~

&]_

&^@

&_!

'=~

'>_

'?@

'@!

(!!

39527

%|~

%}_

%~@

&]~

&^_

&_@

&`!

'>~

'?_

'@@

'A!

(!@

("!

39558

%}~

%~_

&^~

&__

&`@

&a!

'?~

'@_

'A@

'B!

(!_

("@

(#!

39589

%~~

&_~

&`_

&a@

&b!

'@~

'A_

'B@

'C!

(!~

("_

(#@

($!

40457

&{~

&|_

&}@

&~!

'\~

']_

'^@

'_!

(=~

(>_

(?@

(@!

)!!

40488

&|~

&}_

&~@

']~

'^_

'_@

'`!

(>~

(?_

(@@

(A!

)!@

)"!

40519

&}~

&~_

'^~

'__

'`@

'a!

(?~

(@_

(A@

(B!

)!_

)"@

)#!

40550

&~~

'_~

'`_

'a@

'b!

(@~

(A_

(B@

(C!

)!~

)"_

)#@

)$!

41418

'{~

'|_

'}@

'~!

(\~

(]_

(^@

(_!

)=~

)>_

)?@

)@!

*!!

41449

'|~

'}_

'~@

(]~

(^_

(_@

(`!

)>~

)?_

)@@

)A!

*!@

*"!

41480

'}~

'~_

(^~

(__

(`@

(a!

)?~

)@_

)A@

)B!

*!_

*"@

*#!

41511

'~~

(_~

(`_

(a@

(b!

)@~

)A_

)B@

)C!

*!~

*"_

*#@

*$!

42379

({~

(|_

(}@

(~!

)\~

)]_

)^@

)_!

*=~

*>_

*?@

*@!

+!!

42410

(|~

(}_

(~@

)]~

)^_

)_@

)`!

*>~

*?_

*@@

*A!

+!@

+"!

42441

(}~

(~_

)^~

)__

)`@

)a!

*?~

*@_

*A@

*B!

+!_

+"@

+#!

42472

(~~

)_~

)`_

)a@

)b!

*@~

*A_

*B@

*C!

+!~

+"_

+#@

+$!

43340

){~

)|_

)}@

)~!

*\~

*]_

*^@

*_!

+=~

+>_

+?@

+@!

,!!

43371

)|~

)}_

)~@

*]~

*^_

*_@

*`!

+>~

+?_

+@@

+A!

,!@

,"!

43402

)}~

)~_

*^~

*__

*`@

*a!

+?~

+@_

+A@

+B!

,!_

,"@

,#!

43433

)~~

*_~

*`_

*a@

*b!

+@~

+A_

+B@

+C!

,!~

,"_

,#@

,$!

44301

*{~

*|_

*}@

*~!

+\~

+]_

+^@

+_!

,=~

,>_

,?@

,@!

-!!

44332

*|~

*}_

*~@

+]~

+^_

+_@

+`!

,>~

,?_

,@@

,A!

-!@

-"!

44363

*}~

*~_

+^~

+__

+`@

+a!

,?~

,@_

,A@

,B!

-!_

-"@

-#!

44394

*~~

+_~

+`_

+a@

+b!

,@~

,A_

,B@

,C!

-!~

-"_

-#@

-$!

45262

+{~

+|_

+}@

+~!

,\~

,]_

,^@

,_!

-=~

→_

-?@

-@!

.!!

45293

+|~

+}_

+~@

,]~

,^_

,_@

,`!

→~

-?_

-@@

-A!

.!@

."!

45324

+}~

+~_

,^~

,__

,`@

,a!

-?~

-@_

-A@

-B!

.!_

."@

.#!

45355

+~~

,_~

,`_

,a@

,b!

-@~

-A_

-B@

-C!

.!~

."_

.#@

.$!

46223

,{~

,|_

,}@

,~!

-\~

-]_

-^@

-_!

.=~

.>_

.?@

.@!

/!!

46254

,|~

,}_

,~@

-]~

-^_

-_@

-`!

.>~

.?_

.@@

.A!

/!@

/"!

46285

,}~

,~_

-^~

-__

-`@

-a!

.?~

.@_

.A@

.B!

/!_

/"@

/#!

46316

,~~

-_~

-`_

-a@

-b!

.@~

.A_

.B@

.C!

/!~

/"_

/#@

/$!

47184

-{~

-|_

-}@

-~!

.\~

.]_

.^@

._!

/=~

/>_

/?@

/@!

0!!

47215

-|~

-}_

-~@

.]~

.^_

._@

.`!

/>~

/?_

/@@

/A!

0!@

0"!

47246

-}~

-~_

.^~

.__

.`@

.a!

/?~

/@_

/A@

/B!

0!_

0"@

0#!

47277

-~~

._~

.`_

.a@

.b!

/@~

/A_

/B@

/C!

0!~

0"_

0#@

0$!

48145

.{~

.|_

.}@

.~!

/\~

/]_

/^@

/_!

0=~

0>_

0?@

0@!

1!!

48176

.|~

.}_

.~@

/]~

/^_

/_@

/`!

0>~

0?_

0@@

0A!

1!@

1"!

48207

.}~

.~_

/^~

/__

/`@

/a!

0?~

0@_

0A@

0B!

1!_

1"@

1#!

48238

.~~

/_~

/`_

/a@

/b!

0@~

0A_

0B@

0C!

1!~

1"_

1#@

1$!

49106

/{~

/|_

/}@

/~!

0\~

0]_

0^@

0_!

1=~

1>_

1?@

1@!

2!!

49137

/|~

/}_

/~@

0]~

0^_

0_@

0`!

1>~

1?_

1@@

1A!

2!@

2"!

49168

/}~

/~_

0^~

0__

0`@

0a!

1?~

1@_

1A@

1B!

2!_

2"@

2#!

49199

/~~

0_~

0`_

0a@

0b!

1@~

1A_

1B@

1C!

2!~

2"_

2#@

2$!

50067

0{~

0|_

0}@

0~!

1\~

1]_

1^@

1_!

2=~

2>_

2?@

2@!

3!!

50098

0|~

0}_

0~@

1]~

1^_

1_@

1`!

2>~

2?_

2@@

2A!

3!@

3"!

50129

0}~

0~_

1^~

1__

1`@

1a!

2?~

2@_

2A@

2B!

3!_

3"@

3#!

50160

0~~

1_~

1`_

1a@

1b!

2@~

2A_

2B@

2C!

3!~

3"_

3#@

3$!

51028

1{~

1|_

1}@

1~!

2\~

2]_

2^@

2_!

3=~

3>_

3?@

3@!

4!!

51059

1|~

1}_

1~@

2]~

2^_

2_@

2`!

3>~

3?_

3@@

3A!

4!@

4"!

51090

1}~

1~_

2^~

2__

2`@

2a!

3?~

3@_

3A@

3B!

4!_

4"@

4#!

51121

1~~

2_~

2`_

2a@

2b!

3@~

3A_

3B@

3C!

4!~

4"_

4#@

4$!

51989

2{~

2|_

2}@

2~!

3\~

3]_

3^@

3_!

4=~

4>_

4?@

4@!

5!!

52020

2|~

2}_

2~@

3]~

3^_

3_@

3`!

4>~

4?_

4@@

4A!

5!@

5"!

52051

2}~

2~_

3^~

3__

3`@

3a!

4?~

4@_

4A@

4B!

5!_

5"@

5#!

52082

2~~

3_~

3`_

3a@

3b!

4@~

4A_

4B@

4C!

5!~

5"_

5#@

5$!

52950

3{~

3|_

3}@

3~!

4\~

4]_

4^@

4_!

5=~

5>_

5?@

5@!

6!!

52981

3|~

3}_

3~@

4]~

4^_

4_@

4`!

5>~

5?_

5@@

5A!

6!@

6"!

53012

3}~

3~_

4^~

4__

4`@

4a!

5?~

5@_

5A@

5B!

6!_

6"@

6#!

53043

3~~

4_~

4`_

4a@

4b!

5@~

5A_

5B@

5C!

6!~

6"_

6#@

6$!

53911

4{~

4|_

4}@

4~!

5\~

5]_

5^@

5_!

6=~

6>_

6?@

6@!

7!!

53942

4|~

4}_

4~@

5]~

5^_

5_@

5`!

6>~

6?_

6@@

6A!

7!@

7"!

53973

4}~

4~_

5^~

5__

5`@

5a!

6?~

6@_

6A@

6B!

7!_

7"@

7#!

54004

4~~

5_~

5`_

5a@

5b!

6@~

6A_

6B@

6C!

7!~

7"_

7#@

7$!

54872

5{~

5|_

5}@

5~!

6\~

6]_

6^@

6_!

7=~

7>_

7?@

7@!

8!!

54903

5|~

5}_

5~@

6]~

6^_

6_@

6`!

7>~

7?_

7@@

7A!

8!@

8"!

54934

5}~

5~_

6^~

6__

6`@

6a!

7?~

7@_

7A@

7B!

8!_

8"@

8#!

54965

5~~

6_~

6`_

6a@

6b!

7@~

7A_

7B@

7C!

8!~

8"_

8#@

8$!

55833

6{~

6|_

6}@

6~!

7\~

7]_

7^@

7_!

8=~

8>_

8?@

8@!

9!!

55864

6|~

6}_

6~@

7]~

7^_

7_@

7`!

8>~

8?_

8@@

8A!

9!@

9"!

55895

6}~

6~_

7^~

7__

7`@

7a!

8?~

8@_

8A@

8B!

9!_

9"@

9#!

55926

6~~

7_~

7`_

7a@

7b!

8@~

8A_

8B@

8C!

9!~

9"_

9#@

9$!

56794

7{~

7|_

7}@

7~!

8\~

8]_

8^@

8_!

9=~

9>_

9?@

9@!

:!!

56825

7|~

7}_

7~@

8]~

8^_

8_@

8`!

9>~

9?_

9@@

9A!

:!@

:"!

56856

7}~

7~_

8^~

8__

8`@

8a!

9?~

9@_

9A@

9B!

:!_

:"@

:#!

56887

7~~

8_~

8`_

8a@

8b!

9@~

9A_

9B@

9C!

:!~

:"_

:#@

:$!

57755

8{~

8|_

8}@

8~!

9\~

9]_

9^@

9_!

:=~

:>_

:?@

:@!

;!!

57786

8|~

8}_

8~@

9]~

9^_

9_@

9`!

:>~

:?_

:@@

:A!

;!@

;"!

57817

8}~

8~_

9^~

9__

9`@

9a!

:?~

:@_

:A@

:B!

;!_

;"@

;#!

57848

8~~

9_~

9`_

9a@

9b!

:@~

:A_

:B@

:C!

;!~

;"_

;#@

;$!

58716

9{~

9|_

9}@

9~!

:\~

:]_

:^@

:_!

;=~

;>_

;?@

;@!

58747

9|~

9}_

9~@

:]~

:^_

:_@

:`!

;>~

;?_

;@@

;A!

<"!

58778

9}~

9~_

:^~

:__

:`@

:a!

;?~

;@_

;A@

;B!

<"@

<#!

58809

9~~

:_~

:`_

:a@

:b!

;@~

;A_

;B@

;C!

<"_

<#@

<$!

59677

:{~

:|_

:}@

:~!

;\~

;]_

;^@

;_!

⇐~

<>_

<@!

=!!

59708

:|~

:}_

:~@

;]~

;^_

;_@

;`!

<>~

<@@

=!@

="!

59739

:}~

:~_

;^~

;__

;`@

;a!

<@_

=!_

="@

=#!

59770

:~~

;_~

;`_

;a@

;b!

<@~

=!~

="_

=#@

=$!

60638

;{~

;|_

;}@

;~!

<\~

<]_

<^@

<_!

==~

⇒_

=?@

=@!

>!!

60669

;|~

;}_

;~@

<]~

<^_

<_@

<`!

⇒~

=?_

=@@

=A!

>!@

>"!

60700

;}~

;~_

<^~

<__

<`@

=?~

=@_

=A@

=B!

>!_

>"@

>#!

60731

;~~

<_~

<`_

=@~

=A_

=B@

=C!

>!~

>"_

>#@

>$!

61599

<{~

<|_

<}@

<~!

=\~

=]_

=^@

=_!

>=~

>>_

>?@

>@!

?!!

61630

<|~

<}_

<~@

=]~

=^_

=_@

=`!

>>~

>?_

>@@

>A!

?!@

?"!

61661

<}~

<~_

=^~

=__

=`@

=a!

>?~

>@_

>A@

>B!

?!_

?"@

?#!

61692

<~~

=_~

=`_

=a@

=b!

>@~

>A_

>B@

>C!

?!~

?"_

?#@

?$!

62560

={~

=|_

=}@

=~!

>\~

>]_

>^@

>_!

?=~

?>_

??@

?@!

@!!

62591

=|~

=}_

=~@

>]~

>^_

>_@

>`!

?>~

??_

?@@

?A!

@!@

@"!

62622

=}~

=~_

>^~

>__

>`@

>a!

??~

?@_

?A@

?B!

@!_

@"@

@#!

62653

=~~

>_~

>`_

>a@

>b!

?@~

?A_

?B@

?C!

@!~

@"_

@#@

@$!

63521

>{~

>|_

>}@

>~!

?\~

?]_

?^@

?_!

@=~

@>_

@?@

@@!

A!!

63552

>|~

>}_

>~@

?]~

?^_

?_@

?`!

@>~

@?_

@@@

@A!

A!@

A"!

63583

>}~

>~_

?^~

?__

?`@

?a!

@?~

@@_

@A@

@B!

A!_

A"@

A#!

63614

>~~

?_~

?`_

?a@

?b!

@@~

@A_

@B@

@C!

A!~

A"_

A#@

A$!

64482

?{~

?|_

?}@

?~!

@\~

@]_

@^@

@_!

A=~

A>_

A?@

A@!

B!!

64513

?|~

?}_

?~@

@]~

@^_

@_@

@`!

A>~

A?_

A@@

AA!

B!@

B"!

64544

?}~

?~_

@^~

@__

@`@

@a!

A?~

A@_

AA@

AB!

B!_

B"@

B#!

64575

?~~

@_~

@`_

@a@

@b!

A@~

AA_

AB@

AC!

B!~

B"_

B#@

B$!

65443

@{~

@|_

@}@

@~!

A\~

A]_

A^@

A_!

B=~

B>_

B?@

B@!

C!!

65474

@|~

@}_

@~@

A]~

A^_

A_@

A`!

B>~

B?_

B@@

BA!

C!@

C"!

65505

@}~

@~_

A^~

A__

A`@

Aa!

B?~

B@_

BA@

BB!

C!_

C"@

C#!

65536

@~~

A_~

A`_

Aa@

Ab!

B@~

BA_

BB@

BC!

C!~

C"_

C#@

C$!

66404

A{~

A|_

A}@

A~!

B\~

B]_

B^@

B_!

C=~

C>_

C?@

C@!

D!!

66435

A|~

A}_

A~@

B]~

B^_

B_@

B`!

C>~

C?_

C@@

CA!

D!@

D"!

66466

A}~

A~_

B^~

B__

B`@

Ba!

C?~

C@_

CA@

CB!

D!_

D"@

D#!

66497

A~~

B_~

B`_

Ba@

Bb!

C@~

CA_

CB@

CC!

D!~

D"_

D#@

D$!

67365

B{~

B|_

B}@

B~!

C\~

C]_

C^@

C_!

D=~

D>_

D?@

D@!

E!!

67396

B|~

B}_

B~@

C]~

C^_

C_@

C`!

D>~

D?_

D@@

DA!

E!@

E"!

67427

B}~

B~_

C^~

C__

C`@

Ca!

D?~

D@_

DA@

DB!

E!_

E"@

E#!

67458

B~~

C_~

C`_

Ca@

Cb!

D@~

DA_

DB@

DC!

E!~

E"_

E#@

E$!

68326

C{~

C|_

C}@

C~!

D\~

D]_

D^@

D_!

E=~

E>_

E?@

E@!

F!!

68357

C|~

C}_

C~@

D]~

D^_

D_@

D`!

E>~

E?_

E@@

EA!

F!@

F"!

68388

C}~

C~_

D^~

D__

D`@

Da!

E?~

E@_

EA@

EB!

F!_

F"@

F#!

68419

C~~

D_~

D`_

Da@

Db!

E@~

EA_

EB@

EC!

F!~

F"_

F#@

F$!

69287

D{~

D|_

D}@

D~!

E\~

E]_

E^@

E_!

F=~

F>_

F?@

F@!

G!!

69318

D|~

D}_

D~@

E]~

E^_

E_@

E`!

F>~

F?_

F@@

FA!

G!@

G"!

69349

D}~

D~_

E^~

E__

E`@

Ea!

F?~

F@_

FA@

FB!

G!_

G"@

G#!

69380

D~~

E_~

E`_

Ea@

Eb!

F@~

FA_

FB@

FC!

G!~

G"_

G#@

G$!

70248

E{~

E|_

E}@

E~!

F\~

F]_

F^@

F_!

G=~

G>_

G?@

G@!

H!!

70279

E|~

E}_

E~@

F]~

F^_

F_@

F`!

G>~

G?_

G@@

GA!

H!@

H"!

70310

E}~

E~_

F^~

F__

F`@

Fa!

G?~

G@_

GA@

GB!

H!_

H"@

H#!

70341

E~~

F_~

F`_

Fa@

Fb!

G@~

GA_

GB@

GC!

H!~

H"_

H#@

H$!

71209

F{~

F|_

F}@

F~!

G\~

G]_

G^@

G_!

H=~

H>_

H?@

H@!

I!!

71240

F|~

F}_

F~@

G]~

G^_

G_@

G`!

H>~

H?_

H@@

HA!

I!@

I"!

71271

F}~

F~_

G^~

G__

G`@

Ga!

H?~

H@_

HA@

HB!

I!_

I"@

I#!

71302

F~~

G_~

G`_

Ga@

Gb!

H@~

HA_

HB@

HC!

I!~

I"_

I#@

I$!

72170

G{~

G|_

G}@

G~!

H\~

H]_

H^@

H_!

I=~

I>_

I?@

I@!

J!!

72201

G|~

G}_

G~@

H]~

H^_

H_@

H`!

I>~

I?_

I@@

IA!

J!@

J"!

72232

G}~

G~_

H^~

H__

H`@

Ha!

I?~

I@_

IA@

IB!

J!_

J"@

J#!

72263

G~~

H_~

H`_

Ha@

Hb!

I@~

IA_

IB@

IC!

J!~

J"_

J#@

J$!

73131

H{~

H|_

H}@

H~!

I\~

I]_

I^@

I_!

J=~

J>_

J?@

J@!

K!!

73162

H|~

H}_

H~@

I]~

I^_

I_@

I`!

J>~

J?_

J@@

JA!

K!@

K"!

73193

H}~

H~_

I^~

I__

I`@

Ia!

J?~

J@_

JA@

JB!

K!_

K"@

K#!

73224

H~~

I_~

I`_

Ia@

Ib!

J@~

JA_

JB@

JC!

K!~

K"_

K#@

K$!

74092

I{~

I|_

I}@

I~!

J\~

J]_

J^@

J_!

K=~

K>_

K?@

K@!

L!!

74123

I|~

I}_

I~@

J]~

J^_

J_@

J`!

K>~

K?_

K@@

KA!

L!@

L"!

74154

I}~

I~_

J^~

J__

J`@

Ja!

K?~

K@_

KA@

KB!

L!_

L"@

L#!

74185

I~~

J_~

J`_

Ja@

Jb!

K@~

KA_

KB@

KC!

L!~

L"_

L#@

L$!

75053

J{~

J|_

J}@

J~!

K\~

K]_

K^@

K_!

L=~

L>_

L?@

L@!

M!!

75084

J|~

J}_

J~@

K]~

K^_

K_@

K`!

L>~

L?_

L@@

LA!

M!@

M"!

75115

J}~

J~_

K^~

K__

K`@

Ka!

L?~

L@_

LA@

LB!

M!_

M"@

M#!

75146

J~~

K_~

K`_

Ka@

Kb!

L@~

LA_

LB@

LC!

M!~

M"_

M#@

M$!

76014

K{~

K|_

K}@

K~!

L\~

L]_

L^@

L_!

M=~

M>_

M?@

M@!

N!!

76045

K|~

K}_

K~@

L]~

L^_

L_@

L`!

M>~

M?_

M@@

MA!

N!@

N"!

76076

K}~

K~_

L^~

L__

L`@

La!

M?~

M@_

MA@

MB!

N!_

N"@

N#!

76107

K~~

L_~

L`_

La@

Lb!

M@~

MA_

MB@

MC!

N!~

N"_

N#@

N$!

76975

L{~

L|_

L}@

L~!

M\~

M]_

M^@

M_!

N=~

N>_

N?@

N@!

O!!

77006

L|~

L}_

L~@

M]~

M^_

M_@

M`!

N>~

N?_

N@@

NA!

O!@

O"!

77037

L}~

L~_

M^~

M__

M`@

Ma!

N?~

N@_

NA@

NB!

O!_

O"@

O#!

77068

L~~

M_~

M`_

Ma@

Mb!

N@~

NA_

NB@

NC!

O!~

O"_

O#@

O$!

77936

M{~

M|_

M}@

M~!

N\~

N]_

N^@

N_!

O=~

O>_

O?@

O@!

P!!

77967

M|~

M}_

M~@

N]~

N^_

N_@

N`!

O>~

O?_

O@@

OA!

P!@

P"!

77998

M}~

M~_

N^~

N__

N`@

Na!

O?~

O@_

OA@

OB!

P!_

P"@

P#!

78029

M~~

N_~

N`_

Na@

Nb!

O@~

OA_

OB@

OC!

P!~

P"_

P#@

P$!

78897

N{~

N|_

N}@

N~!

O\~

O]_

O^@

O_!

P=~

P>_

P?@

P@!

Q!!

78928

N|~

N}_

N~@

O]~

O^_

O_@

O`!

P>~

P?_

P@@

PA!

Q!@

Q"!

78959

N}~

N~_

O^~

O__

O`@

Oa!

P?~

P@_

PA@

PB!

Q!_

Q"@

Q#!

78990

N~~

O_~

O`_

Oa@

Ob!

P@~

PA_

PB@

PC!

Q!~

Q"_

Q#@

Q$!

79858

O{~

O|_

O}@

O~!

P\~

P]_

P^@

P_!

Q=~

Q>_

Q?@

Q@!

R!!

79889

O|~

O}_

O~@

P]~

P^_

P_@

P`!

Q>~

Q?_

Q@@

QA!

R!@

R"!

79920

O}~

O~_

P^~

P__

P`@

Pa!

Q?~

Q@_

QA@

QB!

R!_

R"@

R#!

79951

O~~

P_~

P`_

Pa@

Pb!

Q@~

QA_

QB@

QC!

R!~

R"_

R#@

R$!

80819

P{~

P|_

P}@

P~!

Q\~

Q]_

Q^@

Q_!

R=~

R>_

R?@

R@!

S!!

80850

P|~

P}_

P~@

Q]~

Q^_

Q_@

Q`!

R>~

R?_

R@@

RA!

S!@

S"!

80881

P}~

P~_

Q^~

Q__

Q`@

Qa!

R?~

R@_

RA@

RB!

S!_

S"@

S#!

80912

P~~

Q_~

Q`_

Qa@

Qb!

R@~

RA_

RB@

RC!

S!~

S"_

S#@

S$!

81780

Q{~

Q|_

Q}@

Q~!

R\~

R]_

R^@

R_!

S=~

S>_

S?@

S@!

T!!

81811

Q|~

Q}_

Q~@

R]~

R^_

R_@

R`!

S>~

S?_

S@@

SA!

T!@

T"!

81842

Q}~

Q~_

R^~

R__

R`@

Ra!

S?~

S@_

SA@

SB!

T!_

T"@

T#!

81873

Q~~

R_~

R`_

Ra@

Rb!

S@~

SA_

SB@

SC!

T!~

T"_

T#@

T$!

82741

R{~

R|_

R}@

R~!

S\~

S]_

S^@

S_!

T=~

T>_

T?@

T@!

U!!

82772

R|~

R}_

R~@

S]~

S^_

S_@

S`!

T>~

T?_

T@@

TA!

U!@

U"!

82803

R}~

R~_

S^~

S__

S`@

Sa!

T?~

T@_

TA@

TB!

U!_

U"@

U#!

82834

R~~

S_~

S`_

Sa@

Sb!

T@~

TA_

TB@

TC!

U!~

U"_

U#@

U$!

83702

S{~

S|_

S}@

S~!

T\~

T]_

T^@

T_!

U=~

U>_

U?@

U@!

V!!

83733

S|~

S}_

S~@

T]~

T^_

T_@

T`!

U>~

U?_

U@@

UA!

V!@

V"!

83764

S}~

S~_

T^~

T__

T`@

Ta!

U?~

U@_

UA@

UB!

V!_

V"@

V#!

83795

S~~

T_~

T`_

Ta@

Tb!

U@~

UA_

UB@

UC!

V!~

V"_

V#@

V$!

84663

T{~

T|_

T}@

T~!

U\~

U]_

U^@

U_!

V=~

V>_

V?@

V@!

W!!

84694

T|~

T}_

T~@

U]~

U^_

U_@

U`!

V>~

V?_

V@@

VA!

W!@

W"!

84725

T}~

T~_

U^~

U__

U`@

Ua!

V?~

V@_

VA@

VB!

W!_

W"@

W#!

84756

T~~

U_~

U`_

Ua@

Ub!

V@~

VA_

VB@

VC!

W!~

W"_

W#@

W$!

85624

U{~

U|_

U}@

U~!

V\~

V]_

V^@

V_!

W=~

W>_

W?@

W@!

X!!

85655

U|~

U}_

U~@

V]~

V^_

V_@

V`!

W>~

W?_

W@@

WA!

X!@

X"!

85686

U}~

U~_

V^~

V__

V`@

Va!

W?~

W@_

WA@

WB!

X!_

X"@

X#!

85717

U~~

V_~

V`_

Va@

Vb!

W@~

WA_

WB@

WC!

X!~

X"_

X#@

X$!

86585

V{~

V|_

V}@

V~!

W\~

W]_

W^@

W_!

X=~

X>_

X?@

X@!

Y!!

86616

V|~

V}_

V~@

W]~

W^_

W_@

W`!

X>~

X?_

X@@

XA!

Y!@

Y"!

86647

V}~

V~_

W^~

W__

W`@

Wa!

X?~

X@_

XA@

XB!

Y!_

Y"@

Y#!

86678

V~~

W_~

W`_

Wa@

Wb!

X@~

XA_

XB@

XC!

Y!~

Y"_

Y#@

Y$!

87546

W{~

W|_

W}@

W~!

X\~

X]_

X^@

X_!

Y=~

Y>_

Y?@

Y@!

Z!!

87577

W|~

W}_

W~@

X]~

X^_

X_@

X`!

Y>~

Y?_

Y@@

YA!

Z!@

Z"!

87608

W}~

W~_

X^~

X__

X`@

Xa!

Y?~

Y@_

YA@

YB!

Z!_

Z"@

Z#!

87639

W~~

X_~

X`_

Xa@

Xb!

Y@~

YA_

YB@

YC!

Z!~

Z"_

Z#@

Z$!

88507

X{~

X|_

X}@

X~!

Y\~

Y]_

Y^@

Y_!

Z=~

Z>_

Z?@

Z@!

[!!

88538

X|~

X}_

X~@

Y]~

Y^_

Y_@

Y`!

Z>~

Z?_

Z@@

ZA!

[!@

["!

88569

X}~

X~_

Y^~

Y__

Y`@

Ya!

Z?~

Z@_

ZA@

ZB!

[!_

["@

[#!

88600

X~~

Y_~

Y`_

Ya@

Yb!

Z@~

ZA_

ZB@

ZC!

[!~

["_

[#@

[$!

89468

Y{~

Y|_

Y}@

Y~!

Z\~

Z]_

Z^@

Z_!

[=~

[>_

[?@

[@!

\!!

89499

Y|~

Y}_

Y~@

Z]~

Z^_

Z_@

Z`!

[>~

[?_

[@@

[A!

\!@

\"!

89530

Y}~

Y~_

Z^~

Z__

Z`@

Za!

[?~

[@_

[A@

[B!

\!_

\"@

\#!

89561

Y~~

Z_~

Z`_

Za@

Zb!

[@~

[A_

[B@

[C!

\!~

\"_

\#@

\$!

90429

Z{~

Z|_

Z}@

Z~!

[\~

[]_

[^@

[_!

\=~

\>_

\?@

\@!

]!!

90460

Z|~

Z}_

Z~@

[]~

[^_

[_@

[`!

\>~

\?_

\@@

\A!

]!@

]"!

90491

Z}~

Z~_

[^~

[__

[`@

[a!

\?~

\@_

\A@

\B!

]!_

]"@

]#!

90522

Z~~

[_~

[`_

[a@

[b!

\@~

\A_

\B@

\C!

]!~

]"_

]#@

]$!

91390

[{~

[|_

[}@

[~!

\\~

\]_

\^@

\_!

]=~

]>_

]?@

]@!

^!!

91421

[|~

[}_

[~@

\]~

\^_

\_@

\`!

]>~

]?_

]@@

]A!

^!@

^"!

91452

[}~

[~_

\^~

\__

\`@

\a!

]?~

]@_

]A@

]B!

^!_

^"@

^#!

91483

[~~

\_~

\`_

\a@

\b!

]@~

]A_

]B@

]C!

^!~

^"_

^#@

^$!

92351

\{~

\|_

\}@

\~!

]\~

]]_

]^@

]_!

^=~

^>_

^?@

^@!

_!!

92382

\|~

\}_

\~@

]]~

]^_

]_@

]`!

^>~

^?_

^@@

^A!

_!@

_"!

92413

\}~

\~_

]^~

]__

]`@

]a!

^?~

^@_

^A@

^B!

_"@

_#!

92444

\~~

]_~

]`_

]a@

]b!

^@~

^A_

^B@

^C!

_!~

_#@

_$!

93312

]{~

]|_

]}@

]~!

^\~

^]_

^^@

^_!

_=~

_?@

_@!

`!!

93343

]|~

]}_

]~@

^]~

^^_

^_@

^`!

_>~

_@@

_A!

`!@

`"!

93374

]}~

]~_

^^~

^__

^`@

^a!

_?~

_A@

_B!

`!_

`"@

`#!

93405

]~~

^_~

^`_

^a@

^b!

_@~

_B@

_C!

`!~

`"_

`#@

`$!

94273

^{~

^|_

^}@

^~!

_\~

]

_^@

__!

`=~

`>_

`?@

`@!

a!!

94304

^|~

^}_

^~@

_]~

__@

_`!

`>~

`?_

`@@

`A!

a!@

a"!

94335

^}~

^~_

_^~

_`@

_a!

`?~

`@_

`A@

`B!

a!_

a"@

a#!

94366

^~~

__~

_a@

_b!

`@~

`A_

`B@

`C!

a!~

a"_

a#@

a$!

95234

_{~

_}@

_~!

`\~

`]_

`^@

`_!

a=~

a>_

a?@

a@!

b!!

95265

_|~

}

_~@

`]~

`^_

`_@

``!

a>~

a?_

a@@

aA!

b!@

b"!

95296

_}~

`^~

`__

``@

`a!

a?~

a@_

aA@

aB!

b!_

b"@

b#!

95327

_~~

`_~

``_

`a@

`b!

a@~

aA_

aB@

aC!

b!~

b"_

b#@

b$!

96195

`{~

`|_

`}@

`~!

a\~

a]_

a^@

a_!

b=~

b>_

b?@

b@!

c!!

96226

`|~

`}_

`~@

a]~

a^_

a_@

a`!

b>~

b?_

b@@

bA!

c!@

c"!

96257

`}~

`~_

a^~

a__

a`@

aa!

b?~

b@_

bA@

bB!

c!_

c"@

c#!

96288

`~~

a_~

a`_

aa@

ab!

b@~

bA_

bB@

bC!

c!~

c"_

c#@

c$!

97156

a{~

a|_

a}@

a~!

b\~

b]_

b^@

b_!

c=~

c>_

c?@

c@!

d!!

97187

a|~

a}_

a~@

b]~

b^_

b_@

b`!

c>~

c?_

c@@

cA!

d!@

d"!

97218

a}~

a~_

b^~

b__

b`@

ba!

c?~

c@_

cA@

cB!

d!_

d"@

d#!

97249

a~~

b_~

b`_

ba@

bb!

c@~

cA_

cB@

cC!

d!~

d"_

d#@

d$!

98117

b{~

b|_

b}@

b~!

c\~

c]_

c^@

c_!

d=~

d>_

d?@

d@!

e!!

98148

b|~

b}_

b~@

c]~

c^_

c_@

c`!

d>~

d?_

d@@

dA!

e!@

e"!

98179

b}~

b~_

c^~

c__

c`@

ca!

d?~

d@_

dA@

dB!

e!_

e"@

e#!

98210

b~~

c_~

c`_

ca@

cb!

d@~

dA_

dB@

dC!

e!~

e"_

e#@

e$!

99078

c{~

c|_

c}@

c~!

d\~

d]_

d^@

d_!

e=~

e>_

e?@

e@!

f!!

99109

c|~

c}_

c~@

d]~

d^_

d_@

d`!

e>~

e?_

e@@

eA!

f!@

f"!

99140

c}~

c~_

d^~

d__

d`@

da!

e?~

e@_

eA@

eB!

f!_

f"@

f#!

99171

c~~

d_~

d`_

da@

db!

e@~

eA_

eB@

eC!

f!~

f"_

f#@

f$!

100039

d{~

d|_

d}@

d~!

e\~

e]_

e^@

e_!

f=~

f>_

f?@

f@!

g!!

100070

d|~

d}_

d~@

e]~

e^_

e_@

e`!

f>~

f?_

f@@

fA!

g!@

g"!

100101

d}~

d~_

e^~

e__

e`@

ea!

f?~

f@_

fA@

fB!

g!_

g"@

g#!

100132

d~~

e_~

e`_

ea@

eb!

f@~

fA_

fB@

fC!

g!~

g"_

g#@

g$!

101000

e{~

e|_

e}@

e~!

f\~

f]_

f^@

f_!

g=~

g>_

g?@

g@!

h!!

101031

e|~

e}_

e~@

f]~

f^_

f_@

f`!

g>~

g?_

g@@

gA!

h!@

h"!

101062

e}~

e~_

f^~

f__

f`@

fa!

g?~

g@_

gA@

gB!

h!_

h"@

h#!

101093

e~~

f_~

f`_

fa@

fb!

g@~

gA_

gB@

gC!

h!~

h"_

h#@

h$!

101961

f{~

f|_

f}@

f~!

g\~

g]_

g^@

g_!

h=~

h>_

h?@

h@!

i!!

101992

f|~

f}_

f~@

g]~

g^_

g_@

g`!

h>~

h?_

h@@

hA!

i!@

i"!

102023

f}~

f~_

g^~

g__

g`@

ga!

h?~

h@_

hA@

hB!

i!_

i"@

i#!

102054

f~~

g_~

g`_

ga@

gb!

h@~

hA_

hB@

hC!

i!~

i"_

i#@

i$!

102922

g{~

g|_

g}@

g~!

h\~

h]_

h^@

h_!

i=~

i>_

i?@

i@!

j!!

102953

g|~

g}_

g~@

h]~

h^_

h_@

h`!

i>~

i?_

i@@

iA!

j!@

j"!

102984

g}~

g~_

h^~

h__

h`@

ha!

i?~

i@_

iA@

iB!

j!_

j"@

j#!

103015

g~~

h_~

h`_

ha@

hb!

i@~

iA_

iB@

iC!

j!~

j"_

j#@

j$!

103883

h{~

h|_

h}@

h~!

i\~

i]_

i^@

i_!

j=~

j>_

j?@

j@!

k!!

103914

h|~

h}_

h~@

i]~

i^_

i_@

i`!

j>~

j?_

j@@

jA!

k!@

k"!

103945

h}~

h~_

i^~

i__

i`@

ia!

j?~

j@_

jA@

jB!

k!_

k"@

k#!

103976

h~~

i_~

i`_

ia@

ib!

j@~

jA_

jB@

jC!

k!~

k"_

k#@

k$!

104844

i{~

i|_

i}@

i~!

j\~

j]_

j^@

j_!

k=~

k>_

k?@

k@!

l!!

104875

i|~

i}_

i~@

j]~

j^_

j_@

j`!

k>~

k?_

k@@

kA!

l!@

l"!

104906

i}~

i~_

j^~

j__

j`@

ja!

k?~

k@_

kA@

kB!

l!_

l"@

l#!

104937

i~~

j_~

j`_

ja@

jb!

k@~

kA_

kB@

kC!

l!~

l"_

l#@

l$!

105805

j{~

j|_

j}@

j~!

k\~

k]_

k^@

k_!

l=~

l>_

l?@

l@!

m!!

105836

j|~

j}_

j~@

k]~

k^_

k_@

k`!

l>~

l?_

l@@

lA!

m!@

m"!

105867

j}~

j~_

k^~

k__

k`@

ka!

l?~

l@_

lA@

lB!

m!_

m"@

m#!

105898

j~~

k_~

k`_

ka@

kb!

l@~

lA_

lB@

lC!

m!~

m"_

m#@

m$!

106766

k{~

k|_

k}@

k~!

l\~

l]_

l^@

l_!

m=~

m>_

m?@

m@!

n!!

106797

k|~

k}_

k~@

l]~

l^_

l_@

l`!

m>~

m?_

m@@

mA!

n!@

n"!

106828

k}~

k~_

l^~

l__

l`@

la!

m?~

m@_

mA@

mB!

n!_

n"@

n#!

106859

k~~

l_~

l`_

la@

lb!

m@~

mA_

mB@

mC!

n!~

n"_

n#@

n$!

107727

l{~

l|_

l}@

l~!

m\~

m]_

m^@

m_!

n=~

n>_

n?@

n@!

o!!

107758

l|~

l}_

l~@

m]~

m^_

m_@

m`!

n>~

n?_

n@@

nA!

o!@

o"!

107789

l}~

l~_

m^~

m__

m`@

ma!

n?~

n@_

nA@

nB!

o!_

o"@

o#!

107820

l~~

m_~

m`_

ma@

mb!

n@~

nA_

nB@

nC!

o!~

o"_

o#@

o$!

108688

m{~

m|_

m}@

m~!

n\~

n]_

n^@

n_!

o=~

o>_

o?@

o@!

p!!

108719

m|~

m}_

m~@

n]~

n^_

n_@

n`!

o>~

o?_

o@@

oA!

p!@

p"!

108750

m}~

m~_

n^~

n__

n`@

na!

o?~

o@_

oA@

oB!

p!_

p"@

p#!

108781

m~~

n_~

n`_

na@

nb!

o@~

oA_

oB@

oC!

p!~

p"_

p#@

p$!

109649

n{~

n|_

n}@

n~!

o\~

o]_

o^@

o_!

p=~

p>_

p?@

p@!

q!!

109680

n|~

n}_

n~@

o]~

o^_

o_@

o`!

p>~

p?_

p@@

pA!

q!@

q"!

109711

n}~

n~_

o^~

o__

o`@

oa!

p?~

p@_

pA@

pB!

q!_

q"@

q#!

109742

n~~

o_~

o`_

oa@

ob!

p@~

pA_

pB@

pC!

q!~

q"_

q#@

q$!

110610

o{~

o|_

o}@

o~!

p\~

p]_

p^@

p_!

q=~

q>_

q?@

q@!

r!!

110641

o|~

o}_

o~@

p]~

p^_

p_@

p`!

q>~

q?_

q@@

qA!

r!@

r"!

110672

o}~

o~_

p^~

p__

p`@

pa!

q?~

q@_

qA@

qB!

r!_

r"@

r#!

110703

o~~

p_~

p`_

pa@

pb!

q@~

qA_

qB@

qC!

r!~

r"_

r#@

r$!

111571

p{~

p|_

p}@

p~!

q\~

q]_

q^@

q_!

r=~

r>_

r?@

r@!

s!!

111602

p|~

p}_

p~@

q]~

q^_

q_@

q`!

r>~

r?_

r@@

rA!

s!@

s"!

111633

p}~

p~_

q^~

q__

q`@

qa!

r?~

r@_

rA@

rB!

s!_

s"@

s#!

111664

p~~

q_~

q`_

qa@

qb!

r@~

rA_

rB@

rC!

s!~

s"_

s#@

s$!

112532

q{~

q|_

q}@

q~!

r\~

r]_

r^@

r_!

s=~

s>_

s?@

s@!

t!!

112563

q|~

q}_

q~@

r]~

r^_

r_@

r`!

s>~

s?_

s@@

sA!

t!@

t"!

112594

q}~

q~_

r^~

r__

r`@

ra!

s?~

s@_

sA@

sB!

t!_

t"@

t#!

112625

q~~

r_~

r`_

ra@

rb!

s@~

sA_

sB@

sC!

t!~

t"_

t#@

t$!

113493

r{~

r|_

r}@

r~!

s\~

s]_

s^@

s_!

t=~

t>_

t?@

t@!

u!!

113524

r|~

r}_

r~@

s]~

s^_

s_@

s`!

t>~

t?_

t@@

tA!

u!@

u"!

113555

r}~

r~_

s^~

s__

s`@

sa!

t?~

t@_

tA@

tB!

u!_

u"@

u#!

113586

r~~

s_~

s`_

sa@

sb!

t@~

tA_

tB@

tC!

u!~

u"_

u#@

u$!

114454

s{~

s|_

s}@

s~!

t\~

t]_

t^@

t_!

u=~

u>_

u?@

u@!

v!!

114485

s|~

s}_

s~@

t]~

t^_

t_@

t`!

u>~

u?_

u@@

uA!

v!@

v"!

114516

s}~

s~_

t^~

t__

t`@

ta!

u?~

u@_

uA@

uB!

v!_

v"@

v#!

114547

s~~

t_~

t`_

ta@

tb!

u@~

uA_

uB@

uC!

v!~

v"_

v#@

v$!

115415

t{~

t|_

t}@

t~!

u\~

u]_

u^@

u_!

v=~

v>_

v?@

v@!

w!!

115446

t|~

t}_

t~@

u]~

u^_

u_@

u`!

v>~

v?_

v@@

vA!

w!@

w"!

115477

t}~

t~_

u^~

u__

u`@

ua!

v?~

v@_

vA@

vB!

w!_

w"@

w#!

115508

t~~

u_~

u`_

ua@

ub!

v@~

vA_

vB@

vC!

w!~

w"_

w#@

w$!

116376

u{~

u|_

u}@

u~!

v\~

v]_

v^@

v_!

w=~

w>_

w?@

w@!

x!!

116407

u|~

u}_

u~@

v]~

v^_

v_@

v`!

w>~

w?_

w@@

wA!

x!@

x"!

116438

u}~

u~_

v^~

v__

v`@

va!

w?~

w@_

wA@

wB!

x!_

x"@

x#!

116469

u~~

v_~

v`_

va@

vb!

w@~

wA_

wB@

wC!

x!~

x"_

x#@

x$!

117337

v{~

v|_

v}@

v~!

w\~

w]_

w^@

w_!

x=~

x>_

x?@

x@!

y!!

117368

v|~

v}_

v~@

w]~

w^_

w_@

w`!

x>~

x?_

x@@

xA!

y!@

y"!

117399

v}~

v~_

w^~

w__

w`@

wa!

x?~

x@_

xA@

xB!

y!_

y"@

y#!

117430

v~~

w_~

w`_

wa@

wb!

x@~

xA_

xB@

xC!

y!~

y"_

y#@

y$!

118298

w{~

w|_

w}@

w~!

x\~

x]_

x^@

x_!

y=~

y>_

y?@

y@!

z!!

118329

w|~

w}_

w~@

x]~

x^_

x_@

x`!

y>~

y?_

y@@

yA!

z!@

z"!

118360

w}~

w~_

x^~

x__

x`@

xa!

y?~

y@_

yA@

yB!

z!_

z"@

z#!

118391

w~~

x_~

x`_

xa@

xb!

y@~

yA_

yB@

yC!

z!~

z"_

z#@

z$!

119259

x{~

x|_

x}@

x~!

y\~

y]_

y^@

y_!

z=~

z>_

z?@

z@!

{!!

119290

x|~

x}_

x~@

y]~

y^_

y_@

y`!

z>~

z?_

z@@

zA!

{!@

{"!

119321

x}~

x~_

y^~

y__

y`@

ya!

z?~

z@_

zA@

zB!

{!_

{"@

{#!

119352

x~~

y_~

y`_

ya@

yb!

z@~

zA_

zB@

zC!

{!~

{"_

{#@

{$!

120220

y{~

y|_

y}@

y~!

z\~

z]_

z^@

z_!

{=~

{>_

{?@

{@!

|!!

120251

y|~

y}_

y~@

z]~

z^_

z_@

z`!

{>~

{?_

{@@

{A!

|!@

|"!

120282

y}~

y~_

z^~

z__

z`@

za!

{?~

{@_

{A@

{B!

|!_

|"@

|#!

120313

y~~

z_~

z`_

za@

zb!

{@~

{A_

{B@

{C!

|!~

|"_

|#@

|$!

121181

z{~

z|_

z}@

z~!

{\~

{]_

{^@

{_!

|=~

|>_

|?@

|@!

}!!

121212

z|~

z}_

z~@

{]~

{^_

{_@

{`!

|>~

|?_

|@@

|A!

}!@

}"!

121243

z}~

z~_

{^~

{__

{`@

{a!

|?~

|@_

|A@

|B!

}!_

}"@

}#!

121274

z~~

{_~

{`_

{a@

{b!

|@~

|A_

|B@

|C!

}!~

}"_

}#@

}$!

122142

{{~

{|_

{}@

{~!

|\~

|]_

|^@

|_!

}=~

}>_

}?@

}@!

~!!

122173

{|~

{}_

{~@

|]~

|^_

|_@

|`!

}>~

}?_

}@@

}A!

~!@

~"!

122204

{}~

{~_

|^~

|__

|`@

|a!

}?~

}@_

}A@

}B!

~!_

~"@

~#!

122235

{~~

|_~

|`_

|a@

|b!

}@~

}A_

}B@

}C!

~"_

~#@

~$!

Conclusion

No matter what hashing strategy is used, collisions are inevitable however, some hashes are worse than others. You can expect String’s hashCode() to be fairly poor.

Keeping a blockchain decentralised

Peter Lawrey — Thu, 19 Jul 2018 00:00:00 GMT

This article proposes a Proof of IP (PoIP) to favour diversity of IP addresses over large number of server concentrated by IP address.

While blockchain solutions using Proof of Work (PoW) and Proof of Stake (PoS) can be decentralised, individuals or companies which are more efficient, or better funded to grow than others will naturally push out smaller players. This can lead to a centralisation of those providing the service to those who have the most capital.

Blockchain lakes

When a company achieves greater economies of scale, it push out the competition which is less efficient. This leads to a small number of big players, who can offer a service at a lower price. This become a problem when a small number of players can start to dictate terms even increasing the cost of service.

For PoW, access to cheap power and specialised hardware gives those companies an advantage. This create lakes of processing power centralised around these locations and companies. Companies with significant investment need to ensure they maintain their advantage, which might not always be in the best interest of the users.

For PoS, access to capital determines who can provide the service. This has its advantages, but also means the direction of solution will be determined by companies and individuals with significant capital who want to protect their investment.

Proof of IP

Proof of IP uses verified IP address for each running node. Voting for each of the ~56,000 /16 domains is equal, ensuring that even a company with 65,000 servers doesn’t have a significant advantage.

Consensus

Each node can add a block of transaction per round. This enables a high degree of concurrency. Voting is required to determine which blocks are added to the chain (and thus in what order) Voting is balanced by the top bits of the IP making it much harder to buy up significant portions of the voting rights.

Want to know more

Proof of IP RFC

Can I play with it?

A working implementation of a block chain which both records the IP verifications and can be extended to support other transactions is in active development.

The github project is Chronicle Accelerate on GitHub

Microsecond latency Microservice Benchmarked

Peter Lawrey — Thu, 14 Jun 2018 00:00:00 GMT

It is common for a vendor to publish benchmarks with synthetic loads and code. However, what can be reasonably achieve in a real application? In this post, I discuss what we achieve with Chronicle Services for a client’s use case, a framework for low latency microservices.

What are we benchmarking?

In Chronicle Services we favour a high level interface where a publisher makes a method call, and the consumer is called back on the same method. This is slower than more direct access approaches but easier to maintain, esp for Java developers who want to develop in natural Java.

Microservice interface

public interface NewOrderSingleListener {
    void newOrderSingle(NewOrderSingle newOrderSingle);
}

A simple interface for messages in and a simple interface for messages out makes writing mocking services, creating data driven and integration tests natural and simple.

When used in the framework, every message is persisted in a logged/replayable manner and the publisher and consumer can be different JVMs or even different machines.

In this performance test, we include the time to:

mock the interface
serialize the NewOrderSingle with 28 FIX fields, including String(s).
write to shared memory
read from shared memory in another microservice
deserialize a NewOrderSingle
make a method call to the component in the service.

A significant portion of the time spent is in string handling. The class for NewOrderSingle was generated for the FIX protocol schema using Chronicle FIX

The test was run for 10,000,000 orders at a rate of 10,000 per second on a dual CPU E5-2650 v4 @ 2.20GHz server running Centos 7. Each service was single threaded. Higher throughputs can be achieved by adding more threads, or with poorer latency profiles i.e the 99.9% is higher.

The worst latency was 9.7 ms.

In this test, no minor or major GCs were triggered.

What about co-ordinated ommission?

For more information on what is co-ordinated ommission How NOT to measure latency by Gil Tene.

In our case, it doesn’t show in these results as we

have a low throughput compared with latency. The messages are 100 micro-seconds apart but typically have pass each message in around 1 micro-second.
in higher percentiles, it’s factor however they are not included here as they are very hard to reproduce from one system to another (OS/filesystem/CPU/Vendor/Java version). Even power settings and temperature are factors.

In short, for the region of the chart shown, co-ordinated ommission isn’t a factor.

How does this compare to other messaging solutions?

It is hard to find comparable benchmark results on the latency of messaging solutions. One good option might be to use a benchmark like https://github.com/openmessaging/openmessaging-benchmark although this doesn’t consider the serialization cost which can be relatively high, esp in Java if it triggers GCs. I couldn’t find any published benchmark results other than to say that Pulsar was faster than Kafka.

Most messaging solutions do not include the cost of serialization which can be higher than the cost of messaging. Some only consider the time to publish or consume a message. It is important to choose a benchmark which is representative of your use case.

Many messaging tests only consider throughput, or message latencies in milli-seconds.

How much is open source?

A good place to start is the https://github.com/OpenHFT/Chronicle-Queue which has 1.4k stars and is a key library in building micro services.

If you are intrested in our low latency micro services framework which supports distribution and data driven testing of these micro-services contact [email protected]

Chronicle downloads exceed 6 million in a month

Peter Lawrey — Wed, 13 Jun 2018 00:00:00 GMT

In the last three months we have seen a significant increase in downloads of our libraries. Wider adoption of our libraries into popular frameworks appears to be driving this growth in downloads.

A total of 6.3 million downloads across 450 thousand unique IPs is a huge increase for us. If you are not familar with all our open source products, these are our most popular:

Java Thread Affinity https://chronicle.software/products/affinity/
Zero Allocation Hashing https://chronicle.software/products/zeroallocationhashing/
Chronicle Core (Low level JVM access) https://github.com/OpenHFT/Chronicle-Core
Java Runtime Compiler https://github.com/OpenHFT/Java-Runtime-Compiler
Chronicle Bytes (Thread safe native memory access for text and binary) https://github.com/OpenHFT/Chronicle-Bytes
Chronicle Wire (Low GC serialization of text/binary to native memory) https://github.com/OpenHFT/Chronicle-Wire
Chronicle Threads https://github.com/OpenHFT/Chronicle-Threads
Chronicle Queue (Low latency journalled IPC) https://chronicle.software/products/queue/
Chronicle Map (Low latency peristed key-value store) https://chronicle.software/products/map/

If you have trouble getting started, ask us on https://stackoverflow.com/questions/tagged/chronicle

Chronicle also provides consulting, custom execution engines, and commercial support and well as enterprise extensions to many of these libraries. You can check out our new web site chronicle.software Email [email protected] for more details.

High throughput Consensus

Peter Lawrey — Wed, 25 Apr 2018 00:00:00 GMT

When achieving consensus across a distributed network, the latency of that network is an important constraint. How can we increase throughput? How does Little’s law help?

Time to consensus

To achieve consensus, each node on a network needs to send information to each other. Depending on your consensus model, it may have to send multiple series of messages to achieve consensus.

Minimum latency

In latency sensitive trading systems, you send every message asynchronously and wait for acknowledgments as little as possible. The goal is to minimise the cost of recovery after a failure, with the expectation some data will be lost, no guarantee each node see messages in the same order (each producers messages should be ordered)

A constraint on the time to get a copy of the data is the network latency one way, or half the round trip time (link). The delay is apparent only to systems receiving a copy of the data rather than the system producing the data.

Using sequencer

If you need to have total ordering between nodes, a "sequencer" can be added. This centralised service listens for messages and broadcasts the order it has chosen for the messages. Typically this is the order it sees them, but it could order them in any manner. This node has a key/trusted role and the impact of going down is significant. Provided the sequencer is simple and on reliable hardware, the likelihood of failure can be minimised.

Using a sequencer adds latency to all message processing, even messages processed on the same node as the producer as the sequencer needs to order the messages before they are processed.

Decentralised consensus

What if you don’t have one trusted, centralised sequencer? What if you need to protect against Byzantine Failures?

In this situation, each of the nodes need to play a role and achieving consensus where trust is in the super majority rather than any individual node.

This is more complicated and requires multiple rounds of messages to achieve agreement, however it handles random failure best as it assumes from the start that nodes are actively trying to disrupt the system.

In the case of Chronicle Accelerate, it has 4 phases to achieve consensus, meaning the time to consensus is a minimum of 4x the networks latency. In the design we assume the minimum round time is 5x the round trip time to include transmission and processing delays.

Table 1. Round time depending on network latency
Network Latency	Round time (5x)	Example
0.2 ms	1 ms	Multiple servers in the same data centre
0.6 ms	3 ms	Multiple data centres close together
2 ms	10 ms	Within a modest sized city
6 ms	30 ms	Across a large city
20 ms	100 ms	Across cities in the same country
60 ms	300 ms	Europe to North Amercia
200 ms	1000 ms	Across continents with slower links
600 ms	3000 ms	World wide, hetrogenous network

600 ms is twice as long as quality network between London and Japan. This is likely to be an up limit on the sort of network which might be used.

Little’s law and achieving high throughputs

A common technique for increasing the throughput when latency is a concern, is to increase the batch (or block) size. To paraphrase Little’s law:

Average number of messages = processing throughput * average time to process

This determines how large the block size needs to achieve a desire throughput for a given latency.

Table 2. Batch size needed to achieve a given throughput
Consensus Latency	100/s	1 K/s	10 K/s	100 K/s
3000 ms	300 txn	3K txn	30K txn	300K txn
10 ms	1 txn	10 txn	100 txn	1K txn
30 ms	3 txn	30 txn	300 txn	3K txn
100 ms	10 txn	100 txn	1K txn	10K txn
300 ms	30 txn	300 txn	3K txn	30K txn
1000 ms	100 txn	1K txn	10K txn	100K txn

IMHO, I feel more comfortable with batch size of 1 to 1000 as larger sizes have proven to be cumbersome in the past.

This all assumes that in each round, only one block is added, as most blockchain solutions do this. In Accelerate’s case, each node can add one block in a round significantly reducing the size each block needs to be. (You could consider the collection of blocks produced across each node to be one batch making the difference somewhat semantic.)

Table 3. Batch size needed with 25 servers in a cluster
Consensus Latency	100/s	1 K/s	10 K/s	100 K/s
3000 ms	12 txn	120 txn	1.2K txn	12K txn
10 ms	1 txn	1 txn	4 txn	40 txn
30 ms	1 txn	2 txn	12 txn	120 txn
100 ms	1 txn	4 txn	40 txn	400 txn
300 ms	2 txn	12 txn	120 txn	1.2K txn
1000 ms	4 txn	40 txn	400 txn	4K txn

Conclusion

Latency is a constraint but using larger batch sizes can increase the throughput which can be achieved within reason. As batches get larger they add to transmission time increasing latency further placing a practical constraints on the batch size.

Java Puzzles

Peter Lawrey — Fri, 20 Apr 2018 00:00:00 GMT

Here are some odd quiz questions in Java which might have interesting answers.

Questions

void arrays

Which of the following doesn’t compile

void[] voids = new void[1]; (1)
Void[] voids = new Void[1]; (2)
Void[] voids = { }; (3)
Object voids = Array.newInstance(void.class, 1); (4)

See the answer at the end.

null reference

What does this do?

Thread t = null;
t.yield();

A compiler error
A runtime error
The JVM crashes
The JVM pauses briefly

What does this do?

Creating an array of generic

Which of the following creates an array of a generic type T which extends Object.

T[] ts = new T[1]; (1)
T[] ts = { new T(); }; (2)
T[] ts = (T[]) new Object[1]; (3)
T[] ts = Array.newArray(T.class, 1); (4)

Multiplying characters

The following code compiles but what does it print?

char ch = '1';
ch /= 0.9;
System.out.println(ch);

prints

1
1.111111111111111
1.9
6

Decimals

Which of the following prints 0.3

int x = 3;
System.out.println(x / 10); (1)
System.out.println(x * 0.1); (2)
System.out.println(x / 10.0); (3)
System.out.println(0 + '.' + x); (4)
System.out.println(0 + "." + x); (5)

try with null

What is NOT true about this code?

    public static void main(String... args) {
        try (PrintWriter pw = null) { }
    }

It compiles but it doesn’t if you replace PrintWriter with Writer.
It produces no error at compile time or runtime.
The code won’t compile if { } is replaced with ;.
It doesn’t compile.

Answers

void arrays

void[] voids = new void[1]; (1)
Void[] voids = new Void[1]; (2)
Void[] voids = { }; (3)
Object voids = Array.newInstance(void.class, 1); (4)

1	a `void[]` isn’t allowed.
2	An array of any class is allowed even the `Void` class
3	Also creates an empty `Void[]`
4	This triggers a runtime error, but not a compile error. The compiler has very little knowledge of how libraries work and doesn’t pick this up as an issue.

null reference

This code

Thread t = null;
t.yield();

is the same as

Thread t = null;
Thread.yield(); // the method is static

So the answer is 4 as it just pauses briefly.

Creating an array of generic

Which of the following creates an array of a generic type T which extends Object.

T[] ts = new T[1]; (1)
T[] ts = { new T(); }; (2)
T[] ts = (T[]) new Object[1]; (3)
T[] ts = Array.newArray(T.class, 1); (4)

Only option (3) compiles. This makes it clear that the raw array is an Object array not the runtime type of T[]

Multiplying characters

The following code compiles but what does it print?

char ch = '1';
ch /= 0.9;
System.out.println(ch);

prints 6.

Each char is an unsigned 16-bit value which holds the unicode of the character. '1' has a unicode of 49. 49 / 0.9 is 54.4444444 however this is cast back to a char in the /= operation so ch = (char) 54 which is the unicode for '6'

Each assignment operator implicitly converts the result back to the type of the variable so ch /= 0.9 is like ch = (char) ((double) ch / 0.9);

Decimals

Which of the following prints 0.3

int x = 3;
System.out.println(x / 10); (1)
System.out.println(x * 0.1); (2)
System.out.println(x / 10.0); (3)
System.out.println(0 + '.' + x); (4)
System.out.println(0 + "." + x); (5)

1	This uses integer division; 3 / 10 is 0 with 3 remainder.
2	0.1 has a representation error which means it is slight larger than 0.1 and when multipied with 3 gets `0.30000000000000004`
3	This prints 0.3 as 10.0 can be represented without error.
4	This uses integer addition i.e. `0 + (int) '.' + x` which is `49`
5	This uses String addition so is ok.

In short, lines 3 and 5 print 0.3

try with null

What is NOT true about this code?

    public static void main(String... args) {
        try (PrintWriter pw = null) { }
    }

It compiles but it doesn’t if you replace PrintWriter with Writer. True as Writer.close() throws an IOException but PrintWriter.close() doesn’t
It produces no error at compile time or runtime. True as a null Closeable is silently ignored at runtime.
The code won’t compile if { } is replaced with ;. True as ; is not allowed as a nexted statement of a try-with-resource block unlike while, if or for
It doesn’t compile. False, it compiles.

When is using a Blockchain compelling

Peter Lawrey — Mon, 16 Apr 2018 00:00:00 GMT

I was recently asked, when is using a Blockchain really needed?

IMHO the main benefit is ease of provider integration Blockchain allows providers to join a system, with a much lower barrier to entry. If you are looking to build a network of new and innovative providers, which don’t have to trust each other, instead they trust the protocol, a blockchain is a compelling solution.

When is Blockchain not a compelling reason?

First I feel I should debunk some reasons often stated.

Blockchain doesn’t make everything better

In many cases, when a blockchain is proposed, it is used as little more than a log of changes in a database. In some cases, a distributed ledger could be used when a centralised database isn’t enough. Blockchain projects are easier to get approved these days as companies and individuals want to improve their blockchain skill sets but this doesn’t make it compelling from a technical point of view IMHO.

Blockchain is unlikely to make things faster

In most cases you will still need a database for reporting services, so adding a blockchain is highly likely to make it more complicated and slower, not simpler and faster than a database alone. See this article which mention speeding up payments

Blockchain can make a system faster if it can replace enough of an existing system which already implements the features a blockchain offers, but in a less efficient manner.

Blockchain doesn’t address all security concerns

To compromise a cluster of nodes you can employ a 51% attack. If you control a majority of nodes, you control the whole system. This could happen by adding or hacking enough nodes. A state level organisation could do this, potentially even with the most popular crypto currencies, however most governments have easier/cheaper ways of exercising policy or influence.

Many cryptocurrencies are public which is a real privacy concern when some of the bank balances are very high (or at least high to the individuals holding them).

At the time of writing This bitcoin address has $1.5 bn, and this ethereum address has around $770 m which makes them targets for hackers and organised crime.

Making this information private is likely to be highly desirable. However it could still be obtained through a hack though that is harder.

When is Blockchain compelling?

When participants trust a protocol, they don’t have to trust each other as much. This makes inclusion of new participants easier and allow existing ones to be more innovative.

Security

Reduced security impacts via a immutable ledger This means a new provider can join without all the existing providers needing to be fully comfortable with their security setup.

A high percentage of hacks involve disgruntled former employees. If you trust every node from every provider you have to trust every person operating it.

Innovative solutions

Using sub-chains, different providers can offer innovative solutions, without everyone else in the system needing to be comfortable with those solutions. By the time every participant is comfortable with a new solution, it’s probably not that innovative/disruptive. If every node needs to be trusted, you can’t offer a solution/transaction type unless every provider is comfortable with the risk associated with it.

Built in fee support

As the system controls the flow of value, it can also include settlement of fees and cut off participants as a result of exceeding some limit. e.g. if a participant, for whatever reason, starts spamming the system, this will cost them and result in them being cut off.

Does a blockchain need to have its own currency?

A blockchain offers a virtualisation of currencies. These can be backed by fiat or another digital currencies, or a new currency or both. If the system has fees to cover the cost of running the service, it needs to be in a supported currency. This could be in USD or EUR rather a new currency, however a crypto currency has the advantage that the actual cost can have a floating exchanging rate with fiat currencies. e.g. each transaction could cost 1 TXN and the value of this can be determined by an exchange.

New currencies can have novel features such as only being usable after a future date. You could have a 1000 USD token which is only usable after 1st Jan 2020, but can be bought now at a discount.

Conclusion

While I feel than many blockchain solutions could have used a database instead, there are some compelling use cases which allow multiple providers to offer innovating solutions to customers.

Blockchain Design considerations

Peter Lawrey — Tue, 03 Apr 2018 00:00:00 GMT

After I announced the release of Chronicle Accelerate, a high throughput blockchain solution in Java. One of the questions which came up was; What were the design considerations that went into the solution, particularly around throughput vs latency?

Many of these design considerations are not specific to Blockchain or Java, but general performance tuning.

If you have any questions, please AMA https://t.me/ChronicleXCL

Why use Java?

If you want maximum performance, why use Java?

This has two assumptions; what are you maximising the performance of, and is the Java portion a bottleneck anyway.

In most IT solutions, the cost of the hardware is small compared with the cost of IT development, esp if you don’t use a solution which is designed to be expensive such as Proof of Work. Use a lower CPU model, and the resource you want to maximise is development of the solution ie people. Most of the cost of development is actually in integration with existing systems. So you want to spend most of your time designing a system which is easy to develop and integrate with. Java is one of the most widely used languages, and one of the easiest to master all it’s lean set of features. By supporting multiple common APIs from the start, you make sure ease of integration is a priority in the design.

In terms of the blockchain solution we chose, the key bottleneck CPU wise is the Ed25519 signature and verification. The core of this algorithm is actually written in assembly to maximise performance. In designing a "maxed out" node to get the highest throughput per sub chain I would estimate the number of CPUs to be

Code type	CPUs
Assembly (Ed25519)	40
Operating System (Mostly TCP)	24
Java	4

While all the interesting custom development and business logic will be in Java, most of the CPU will be consumed by code already written and optimised in another language.

In short, we want to maximise developer efficiency, and most of the CPU consumed isn’t written in Java anyway.

Why develop a Blockchain?

Many solutions which are blockchain based, when they optimise the CPU consumed end up taking away some of the reason for having a blockchain in the first place. If all you end up developing is a distributed ledger or a simple database, I don’t see the point as these solutions already exist.

An essential feature which makes a blockchain different is; not needing to trust individual nodes are not fraudulent. If we optimise the solution but lose this feature in the process, we really have a distributed ledger (sometimes called a "Private Blockchain") Basically if you have a blockchain which can’t be run/mined publically I don’t see the use case, though it might be a good marketting strategy.

Ways of protecting against fraud

Fraud protection should prevent creating unathorized messages. Note: preventing a message from being falsified doesn’t prevent it from being read.

In our case, we use cryptographic signatures to transactions so that only the holder of a private key can create or modify the the transaction. For this case we use Ed25519 as one of the fastest 256-bit signatures.

Use of such a signature and verification, adds significantly to latency. The backend blockchain add about 2.5 micro-seconds latency however the verification and signing needed adds about 100 micro-seconds. While we can add CPUs to increase throughput, they won’t help in reducing latency.

Optimising for throughput

While most systems are optimized for throughput, trading systems tend to optimise for latency. Reduce latency enough and you will also get the throughput you need. Whether you optimise for throughput or latency depends on the type of problem you have. If many portions of the work can be done at once without having to work together, you can optimise for throughput with concurrent processing, esp as this is usually easier. If you have have key portions of work which must be performed in order such as transactions, you have to reduce the latency of each transaction to increase throughput.

As we have identified, most of the work is CPU bound, and independant. To optimise the system, we need to examine which pieces of work are serial by nature.

Identifying serial bottlenecks

Concurrent	Serial
Sign/verify	Consensus
Client TCP	Transaction processing

Concurrent

Serial

Sign/verify

Consensus

Client TCP

Transaction processing

Consensus

The cost of consensus increases with the rate at which this happens O(N), and the number of nodes in the cluster O(M ln M). In the later case, M nodes have M times the processing power so the overhead is just O(ln M)

However, both of these are in our control. We determine how often consensus is reached. We decide if its 10 ms, 1 second or 1 minute. Obviously we want this to be low, as this largely determines the latency of each transaction, however we can adjust it to suit our needs and the enviroment the nodes are running in.

The number of nodes in the cluster is also something we have some control over. We don’t want too few nodes, but we get diminishing returns and increasing cost on having more nodes.

In our case, we are looking to split the chain to improve efficiency once we have more nodes than we need in a chain.

The cost of consensus doesn’t increase with throughput, and is largely constant. i.e. when there is no transactions, confirming nothing is happening is all the nodes will do.

Transaction processing

The cost of processing transactions increases with throughput, and this determines the limit as to how much each sub-chain can do. Our aim is to make processing each transaction as lightweight as possible. Currently each transaction takes around 2.5 micro-seconds, which means the throughput achievable is 400K per second per sub-chain (1/2.5 us) We believe this can be improved, however with the option of having thousands of sub-chains, we might never need to do this.

Chain splitting

A straight forward way to split a chain is by address. We could use a bit of the address to determine which chain the address will be managed by. However, if we have a random arrangement of addresses, as we split, it gets increasingly unlikely that a transaction with only involve one sub-chain. Ideally we want a high proportion of transaction to involve just one chain to maximise concurrency and reduce overhead.

Another approach is to attempt to regionalise the addresses. For this purpose we have chosen the ISO 3166 standard for country and region codes around the world, giving us around 4000 regions which have some meaning geographically. This follows the assumption that most transactions a person or local business has, will involve other people or businesses in their local area. A person or business can hold multiple addresses to benifit from local transactions across multiple sub-chains.

For example, if I live in New York, or do some business there, I could have an New York address. The blockchain address in base 32 appears as @usny6897dh38d. The usny is the region code. I can trade with any address on the same chain quickly and efficiently. If I need to send money to another region, this will take longer, but it might take seconds instead of being sub-second.

Weekly checkpointing

Some blockchain solutions require every transaction from the genesis block to be available to work out if any given transaction was successful. The cost of doing this grows both with the number of transactions over time. This is fine provided that computing power grows faster, however what works for say 10 transactions per second won’t scale to beyond 100,000 transactions per second.

So based on how foriegn exchange systems work, we will be using a weekly cycle. This has a number of benefits.

it reduces the volume of data which needs to be retained to the state at the start of the week and each transaction which has happened in the week.
GDPR includes the right to be forgotten. However if a blockchain requires your transaction to be remembered forever, it’s not clear how this can work. If you use weekly cycles, your transactions can be forgotten after N weeks (data may need to be retained for legal reasons, but not more than that)

Conclusion

There are many design consideration is how to layout a blockchain solution. My focus is on the sort of problem only a blockchain could solve i.e. with untrusted nodes running the service. I firmly believe these problems are solvable.

Blockchain basics

Peter Lawrey — Wed, 21 Mar 2018 00:00:00 GMT

The key difference between blockchain and traditional databases is the level of trust needed in those running the service. With blockchain you trust the protocol, not those running it.

What does a blockchain do?

A blockchain records transactions without needing to trust any individual, organisation or computer, in a tamper proof way (or pretty close). This serves the same purpose as the record of transactions for your bank account, without needing to trust a bank.

What is a blockchain

A blockchain is a chain of transactions. This chain records which transactions occured and in what order. The order matters when trying to prevent double spend (spending the same money twice) The servers running a blockchain agree on this order in rounds which can be sub second, up to minutes. Bitcoin for example has a round every 10 minutes.

If the blockchain could only agree on one transaction every ten minutes, this would be impractially slow. Instead they agree on a block of transactions, which is like a page of thousands of transactions. By agreeing on blocks at a time, they can process many transactions per second on average.

A blockchain is a chain of blocks of transactions.

How does it differ from a database?

A traditional database can also record transactions. Traditional databases require trust between servers, which isn’t usually a problem within an organisation. Traditional databases are designed to recover from accidental failure, but cannot protect against deliberate attack by one of the servers. Banks use databases as they provide every server involved and ensure they are secure enough not to be compremised.

From my experience, many blockchain projects could have used a database as there is an assumption of trust between servers running the database. One reason blockchain might have been used as it is a more desirable technology to have experience and expertise in.

Characteristics of a blockchain

How nodes running a blockchain come to concensus is important to;

how much power they consume.
how much trust is required between nodes.
how fast it can process transactions

Ideally you want is; low power consumption, low level of trust and a high throughput. Newer blockchain solutions are looking to achieve these three in combination.

Power consume is a concern in some cases as blockchains like Bitcoin can use more power than a modest sized country like Ireland.

The level of trust required is important as the low the level required the easier it is add the blockchain and join it.

The transaction rate is key to keeping up with demand and a low transaction rate limits what it can be used for.

Private blockchains

Private blockchains can have a lower overhead, and not publically expose your data, however they generally assume that each of the servers is trusted to a high degree and don’t look to protect against actively fraudulent behaviour.

This doesn’t mean you shouldn’t have private blockchains, rather that they could have just used a traditional database.

Public blockchains

Public blockchains are ones which could be run by anyone with appropriate hardware (and possibly money for Proof of Stake) trusting the protocol, without needing to trust individuals however they are not completely safe and can be changed.

The 50% + 1 attack

If you control 50% + 1 of the nodes of a blockchain, you can override the behaviour of the blockchain just through majority, however you don’t need that many to stop one running.

It is possible that a nation state could have the resources to control a public blockchain.

The 1/3 attack

If you have a Byzantine Fault i.e. nodes actively trying to prevent the running of a service, controlling just 1/3 of the nodes can prevent operation of the service.

Some care needs to be taken to prevent 1/3 of the nodes actively trying to stop operation.

Blockchain doesn’t have to be complicated

The ecosystem around blockchain is complex and rapidly evolving, however the core of the solution needs to be simple to be easy to verify that it’s trustworthy.

In the future, like databases, we will see a variety of solutions to suit different use cases, and many more solution built on top of them to provide services and fill customer needs.

StringBuffer and how hard it is to get rid of legacy code

Peter Lawrey — Thu, 13 Apr 2017 00:00:00 GMT

In 2006, Java 5.0 was released with StringBuilder, a more light weight and sane version of StringBuffer. The Javadoc for Java 5.0 for StringBuffer notes

As of release JDK 5, this class has been supplemented with an equivalent class designed for use by a single thread, StringBuilder. The StringBuilder class should generally be used in preference to this one, as it supports all of the same operations but it is faster, as it performs no synchronization.

Having synchronized on StringBuffer was never a good idea. The basic problem is that one operation is never enough. A single .append(x) is not useful without another .append(y) and a .toString(). While individual methods were thread safe, you couldn’t make multiple calls to StringBuffer without race conditions. Your only option is external synchronized or using ThreadLocal StringBuilders (or more obviously create them on demand)

So more than ten years later, no one uses StringBuffer!? Certainly not for new functionality!?

How many objects does this create?

As I have noted before, the JVM creates many objects on start up or starting core libraries. Much more than you might expect making question like the following are a bit meaningless;

How many objects does this create?

public class Main {
    public static void main(String... args) {
        System.out.println("Hello " + "world");
    }
}

Object Pools revisited

Peter Lawrey — Sun, 12 Mar 2017 00:00:00 GMT

Object pools were popular before Java 5.0 however more efficient allocation made most of these pools a needless complication. Can a Object Pool still make sense and how fast do they need to be?

Overview

Up to Java 5.0 using object pools could significantly improve performance. However from Java 5.0, the cost of using naive object pools was often worse (and more complicated) than just allocating new objects all the time. However, if you work in a low latency environment and you want to keep allocations low, is there a way to make an object pool light weight enough to make sense.

A common use of a low level object is in the creation of Strings esp as input. Whether you have a service reading data from the network, or loading data from a database or file, you are likely to use a lot of Strings. While there are tricks to avoid using Strings, most of the alternatives lead to unnatural Java code which is ugly and harder to maintain. It would be much better if there was an efficient way to reuse Strings (assuming a high rate of duplication)

The test

This test assume we have some data in native memory (from a TCP socket or a file), and we have the option to avoid copying the data into a byte[] before creating a String.

For different lengths of bytes (1, 2, 4, 8, 16, 32) we use JMH to benchmark how long it takes to provide a matching String.

"Object Pool" uses an object pool for the bytes converted into a String.

"new String US-ASCII" copies the data to a byte[] and uses US-ASCII encoding to create the String.

"new String hibyte=0" copies the data to a byte[] and uses a deprecated constructor to set the hi byte to 0 create the String.

The Source code is available here ObjectPoolMain.java

The results

The average time to use the Object Pool was around 9 nano-seconds for short strings of up to 8 characters. About half the saving comes from avoiding the need to copy the data to a byte[] first. Also avoiding the use of even a trivial Charset character encoding also saved a significant amount.

Why use an Object Pool at all?

In this case the main reason is to avoid creating objects. If the String can be reused, it can dramatically reduce the garbage produced. Most of the time, only new Strings take space, rather than every String your use and this can be a 90% reduction in memory use and garbage production.

Conclusion

For some use cases, an Object Pool is fast enough, possibly faster when it is has been optimised to minimise copies and supporting functions like character encoding.

The library used only supports ISO-8859-1 and UTF-8, so if you need another character encoding it would be significant work or use would have to use the standard functions.

Can you have encryption and low latency in Java

Peter Lawrey — Fri, 03 Mar 2017 00:00:00 GMT

While using encryption is slower than writing raw messages, how much slower is it and does it have to be a performance problem?

In this post, I look at Chronicle Queue, with and without encryption to see how much difference it makes to latency.

The test

In this test, there is one writer or Appender, writing data at regular intervals using a Marshallable object, containing a nano-second timestamp. Another reader or "Tailer" is reading those messages. The timestamp used is the time the message should have been written rather than when it was written to avoid co-ordinated omission.

The message is 32 bytes in length, and 5 million messages were sent in each case after ignoring the first 100 thousand to allow the JVM to warmup.

The computer used is a Dell XPS 15 with an i7-6700HQ with 8 GB memory running Windows 10.

Salted AES encryption.

AES128 is a fast 128 bit encryption, though it has one weekness. If all the messages start the same (and in this test and is often the case) the first bytes become predictable. This makes cracking the key easier.

A standard soluton is to use a "salt", which is a random block at the start of the message. In our case we use a 64-bit psedo random number with the System.nanoTime() (also 64-bit)

The latency distribution

In throughput tests, the machine can write/read over one million messages per second with encryption, however the latency distribution is poor in this range. For the purposes of this test we are looking at what throughput do we get low latency as well .

Low latency encrypted messages with Chronicle Queue Enterprise

Peter Lawrey — Tue, 07 Feb 2017 00:00:00 GMT

Chronicle Queue Enterprise supports replication in a cluser and system monitoring. We recently added encrypted messages and the inital results are encouraging.

What did we test?

This test s similar to our previous non-encrypted version: Latency tests with Chronicle Queue, except we added Salted AES 128 encryption. We chose AES as a fast encryption, and we added salting to make it harder to obtain the key

Why use Salting?

Most messages start with the same bytes. Whether the message is XML, JSON, FIX, Java Serialization, the first few bytes are predictable. The start of every encrypted message can end up the same. This makes brute force cracking of the key easier because you know what you are looking for.

To avoid this we add a 64 bit random number to the start of every message using SecureRandom, which makes brute force attack harder.

The results.

In short the 99%ile latencies were great, the 99.9%ile latencies were also good if you ignore co-ordinated omission as a problem. Unfortunately, with co-ordinated omission correction, the 99.9%ile numbers need to be improved.

Nevertheless, the early results look good. We can achieve throughputs of 400K/s and still get latencies around 2 micro-seconds 99% of the time. In addition, at 1.1 million messages per second we can get around 10 microseconds, 99% of the time.

Conclusion

Using encryption is slower, however it might still be fast enough for your needs.

Improving percentile latencies in Chronicle Queue

Peter Lawrey — Mon, 06 Feb 2017 00:00:00 GMT

Compared to a year ago, we have significantly improved the throughput at which we can achieve the 99%ile (worst one in 100). What tools and tricks did we use to achieve that?

What are we testing?

Chronicle Queue appends messages to a file while another thread or process can be reading it. This gives you persisted IPC (InterProcess Communication).

For our clients with higher expectations for latency, they are looking to have the whole service which is under 100 micro-seconds 99% of the time.

For our test, we have chosen to find the throughput you can achieve and still be under 10 micro-seconds 99% of the time. The test writes 20 million 40 bytes messages, which contains the time the message should have been sent to avoid co-ordinated omission, and read by another thread. The difference in time is recorded.

We have also added encryption support for our enterprise solution. We test here a salted AES 128-bit encryption.

The improvement

Test

Throughput where 99%ile is 10 microseconds

March 2016, unencrypted
Centos 7 server

100 K/s

February 2017, encrypted
Centos 7 server

700 K/s

February 2017, unencrypted
Windows 10 Laptop

1,200 K/s

February 2017, unencrypted
Centos 7 server

2,400 K/s

What makes this improvement significant, is that we added correction for co-ordinated omission.

Sampling tool

While profilers are very useful, one thing they struggle with is helping you find the cause of latency outliers. This is because profilers show you averages, and unless your outliers are really large, they don’t show up as significant.

To address this we added a class which acts as a basic stack sampler.

package net.openhft.chronicle.core.threads;

import java.util.concurrent.locks.LockSupport;

/**
 * Created by peter on 04/02/17.
 */
public class StackSampler {
    private final Thread sampler;
    private volatile Thread thread = null;
    private volatile StackTraceElement[] stack = null;

    public StackSampler() {
        sampler = new Thread(this::sampling, "Thread sampler");
        sampler.setDaemon(true);
        sampler.start();
    }

    void sampling() {
        while (!Thread.currentThread().isInterrupted()) {
            Thread t = thread;
            if (t != null) {
                StackTraceElement[] stack0 = t.getStackTrace();
                if (thread == t)
                    stack = stack0;
            }
            LockSupport.parkNanos(10_000);
        }
    }

    public void stop() {
        sampler.interrupt();
    }

    public void thread(Thread thread) {
        this.thread = thread;
    }

    public StackTraceElement[] getAndReset() {
        StackTraceElement[] stack = this.stack;
        thread = null;
        this.stack = null;
        return stack;
    }
}

We can accumulate the results in a Map which is nothing special. Except we can filter only those which contributed to an outlier e.g. a delay of over 10 microseconds.

The results are pretty crude, however we found issues in code that the profile didn’t show. The issue which came up again and again was default methods. As of Java 8 update 121, they just don’t seem to be optimised as well as methods in classes. We found that copying the default method to selected classes and only for the selected methods in this sampler, we saw a reduction in outliers which allowed us to increase the throughput further.

There were other optimisations more specific to our problem, but using class methods instead of default methods is a trick we have used before.

Not all default methods are bad, we still use them often without a problem. Only override a default method for performance if you can show this helps.

Charting the 99%ile latency.

For the unencrypted messages we achieve reasonable (less than 10 micro-seconds) latencies in the 99.9%ile up to 1.4 million messages per second and in the 99%ile up to 2.3 million per second.

Conclusion

It is possible to have low latency encrypted messages where the 99%ile is less than 10 microseconds, however we need to have a throughput of less than 700K messages per second (or use multiple threads / queues).

While minimising the latency of outliers is tricky, reducing the 99%ile latency can improve the consistency dramatically and increase the throughput you can safely sustain.

Chronicle Queue storing 1 TB in virtual memory on a 128 GB machine

Peter Lawrey — Fri, 27 Jan 2017 00:00:00 GMT

If you use a standard JVM like the Oracle JVM, or the OpenJDK, you might find that as the heap size grows the performance of your JVM can drop as GC pause time escalates. This tends to be a problem around 32 GB of heap, but it often depends on the application at which point the size of you heap becomes a problem.

One way around this is to use an always concurrent collector such as Azul Zing which is designed to both scale to much larger heap sizes and even reduce the GC pause times for smaller heap consistently.

Data set larger than main memory?

What if your data set sizes are larger than main memory? At this point using the heap doesn’t scale and you need a data store off heap. This could be a database, NoSQL, but these can be dramatically slower depending on what you are doing.

Chronicle supports a huge, persisted dataset.

Chronicle Queue and Chronicle Map allows you to have a persisted store which can be embedded into multiple JVMs on the same server. How does it perform when you exceed main memory size. In this page, we look at Chronicle Queue with favouring for sequential access, scales very well, and shows a little slow down.

What does a JVM which is over 1 TB in virtualsize look like?

Figure 1. top on a machine with 128 GB of memory, and a JVM with 1 TB of queue data

In this example, the JVM with 1 TB of data reports that 0.111t or 111 G is in memory, though the virtual size is 1.281t or 1,281 GB (with heaps and indexes)

But how does it perform? It must get slower.

If you attempted to create and use a 1 TB heap on a machine with 128 GB of memory, it would either fail to start, or with some tuning, start but make your machine unusable. How much does using Chronicle Queue to store the data slow down?

In this test, it writes a bursts of 2 million 512 bytes messsage (1024^3 bytes of data), it then reads the data and waits 8 seconds to let the disk catch up. While the burst rate is about 1 GB/s, the underlying disk doesn’t have the write speed and for this test it averages about 100 MB/s. It takes about 2.5 hours to write 1 TB.

Figure 2. The read time is fairly consistent for this test

We would expect reads to be consistent as we are always reading something we just wrote.

While the machine has 128 GB of memory, it has two NUMA regions of 64 GB. This shows around 64 GB has been written.

The write performance is more dramatic. There is also significant variation as it has to find new memory to write to. This can be mitigated by using a pretouch() call to pre-allocate memory to write to. Normally, this would be run in a background thread, but for the purposes of this test it was run in the same thread but not timed.

Figure 3. The write time is fairly consistent beyond 192 GB

The average time to write a GB for the first 64 GB was 885 ms. From 256 GB in size this takes an average of 1,084 ms which is an increase of 22%.

However, let us consider that the alternative is to pump 2 million records (1 GB) of data to a database, and query it to get the data back. By having it in the JVM, we can read 2 million record in as little as 200 ms using just one thread.

Conclusion

Chronicle Queue performs very well up to the limit of main memory and beyond. It uses very little heap and has only a notional impact on GC pause times even if the dat set size is many times main memory.

You can try this test yourself here RunLargeQueueMain

For more information on Chronicle Queue GitHub source Chronicle Queue Product page

Having a queue larger than main memory only works on Unix at the moment. On Windows, a cycle e.g. a day, has to fit into main memory. This is something we would like to fix in the future.

Choosing Chronicle FIX Engine

Peter Lawrey — Fri, 20 Jan 2017 00:00:00 GMT

Overview

The FIX Trading Community web site has posted a list of common questions about FIX Engines. This page brings together our answers for these questions.

For more details on Chronicle FIX

Capabilities/throughput

Chronicle FIX supports;

100,000 messages per second per core. (NewOrderSingle / ExecutionReport sized messages)
FIX Services which need to have a 30 micro-seconds tick to trade.
FIX 4.0, 4.1, 4.2, 4.3, 4.4, 5.0, 5.0 sp 1, 5.0 sp2, FIXT 1.1 is planned.
failover of a FIX server to a hot spare via replication
encryption of all message logged and replicated.
zero copy between the FIX message and your data model. An intermediate data model is provided for convenience but is not required.
designed for ultra low GC systems (minor GC less than once a day)

Technologies used

Core Java 8.
Build on largely Open Source libraries, also from Chronicle.
YAML for configuration.
QuickFIX style XML Schema files.
Source on GitHub.

Support and services offered

Chonicle Software offers Silver support (long London day, 5 days a week) and Gold support (24/7)

Versions supported

Q: Does the engine support all current FIX versions
A: FIX 4.0, 4.1, 4.2, 4.3, 4.4, 5.0, 5.0 sp 1, 5.0 sp2, FIXT 1.1 is planned.

Q: Does it support all tags of each version
A: All tags for these version are supported.

Q: Can it support more than one version at once
A: An Engine supports being an acceptor and an intiliator and each session can have a different FIX version and/or custom FIX schema.

Q: What is involved in supporting new versions of FIX?
A: You start with an XML Schema to generate the code for that schema. You can customise the behaviour further in plugin code. You could add a version of FIX which which we don’t have on our supported list.

Support for asset classes other than equities

Q: Can the engine support fixed income, derivatives, FX etc.
A: We support all the standard messages/field/components, for any asset class.

Q: What is involved in adding support for additional products?
A: The level of support you need is orthogonal to the products you want. If you have Gold SUpport that covers the open source products and any licensed products. You can have Gold Support for the open source products alone.

High availability, load balancing, and scalability

Q: Does the FIX engine support a software-based high availability option for high-volume, many-connection implementations
A: We support failover to a hot spare using replication. When a message is published we can choose to wait for the message to be replicated/acknowledge before sending it to ensure it isn’t lost. We don’t offer a load balancing facility at the moment, however one dual socket server can comfortably handle one million messages per second.

Speed and robustness

Q: How many messages a second can the engine process
A: Chronicle FIX can comfortably handle 100,000 messages per second per core and one million message per second per server.

Q: What fall-back and redundancy options are available
A: You can set a hot spare using Chronicle Queue Entperise to provide replication of the logs.

Encryption options

Q: Does the engine support common encryption methodologies, Is SSL supported
A: Not currently, but this could be added if you need it.

Ability to implement per-connection business logic

Q: Each FIX connection tends to be slightly different. Can you embed counterparty specific logic within the engine rather than having to implement from outside within your systems?
A: You can have per session

data model for storing messages
custom parser
message validation
message handling

You can also share this logic to minimise the overhead of managing different providers. e.g. Youc an combine the custom schema of 20 providers into a single Uber schema even if they use different versions of FIX. This allows you to code to one aggregate data model.

It is assumed each session will have at most one connection.

Platforms supported

Q: Not all FIX engines run on all platforms. Some FIX engines sell themselves on the basis that they will run on all platforms, others take the opposite view and market themselves on the basis that they are optimized to run on one platform only.
A: Chronicle FIX only supports Oracle Java 8, OpenJDK 8, Azul Zing/Zulu 8 on x64 processors. We support Linux, Windows and MacOSX.

Architectural flexibility

Q: Does the engine restrict your implementation to a specific architecture
A: Realistically it has to be in Java.

Q: Are you forced to use a database for persistence or a particular type of middleware for example
A: Your must data store must be accessible from Java.

Provided as a set of class libraries or a FIX-in-a-box solution

While we offer a set of class libraries you could customise heavily (we use the same libraries to implement our non FIX Engine) most clients use it as FIX-in-a-box. We feel the like the fact they could take it apart and build it however they need covers potential technical risks.

Q: FIX engines supplied as class libraries (APIs) offer complete flexibility over your implementation but you have to do the work.
A: We want to offer complete flexability even if you won’t use a fraction of the flexability. As the product matures we want to reduce the amount of work you need to do, but teher will always be some customisation you will need to do to suit your soluton.

Q: FIX-in-a-box solutions provide ready-made functionality for many commonly used activities and seamlessly handle network connectivity. They are easier to implement but aren’t so flexible.
A: We attempt to handle all the session messages and details automatically from configuration. You should only have to worry about the application messages most of the time. We support custom session messages as well.

Access to source code

Q: Some FIX engine vendors make available the source-code so that you can modify their product. Typically this is only done for a fee and for the largest clients.
A: Our FIX engine is in a closed source repository on GitHub. Once you have a license and have access you can fork the code, issue Pull Request and add issue just as you can on GitHub. Out support agreements includes some days a month for bespoke development so you can get us to make the changes if you prefer.

Support offered

Q: What level of support is offered and at what times.
A: Silver support is a long London day, 5 days a week. Gold is 24/7 and …

Q: Is on-site support available
A: Platnium support includes three months a year on site on days of your choice.

Upgrades and updates

Q: How many updates and upgrades does your license entitle you to
A: The perpetual license alone entitles you to updates/upgrades for 120 days. If you get support it includes updates for the period under support.

Q: Does the vendor charge a license fee for an engine in a disaster recovery / stand-by environment
A: How you use the product doesn’t affect the price.

Cost and pricing options

Q: Is the cost reasonable? Is the vendor flexible around how you would like to pay?
A: We can be flexable for smaller clients. To date we have only had real interest and sales for business unit license covering a development team.

Monitoring tools

Q: Does the engine come with tools that allow monitoring of your FIX sessions. A good error translator can prevent you spending of a great deal of time trying to find an error message.
A: We have a HTML5 GUI for monitoring sessions and querying logs of messages.

IT experts you should follow on twitter

Peter Lawrey — Sat, 03 Sep 2016 00:00:00 GMT

When I read lists like this they always seem to be male dominated, so here is a list of experts I follow which isn’t.

Dr Sue Black OBE

Dr Sure Black’s Home Page

#CMTV speaks to Dr Sue Black; Award-Winning Computer Scientist Part One Part Two

Saving Bletchley Park "The story of the saving of the home of modern computing by Sue Black"

Tech Mums "Empowering mums, their families and communities through technology"

Follow @Dr_Black

Sara Rey Chipps

Just a girl, standing in front of a microprocessor, asking it to love her. I made @girldevelopit. I’m making @jewelbots. Pull requests welcomed. 30 K followers

Sara Rey Chipps' Blog

Follow @SaraJChipps

Kelly Sommers

4x Windows Azure MVP & Former 2x DataStax MVP for Apache Cassandra, Backend brat, big data, distributed diva. Relentless learner. I void warranties. 25.7K followers

Kellabyte’s blog

Kelly Sommers YouTube Channel

Follow @kellabyte

Julie Lerman

Vermont Geekette, DDD, .NET (& EF) Mentor, Author, MS MVP, MS Regional Director, VTdotNET, Pluralsight, MSDN Mag. Talk to me about mentoring your dev team! 22.5K

The Data Farm "Julie Lerman’s World of Data"

Julie Lerman’s Channel 9 "Julie Lerman is a Microsoft MVP, mentor and consultant who lives in the hills of Vermont. You can find Julie presenting on Entity Framework , Domain-Driven Design and other topics at user groups and conferences around the world"

Follow @julielerman

jessfraz

I contribute to open source software for fun and as my job. 'Weird sun beam of awesome.' http://git.j3ss.co 21.7k followers

Jessie Frazelle’s Blog

Follow @jessfraz

jennmoneydollars

my father’s strongest most handsome daughter. i came to win, 19K followers

Jenn Schiffer’s Blog

No one expects the lady code troll "@jennschiffer’s hilarious talk on how and why she satirizes the tech industry." - @xoxo

Jenn Schiffer’s Pixel Art

Follow @jennschiffer

Iris Classon

The world’s happiest .NET developer & Microsoft C# MVP! More energy than a 5 year old, talks more than your grandmother, and does anything to make you smile! 18.7K followers

Iris Classon’s Blog

Iris Classon’s StackOverflow profile

Follow @IrisClasson

Jessica Kerr

Functional developer, speaker, mother, crazy nut. Stripe. Learning and growing. All tweets are mine, licensed CC0. she/her. 16.6K followers

Jessitron’s Blog

Jessica Ker’s InfoQ videos

Jessitron’s Home Page

Follow @jessitron

Jen Myers

Technologist & writer. Curriculum director at @pluralsight. Advisor at @girldevelopit. Founder of @codecupcakeschi. Likes adventure, changing the world, otters. 15.7K followers

Jen Myer’s Home Page

Follow @antiheroine

Lucy Leiderman

Funnier than you’d expect. Full-stack growth marketer. Building @helloretreaver. Scrum master. I have 5 minutes, come say hi. 13.2K followers

Lucy Leidrman’s Home Page

https://plus.google.com/LucyLeiderman[Lucy Leiderman's Google page]

Follow @lucyleid

☭ 🚀 🐶 Bodil 🐶 🚀☭

The Hound of the SJWs. 11.1K followers

Bodil’s Home Page

Bodil Stokke - The Miracle of Generators

Bodil Stokke - Reactive Game Development For The Discerning Hipster

Follow @bodil

Femgineer

We empower techies and provide courses and workshops to: educate, empower, and encourage professionals in the high-tech industry. 10K followers

Femginerr’s YouTube Channel

Follow @femgineer

Caitie McCaffrey

Backend Brat & Distributed Systems Diva @twitter Formerly #343i building @Halo Services with @projectorleans. Valkyrie AF. 9.7K followers

CaitieM’s Blog

Talks by Caitie McCaffrey

Follow @caitie

Trisha Gee

Coder/blogger/speaker, working for JetBrains. Human. More or less. 7.7K followers

Trisha Gee’s Home Page

Trisha Gee’s Blog

Trisha Gee’s content on InfoQ

Interview with Trisha Gee

Follow @trisha_gee

Jen Golbeck

Prof at Univ. of MD., Computer Scientist. Tweets about social media, research, zombies. My new book is Social Media Investigation -how to track people online! 5.9K followers

Jen Golbeck’s Home Page

Jennifer Golbeck’s Work Page

Jen Golbeck’s Wikipedia Page

Follow @jengolbeck

Yara M H Senger

Yara is President of SouJava and co-founder and director of GlobalCode, the largest Java training company in Latin America, currently based in 13 different cities. 5.7K followers

GlobalCode YouTube Channel

Follow @yarasenger

Lynn Langit

Cloud architect who also codes, prefers AWS & GCP. 5.3K followers

Lynn Langit’s Blog

Lynn Langit’s presentations

Follow @lynnlangit

Maxime Chevalier

PhD in compiler design, dynamic languages and optimization. Interested in programming languages, graphics, electronics, music and DIY. All opinions are my own. 4.7K followers

Maxime Chevalier’s Blog "Pointers Gone Wild A blog about compilers, programming and technology."

Follow @Love2Code

fabianenardon

Data Scientist, Java Champion and impossible projects expert. Founder of http://toolscloud.com and partner at http://tailtarget.com 4.1K followers

Fabiane Nardon - Java Champion Brasil & impossible projects expert

Follow @fabianenardon

Susan Potter

Post-postmodern infrastructure engineer (Scala, Haskell, Nix) obsessed with finance, Charlotte Brontë, bad pop, and abstract algebra. 4.0K followers

Susan Petter’s Home Page

Follow @SusanPotter

script kitty

I write the softest software you’ve ever touched @uber engineering. I wanna be an indie game dev when I grow up. oh, and kelly is my middle name 4.0K followers

Follow @marthakelly

Stacey Mason

Researcher/creator of games & playable stories. Twitch critic. Contributor: @cerebralarcade, @ScholarsPlay, @igdafoundation Prev: @zynga, @eastgate 3.8K followers

Stacey Mason’s Home Page

Follow @stcymsn

wendydevolder

Helping #community learn and share skills to write better software by producing talks, conferences, magazine, workshops, skillscasts on #agile #opensource 3.7 K followers

What is Skills Matter Wendy Devolder is the CEO of Skills Matter.

Follow @wendydevolder

Mathilde Lemee

CoFounder @SoFizzApp - L’appli pour partager tes activités à proximité avec de nouvelles personnes ! CoFounder @duchessfr - Réseau de femmes devs 2.8K followers

Duchess France - Women in Tech "Mathilde Rigabert Lemée [is a] co-founder and active member of Duchess France"

Follow @MathildeLemee

Andrea McAts

All tweets about Programming. For everything else @roundcrisis 2.7K followers

Andrea McAts' Blog

Follow @silverSpoon

Tiffany Conroy

Interaction designer. Developer. Cutter of bullshit. Made @weareallawesome. Micro diary: @whattiffanydid. she/her. Has strong opinions, loosely held.

Tiffany Conroy: Workplace confidence

Tiffany Conroy, Beautiful authentication: Tear down the barbed wire

Talks by Tiffany Conroy

Follow @theophani

Karen Catlin

Advocate for women in tech. Leadership coach, TEDx speaker, co-author of Present! Board member @TheCLUBSV. Former VP @Adobe. Happy mom. 2.6K followers

Karen Catlin’s Home Page "Advocating for women in the tech industry"

Karen Catlin’s presentations

Poornima Vijayashanker & Karen Catlin on Mentoring

A Techie’s Guide to Public Speaking Karen Catlin

Follow @kecatlin

Ludwine Probst

Data Engineer / Scientist 💻 open source contributor @@ousmotards 🏍 @L@diesCodeParis co-founder 🌍 Tech blogger #TechBeyondBorders 2.6K followers

Ludwine Probst’s Blog

Tech Beyond Borders by Ludwine Probst

Follow @nivdul

Amy Chen

Ramblings of a 20 something software engineer. 2.0K followers

Amy Chen’s Blog

Follow @TheAmyDance

Amira LAKHAL

#Agile #Java #Scala #Developer at @Valtech_fr || one of @duchessfr leaders || running addict #WomenInTech #yesWeCode

IOT, timeseries and prediction with Android, Cassandra and Spark

Nighhacker Interview

Follow @MiraLak

1+K followers

Claude Falguière

Java, Performance, DevOps, Clojure, DataScience, funny ways to learn programming, Devoxx4Kids, ParisJUG, Devoxx, Duchess

Follow @cfalguiere

Stéphanie Hertrich

Developer Evangelist Girl @Microsoft, Technical Angel for #startup ❤️, I’m a coder and a speaker for Tech event, Proud @duchessfr

Follow @stepheUp

Agnès Crepet

Java Champion & JS Newbie, @ninjasquad Co-Founder, @MINES_StEtienne CS Teacher & Agile Learning Facilitator, @mixIT_lyon Co-Founder, @duchessfr Leader

Follow @agnes_crepet

Heather VanCura

Community Builder, Connector, Java Connoisseur (for JCP tweets see @jcp_org); Women & Girls in Tech, Open Source, Fitness, Fashion, Fun.

Follow @heathervc

Aysylu Greenberg

Programmer, Artist, Lifelong Learner, distributed infrastructure @google

Follow @Aysylu22

Holly Cummins

IBMer, developer, author, hat-hacker and duvet-cover-maker. My views are my own.

Follow @holly_cummins

Kasia Mrowca

Product magician, IT passionate, agile & lean enthusiast, PhD candidate, conference junkie. Love skiing and hiking :)

Follow @MrowcaKasia

Katia Aresti

Freelance Developer, Open-source enthusiast, drama and dance passionate. @duchessfr Paris MUG

Follow @karesti

Monica Beckwith

(Java/JVM/GC) performance consultant. Mother of 2 awesome kids. Enjoys country living. Java community editor for InfoQ.

Follow @mon_beck

Anne Gabrillagues

Agile coach / CSM / CSPO at @ippontech - interested in everything about #agile #lean #designThinking #devops #ux … - member of @LeanKanbanFr team

Follow @agabrillagues

Amelia Eiras

Ecuatoriana-Española-American, #badass #usualsuspect #iloveourITcommunity. Brutal honesty trumps hypocritical politeness. The backbone @Tomitribe

Follow @ameliaeiras

For now, I have limited the list to those with at least 1000 followers, but I will continue to update it.

Groups supporting women in tech

IEEE Women in Engineering

IEEE Women in Engineering YouTube page

Why don't I get the throughput I benchmarked?

Peter Lawrey — Sat, 23 Jul 2016 00:00:00 GMT

In synthetic benchmarks, you can achieve a high throughput for your system by throwing lots of independant tasks/clients at it to see what the theoretical limit of your system is, however in real world situations, the throughput you achieve is often much, much lower. One of of the explanations for this comes from Little’s Law

What is Little’s Law?

This law comes from queuing theory, an example being the number of customers in a store.

Little's Law tells us that the average number of customers in the store L, is the effective arrival rate λ, times the average time that a customer spends in the store W

L=λ × W

For a given latency, the higher the throughput you need to achieve, the higher the number of independant tasks you need. Say you have a shop where checking out at an automatic till takes 10 minutes on average. To achieve, a given throughput, how many tills, and people wanting to check out do you need?

Throughput

People trying to check out at once

1 every 10 minutes

1 person and 1 till

1 per minute

10 people and 10 tills

10 per minute

100 people and 100 tills

There might not be 10 or 100 people trying to check out at once, so even if you have the tills, there might not be enough people/users to utlise the tills you have.

Say instead it only takes 1 minute to pass through a till, how many people do you need to be checking out at once to get the throughput you are looking for.

Throughput

People trying to check out at once

1 every 10 minutes

1 person and 1 till

1 per minute

1 person and 1 till

10 per minute

10 people and 10 tills

Reducing the latency by a factor of 10 means you need one tenth of the resources. More importantly, you only need one tenth of the people trying to check out/tasks to achieve the desired throughput.

Some problems have inherent limits to the number of independant tasks you have. Trading systems and business applications might only have an intrinsic concurrency of between 1 and 10, in which case, latency rather than throughput is your main constraint.

Chronicle Queue vs Apache Kafka

On the surface, Chronicle Queue and Apache Kafka do many of the same things. They are both high throughput, persisted queues. What difference do Chronicle’s much lower latencies make?

In this benchmark, Apache Kafka achieved a throughput of around 400,000/s - 800,000/s on one machine, with linear scalability to three machines. This is a very good throughput. However the latency measured 2 ms and the 99%ile was 3 ms. This means any individual task which must wait for replication before proceeding must wait around 2 milli-seconds, or more conservatively 3 milli-seconds.

If the latency is 3 milli-seconds, how many independant tasks do you need to have to reach a desired throughput?

To achieve higher throughputs, you need more independant tasks. What if you only have 1 to 100 independant tasks?

With a small set of tasks, you are not going to achieve a high throughput with a latency of 3 ms. By comparison if we look at the 99%ile latency of Chroncile Queue synchronous replication, which is between 20 - 40 micro-seconds, you can achieve high throughputs with relatively few independant tasks.

Independant Task(s)

Chronicle Queue Throughput

Apache Kafka Throughput

50,000 per second

340 per second

290,000 per second

3,400 per second

100

2,000,000 per second (2 servers)

34,000 per second

To achieve, the benchmark throughput with Kafka, you need a problem which has a very high number of independant tasks (many thousands), or you either need asynchronous replication.

If asynchronous replication is acceptable, then Chronicle Queue has a much lower latency of 1.2 micro-seconds for the 99%ile. This means it can support close to one million messages per second with a single thread and only one task at a time. Two threads are enough to get 80 million events per minute which is our benchmark throughput for the E5-2650 v2 server we tested.

When do I add monitoring to my application?

Apache Kafka was designed for web application monitoring. It is widely used for this purpose today. As such it does the job very well.

However, Chronicle Queue is design to be fast enough to be part of the critical path, recording all the inputs and outputs of your services. Since you are already recording all the data needed to recreate the state of your component at any point, little additional monitoring is required. (System monitoring is still required) It is not a case of; Now our application is in production, how do we monitor it? Or how do we replay message to recreate an issue?

Chronicle Queue is integral to the working of the application so you know no information is missing or the application wouldn’t work.

Conclusion

If you have a problem with many thousands of independant tasks, then high number of tasks "in flight", or customers in the store, is a relatively simple way to get the throughput you need and the impact of latency is low. If you have a few tasks, or just one task you can perform at a given moment, latency rather than throughput is critical.

Improving performance with simple compression

Peter Lawrey — Fri, 22 Jul 2016 00:00:00 GMT

Chronicle Wire supports multiple Wire Formats such as YAML, JSON and CSV. It also supports a binary format of YAML for performance. Chronicle Wire Enteprise has an additional Wire Format which performs simple compression which can be faster AND smaller than not compressing data.

Compression of serialized objects using delta-ring.

Delta Wire automatically detects which fields in an object have changed and sends only those fields. If the field is a number it can send the difference using less bytes. It does this for nested objects individually as well.

You can still utilised generic compression like GZIP, LZW or Snappy to achieve further compression. However, these compression techniques are releatively more expensive and they can be ten times slower than no compression. What if you want a compression technique which is actually faster?

A sample data structure in Java

class MyDataType extends AbstractMarshallable implements KeyedMarshallable {
    long firstId; (1)
    int secondId; (1)
    String thirdId; (1)

    String staticOne; (2)
    long staticTwo; (2)
    ZonedDateTime staticThree; (2)
    double staticFour; (2)

    long changesA; (3)
    double changesB; (3)

    @Override
    public void writeKey(@NotNull Bytes bytes) {
        bytes.writeLong(firstId).writeInt(secondId).writeUtf8(thirdId); (4)
    }
}

1	Composite key for this data transfer object
2	Fields which rarely change
3	Fields which often change
4	Write a key to signify when two objects represent the same data.

To write this object you can use the Chronicle Wire library to write in different formats.

Update message as YAML - 268 bytes

update: !MyDataType {
  firstId: 1010101010101,
  secondId: 2222,
  thirdId: thirdId-1234,
  staticOne: staticOne-1234,
  staticTwo: 2020202020202,
  staticThree: "2016-07-22T12:34:56.789Z[UTC]", (1)
  staticFour: 1000000.0,
  changesA: 3000000000,
  changesB: 123456.0
}

1	the date/time is in quotes as it contains [ and ]

Update message as JSON - 242 bytes, smaller without formatting

"update":{"firstId":1010101010101,"secondId":2222,"thirdId":"thirdId-1234","staticOne":"staticOne-1234","staticTwo":2020202020202,"staticThree":"2016-07-22T12:34:56.789Z[UTC]","staticFour":1000000.0,"changesA":3000000001,"changesB":123457.0}

Update message as Binary YAML - 205 bytes

Æupdate¶⒑MyDataType\u0082µ٠٠٠ÇfirstId§µ>¶.ë٠٠٠ÈsecondId¥®⒏ÇthirdIdìthirdId-1234ÉstaticOneîstaticOne-1234ÉstaticTwo§j}l]Ö⒈٠٠ËstaticThreeµ\u001D2016-07-22T12:34:56.789Z[UTC]ÊstaticFour\u0090٠$tIÈchangesA£⒉^Ð²ÈchangesB\u0090٠!ñG

While Binary YAML is slightly smaller (< 20%) it’s main purpose is speed of encoding and decoding. This is most evident when you have lots of primitive types, and less of a benefit when you have string/datetime fields which are encoded as strings anyway.

By comparison DeltaWire is designed to compact the message by reducing duplication with a loss-less compression. This reduces the time writing to memory, which can speed up the serialization operation.

Two updates, one change for the changesA and one change for changesB - 10 bytes average

00000000 BA 00 89 00 80 04 BA 08  A8 C5 BA 00 89 00 80 04 ········ ········
00000010 BA 09 9A 05                                      ····

Wire Format

Size per message

YAML

268 bytes

JSON

242 bytes

Binary YAML

205 bytes

Delta Binary YAML

10 bytes

One of the challenges of using binary formats is human readability (as binary formats emphasis machine readability) For this reason, we have ensured you can automatically convert both Binary YAML and Delta Binary YAML to YAML without knowledge of the application or schema. The messages are still self describing allowing you to use this data even if the application’s data structure changes over time.

Doesn’t compression makes it slower?

It doesn’t have to be slower if the compression is simple enough. In fact writing/reading less data can improve performance. Writing/reading less data to memory, let alone to disk or a network, can improve latency and throughput by touching less memory and writing less data.

The test above is repeated 2,500 times resulting in 5,000 updates. The average time to serialize each message/udpate is recorded below.

Average time to serialize each update.

TextWire Took an average of 3,446 ns
JSONWire Took an average of 2,972 ns
BinaryWire Took an average of 1,473 ns
DeltaWire Took an average of 554 ns

What I find interesting is that the compressed wire format is also approximately 3-5x faster to serialize, as well as being approximately 20x smaller.

Conclusion

Using simple compression such as delta-ring can not only be much smaller such as 1/20 th the size, it can also be faster to serialize the data due to less memory being touched. In this example it as at least 3 times faster.

After delta-ring you can still use generic compression to obtain a further reduction of the size of data.

Contributing to Chronicle

Peter Lawrey — Thu, 21 Jul 2016 00:00:00 GMT

Looking to contribute to a high peformance Open Source library in Java. This may be a good place to start.

There is a number of ways to contribute to OpenHFT/Chronicle Software. You need to;

fork one of the projects,
try an improvement such as adding documentation, a unit test, or a fix.
issue a Pull Request.

I am not familiar with these projects

A good way to get a feel of these projects is to look at our projects web site

Chronicle Products

I also suggest you read this blog as it contains more detailed information about using our products in context. My presentation on Low Latency Microservices may also help.

Once you have found a product you are interested in, you can read the README for those products

For example if you click Chronicle Queue you can see links on getting started and the documentation on the right.

If you get stuck, you can ask questions on our Google Group and if you find a issue, please let us know via the Issue tab on GitHub for each project.

Latency for a set Throughput

Peter Lawrey — Wed, 20 Jul 2016 00:00:00 GMT

Without a set throughput, a latency measurement might be meaningless. Often you see benchmark results with throughput measurements, and sometimes the include latency measurements. However, latency varies with the throughput you perform, and without the throughput you have little idea of what the latency means. Conversely, without an idea of what latencies you find acceptable, the throughput you can achieve for an acceptable latency might not be the maximum throughput you can stress test your system up to.

Benchmarketing

When you are reporting on the throughput, or latencies of your software, you want to put forward the best numbers you can. However, you don’t want to fall into the trap of believing your own benchmarketing. As a technologist, you want tools that will help you find problems you need to solve.

A common question I get is; how do I convince my manager to allow me to spend more time optimising the application. The simple solution is to avoid benchmarketing and use tools which help you find problems.

To start with, look at the latencies of your system at given throughputs. Look not at the average latency or typical latency, but rather start with the 99%ile (worst 1 in 100 latency). After you have worked on the 99%ile, you can try improving the 99.9%ile. The 99%ile is often 4x higher than the typical latencies, even in well tuned systems, and can be many orders of magnitude higher if not tuned.

Co-ordinated ommission

One of the ways in which your testing tools can lie to you is to back off whenever your tested system isn’t performing well. Often this is a consequence of flow control.

Flow control is a very useful technique for avoiding overloading your system and improves performance. Flow control does a good job of smoothing out any bad latencies. However, if your purpose is to look for problems, it is not what you want. You don’t want a system to be able to tell a load generator: 'can you hold off for a while, I am having trouble keeping up'.

Gil Tene coined this benchmarking blind spotting of your load testing tool Co-ordinate Ommission, as your testing tool is effectively conspiring with the tested system to hide or dramatatically down play the importance of poor latencies.

A simple way to correct for this is to measure the end-to-end latency from the time a test should have started, not when it actually started. By doing this you bias the result to include any failure of the testing tool to start the test on time.

Setting the Throughput

How can we calculate the time a test should have started? We need to test for a given throughput. The simplest approach is to have a spacing between tasks and wait for that time to be reached.

long ratePerSecond = 1_000_000;
long intervalBetweenTasks = 1_000_000_000 / ratePerSecond;

long next = System.nanoTime() + intervalBetweenTasks;

for (int i = 0; i < tests; i++) {
    while (System.nanoTime() < next) {
        // busy wait
    }

    long start = next; (1)
    performTask();
    long time = System.nanoTime() - start;

    next += intervalBetweenTasks;
}

1	The important step is to not use the time it actually started, rather, the time it should have started.

How can we measure latency without a set throughput?

The simple answer is; you can’t. A latency by itself only tells you what can be achived for some throughput, and you might assume this is the latency for low throughputs, but it might not be.

Some systems perform worse with lower throughputs. For our software, we tend to see a small worsening of the performance below 50K events/second. This is due to the CPU not running as hot and the underlying interruptions of the system becoming more prominent. e.g. Your OS has a timer interrupt, typically 100 times a second, which you cannot turn off. At 100K events per second, this will impact your 99.9%ile, at 10K events per second this will impact your 99%ile, and below 100 events second it will impact every event.

Latency Test for Chronicle Queue replication

The following charts time how long it takes to:

Write a 40 byte message to a Chronicle Queue.
Have the write replicated over TCP.
Have the second copy acknowledge receipt of the message.
Have a thread read the acknowledged message.

The test is run for ten minutes and the distribution of latenices plotted.

There is a step in latency at around 10 million message per second jumps as the messages start to batch. At rates below this, each message can be sent individually.

The 99.99%ile and above are believed to be delays in passing the message over TCP. Further reserach is needed to prove this. In any case, these delays are much the same regardless of the throughput.

The 99.9%ile and 99.93%ile are a function of how quickly the system can recover after a delay. The higher the throughput, the less head room the system has to recover form a delay.

Summary

In the test above, the typical latency varied between 14 and 40 micro-seconds, the 99%ile varied between 17 and 56 micro-seconds depending on the throughput being tested. Notably, the 99.93% latency varied between 21 micro-seconds and 41 milli-seconds, a factor of 2000.

Table 1. Possible Throughput results depending on acceptable latencies
Acceptable Latency	Throughput
< 30 micro-seconds 99.3% of the time	7 million message per minute
< 20 micro-seconds 99.9% of the time	20 million messages per minute
< 1 milli-seconds 99.9% of the time	50 million messages per minute
< 60 micro-seconds 99.3% of the time	80 million message per minute

Conclusion

Your choice of what is an acceptable latency can determine the throughput a suspect can support and meet your Service Level Agreement. Conversely, your choice of throughput can change the latency distribution you get.

When measuring performance you have to consider both latency distribution and throughput.

Batching and Low Latency

Peter Lawrey — Sat, 09 Jul 2016 00:00:00 GMT

This is testing the next release of Chronicle Queue 4.5.0

Why batch your data?

Batching of multiple messages or updates into a single transaction is a common technique for improving performance, in particular it is useful for increasing throughput (messages per second) when the latency (time to process a single message) is high. However when latencies are low, can batching still help?

A couple of weeks ago, I was looking at testing and optimising our Chronicle Queue replication over TCP. One of the first tests I did was to see how batching changed the performance and it made a dramatic difference, and I assumed this was a bug, batching shouldn’t help a well tuned low latency system. Now I have had a chance to optimise replication, does batching make much difference?

Why do batches help/hinder?

When your system has an operation with a significant latency, you can utilise more of the available bandwidth by increasing the batch size.

Imagine you have a questionaire with 10 questions you want to ask someone. You could send an email for each question and wait for the response to each question before asking the next one. Say it takes 1 minute to answer each question but 10 minutes to send an email, have the person notice it and for you to notice the response.

sending one question at a time, means each question takes 10 + 1 minutes or 110 minutes in total.
sending all 10 questions at once means that the whole questionaire takes 10 + 1 * 10 minutes, or 20 minutes in total.

It makes sense to ask all your questions at once and get the replies in one go.

However, there is a problem, what if you

don’t know all the questions in advance because you are still thinking of them. You have to wait to think of the questions, and you might not know how long this will take.
might need to ask each question in response to a previous answer.

The longer you wait to build a batch, the more you delay the processing of the messages you have.

Batching works best when you know how many messages you are about to get or you know what delay would be acceptable and you can delay sending the messages or committing the transaction for that amount of time.

What if you want to process each message as soon as possible?

What is being tested?

I am testing the latency under a fixed throughput for publishing a small 40 byte message including time to

write the message to the persisted queue.
read the message and write over TCP.
read the TCP socket and write it to a copy of the queue
read the message from the queue copy.

To correct for co-ordinated omission, the sending timestamp used is the time the message should have been sent, indead of the time it was actually sent. For the received time, I used System.nanoTime() to get high resolution timing. The replication is over loopback for a consistent nanoTime(). As I am interested in the outliers, I am assuming the overhead using a low latency 10 GigE network wouldn’t impact these results significantly. The highest throughput test here would use less than 20% of a 10 GigE network connection as each message is small.

The test spends 30 seconds warming up, and 120 seconds running. The distribution of latencies for each message is summarised.

As I have discussed in prevous posts, I am focusing on minimising the 99%ile latency (worst 1 in 100). On the system, I am reporting no more than 100 million messages per second as this is close to the point there the 99% starts to increase dramatically. i.e. it is close the limit of what this system can process in soft real time.

A Centos 7 machine with i7-4790 and 32 GB of memory was used.

End to End latency for different batch sizes

Table 1. 99%ile latency end to end
Batch Size	10 million events per minute	60 million events per minute	100 million events per minute
1	20 µs	28 µs	176 µs
2	22 µs	29 µs	30 µs
5	38 µs	22 µs	27 µs
10	72 µs	26 µs	27 µs
20	125 µs	34 µs	31 µs

1 µs is 0.001 ms or 1 millionth of a second.

So you can see that batching helps for size of one to five 40 byte messages when the delay between messages is small. However when the delay between messages is relatively large, in this case, every 6 µs, having to wait for enough messages to build a batch hurts the latency.

The high latency for the single message at a time for 100 Mmsg/s may yet prove to be a performance bug which can be solved later, but for now, batching could help reduce the jitter, but you don’t want any more batching so you need to avoid any impact. In this case, I would consider a batch of two, rather than a larger batch size.

Why not look at the typical or average latency?

The typical/average latencies are usually better which is why vendors like to report them. However, they only tell you what the performance looks like momentarily when everything is going well. By looking at the 99%ile or 99.9%ile you are looking at how something performs when things are not going well.

By comparison, the typical latencies all look fine, and you would not know that batching might help at 100 messages per minute.

Table 2. 50%ile latency end to end
Batch Size	10 million events per minute	60 million events per minute	100 million events per minute
1	10 µs	13 µs	16 µs
2	13 µs	13 µs	13 µs
5	22 µs	13 µs	13 µs
10	36 µs	15 µs	13 µs
20	68 µs	20 µs	15 µs

Having to wait for a whole batch adds latency and this can be far higher than the time you save. You want your batching to be no larger than necessary.

How is batching used internally?

While batching messages published made a little difference in the example above, we use batching internally because it can make a big difference when passing lots of small messages over TCP.

As the overhead of passing data over TCP is relatively high, it makes sense to group available data up to some threshold such as 4 KB. When reading the queue you can determine whether more data is pending as you read it.

In particular, making a socket write can be 5 - 10 µs. However we are writing a message around a micro-second or less, this would add an enormous amount to every message if they were sent individually. By having a background thread batching up these messages we can reduce the latency impact of the socket write.

Conclusion

Batching can be helpful in reducing the impact of latency to improve throughput. When you are reaching the limit of the throughput you can achieve, batching can improve the overhead and give you higher throughputs and lower latencies.

However, batching is not always possible or appropriate and you want a solution which has low latencies even when you are not reaching the limits of your throughput.

A quick look at the 99.9%ile.

These worst 1 in 1000 has mixed result which needs further investigation. I suspect, the OS might be a cause of this jitter. Note: we didn’t use thread pinning and that might have made a difference.

Table 3. 99.9%ile latency end to end
Batch Size	10 million events per minute	60 million events per minute	100 million events per minute
1	901 µs	705 µs	5,370 µs
2	500 µs	1,610 µs	2,000 µs
5	80 µs	1,540 µs	2,160 µs
10	3,080 µs	1,470 µs	2,000 µs
20	336 µs	1,210 µs	1,670 µs

Table 4. 99.9%ile latency to publish without replication
Batch Size	10 million events per minute	60 million events per minute	100 million events per minute
1	1.2 µs	1.3 µs	1.5 µs
2	1.2 µs	1.3 µs	1.5 µs
5	2.4 µs	1.5 µs	1.6 µs
10	9.5 µs	1.7 µs	1.8 µs
20	11 µs	12 µs	2.1 µs

More investigation is required to draw any conclusions.

Goldilocks Microservices

Peter Lawrey — Thu, 30 Jun 2016 00:00:00 GMT

How to structure microservices?

When structuring microservices we have to consider;

how fine grain should our components be?
how distributed should they be?

I believe it’s important to treat these as separate concerns, even to the extent of ensuring your business logic components are not dependant on the choice of transport, or even whether you have a transport at all.

How do we right size microservices?

The business component in your system are;

the smallest deployable unit of code and data.
functionality which could makes sense to a business user based on your requirements.

The right size for your components can depend on why you chose microservices.

is it to scale the development effort, allowing each developer to work as independently as possible. (Developer efficiency)
is it to scale the utilisation of the hardware, allowing each CPU or server to work as independently as possible. (Computer efficiency)

Often we want some of each where the number of components under development is likely to be a function of the number of developers and the number of deployed instances of those components is likely to be a function of the number of CPU or servers.

Unless you know performance is a key concern, I would make sure that you prioritise developer efficiency. I would expect for most projects to have around one to three business components per developer.

How do we deploy our components?

A microservice is a business component with the option of a transport. I believe having an optional transport is an important consideration because the business component shouldn’t be influenced too heavily by the choice of transport and not having a transport can be helpful at different stages of the project.

When you are writing unit tests and debugging your business component, you shouldn’t need to have a transport involved. If you want to see how two components interact you should be able to create a simple program which creates two or more compoenents, run from your IDE and see how they work together in the same thread.

Levels of distribution

There is different levels of distribution you want to consider. Initially you might want no transport at all, provided you ensure these component can be distributed. Later you need either fine grain or course grained distribution, but over time as the component matures you don’t need the overhead of managing lots of services and you want the ability to consolidate them.

Instances are in same logical task and are wired together with no layer between them.
Instances are in separate logical tasks, but share the same thread pool ^[1].
Instances are in separate thread pool, but in the same process.
Instances are in separate OSes, but in the same physical machine.
Instances are in the same data centre, but different machines.
Instances are in different data centres.

For performance, I favour #1, #2 & #3, for testing and development I favour #1 and #3 and for High Availability you need either #5 and #6.

If you don’t need to distriibute instances across machines for HA, you want your instances to be no more seperate than needed. The degree of separation desirable can change over time. When a component is being added to production initially, it can be useful to be able to deploy, upgrade and restart that component without impacting the rest of the system. However as the component stablises and is not changing so much you may want to reduce the overhead of managing this service and include it in a process which has multiple services. You might find the service uses a trivial amount of CPU and you can combine it into the same thread pool as other services. If it turns out it’s interaction with another instance is highly coupled you might wire them together as a single component.

Migrating to Microservices

Say you have a monolith, how do you migrate to using microservices? Do you have to re-engineer your entire solution? NO. Migrating is easier than it sounds as the main advantage for microservices is in the early stages of development when you are putting a service into production. Anything which is running well in your monolith, leave it there. Anything you need to add or make major changes to, move it into it’s own service while it’s under development and maturing. You can imagine this as one monolith, planet sized microservice and a number of smaller satelite micro-services surrounding it.

Flexable Design

You want your developers to work efficiently and your system to make good utilisation of your servers. You don’t want the choices you made at the start to bind you into a solution you will regret later. If you use a flexable design, you can maximise productivity, and ensure you use microservices to the extend they are helping you, but without the disadvantages of over using this technique.

Reviewing Exception Handling

Peter Lawrey — Tue, 21 Jun 2016 00:00:00 GMT

When developing an application it can be hard enough to get the happy path working, let alone worry about what might happen when something goes wrong.

I have asked a number of developers recently what they do when they get an exception and usually they log it or pass it back to the user.

What are some alternatives? If you have to pass on the exception how might you do that?

When to consider exception handling?

Ideally, you should be only catching an exception when you know what to do with it. If you don’t think you can add value, pass it back to the caller. I highly recommend letting your IDE manage the updating of the method signature, as this can be tedious to do manually.

Even if you give exception handling some consideration in your code, it is worth doing a periodic review of your exception handling code to make sure that they are being handled appropriately.

Handling the Exception

Catch an Exception to fall back.

When an expected Exception occurs you can fall back to a default result.

Simple fallback

private static String getHostName0() {
    try {
        return InetAddress.getLocalHost().getHostName();
    } catch (UnknownHostException e) {
        return "localhost";
    }
}

This method looks for a field in a class. If this fails it looks for a field in it’s super class. This fall back behaviour requires that the appropriate exception is caught.

The discard exception is added to the original with addSuppressed. Whether this is a good idea, depends on each case.

Fallback on a specific exception

/**
 * Get the Field for a class by name.
 *
 * @param clazz to get the field for
 * @param name  of the field
 * @return the Field.
 * @throws IllegalArgumentException if no field with that name could be found.
 */
public static Field getField(Class clazz, String name) throws IllegalArgumentException {
     try {
         Field field = clazz.getDeclaredField(name);
         field.setAccessible(true);
         return field;

     } catch (NoSuchFieldException e) {
         Class superclass = clazz.getSuperclass();
         if (superclass != null)
             try {
                 return getField(superclass, name);
             } catch (Exception e2) {
                 e.addSuppressed(e2);
             }
         throw new IllegalArgumentException(clazz + " does not have a public field " + name, e);
     }
 }

Signal for special handling.

Special handling may be a delibrate exception to say this component is no longer valid and shouldn’t be used again.

Catch an Exception in a nested call and remove a subscriber which is no longer valid.

try {
 for (int i = 0; i < kvStore.segments(); i++)
     kvStore.entriesFor(i, e -> subscriber.onMessage(e.getKey(), e.getValue()));

} catch (InvalidSubscriberException dontAdd) {
 topicSubscribers.remove(subscriber);
}

The checked exception is thrown inside a lambda which expects this specific exception.

Wrap an Exception with AssertionError

In this case, the Field returned by getField shouldn’t ever throw an IllegalAccessException, so it has been wrapped with an AssertionError.

It only make senses to wrap an Exception with an AssertionError when you know this is something which should never happen (not something you hope will never happen)

Exception is not possible

/**
 * get a the value of a field by name.
 * 
 * If the name has a path with a / it is split into names and navigated into the object. e.g. "a/b" will look for a field "b" in the object in field "a"
 * 
 * If any reference in the path is null, the return is null.
 *
 * @param obj  Object to extract the value from
 * @param name path to the field.
 * @return the value of the field as an object if found, or null if any field in the path was null.
 * @throws IllegalArgumentException if the field could not be found.
 */
public static  V getValue(Object obj, String name) throws IllegalArgumentException {
    for (String n : name.split("/")) {
        Field f = getField(obj.getClass(), n);
        try {
            obj = f.get(obj);
            if (obj == null)
                return null;
        } catch (IllegalAccessException e) {
            throw new AssertionError(e);
        }
    }
    return (V) obj;
}

Set the interrupted flag if caught

When a thread is interrupted, it should remain so until the overall task is

/**
 * Silently pause for milli seconds.
 *
 * @param millis to sleep for.
 */
public static void pause(long millis) {
    long timeNanos = millis * 1000000;
    if (timeNanos > 10e6) {
        try {
            Thread.sleep(millis);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupted();
        }
    } else {
        LockSupport.parkNanos(timeNanos);
    }
}

Passing on the exception

Using a callback to handle the exception.

Using a callback allows a developer using a library to control how exceptions should be handled.

for production you might want to shutdown the whole server on a fatal error, log warnings and ignore debug messages.
for unit tests you might wish to capture your exceptions to see if any error occurred, or only the expected error occured.

An interface you could call in the event of an Exception.

@FunctionalInterface
public interface ExceptionHandler {
    default void on(Class clazz, Throwable thrown) {
        on(clazz, "", thrown);
    }

    default void on(Class clazz, String message) {
        on(clazz, message, null);
    }

    /**
     * A method to call when an exception occurs. It assumes there is a different handler for different levels.
     *
     * @param clazz the error is associated with, e.g. the one in which it was caught
     * @param message any message associated with the error, or empty String.
     * @param thrown any Thorwable caught, or null if there was no exception.
     */
    void on(Class clazz, String message, Throwable thrown);
}

We have an ExceptionHandler which opens a web page on Google or Stackoverflow approriate for the error, or using a fallback Exception handler.

    try {
        if (Jvm.isDebug() && Desktop.isDesktopSupported())
            Desktop.getDesktop().browse(new URI(uri));
        else
            fallBack.on(clazz, message, t);

    } catch (Exception e) {
        fallBack.on(clazz, message, t);
        fallBack.on(getClass(), "Failed to open browser", e);
    }

Additional printing for debugging only.

Sometimes an error which would be too "noisy" for production code might be useful in trying to trace a bug in the code.

In this case, we check whether the code is running in the debugger and log an exception we normally expect to handle queiter or silently.

Additional logging when attempting to reconnect to a TCP server.

if (Jvm.isDebug())
    e.printStackTrace();
// continue handling the exception.

Using printStackTrace makes it clearer this is not intended for production use and makes it easier to find and remove later.

Adding the Exception to the result.

In a method which does a best attempt at decoding some data, and the caller wants to see as much as could be decoded, even if an exception occurred.

Add the Exception to the StringWriter.

} catch (Exception e) {
    e.printStackTrace(new PrintWriter(writer));
    }

Passing on a check exception so it can be caught

Rethrow as an unchecked exception.

In this case, rather than wrap the checked exception as an unchecked one, the Exception can be blindly re-thrown as the original exception

This is useful when a checked exception is thrown inside a lambda which doesn’t expect a checked exception.

public List collectFiles(List filenames) throws IOException {
    return filenames.stream()
            .flatMap(f -> {
                try {
                    return Files.lines(Paths.get(f));
                } catch (IOException e) {
                    throw Jvm.rethrow(e);
                }
            })
            .collect(Collectors.toList());
}

Where Jvm.rethrow is implemented as follows

/**
 * Cast a CheckedException as an unchecked one.
 *
 * @param throwable to cast
 * @param        the type of the Throwable
 * @return this method will never return a Throwable instance, it will just throw it.
 * @throws T the throwable as an unchecked throwable
 */
@SuppressWarnings("unchecked")
public static  RuntimeException rethrow(Throwable throwable) throws T {
    throw (T) throwable; // rely on vacuous cast
}

However, this is really a hack to get around the fact that the Function used, doesn’t support a checked exception. A better solution, if you can choose the type of lambda is to have one which expects an Exception. See next.

Capturing a Throwable thrown in a plain thread in a unit test.

Instead of an Executor service or a parallelStream(), sometimes you just want to use a plain thread for testing purposes. You still need an exception thrown in that thread to cause the test to fail.

Throwable[] thrown = { null };

Thread t = new Thread(() -> {
    try {
        // something
    } catch (Throwable e) {
        thrown[0] = e;
    }
});
t.start();

// check something.

t.join();

if (thrown[0] != null)
    throw thrown[0];

Using a lambda which expects a checked exception.

We have a number of functional interfaces which work just like the built in classes of a similar name except they expect to throw a checked exception.

Three of the FunctionalLambdas which can throw a Checked Exception

@FunctionalInterface
public interface ThrowingConsumer {
    /**
     * Performs this operation on the given argument.
     *
     * @param in the input argument
     */
    void accept(I in) throws T;
}

@FunctionalInterface
public interface ThrowingFunction {
    /**
     * Applies this function to the given argument.
     *
     * @param in the function argument
     * @return the function result
     */
    R apply(I in) throws T;
}

@FunctionalInterface
public interface ThrowingSupplier {
    /**
     * Gets a result.
     *
     * @return a result
     */
    V get() throws T;
}

Using a ThrowingConsumer

In the following example, you can pass a consumer to forEachChild which can throw a checked exception, which is then thrown back to the caller.

If the acceptor throws a checked Exception, the method throws the same Exception

public  void forEachChild(@NotNull ThrowingConsumer consumer) throws T {
    for (Asset child : children.values()) {
        consumer.accept(child);
    }
}

onMessage can throw an InvalidSubscriberException which throw out of this method.

void bootstrapTree(@NotNull Asset asset, @NotNull Subscriber subscriber) throws InvalidSubscriberException {
    asset.forEachChild(c -> {
        subscriber.onMessage(ExistingAssetEvent.of(asset.fullName(), c.name()));
        bootstrapTree(c, subscriber);
    });
}

Using temporarily checked exception.

One way to ensure your documentation and handling of unchecked exception is correct is to make them temporarily checked. I recently did this for one of our custom exceptions and ended up changing 65 files. In many cases, the exception was documented as occuring, but didn’t and in many cases it could occur but wasn’t documented. In a couple of cases, this forced me to consider whether this was the most appropriate exception to be throwing and I changed it. I would say I ended up fixing around 6 bugs as a part of this review.

We also have a checked version of many built in unchecked exceptions and we use this to review those as well from time to time. https://github.com/OpenHFT/Chronicle-Core/tree/master/checked-exceptions

What do we do in our libraries?

I reviewed our OpenHFT libraries in terms of exception handling and refactored it quite a bit as well as fixing a number of issues. Afterwards the profile looked like this

In the end about 30% were hndled in the code itself. The FATAL ones mean the code is broken, and the DEBUG ones are expected to be ignored, possibly logged. The wrapped and rethrown exceptions expect the caller to handle the exception in some way.

Conclusion

Knowing when to consider about exception handling and what to do about it is not easy. Having checked exceptions can help you with that revirew when you are ready to do that.

Until you are ready to think about how to handle these exceptions I suggest passing the exception to the caller rather than logging them and pretending they didn’t happen.

Distributing Common Java APIs

Peter Lawrey — Sat, 04 Jun 2016 00:00:00 GMT

Distributing data stores vs Private data stores in Microservices

Distributing data containers e.g. Maps, can be a way of avoiding having to think too much about distributing your application. Your business logic is much the same, and it is your data collections which are visible to all your services.

Using centralised or even distributed data stores have a number of scalability issues, as it requires every low level data access to be distributed in a generic way which isn’t optimised for particular business requirements.

Distributing business components with private data stores is the favoured approach of Microservices and it limits the "surface area" of each service which reduces security issues, performance considerations and gives you more freedom for independant changes to service’s data structures.

In this review, I will be focusing on distributed data containers, largely because the interfaces are available in the JDK and available for everyone to look at. I expect the conclusions drawn here are broadly similar for Business focused APIs, though each business component will vary.

Review of different interaction types for common Data store APIs in the JDK.

I have reviewed a number of APIs in the JDK using a tool available here

The interfaces reviewed were:

ScheduledExecutorService (incl ExecutorService)
ReadWriteLock
Lock
BlockingDeque (incl BlockingQueue)
List (incl Collection)
ConcurrentNavigableMap (Incl SortedMap)
ConcurrentMap (incl Map)
NavigableSet (incl SortedSet, Set)

Interfaces higher up the inheritance tree where not included to avoid duplication. However there is still some duplication e.g. Set and List are Collection(s).

Request-Response - 104 methods

Request-Proxy - 29 methods

Request-Visitor - 26 methods

Asynchronous Lambda - 18 methods

7 methods

Default Call - 22 methods

"Default Call" means the default implimentation of the interface is appropriate an can be executed on the caller.

Request-Visitor is variation on Request-Repsonse but rather than passing a Data Transfer Object, a Command Object is passed.

Request-Callback is a variation of Request Subscription where you expect to get exactly one invocation. There where no examples here.

As I have noted in the past, while I believe using Lambda style asynchronous calls is ideal, this is not a natural interaction for many APIs and wouldn’t work so well in these methods.

Lastly, the Client Injected Handler might only make sense for a distributed component, and I wouldn’t expect it to occur in an API which wasn’t designed to utilise it.

Request-Response examples

// from Map
V get(Object key);

// from NavigableMap
V lastEntry();

// from Lock
boolean tryLock();

Request-Proxy examples

// from ReadWriteLock
Lock readLock()

// from Lock
Condition newCondition();

// from ConcurrentNavigableMap
NavigableSet descendingKeySet();

// from ScheduledExecutorService
ScheduledFuture scheduleAtFixedRate(Runnable run, long delay, long period, TimeUnit timeUnit)

Request-Visitor examples

// from List
Collection removeIf(Predicate test);

// from ConcurrentMap
V ConcurrentMap.computeIfPresent(K key, BiFunction mergeFunction);

Asynchronous Lambda examples

// from BlockingDeque
void addFirst(E element);

// from Executor
void execute(Runnable runnable);

// from List
void replaceAll(UnaryOperator oper); // also a Visitor

Default Call examples

// from ConcurrentMap
default V getOrDefault(Object key, V defaultValue) {
    V v;
    return ((v = get(key)) != null) ? v : defaultValue;
}

// from BlockingDeque
Stream parallelStream(); (1)

1	later the paralellStream itself could have it’s work distributed across a grid of machines.

Conclusion

The Request-Response call is the most often used in this example. While you can avoid using it in a distributed system, there is often cases where using Request-Response is just simpler e.g. for control functions which don’t have to scale as much as events which occur thousands of times a second.

The Request Proxy and Asynchronous Lambda calls have some natural use cases and have been around for some time.

The Request Visitor use cases where all added in Java 8 with the inclusion of Lambdas.

In some cases, a default method on the client might be enough. This will usually call through to a method which does have to go across the transport. Ideally this should result in just one method call. If a default method has more than one method call it might be more efficient to execute this on the server.

The Request Callback wasn’t use in these cases, but it can be an effective way to transform a Request-Response call into an asynchronous call, although it requires an API change.

Footnote on Request-Callback

What I have done in the past is make Request-Callback interchangeable with Request-Response where the Callback is added as the last argument. This could be kept visible only to the client, and the server doesn’t need to know. e.g.

Request-Callback examples calling Request-Response

// from Map
default void get(Object key, ThrowableConsumer consumer) {
    V v;
    try {
        v = get(key);
    } catch (Throwable t) {
        consumer.onException(t);
        return;
    }
    consumer.accept(v);
}

Modelling Microservice Patterns in Code

Peter Lawrey — Tue, 17 May 2016 00:00:00 GMT

Service Interactions

There is a number of simple interactions a service can support. Which pattern is best for your application can depend on what an existing application expects, and what latency requirements you have. Broadly speaking these interactions fall into client-server and peir-to-peir messaging.

For peir-to-peir messaging, one approach to take is Lambda Architecture however from supporting GUIs, client - server models can be easier to work with.

I feel it is important to design components which could be tested and debugged together, as in a monolith, but can be deployed as multiple right sized services to different threads, JVMs, or machines.

Client-Server Messaging

Client-Server messaging is often used in a synchronous way. Asynchronous messaging can support multiple concurrent requests, reducing the cost of network latency and increasing throughput. Asynchronous messaging can perform best when it is latency, rather than network bandwidth which is your limiting factor.

Using a human readable protocol

It is useful to be able to see the underlying messages in readable text. I suggest using either text or a binary format which can be automatically converted to text to make it easy to check the data sent. I suggest using YAML as the human readable format as;

it is designed to be human readable instead of a subset of another language/format.
it supports messages, types and comments.
it can be sent as binary for performance and converted to text as required

A human readable format allows you to quickly determine whether it is the sender or receiver which is behaving incorrectly. It can allow you to see and stop undesirable behaviour which doesn’t show up in a test. e.g. are there too many heartbeats.

Request/Response

The client sends a message to a server. That message contains a message type to choose an action to perform on the server and usually includes a payload of data. The response is usually just data.

For every message the client sends the server, it response with a single message. Often the client waits for the response, however the client can process the response asynchronously to improve throughput.

With asynchronous response processing, the client can send multiple requests over the same channel rather than wait for each one to complete.

Synchronous server with synchronous client

interface OneRequestResponse {
    Response requestType(RequestData data);
}

Synchronous server with asynchronous client

interface OneRequestResponse2 {
    void requestType(RequestData data, Consumer responseConsumer);
}

Using this API could be translated into YAML such as

Synchronous server with synchronous or asynchronous client

# client sends to server
---
requestType: {
  data: 1,
  text: my text
}

# server sends to client
---
reply: !MyResponse {
  moreData: 128,
  message: Success
}
...

Request/Proxy

This is like request/response, except the object returned is a proxy for further events. This is useful when the value returned represents a complex, or very large object.

This is used in Map returning a key set or values which is a proxy to the underlying map.

Method on java.util.Map

public interface Map {

    Set keySet();

    Set> entrySet();

    Collection values();
}

Using a proxy gives access to data without having to pass all the data from the server to the client.

Method on java.util.Map

# client sends to server
--- !!meta-data # binary
csp: /map/my-map?view=map
---
keySet: []
---
entrySet: []
---
values: []

# server sends to client
---
reply: !set-proxy {
   csp: /map/my-map?view=keySet
}
---
reply: !set-proxy {
   csp: /map/my-map?view=entrySet
}
---
reply: !set-proxy {
   csp: /map/my-map?view=values
}

# client sends to server
--- !!meta-data # binary
csp: /map/my-map?view=keySet
--- !data # binary
size: []
---

# server sends to client
---
reply: 128000 (1)

# client sends to server
--- !!meta-data # binary
csp: /map/my-map?view=keySet
--- !data # binary
remove: "key-111"
---

# server sends to client
---
reply: true (2)
...

1	no need to send 128,000 keys just to determine how many there was.
2	key was removed on the server, not a copy sent to the client.

Request/Callback

The client sends a message to a server. That message contains information to call an action on the server and usually includes a payload of data. The callback is also a message containing an action and data.

This is like a Subscription except that exactly one event is expected to be returned.

The use of a callback provides a richer interaction between the caller and callee.

Synchronous server with a callback

interface OneCallback {
    void resultOne(ResultOne result);

    void resultTwo(List results);

    void errorResult(String message);
}

interface OneRequestCallback {
    void requestType(RequestData data, OneCallback callback);
}

The client could be configured to either wait for the server to call the callback, or handle the callback asynchronously. The thread which performs the method in the callback will be on the client side.

Synchronous server with a callback

# client sends to server
---
requestType: {
  data: 1,
  text: my text
}

# server sends to client
---
resultTwo: [
  {
      moreData: 128,
      message: Success
  },
  {
      moreData: 1111,
      message: Failure
  }
}
...

Request/Visitor

The client sends one or two visitors to the server to apply to local objects or actors. This visitor can be an update which applied atomically to an actor, and/or a vistor can be applied to retrieve specific information.

Pass a function to apply on a server for a given key

interface KeyedResources {

    void asyncUpdate(String key, Visitor vistor);

     R syncUpdate(String key, Visitor updater, Function returnFunction);

}

This approach allows the caller to apply an operation to an actor without needing to know where that actor is.

Pass a function to apply on a server for a given key

# client sends to server
---
asyncUpdate: [
    "key-5",
    !MyVisitor { add: 10 }
]
# no return value
--- # subtract 3 and return x * x
syncUpdate: [
    "key-6",
    !MyVisiitor { add: -3 },
    !Square { }
];

# server sends to client
---
reply: 1024
...

Request/Subscription

By requesting a subscription, a client can receive multiple asynchronous events. This can start with a bootstrap of existing information, followed by live updates.

Once a subscription ahs been made, it should be altered, or cancelled

Pass a function to apply on a server for a given key

interface Queryable {

     Subscription subscribe(Filter filter, Function returnMapping, Subscriber subscriber);

}

interface Subscription {
    // change the current filter.
    void setFilter(Filter newFilter);

    void cancel();
}

Up to this point, all the message are actions lived with a single response. In Chronicle-Engine, we associate a csp or Chronicle Service Path for each actor, and a tid or Transaction ID with each operation. This allows multiple concurrent actions to different actors. This routing information is passed in meta data, with the actions for that destination following

Pass a function to apply on a server for a given key

# client sends server
--- !!meta-data # binary
csp: /maps/my-map
tid: 12345
--- !!data # binary
subscribe: [
   !MyFilter { field: age, op: gt, value: 18 },
   !Getter { field: name }
]
request: 2 # only send me two events for now.

# server sends client
--- !!meta-data # binary
tid: 12345
--- !data-not-complete # binary
reply: Steve Jobs
--- !data-not-complete # binary
reply: Alan Turing

# client sends server
--- !!meta-data # binary
tid: 12345
--- !data # binary
cancel: []

# server sends client
--- !!meta-data # binary
tid: 12345
--- !data # binary
cancelled: "By request"
...

Client Injected Handler

This approach allows the client to version and configure which handlers are used on the server on the client’s behalf. In particular, this is useful when supporting multiple versions of clients concurrently.

Client passes a handler to intergate with the server and act it’s behalf

interface AcceptsHandler {

    /**
     * The accept method takes a handler to pass to the server.
     * and it returns a proxy it can call to invoke that hdnler on the server.
     */
     H accept(H handler);
}

A simple example of a handler we use is for heartbeats

# client sends server
--- !!meta-data # binary
csp: /
cid: 1
handler: !HeartbeatHandler {
    heartbeatTimeoutMs: 10000
    heartbeatIntervalMs: 2000
}
...

This allows different clients to be working with dfferent versions of heartbeat handlers at the same time, supporting old and new clients with a single server.

Conclusion

In addition to Lambda Architecture models for back end, peir-to-peir services, we can support a rich set of interactions between clients and servers.

These interactions can be performed without a transport i.e. one component directly calls another to make testing and debugging easier.

Simple Asynchronous Microservices using Lambda Architecture.

Peter Lawrey — Mon, 16 May 2016 00:00:00 GMT

Lambda Architecture

Lambda Architecture is a simple, powerful, though limited example of a Microservice. As it is so simple, you want to use it as much as possible, to expose the more complex services/component in your system which cannot support this interaction model.

Lambda Architecture depends on a data model with an append-only, immutable data source that serves as a system of record. It is intended for ingesting and processing timestamped events that are appended to existing events rather than overwriting them. State is determined from the natural time-based ordering of the data.

A translation function

The microservice takes messages in and produces messages out. It’s input is an append only data structure, and the function has no state of it’s own which is not derived from it’s inputs.

This simple translator is useful for taking messages from external systems and normalising those messages into an internal format. Conversely, you can convert messages from an internal message format to an external format.

Working with history

Notionally, all the messages to date form an input of the function. Replaying every message on every new message is too expensive. You can instead cache key information derived from those messages to provide a real time solution.

This is a variation on the standard function where state is retained based on it’s inputs. Provided this is only an optimisation, rather than a change in behaviour, this is still a function. i.e. a function of all the messages, rather than just one message.

Having a function with private state gives it memory and makes it practical for more complex operations such as control (permissioning, turning functionality on and off), matching of messages over time (e.g. order matching)

Putting these together

By having translators for messages in and out, as well as a central control system, you can build a more complex processing system.

The functionality here should form your critical path. You want a simple message to be able to pass from one end of your system to the other in the shortest time possible. In Java this can mean as low as 10 micro-seconds 99% of the time. As well as being fast it is simple to test each function independently, as well as test this without transports for ease of debugging.

Non-critcial path functions.

Not everything can or should be on the critical path. There will be operations which either use a lot of CPU, or need to obtain data from external systems such as databases. You need a way to interact with these systems without impacting the critcial path. Using feedback is a simple way to achieve this.

In this diagram, the slower functions are CPU bound strategies, but you could have components which obtain data from a database for example, without slowing the critical path.

Reading more

You can read my earlier posts on how to implement these Lambda Architecture components in Java and easily test them. Micro services for Performance as well has how you can implement a simple service to asynchronously access a JDBC database A JDBC Gateway Microservice

For low latency, high throughput persistence we recommend using Chronicle Queue which is Apache 2.0 open source project available at https://github.com/OpenHFT/Chronicle-Queue and on Maven Central

Microservices are about applying a group of Best Practices

Peter Lawrey — Sat, 30 Apr 2016 00:00:00 GMT

Microservices Denial

A number of times clients have said; they can’t imagine their organisation using Microservices. I found this surprising as I know those people are using many of the principles of Microservices already.

I can understand that they feel no need to join the hype around microservices, but the reality is, like it or not, you are most likely using some of the best practices Microservices advocates.

Stages of denial

It all seems like hype, we don’t go in for that.
Perhaps not all hype, but does it really mean anything.
It all sounds pretty familiar.
It sounds like what we are doing already.

Formally or informally, most likely you have been following some best practices already.

Adopting Best Practices.

Perhaps you don’t like the name Microservices, and perhaps not all the different things people associate with Microservices are right for your team, your projects. Instead lets consider how do you formalise what you are trying to achieve and finding a clearer path to adopting best practices.

Why do this at all?

Within larger teams there can be some disagreement as to how to proceed. There can be strong feelings on what is bad, or broken about what you have and the temptation is to just throw away large portions of what you have or throw away everything.

The problem with doing this is you risk taking out the old known problems and putting in more new unknown ones. You need to make changes, possibly selectively radical changes, which are manageable and achieveable for your team.

By formalising what you are talking about, even using buzz words, you can state more clearly what you are trying to achieve and why. It gives you a common language in which to communicate your ideas. It can give you a better perspective of where you are today and where you need to be.

Best Practices Scorecard.

Using a scorecard you can quickly see where you are today, where the quick wins are and where you need to be in the medium term. A big part of the question; where are we today, is just rebranding what you have already. This review can lead you to see in some ways you are not in as bad position as you might have imagined, while putting in to stark contrast the areas with the most opportunity to improve.

Initial steps

The initial steps I suggest are

rebrand what you have; you will have some best practices already.
quick wins; low risk changes could help improve your position.
medium term improvements; what do you need to achieve in the next six months.

An example.

This is a score card I put together for a senior manager for firm of over 60 developers. In the space of an hour we went from not considering Microservices, to being convinced it was a path to enhance their solutions.

Table 1. Best Practice Scorecard
	Today	Quick Wins	6 Months
Simple bsuiness component based design.	★★	★★☆	★★☆
Distributed by JVM and Machine	★★	★★	★★☆
Service Discovery	★	★☆	★★
Resilience to failure	★☆	★☆	★★
Transport agnostic	★	★☆	★★
Asynchronous messaging.	★☆	★★	★★
Automated, dynamic deployment of services.	★☆	★★	★★☆
Service local private data sets.	☆	★	★
Transparent messaging.	☆	★★	★★☆
Lambda Architecture	★	★★	★★★

This is not intended to be an exhaustive list. It is what we reviewed in the first hour.

The last two areas were recognised as the most significant areas for improvement as they are both low risk but highly likely to reveal the cause of some of the recurring issues they have been having.

In particular, performance and stability issues require quality, detailed information about what your system is doing so you can take an informed view as what needs to be changed to fix it.

Conclusion

Whether you love or loath Microservices, most likely you are using some Best Practices, and a review of the Best Practices used in Microservices may prove to be useful in seeing how you can improve what you have.

Contact Us.

Chronicle Software provides one and two week workshop for starting new projects, training and consulting. We provide Professional Support. We sponsor open source software on github as well as a low latency FIX Engine and enterprise versions of a high performance Queue, a key value store Map and a data distributions Engine

You can email us on [email protected]

Light weight Microservices

Peter Lawrey — Sat, 30 Apr 2016 00:00:00 GMT

What do we see as light weight Microservices?

A key requirements for productivity is a short development lifecycle. Every time you have to wait between changing code and knowing there is an error to be fixed, increases the cost of fixing that error. You want fast feedback to ensure you stay productive.

Another key requirement is simple components which are easy to reason about. One of the simplest is services which follow the Lambda Architecture.

Using your IDE as much as possible.

You should be able to

see most errors in your IDE as you type, before you even compile your code.
run your program using the Run button on your IDE.
debug your program by running it in your IDE.
profile your application from your IDE

Run your application quickly on your desktop

It is essential to be able to run your service entirely from your desktop. This allows you to

write repeatable unit tests for key components of your system.
run your application using state which is local to you.
work without contention on shared resources such as a shared development database.
reproduce production issues from your development environment.

Microservices which meets your business needs.

The components which make up you microservices should be

directly releated to a business requirement. If you couldn’t explain to an end user/business representaive why the component is needed to fulfill what they need, it’s not a business component.
the transport fo messages between services should be a seperate concern and even optional. e.g. for unit tests and debugging.
a microservice is not a browser, and how a browser talks to a web service is not the only model for how microservices can talk to each other.

How to define components.

When you define your components, it should be a direct reflection of the business function it performs.

microservices should be coding in terms of top down design, sarting with what it needs to do at the highest level, calling methods which implement the how this is done.
transport considerations should be defined externally to the component. The transport should not have any influence on the business requirements, and should be interchangeable.

Lambda Architecture.

Lambda Architecture (not the same as Lambdas in Java which are closures) provides a simple model for microservices to follow. Not all microservices can follow the Lambda Architecture, however the more service which do follow it the easier your system will be to reason about.

Microservice with a Websocket transport

Peter Lawrey — Mon, 25 Apr 2016 00:00:00 GMT

In this post, we will look at a simple component to publish market data and accept orders. How can this be accessed using websockets as a transport?

Our service

Interface for messages from the client to the server

public interface GUIGateway {
    void enableMarketData(boolean enabled);
    void newOrder(Order order);
}

Interface for messages from the server to the client

public interface GUIGatewayListener {
    void market(MarketData marketData);
    void order(OrderStatus orderStatus);
}

Bad String

Peter Lawrey — Thu, 21 Apr 2016 00:00:00 GMT

This program has two threads printing messages alternatively. However if you change a String from "cC" to "cc" it doesn’t print anything, WHY?

public class PingPongMain {
    public static void main(String[] args) throws InterruptedException {
        new Thread(() -> {
            try {
                synchronized ("bb") {
                    while (true) {
                        "bb".wait();
                        "bb".notifyAll();
                        System.out.println("b");
                    }
                }
            } catch (InterruptedException e) {
                throw new AssertionError(e);
            }
        }).start();
        Thread.sleep(100);
        setString("bb", 'c', 'C');
        new Thread(() -> {
            try {
                // change "cC" to "cc" and this program prints nothing.
                synchronized ("cC") {
                    while (true) {
                        "cC".notifyAll();
                        "cC".wait();
                        System.out.println("c");
                    }
                }
            } catch (InterruptedException e) {
                throw new AssertionError(e);
            }
        }).start();

    }

    public static void setString(String s, char... chars) {
        try {
            Field value = String.class.getDeclaredField("value");
            value.setAccessible(true);
            value.set(s, chars);
        } catch (Exception e) {
            throw new AssertionError(e);
        }
    }
}

The solution is below

A combination of strangeness

There is a couple of elements to this puzzle

using a String literal as a Object to lock on.
corrupting a String in the literal pool.
replacing one String with another with the same hashCode so the replacement is found. "bb".hashCode() == "cC".hashCode()

A JDBC Gateway Microservice

Peter Lawrey — Tue, 12 Apr 2016 00:00:00 GMT

A deep dive into a low latency microservice

We look at a microservice which can run in it’s own JVM, can perform JDBC updates and queries via a persistent queue for in bound request and a queue for results.

In previous posts I looked at the theory behind there low latency micro-services so lets have a look at a micro-service which can do something useful.

I would consider this a Gateway Service as it interacts with a system which is outside the microservice model.

What does this service do?

The service supports two messages executeQuery and executeUpdate. These methods mirror the same methods for PreparedStatement except the results are passed as messages

Two asynchronous messages in

public interface JDBCStatement {
    void executeQuery(String query, Class resultType, Object... args);

    void executeUpdate(String query, Object... args);
}

Two asynchronous results, possibly with an Exception thrown

public interface JDBCResult {
    void queryResult(Iterator marshallableList, String query, Object... args);
    void queryThrown(Throwable t, String query, Object... args);

    void updateResult(long count, String update, Object... args);
    void updateThrown(Throwable t, String update, Object... args);
}

Component wrapped as a Service

As in previous posts, we create a component which can be executed without a transport. This can be unit tested stand alone, or with a series of components without the transport complicating testing and debugging.

Looking at the executorUpdate method

public class JDBCComponent implements JDBCStatement {
    private final Connection connection;
    private final JDBCResult result;

    public JDBCComponent(ThrowingSupplier connectionSupplier, JDBCResult result) throws SQLException {
        connection = connectionSupplier.get();
        this.result = result;
    }

    @Override
    public void executeUpdate(String query, Object... args) {
        try (PreparedStatement ps = connection.prepareStatement(query)) {
            for (int i = 0; i < args.length; i++)
                ps.setObject(i + 1, args[i]);
            int count = ps.executeUpdate();
            // record the count.
            result.updateResult(count, query, args);
        } catch (Throwable t) {
            result.updateThrown(t, query, args);
        }
    }

You can see that every input message creates an output message with the results. This will be useful later for restarting the service from where it got up to and monitoring it’s progress, as well as obtaining the results.

How to wrap this as a service

public class JDBCService implements Closeable {
    private static final Logger LOGGER = LoggerFactory.getLogger(JDBCService.class);
    private final ChronicleQueue in;
    private final ChronicleQueue out;
    private final ExecutorService service;
    private final ThrowingSupplier connectionSupplier;
    private volatile boolean closed = false;

    public JDBCService(ChronicleQueue in, ChronicleQueue out, ThrowingSupplier connectionSupplier) throws SQLException {
        this.in = in;
        this.out = out;
        this.connectionSupplier = connectionSupplier;

        service = Executors.newSingleThreadExecutor(
                new NamedThreadFactory(in.file().getName() + "-JDBCService", true)); (1)
        service.execute(this::runLoop); (2)
        service.shutdown(); // stop when the task exits.
    }


    void runLoop() {
        try {
            JDBCResult result = out.createAppender() (3)
                    .methodWriterBuilder(JDBCResult.class)
                    .recordHistory(true)
                    .get();
            JDBCComponent js = new JDBCComponent(connectionSupplier, result);
            MethodReader reader = in.createTailer().afterLastWritten(out).methodReader(js); (4)
            Pauser pauser = new LongPauser(50, 200, 1, 10, TimeUnit.MILLISECONDS);
            while (!closed) {
                if (reader.readOne()) (5)
                    pauser.reset();
                else
                    pauser.pause();
            }
        } catch (Throwable t) {
            LOGGER.error("Run loop exited", t);
        }
    }

    @Override
    public void close() {
        closed = true;
    }

    public JDBCStatement createWriter() {
        return in.createAppender() (6)
                .methodWriterBuilder(JDBCStatement.class)
                .recordHistory(true)
                .get();
    }

    public MethodReader createReader(JDBCResult result) {
        return out.createTailer().methodReader(result);
    }
}

1	Create a thread with a meaningful name. We use an ExecutorService in case we want to do something more complex with it later.
2	Add this task to the pool
3	Create a proxy to write to the output queue
4	Start reading after the last message to be successfully processed.
5	Read one message at a time.
6	Add a helper method to create a writer to the input of this service
7	Add a helper method to read the results of this service.

How does it perform?

I tested this writing to HSQLDB which is pretty fast, even writing to a file. Even so, using it as a Service could be useful for very bursty activity as we can handle much higher rates for periods of time.

The performance test writes 200K messages as fast as possible and waits for the to all complete. The first timing is the average latency to write each request, and the second latency is the average time to receive the result.

Average time to write each update 1.5 us, average time to perform each update 29.7 us

While HSQLDB was able to sustain over 33 K updates per second, (1 / 29.7 us), the service wrapping could handle bursts of over 660K writes per second. (1 / 1.5 us) This represents a 20 fold improvement in the burst throughput it can support.

How long can a burst be?

Both Linux and Windows tend to perform well up to 10% of main memory being "dirty" or not written to disk. For example, if you have 256 GB, you can have 25 GB of "dirty" data. Even so, if the burst rate is faster than the consuming service, but slow enough that the disk subsystem can keep up, your bursts can exceed main memory size. To put that in context, if your messages are 256 bytes long, the service could be behind by more than one billion messages, and it will not run out of memory, or fail. The main limitation in this case, is the amount of free disk space you have. At the time of posting you can buy 1 TB of Enterprise SSD for less than $600, and Samsung is selling 16 TB SSD drives. I expect storage costs will continue to fall.

Conclusion

Building a microservice by wrapping a component with an asynchronous API with a transport for messaging in and out has worked without too much complexity.

The best way to go fast is to do less work.

Microservices in the Chronicle World - Part 5

Peter Lawrey — Sat, 02 Apr 2016 00:00:00 GMT

In this part we look at putting a micro service together as a collection of services, and consider how we can evaluate the performance of these services. We introduce JLBH (Java Latency Benchmark Harness) to test these services.

Building a Service Wrapper.

For more complex services, we use an EventLoop in Chronicle Threads to manage multiple concurrent tasks. In this example we have only one task, so it is simpler to have a custom class to support it.

This class is available at ServiceWrapper.

public class ServiceWrapper implements Runnable, Closeable {
    private final ChronicleQueue inputQueue, outputQueue;
    private final MethodReader serviceIn;
    private final Object serviceOut;
    private final Thread thread;
    private final Pauser pauser = new LongPauser(1, 100, 500, 10_000, TimeUnit.MICROSECONDS); (1)

    private volatile boolean closed = false;

    public ServiceWrapper(String inputPath, String outputPath, I serviceImpl) {
        Class outClass = ObjectUtils.getTypeFor(serviceImpl.getClass(), ServiceHandler.class); (2)

        outputQueue = SingleChronicleQueueBuilder.binary(outputPath).build(); (3)
        serviceOut = outputQueue.createAppender().methodWriter(outClass);
        serviceImpl.init(serviceOut); (4)

        inputQueue = SingleChronicleQueueBuilder.binary(inputPath).build();
        serviceIn = inputQueue.createTailer().methodReader(serviceImpl); (5)

        thread = new Thread(this, new File(inputPath).getName() + " to " + new File(outputPath).getName());
        thread.setDaemon(true);
        thread.start(); (6)
    }

    @Override
    public void run() {
        AffinityLock lock = AffinityLock.acquireLock(); (7)
        try {
            while (!closed) {
                if (serviceIn.readOne()) { (8)
                    pauser.reset(); (9)
                } else {
                    pauser.pause(); (9)
                }
            }
        } finally {
            lock.release();
        }
    }

    @Override
    public void close() {
        closed = true;
    }

    @Override
    public boolean isClosed() {
        return closed;
    }
}

1 This Pauser controls the back off strategy in which no events are coming through. It will retry once, yield 100 times, then start sleeping from half a millisecond to 10 milliseconds.

2 Obtain the type of the parameter for the ServiceHandler and in this case it is a Service.

3 Create an output queue.

4 And pass it to the implementation so it can write to it’s output queue.

5 Create a reader for the input queue.

6 Start a thread which will read from the serviceIn reader.

7 Bind this thread to an isolated CPU where possible.

8 Read and process one message.

9 reset() the pauser if a message came, otherwise call it for a possible pause.

Timing our service.

A simple service can time itself. This could be implmented as a wrapper, however for a more complex service you can use the builing in history recording and only examine the result at the end.

class ServiceImpl implements Service, ServiceHandler { private final NanoSampler nanoSampler; private final NanoSampler endToEnd; private Service output; public ServiceImpl(NanoSampler nanoSampler) { this(nanoSampler, t -> { }); } public ServiceImpl(NanoSampler nanoSampler, NanoSampler endToEnd) { this.nanoSampler = nanoSampler; this.endToEnd = endToEnd; } @Override public void init(Service output) { this.output = output; } @Override public void simpleCall(SimpleData data) { data.number *= 10; // do something. long time = System.nanoTime(); nanoSampler.sampleNanos(time - data.ts); (1) data.ts = time; // the start time for the next stage. output.simpleCall(data); // pass the data to the next stage. endToEnd.sampleNanos(System.nanoTime() - data.ts0); (2) } }

1 Take the timing since the last stage

2 Take the timing from the start

Using JLBH Java Latency Benchamrk Harness

This tool is based on JMH (Java Microbenchmark Harness) where the main difference is support for testing asynchronous processes where you want to examine the timings at different stages, possibly in different theads.

JLBHOptions jlbhOptions = new JLBHOptions() .warmUpIterations(50_000) .iterations(MESSAGE_COUNT) .throughput(THROUGHPUT) (1) .runs(6) .recordOSJitter(true) (2) .pauseAfterWarmupMS(500) .accountForCoordinatedOmmission(ACCOUNT_FOR_COORDINATED_OMMISSION) (3) .jlbhTask(new MultiThreadedMainTask()); new JLBH(jlbhOptions).start();

1 Benchmark for a target throughput.

2 Add a thread to record the OS jitter over the interval.

3 Turn on correction for coordinated ommission.

To set up the test, we create three services. This models a gateway which accepting data from external systems such as aweb service or FIX Engine. This is picked up by one service, which passes a message to a second service and finally this is written to a gateway service which can pass the data to an external system.

UUID uuid = UUID.randomUUID(); String queueIn = OS.TMP + "/MultiThreadedMain/" + uuid + "/pathIn"; String queue2 = OS.TMP + "/MultiThreadedMain/" + uuid + "/stage2"; String queue3 = OS.TMP + "/MultiThreadedMain/" + uuid + "/stage3"; String queueOut = OS.TMP + "/MultiThreadedMain/" + uuid + "/pathOut"; @Override public void init(JLBH jlbh) { serviceIn = SingleChronicleQueueBuilder.binary(queueIn).build().createAppender().methodWriter(Service.class); (1) service2 = new ServiceWrapper<>(queueIn, queue2, new ServiceImpl(jlbh.addProbe("Service 2"))); (2) service3 = new ServiceWrapper<>(queue2, queue3, new ServiceImpl(jlbh.addProbe("Service 3"))); (3) serviceOut = new ServiceWrapper<>(queue3, queueOut, new ServiceImpl(jlbh.addProbe("Service Out"), jlbh)); (4) (5) }

1 Just a writer

2 Reads that message and writes to the third service

3 Reads from the second service and writes to the outbound service.

4 The output gateway reads from the third service and writes its result to a log/queue.

5 The last service also sets the end to end timing.

Every message is being persisted at each stage and is available on restart. As there is one output message for every input pmessage you could restart by winding to the same index as the output. A more robust strategy would be to record te history in the output as covered in the previous post.

Running the tests

There are two important considerations when running performance tests

what is the percentile that you care about?

Typical,

99%tile (worst 1 in 100)

99.9%tile (worst 1 in 1000)

99.99%tile ( worst 1 in 10000)

worst, ever

what is the throughput you are looking to test.

It is important that you control the throughput for the test so you can see how your system behaves at different sustained throuhgputs. You system will run as fast as possible for short periods, however buffers and caches quickly fill up and cannot support this rate without getting large delays.

Looking at the typical performance.

In this test on a E5-2650 v2, the throughput it can achieve for this test is 600,000 messages/second. However, it wouldn’t be practical to do this for any long period of time as the system quickly gets to the point where it is behind with increasing delay the long this goes on. This is because there is no head room to deal with any jitter or delay in the system. Every delay accumulates as the system struggle to keeps up. So what is a more practical throughput for this mock system.

Figure 1. Worst Typical was the highest of 15, 2 minute runs.

This looks fine, for all the throughputs up to 400,000 messages per second, the typical performance is consistent. However, for a throughput of 450,000 messages per second, the service could get a delay which it would struggle to recover from and the typical latency would jump to 20 - 40 seconds.

In short, by looking at the typical performance our estimate of throughput we might prefer has dropped from 600K/s to 400K/s

Looking at the nines.

By looking at the higher percentiles (worst results) we can for a view as to what delays would be acceptable and how often. Typically, I would consider a 99%tile which 4x the typical and a 99.9%tile which 10x the typical latency. This is rule of thumb I use, however the results vary between systems.

Figure 2. The worst 1 in 100 gets higher as the throughput increases.

You might take the view that the 99%tile should be under 10 micro-seconds, and conclude the system can handle 300K messages/second.

Figure 3. The worst 1 in 1000 gets higher as the throughput increases.

Looking at the 99.9%tile you can see that above 200K msg/second our latencies shoot up. Up to 200 K/s our system has very stable latencies.

Can we sustain 200 K msg/second?

The problem arises that we will not want to sustain this rate for long. Bursts are fine, but do this all day long and you generate a lot of data. If all the messages are recorded and they total say 1/2 KB for each inbound message, this will be producing 200 MB/s, and while an SSD can do this easily it will run out of space pretty fast. 200 MB/s is 9 TB per day. Nine TB of usable high performance SSD is still pretty pricy.

Lets say we wanted to record less than 2 TB per day. A few high capacity HDD could persist all your messages for a week. This is 23 MB/s sustained. At 512 bytes per message (total) you are looking at a more modest 50K message/second sustained, but with burst of up to 200K/s - 600K/s depending on your requirements.

In summary

We have a test harness for multi-threaded asynchronous processes and it can help you explore how your service might behave under various throughput loads. While your system might be able to support high throughputs for very short periods of time, how sustained throughput impacts the latency of your system.

Microservices in the Chronicle world - Part 4

Peter Lawrey — Tue, 29 Mar 2016 00:00:00 GMT

A common issue we cover in our workshops is, how to restart a queue reader after a failure.

The answer is not a simple as you might think.

We do an on-site one week workshop to help kick start a new project, with a look at ensuring the infrastructure has a good balance of speed and simplicity. Often, simplicity is the most important and it will also be fast enough. You can contact Chronicle Software Sales for more details.

Knowing when a message should be replayed on startup.

It’s not enough to know which messages have been played. You need to know which messages were completed successfully in a transaction. This assumes you must have each message processed exactly once. Simpler alternatives are:

Play every message again and ignore duplicates.

Play every message from the end (or the last N minutes) and assume anything older than that has expired.

When updating a database, one way to achieve this is to update the index read in a row in the database, this way either:

The transaction succeeds and the message doesn’t need to be played again.

The transaction fails and the message does need to be played again.

The important detail is that there is no situation where it is unclear whether the input message should be replayed.

Restarting a reader when writing to a queue as output.

In general, we suggest you write your results to an output queue. An output queue can be a replacement for logging and a means of monitoring, but can also record where each event came from. In particular, and output queue can help:

Replay messages in the same order, which were sourced from multiple input queue.

Ensure that after an upgrade of your software, you honour the decisions you made earlier. i.e. new software replaying the input message might make different decisions. By reading from the output, you ensure that after an upgrade you know what state you should be in.

Restart an input queue from the last message successfully outputed for an input from that queue.

In this example, it reads just one unprocessed message.

Read one message which hasn’t been processed.

try (SingleChronicleQueue in = SingleChronicleQueueBuilder.binary(queuePath) .sourceId(1) (1) .build(); SingleChronicleQueue out = SingleChronicleQueueBuilder.binary(queuePath2) .rollCycle(RollCycles.TEST_DAILY) .build()) { MarketDataListener mdListener = out.createAppender() .methodWriterBuilder(MarketDataListener.class) .recordHistory(true) (2) .get(); SidedMarketDataCombiner combiner = new SidedMarketDataCombiner(mdListener); MethodReader reader = in.createTailer() .afterLastWritten(out) (3) .methodReader(combiner); assertTrue(reader.readOne()); }

1 Give the queue a unique id for tracing purposes.

2 Write a history for timings and sources for each message processed.

3 Read the output queue to see what the last message processed was.

It would be really inefficient to do all this every time. The only line which is required for each message is

reader.readOne();

Conclusion

While there is a number of ways you could implement restart, if you need it, it is useful to have built-in support for one of the most common ways to do this.

In the next part.

How does this perform end to end with multiple asynchronous services are how can we measure there?

Microservices in the Chronicle World - Part 3

Peter Lawrey — Sat, 26 Mar 2016 00:00:00 GMT

One of the problems with using microservices is performance. Latencies can be higher due to the cost of serialization, messaging and deserialization, and this reduces throughput. In particular, poor throughput is a problem because the reason we are designing a scalable system^[1] is to increase throughput.

In Part 2 we saw how we can take a component and add a transport to it to make it a service.

Passing data between threads is not free. This information needs to be passed over the L2 CPU Cache Coherence bus. If you do this in an uncontrolled manner and just let the application discover the objects it needs to pull from one thread’s cache to its own, it can be slower than only passing the data you need, streamed serially. Chronicle Queue gives greater transparency by recording every event, allowing you to optmise exactly what one thread passes to another.

In one low latency trading system, before adding Chronicle Queue, the average latency from read in to write out was 35 micro-seconds, after utilising Chronicle Queue to optimie the data passed between threads the latency dropped to 23 micro-seconds. Using Chronicle Queue also showed up issues which were not apparent before, and with replay of events, gave confidence these issues had been fixed.

Benchmarking with JMH

JMH^[2](Java Micro-benchmark Harness) is an excellent tool for measuring the throughput and sampling latencies end to end. We can look at an example of what it is good for with regard to our sample microservice.

We create our own micro-benchmark harness, in Chronicle-Core, for measuring asynchronmos tasks run across multiple threads where you want to time individual portions (which will be covered in Part 4). For now we will look at latencies end-to-end.

JMH latency test of our service

With JMH we can measure timings for the end to end benchmark. We have to include a producer to drive the test rather than time a service standalone. We are looking at the single threaded timings.

Our JMH benchmark

@Setup public void setup() { String target = OS.TMP; upQueuePath = new File(target, "ComponentsBenchmark-up-" + System.nanoTime()); upQueue = SingleChronicleQueueBuilder.binary(upQueuePath).build(); (1) smdWriter = upQueue.createAppender().methodWriter(SidedMarketDataListener.class); (2) downQueuePath = new File(target, "ComponentsBenchmark-down-" + System.nanoTime()); downQueue = SingleChronicleQueueBuilder.binary(downQueuePath).build(); (3) MarketDataListener mdWriter = downQueue.createAppender().methodWriter(MarketDataListener.class); (4) SidedMarketDataCombiner combiner = new SidedMarketDataCombiner(mdWriter); (5) reader = upQueue.createTailer().methodReader(combiner); (6) System.out.println("up-q " + upQueuePath); } @TearDown public void tearDown() { upQueue.close(); downQueue.close(); IOTools.shallowDeleteDirWithFiles(upQueuePath); IOTools.shallowDeleteDirWithFiles(downQueuePath); } @Benchmark public void benchmarkComponents() { switch (counter++ & 3) { case 0: smdWriter.onSidedPrice(sidedPrice.init("EURUSD", 123456789000L, Side.Sell, 1.1172, 1e6)); break; case 1: smdWriter.onSidedPrice(sidedPrice.init("EURUSD", 123456789100L, Side.Buy, 1.1160, 1e6)); break; case 2: smdWriter.onSidedPrice(sidedPrice.init("EURUSD", 123456789000L, Side.Sell, 1.1172, 2e6)); break; case 3: smdWriter.onSidedPrice(sidedPrice.init("EURUSD", 123456789100L, Side.Buy, 1.1160, 2e6)); break; } assertTrue(reader.readOne()); (7) }

1 Create an upstream queue.

2 Create a proxy which writes all methods calls to the upstream queue.

3 Create a downstream queue.

4 Create a proxy for the downstream queue.

5 Create the component which will write all outputs to the downstream queue.

6 Create a reader for the upstream queue which will call the combiner.

7 After writing a message to the queue, read it and call the appropriate method in the component.

The first portion sets up and tears down the test. The actual benchmark injects a message which when read and processed will trigger an output message.

Running the tests in JMH

Percentiles, us/op: p(0.0000) = 2.552 us/op p(50.0000) = 2.796 us/op p(90.0000) = 5.600 us/op p(95.0000) = 5.720 us/op p(99.0000) = 8.496 us/op (1) p(99.9000) = 15.232 us/op (1) p(99.9900) = 19.977 us/op (2) p(99.9990) = 422.475 us/op p(99.9999) = 438.784 us/op p(100.0000) = 438.784 us/op

1 Critical latency threashold for many systems.

2 Can still be important in some systems.

This is running on my development machine (Ubuntu 15.04, two E5-2650 v2, 128 GB memory). For better results, I suggest the latest Haswell or Skylake and Centos. The exact timing of this benchmark isn’t important as the number and type of fields in the message is also a significant factor. What is particularly interesting to me is the 99.9%tile latency (worst 1 in 1000) which is consistently under 20 mciro-seconds in this example. This demonstrates both high performance and consistently fast latencies.

Looking at how JMH is called.

To control how JMH is run the following parameters were used:

int time = Boolean.getBoolean("longTest") ? 30 : 3; System.out.println("measurementTime: " + time + " secs"); Options opt = new OptionsBuilder() .include(ComponentsBenchmark.class.getSimpleName()) .warmupIterations(8) .forks(1) .mode(Mode.SampleTime) (1) .measurementTime(TimeValue.seconds(time)) .timeUnit(TimeUnit.MICROSECONDS) .build(); new Runner(opt).run();

1 SampleTime mode to test latencies rather than throughput.

However, I have had trouble profiling and debugging JMH benchmarks so I change the way the test is run depending on how it is started:

Running in Flight Recorder and Debug

if (Jvm.isFlightRecorder()) { // -verbose:gc -XX:+UnlockCommercialFeatures -XX:+FlightRecorder // -XX:StartFlightRecording=dumponexit=true,filename=myrecording.jfr,settings=profile // -XX:+UnlockDiagnosticVMOptions -XX:+DebugNonSafepoints (2) System.out.println("Detected Flight Recorder"); main.setup(); long start = System.currentTimeMillis(); while (start + 60e3 > System.currentTimeMillis()) { (1) for (int i = 0; i < 1000; i++) main.benchmarkComponents(); } main.tearDown(); } else if (Jvm.isDebug()) { for (int i = 0; i < 10; i++) { runAll(main, Setup.class); runAll(main, Benchmark.class); runAll(main, TearDown.class); }

1 Run for 1 minute before shutting down.

2 Enable profiling between safepoints.

In our next part

Part 4: How can we time just the component running in another thread. In particular see how long it takes to read, process and write each message with individual timings.

Glossary

Latency- The time an individual operation takes. "Together, latency and bandwidth define the speed and capacity of a network."^[3]

Serialization- "The process of translating data structures or object state into a format that can be stored"^[4]See also Serialization libraries- The process that translates data into a format that can be consumed by another system.

Throughput- The rate of data or messages transferred which is processed in a certain amount of time. This rate is written in terms of throughput, e.g a road could have a throughput of 10 cars per minute.

1. Rouse, M. (2016). What is scalability? - Definition from WhatIs.com. Online. SearchDataCenter. Available at: http://searchdatacenter.techtarget.com/definition/scalability [Accessed Mar. 2016

2. Openjdk.(2016). OpenJDK: jmh. Online. Available at: http://openjdk.java.net/projects/code-tools/jmh/. Accessed Mar. 2016

3. Webopedia.com. (2016). What is Latency? Webopedia Definition. Online. Available at: http://www.webopedia.com/TERM/L/latency.html. Accessed Jul. 2016

4. Wikipedia. (2016). Serialization. Online. Available at: https://en.wikipedia.org/wiki/Serialization. Accessed Jul. 2016.

Microservices in the Chronicle world - Part 2

Peter Lawrey — Thu, 24 Mar 2016 00:00:00 GMT

In this part we look at turning a component into a service.

In Part 1, we looked at how we can easily create and test components which expect asynchronous messages^[1] in and produce asynchronous messages out. However, how do we turn this into a service?

Turning our components into a service.

The key thing which is missing from our components is a transport. A lack of a transport simplifies testing, profiling and debugging, but we need to distribute our components, and for this we need a transport.

There is a wide range of possible transports available:

Chronicle Queue

Raw TCP messages or UDP packets with a library like Netty^[2]

JMS Messaging^[3]

REST API^[4]

Database tables via JDBC^[5]

Files dropped into a directory and use the directory WatchService^[6]

a thread safe Queue, like BlockingQueue

shared memory^[7]

Apache Aries^[8] for pluggable transports

no transport at all (method calls are fine for a given use case)

It is the Chronicle Queue we will be looking at in the post.

Using queue in a unit test

Chronicle Queue is persisted, however in unit tests you usually want to start fresh and remove the queue afterwards. The idiom you can use is as follows;

Creating a temporary Queue

File queuePath = new File(OS.TARGET, "testName-" + System.nanoTime()); try { try (SingleChronicleQueue queue = SingleChronicleQueueBuilder.binary(queuePath).build()) { // use the queue } } finally { IOTools.shallowDeleteDirWithFiles(queuePath); }

This creates a queue which is stored in a single file. The file is rolled daily by default and includes the current date in the path.

Writing events

If we repeat our test as before, instead of using a mock listener, we can use a listener which writes each method called to a queue:

Write methods called to a queue for either interface

OrderIdeaListener orderManager = queue.createAppender() .methodWriter(OrderIdeaListener.class, MarketDataListener.class);

Our combiner writes to this queue, as does our test:

The SidedPrice combiner

SidedMarketDataCombiner combiner = new SidedMarketDataCombiner((MarketDataListener) orderManager);

We can also repeat the events inbound. Putting all this together we get:

try (SingleChronicleQueue queue = SingleChronicleQueueBuilder.binary(queuePath).build()) { OrderIdeaListener orderManager = queue.createAppender().methodWriter(OrderIdeaListener.class, MarketDataListener.class); SidedMarketDataCombiner combiner = new SidedMarketDataCombiner((MarketDataListener) orderManager); // events in orderManager.onOrderIdea(new OrderIdea("EURUSD", Side.Buy, 1.1180, 2e6)); // not expected to trigger combiner.onSidedPrice(new SidedPrice("EURUSD", 123456789000L, Side.Sell, 1.1172, 2e6)); combiner.onSidedPrice(new SidedPrice("EURUSD", 123456789100L, Side.Buy, 1.1160, 2e6)); combiner.onSidedPrice(new SidedPrice("EURUSD", 123456789100L, Side.Buy, 1.1167, 2e6)); orderManager.onOrderIdea(new OrderIdea("EURUSD", Side.Buy, 1.1165, 1e6)); // expected to trigger }

Once we have written all the events to our queue, we can process the queue in our test. A more realistic example would be to run these two components in different threads, processes or on different machines, however this just complicates the tests and the result should be the same provided the transport does it’s job.

Reading events.

When we read the events we need a component which implements the methods called above and a mock listener to ensure it triggers the right events.

Read all the events and check the right output

// what we expect to happen OrderListener listener = createMock(OrderListener.class); listener.onOrder(new Order("EURUSD", Side.Buy, 1.1167, 1_000_000)); replay(listener); try (SingleChronicleQueue queue = SingleChronicleQueueBuilder.binary(queuePath).build()) { // build our scenario OrderManager orderManager = new OrderManager(listener); (1) MethodReader reader = queue.createTailer().methodReader(orderManager); (2) for (int i = 0; i < 5; i++) assertTrue(reader.readOne()); (3) assertFalse(reader.readOne()); (4) System.out.println(queue.dump()); (5) } verify(listener);

1 our component to test

2 our queue reader which will call the methods

3 loop to read/process one method at a time.

4 we have no more messages

5 dump the queue contents so we can see what the input was.

Finally, the test dumps the raw contents of the queue. This reads the data stored in the file that queue uses. This dump is only useful for smaller queue with a few MB of data. If you have a few GB, it won’t be able to be stored in a String. You can use DumpQueueMain f

The output of dump()

--- !!meta-data #binary header: !SCQStore { wireType: !WireType BINARY, writePosition: 777, roll: !SCQSRoll { length: 86400000, format: yyyyMMdd, epoch: 0 }, indexing: !SCQSIndexing { indexCount: !int 8192, indexSpacing: 64, index2Index: 0, lastIndex: 0 } } # position: 227 --- !!data #binary onOrderIdea: { symbol: EURUSD, side: Buy, limitPrice: 1.118, quantity: 2000000.0 } # position: 306 --- !!data #binary onTopOfBookPrice: { symbol: EURUSD, timestamp: 123456789000, buyPrice: NaN, buyQuantity: 0, sellPrice: 1.1172, sellQuantity: 2000000.0 } # position: 434 --- !!data #binary onTopOfBookPrice: { symbol: EURUSD, timestamp: 123456789100, buyPrice: 1.116, buyQuantity: 2000000.0, sellPrice: 1.1172, sellQuantity: 2000000.0 } # position: 566 --- !!data #binary onTopOfBookPrice: { symbol: EURUSD, timestamp: 123456789100, buyPrice: 1.1167, buyQuantity: 2000000.0, sellPrice: 1.1172, sellQuantity: 2000000.0 } # position: 698 --- !!data #binary onOrderIdea: { symbol: EURUSD, side: Buy, limitPrice: 1.1165, quantity: 1000000.0 } ... # 83885299 bytes remaining

To run the test and dump the queue in my IDE took 233 ms.

Conclusion

We can test components stand alone with a queue or in a chain by using more queues. More importantly we can test our components without the infrastructure complicating the debugging process. When our components work without a transport, we can show they do the same thing with a transport.

In our next part

In part 3, we will look at benchmarking and profiling with Queue. While Queue is designed to be simple and transparent, it is also designed to be faster than other persisted transports, even with no tuning.

Glossary

Idiom- "A means of expressing a recurring construct in one or more programming languages."^[9]

Mock listener- Method call/messages can be sent to a mock listener. This acts as a pretend Object for the purposes of testing in order to see that would happen to a Concrete Object.

Service- A program that is available to other programs to run and make use of.

Transport- A program or hardware that takes data from ome process to another.e.g Middleware^[10]// = Your Blog title

1. Beal, V. (2016). What is asynchronous messaging? Webopedia Definition. Online. Webopedia.com. Available at: http://www.webopedia.com/TERM/A/asynchronous_messaging.html. Accessed Jul. 2016

2. Netty.io. (2016). Netty: Home. Online. Available at: http://netty.io/. Accessed Mar. 2016

3. Oracle (2013). The JMS API Programming Model - The Java EE 6 Tutorial. Online. Available at: https://docs.oracle.com/javaee/6/tutorial/doc/bnceh.html. Accessed Mar. 2016

4. Wikipedia. (2016). Java API for RESTful Web Services. Online. Available at: https://en.wikipedia.org/wiki/Java_API_for_RESTful_Web_Services. Accessed Mar. 2016

5. Docs.oracle.c(2016). Java JDBC API. Online. Available at: https://docs.oracle.com/javase/8/docs/technotes/guides/jdbc/. Accessed Mar. 2016

6. Oracle (2016). WatchService (Java Platform SE 8 ). Online. Available at: https://docs.oracle.com/javase/8/docs/api/java/nio/file/WatchService.html.Accessed 23 Mar. 2016

7. Oracle (2016). BlockingQueue (Java Platform SE 8 ). Online. Available at: https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/BlockingQueue.html Accessed 23 Mar. 2016

8. Apache Aries. (2016). Apache Aries - Index. Online. Available at: http://aries.apache.org/. Accessed 23 Mar. 2016

9. Wikipedia. (2016). Programming idiom. Online. Available at: https://en.wikipedia.org/wiki/Programming_idiom. Accessed Mar. 2016

10. Beal, V. (2016). What is Middleware? Webopedia Definition. Online. Webopedia.com. Available at: http://www.webopedia.com/TERM/M/middleware.html. Accessed Jul. 2016

Microservices in the Chronicle world - Part 1

Peter Lawrey — Wed, 23 Mar 2016 00:00:00 GMT

At a high level, different Microservice strategies have a lot in common. They subscribe to the same ideals. When it comes to the details of how they are actually implemented, they can vary.

Microservices in the Chronicle world are designed around:

Simplicity- simple is fast, flexable and easier to maintain.

Transparency- you can’t control what you don’t understand.

Reproduceablity- this must be in your design to ensure a quality solution.

What do we mean by simple?

A key part of the microservices design is how messages are passed between services/components. The simplest messages could be called asynchronous method calls.

An asynchronous method call is one which;

doesn’t return anything,

doesn’t alter it’s arguments;

doesn’t throw any exceptions (although the underlying transport could).

The reason this approach is used, is that the simplest transport is no transport at all. One component calls another. This is not only fast ( and with inlining might not take any time at all), but it is simple to setup, debug and profile. For most unit tests you don’t need a real transport so there is no advantage in making the test more complicated than it needs to be.

Let’s look at an example.

Say we have a service/component which is taking incremental market data updates. In the simplest case, this could be a market update with only one side, a buy or a sell. The component could transform this into a full market update combining both the buy and sell price and quantity.

In this example, we have only one message type to start with, however we can add more message types. I suggest you create a different message name/method for each message rather than overloading a method.

Our inbound data structure

public class SidedPrice extends AbstractMarshallable { final String symbol; final long timestamp; final Side side; final double price, quantity; public SidedPrice(String symbol, long timestamp, Side side, double price, double quantity) { this.symbol = symbol; this.timestamp = timestamp; this.side = side; this.price = price; this.quantity = quantity; } }

Our outbound data structure

public class TopOfBookPrice extends AbstractMarshallable { final String symbol; final long timestamp; final double buyPrice, buyQuantity; final double sellPrice, sellQuantity; public TopOfBookPrice(String symbol, long timestamp, double buyPrice, double buyQuantity, double sellPrice, double sellQuantity) { this.symbol = symbol; this.timestamp = timestamp; this.buyPrice = buyPrice; this.buyQuantity = buyQuantity; this.sellPrice = sellPrice; this.sellQuantity = sellQuantity; } // more methods (1) }

1 For the complete code TopOfBookPrice.java.

The component which takes one sided prices could have an interface;

Inbound interface for the first component

public interface SidedMarketDataListener { void onSidedPrice(SidedPrice sidedPrice); }

and it’s output also has one method;

Outbound interface for the first component

public interface MarketDataListener { void onTopOfBookPrice(TopOfBookPrice price); }

What does our microservice look like?

At a high level, the combiner is very simple;

public class SidedMarketDataCombiner implements SidedMarketDataListener { final MarketDataListener mdListener; final Map priceMap = new TreeMap<>(); public SidedMarketDataCombiner(MarketDataListener mdListener) { this.mdListener = mdListener; } public void onSidedPrice(SidedPrice sidedPrice) { TopOfBookPrice price = priceMap.computeIfAbsent(sidedPrice.symbol, TopOfBookPrice::new); if (price.combine(sidedPrice)) mdListener.onTopOfBookPrice(price); } }

It implements our input interface and takes the output interface as a listener.

What does AbstractMarshallable provide?

The AbstractMarshallable class is a convenience class which implements toString(), equals(Object) and hashCode(). It also supports Marshallable’s writeMarshallable(WireOut) and readMarshallable(WireIn).

The default implementations use all the non-static non-transient fields to either print, compare or build a hashCode.

the resulting toString() can always be de-serialized with Marshallable.fromString(CharSequence).

Let’s look at a couple of examples.

SidedPrice sp = new SidedPrice("Symbol", 123456789000L, Side.Buy, 1.2345, 1_000_000); assertEquals("!SidedPrice {\n" + " symbol: Symbol,\n" + " timestamp: 123456789000,\n" + " side: Buy,\n" + " price: 1.2345,\n" + " quantity: 1000000.0\n" + "}\n", sp.toString()); // from string SidedPrice sp2 = Marshallable.fromString(sp.toString()); assertEquals(sp2, sp); assertEquals(sp2.hashCode(), sp.hashCode());

As you can see, the toString() is in YAML^[1], concise, readable to a human and in code.

TopOfBookPrice tobp = new TopOfBookPrice("Symbol", 123456789000L, 1.2345, 1_000_000, 1.235, 2_000_000); assertEquals("!TopOfBookPrice {\n" + " symbol: Symbol,\n" + " timestamp: 123456789000,\n" + " buyPrice: 1.2345,\n" + " buyQuantity: 1000000.0,\n" + " sellPrice: 1.235,\n" + " sellQuantity: 2000000.0\n" + "}\n", tobp.toString()); // from string TopOfBookPrice topb2 = Marshallable.fromString(tobp.toString()); assertEquals(topb2, tobp); assertEquals(topb2.hashCode(), tobp.hashCode()); }

One of the advantages of using this format is that it makes it easier to find the reason for a failing test even in complex objects.

Even in a trivial test it’s not obvious what the problem is

TopOfBookPrice tobp = new TopOfBookPrice("Symbol", 123456789000L, 1.2345, 1_000_000, 1.235, 2_000_000); TopOfBookPrice tobp2 = new TopOfBookPrice("Symbol", 123456789000L, 1.2345, 1_000_000, 1.236, 2_000_000); assertEquals(tobp, tobp2);

However when you run this test in your IDE^[2], you get a comparison window.

Figure 1. Comparison Windows in your IDE

If you have a large nested/complex object where assertEquals fails, it can really save you a lot of time finding what the discrepency is.

Mocking our component

We can mock an interface using a tool like EasyMock. I find EasyMock is simpler when dealing with event driven interfaces. It is not as powerful as PowerMock or Mockito, however if you are keeping things simple, you might not need those features.

// what we expect to happen SidedPrice sp = new SidedPrice("Symbol", 123456789000L, Side.Buy, 1.2345, 1_000_000); SidedMarketDataListener listener = createMock(SidedMarketDataListener.class); listener.onSidedPrice(sp); replay(listener); // what happens listener.onSidedPrice(sp); // verify we got everything we expected. verify(listener);

We can also mock the expected output of a component the same way.

Testing our component

By mocking the output interface and calling the input interface for our compoonent we can check it behaves as expected.

MarketDataListener listener = createMock(MarketDataListener.class); listener.onTopOfBookPrice(new TopOfBookPrice("EURUSD", 123456789000L, 1.1167, 1_000_000, Double.NaN, 0)); (1) listener.onTopOfBookPrice(new TopOfBookPrice("EURUSD", 123456789100L, 1.1167, 1_000_000, 1.1172, 2_000_000)); (2) replay(listener); SidedMarketDataListener combiner = new SidedMarketDataCombiner(listener); combiner.onSidedPrice(new SidedPrice("EURUSD", 123456789000L, Side.Buy, 1.1167, 1e6)); (1) combiner.onSidedPrice(new SidedPrice("EURUSD", 123456789100L, Side.Sell, 1.1172, 2e6)); (2) verify(listener);

1 Setting the buy price

2 Setting the sell price

Testing a series of components

Lets add an OrderManager as a down stream component. This order manager will receive both market data updates and order ideas, and in turn will produce orders.

// what we expect to happen OrderListener listener = createMock(OrderListener.class); listener.onOrder(new Order("EURUSD", Side.Buy, 1.1167, 1_000_000)); replay(listener); // build our scenario OrderManager orderManager = new OrderManager(listener); (2) SidedMarketDataCombiner combiner = new SidedMarketDataCombiner(orderManager); (1) // events in orderManager.onOrderIdea(new OrderIdea("EURUSD", Side.Buy, 1.1180, 2e6)); // not expected to trigger combiner.onSidedPrice(new SidedPrice("EURUSD", 123456789000L, Side.Sell, 1.1172, 2e6)); combiner.onSidedPrice(new SidedPrice("EURUSD", 123456789100L, Side.Buy, 1.1160, 2e6)); combiner.onSidedPrice(new SidedPrice("EURUSD", 123456789100L, Side.Buy, 1.1167, 2e6)); orderManager.onOrderIdea(new OrderIdea("EURUSD", Side.Buy, 1.1165, 1e6)); // expected to trigger verify(listener);

1 The first component combines sided prices

2 The second component listens to order ideas and top of book market data

Debugging our components

You can see that one component just calls another. When debugging this single threaded code, each event from the first component is a call to the second component. When that finishes it returns to the first one and the tests.

When any individual event triggers an error, you can see in the stack trace which event caused the issue. However, if you are expecting an event which doesn’t happen, this is tricker unless your tests are simple (or you do a series of simple tests with verify(), reset() and replay().

it takes almost no time at all to start up the test and debug it in your IDE. You can run hundreds of tests like this in less than a second.

Source for examples

https://github.com/Vanilla-Java/Microservices/tree/master/src/main/java/net/openhft/samples/microservices

How do we create these as services?

We have shown how easy it is to test and debug our components. How do we turn these into services in Part 2.

Glossary

Microservices- Independantly deployable programmes that act as components in a larger network.

Serialization- "The process of translating data structures or object state into a format that can be stored"^[3]See also Serialization libraries- The process that translates data into a format that can be consumed by another system.

Stack trace- "A report of the active stack frames at a certain point in time during the execution of a program." ^[4] // = Your Blog title

1. Ben-Kiki, et al (2009). YAML Ain’t Markup Language (YAML™) Version 1.2. Online. Available at: http://www.yaml.org/spec/1.2/spec.html. Accessed Jul. 2016

2. Wikipedia. (2016). Integrated development environment. Online. Available at: https://en.wikipedia.org/wiki/Integrated_development_environment. Accessed Mar. 2016

3. Wikipedia. (2016). Serialization. Online. Available at: https://en.wikipedia.org/wiki/Serialization. Accessed Jul. 2016.

4. Wikipedia. (2016). Stack trace. Online. Available at: https://en.wikipedia.org/wiki/Stack_trace. Accessed Jul. 2016

Micro-services for performance

Peter Lawrey — Tue, 22 Mar 2016 00:00:00 GMT

Overview

Microservices is a buzz word at the moment. Is it really something original or based on established best practices? There are some disadvantages to the way microservices have been implemented, but can these be solved?

Component testability and consistency

Once you have assembled a large system, it can be hard or even impossible to profile where the highest delays come from. You can profile for average latency or throughput, but to achieve consistent latencies, you need to analyse key portions of your system. This is where having simple components which run independently, and can be tested as stand alone, could help you achieve the consistency of your system needs end to end.

The UNIX Philosophy

Many of the key concepts of microservices have been used in distributed systems for many years.

Microservices have much in common with the Unix Philosophy^[1]

Mike Gancarz^[2] is quoted as summed these principles as follows:

Small is beautiful.

Make each program do one thing well.

Build a prototype as soon as possible.

Choose portability over efficiency.

Store data in flat text files.

Use software leverage to your advantage.

Use shell scripts^[3] to increase leverage and portability.

Avoid captive user interfaces.

Make every program a filter.

The Microservices Architecture^[4] is the UNIX Philosophy applied to distributed systems.

Philosophy of microservices architecture essentially equals the Unix philosophy of "Do one thing and do it well". It is described as follows:

The services are small - fine-grained to perform a single function.

The organization culture should embrace automation of deployment and testing. This eases the burden on management and operations.

The culture and design principles should embrace failure and faults, similar to anti-fragile systems.

Each service is elastic, resilient, composable, minimal, and complete.

There are disadvantages^[5] to using a microservices archictecture some of which are;

Services form information barriers^[6].

The architecture introduces additional complexity and new problems to deal with, such as network latency, message formats^[7], load balancing ^[8] and fault tolerance^[9]. Ignoring one of these belongs to the "fallacies of distributed computing".

Testing and deployment are more complicated.

The complexity of a monolithic application^[10] is only shifted into the network, but persists.

Too-fine-grained microservices have been criticized as an anti-pattern.

Can we get the best features of a monolith, and micro-services? Does it have to be one or the other? Should we not use the approach which best suits our problem. One of the key aspects of Micro-services is controlled deployment of an application. In which case, shouldn’t we be able to deploy components as a Monolith or Micro-services where it makes the most sense to do so.

Proposed alternatives to nanoservices include;

Package the functionality as a library, rather than a service.

Combine the functionality with other functionalities, producing a more substantial, useful service.

Refactor the system, putting the functionality in other services or redesigning the system.

How can we get the best of both worlds?

Make sure your components are composable.

If your components are composable, then they are always the right size. You can combine them as needed into a collection of services, or everything into one service.

This is particularly important for testing and debugging. You need to know a group of business components work together without the infrastructure (eg. Middleware) getting in the way. For the purposes of a unit test, you may want to run all your components in one thread and have one directly call the other. This can be no more complicated than testing components of a monolith where you can step through your code from one component to another and see exactly what is happening.

Only once your components work together correctly without infrastructure, do you need to test how they behave with infrastructure.

Make your infrastructure as fast as your application needs.

Low latency trading systems are distributed systems, and yet they also have very stringent latency requirements. Most trading systems are designed to care about latencies much faster than you can see. In the Java space, it is not unusual to see a trading system which needs to have latencies below 100 micro-seconds, 99% of the time or even 99.9% of the time. This can be achieved using commodity hardware in a high level language like Java.

The keys to achieving low latencies are;

low latency infrastructure for messaging and logging. Ideally around a 1 micro-second for short messages,

a minimum of network hops,

a high level of reproduceability of real production load so you can study the 99%tile (worst 1 %) or 99.9%tile (worst 0.1%) latencies,

viewing each CPU core as having a specific task/service, with it’s own CPU cache data and code. The focus is on the distribution of your application between cores (rather than between computers).

Your L2 cache coherence bus is your messaging layer between high performance services.

You can perform a CAS operation on the same data between two different cores. Here, each thread toggles the value set by the other thread with a round trip time of less than 50 nano-seconds on Sandy Bridge processors^[11], less on newer generations.

Examples of low latency instructure in Java are;

Aeron^[12] - A reliable UDP transport,

Chronicle Queue - A persisted queue for messaging and logging.

These transports have different advantages in terms of handling load balancing and failover.

Make the message format a configuration consideration.

There is a number of competing concerns in message formats. You want;

Human readability so you can validate the messages are not only behaving correctly, but doing so in the manner you expect. I am often surprised how many issues I find by dumping a storage file or the message logs.

Machine friendly binary format for speed.

Flexability in terms of future schema changes. Flexability means adding redundancy so the software can cope with adding/removing fields and changing their data types in future. This redundancy is a waste if you don’t need it.

Ideally, you can choose the best option at testing/deployment time.

Some examples of serialization libraries where you can change the actual wire format to suit your needs are:

Jackson Speaming API^[13] - Which supports JSON, XML, CSV, CBOR (a binary format),

Chronicle Wire - Which supports object serialization YAML, a number of different forms of Binary YAML, JSON, CSV, Raw data.

What I found useful in YAML^[14] verses JSON, is the cleaner syntax which is designed to be human readable, rather than the subset of another language, the natural support for data types, comments, binary content and message seperators.

Conclusion

I think there is a lot of good ideas on how to use microservices, and I think many of the criticisms around them are based on how they have been implemented and I believe they are solvable.

Glossary

CPU core- "A processor core is a processing unit which reads in instructions to perform specific actions."^[15]

Debugging- the process of searching for and fixing defects in code.

Distributed System- A collection of autonomous computers linked in a network by middleware^[16]. A test can be distributed between a number of systems.

Failover- "A backup operation that automatically switches to a standby server or network if the primary system fails or is temporarily shut down for servicing."^[17]

Latency- The time an individual operation takes. "Together, latency and bandwidth define the speed and capacity of a network."^[18]

Library- "A collection of precompiled routines that a program can use."^[19]

Microservices- Independantly deployable programmes that act as components in a larger network.

Throughput- The rate of data or messages transferred which is processed in a certain amount of time. This rate is written in terms of throughput, e.g a road could have a throughput of 10 cars per minute.

Serialization libraries- The process that translates data into a format that can be consumed by another system.

Wire format- A defined way for sending data between mechines as bytes.

1. Wikipedia. (2016). Unix philosophy. Online. Available at: https://en.wikipedia.org/wiki/Unix_philosophy. Accessed: Mar. 2016

2. Wikipedia. (2016). Unix philosophy. Online. Available at: https://en.wikipedia.org/wiki/Unix_philosophy#Mike_Gancarz:_The_UNIX_Philosophy. Accessed Mar. 2016

3. Wikipedia. (2016). Shell script. Online. Available at: https://en.wikipedia.org/wiki/Shell_script. Accessed Mar. 2016

4. Wikipedia. (2016). Microservices. Online. Available at: https://en.wikipedia.org/wiki/Microservices#Philosophy. Accessed Mar. 2016

5. Wikipedia. (2016). Microservices. Online. Available at: https://en.wikipedia.org/wiki/Microservices#Criticism. Accessed Mar. 2016

6. Shirako, J., et al (2008). Phasers. Proceedings of the 22nd annual international conference on Supercomputing - ICS '08. Online. Available at: https://en.wikipedia.org/wiki/Barrier_(computer_science). Accessed Mar. 2016

7. Luca, A. (2016). Message Formatting. Online. Available at: http://networking.xtreemhost.com/wp/?p=279&ckattempt=1. Accessed Mar. 2016

8. Rouse, M. (2016). What is load balancing? - Definition from WhatIs.com. Online. Available at: http://searchnetworking.techtarget.com/definition/load-balancing. Accessed Mar. 2016

9. Rouse, M. (2016). What is fault-tolerant? - Definition from WhatIs.com. Online. Available at: http://searchdisasterrecovery.techtarget.com/definition/fault-tolerant. Accessed Mar. 2016

10. Wikipedia. (2016). Monolithic application. Online. Available at: https://en.wikipedia.org/wiki/Monolithic_application Accessed Mar. 2016

11. Intel® ARK (Product Specs). (2016). Products (Formerly Sandy Bridge). Online. Available at: http://ark.intel.com/products/codename/29900/Sandy-Bridge#@All. Accessed Mar. 2016

12. GitHub. (2016). real-logic/Aeron. Online. Available at: https://github.com/real-logic/Aeron. Accessed Mar. 2016

13. GitHub. (2016). FasterXML/jackson-core. Online. Available at: https://github.com/FasterXML/jackson-core. Accessed Mar. 2016

14. Ben-Kiki, et al (2009). YAML Ain’t Markup Language (YAML™) Version 1.2. Online. Available at: http://www.yaml.org/spec/1.2/spec.html. Accessed Jul. 2016

15. Stieben, D. (2012). What Is A Processor Core? MakeUseOf Explains. Online. Available at: http://www.makeuseof.com/tag/processor-core-makeuseof-explains-2/. Accessed Jul. 2016

16. Wikipedia. (2016). Middleware. Online. Available at https://en.wikipedia.org/wiki/Middleware. Accessed Jul.2016

17. Webopedia.com. (2016). What is failover? Webopedia Definition. Online. Available at: http://www.webopedia.com/TERM/F/failover.html. Accessed Jul. 2016

18. Webopedia.com. (2016). What is Latency? Webopedia Definition. Online. Available at: http://www.webopedia.com/TERM/L/latency.html. Accessed Jul. 2016

19. Webopedia.com. (2016). What is Library? Webopedia Definition. Onilne. Available at: http://www.webopedia.com/TERM/L/library.html. Accessed Jul. 2016

1	This Pauser controls the back off strategy in which no events are coming through. It will retry once, yield 100 times, then start sleeping from half a millisecond to 10 milliseconds.
2	Obtain the type of the parameter for the `ServiceHandler` and in this case it is a `Service`.
3	Create an output queue.
4	And pass it to the implementation so it can write to it’s output queue.
5	Create a reader for the input queue.
6	Start a thread which will read from the `serviceIn` reader.
7	Bind this thread to an isolated CPU where possible.
8	Read and process one message.
9	`reset()` the pauser if a message came, otherwise call it for a possible pause.

1	Take the timing since the last stage
2	Take the timing from the start

1	Benchmark for a target throughput.
2	Add a thread to record the OS jitter over the interval.
3	Turn on correction for coordinated ommission.

1	Just a writer
2	Reads that message and writes to the third service
3	Reads from the second service and writes to the outbound service.
4	The output gateway reads from the third service and writes its result to a log/queue.
5	The last service also sets the end to end timing.

1	Give the queue a unique id for tracing purposes.
2	Write a history for timings and sources for each message processed.
3	Read the output queue to see what the last message processed was.

1	Create an upstream queue.
2	Create a proxy which writes all methods calls to the upstream queue.
3	Create a downstream queue.
4	Create a proxy for the downstream queue.
5	Create the component which will write all outputs to the downstream queue.
6	Create a reader for the upstream queue which will call the combiner.
7	After writing a message to the queue, read it and call the appropriate method in the component.

1	Critical latency threashold for many systems.
2	Can still be important in some systems.

1	Run for 1 minute before shutting down.
2	Enable profiling between safepoints.

1	our component to test
2	our queue reader which will call the methods
3	loop to read/process one method at a time.
4	we have no more messages
5	dump the queue contents so we can see what the input was.

1	The first component combines sided prices
2	The second component listens to order ideas and top of book market data