Meat is sexier: is that why we love it?

This is different. Out of scope, yes, but I need to publish this. It seems somewhat novel—or rather, I could not immediately find this thought when searching. Please let me know if you find a reference to similar ideas.

The background is mismatch -- there is a mismatch between the environment we are adapted to and the one we live in. Our bodies are adapted to the Stone Age (say, 100,000 years ago), when we were hunters and gatherers. We have not even adapted to farming (notable exception: some of us can digest milk). We are certainly not adapted to our modern society. For example, we love fast calories (sugar, processed carbs). In the Stone Age, this was advantageous for our survival—food was scarce, and we needed every calorie we could get. That is why we love it; we just cannot resist it. We are designed for that. Similarly, we love to relax. We are lazy by nature, we preserve our energy in front of Netflix. Good for us in the Stone Age, bad for us today.

Health problems associated with the Western lifestyle can typically be explained by this mismatch. But what about our love for meat? Why do we prefer meat over nuts and fat fish? They all have plenty of calories. Why do we gather around a fire to feast on grilled meat? Why don't we gather to feast on nuts? If nuts and fish are better for us, why haven't we developed a taste to prefer them? Shouldn't the survival rate of those who preferred nuts and fish have been higher than that of those who preferred meat?

Perhaps it (to some extent) is because meat is sexier. Men hunted in groups. The best hunters had good reproductive success with women. Women, think about it. Who is sexiest? The best hunter of a group of men -- the man who brings meat to the dinner feast? Or the man who gathers nuts? We are hardwired to support the survival of our genes. Even though nuts and fish may be better for our cholesterol levels, hunting and meat could result in more sex, more offspring. In evolution, that is what counts.

Not sure whether this is a good explanation, but at least it motivates me to lower my cholesterol by eating more plants and less saturated fat. This is not sexy. But, it is healthy.

Binson is implemented in 9 languages

I just updated binson.org and noticed that I now know of 12 implementations of Binson. In 9 languages: Java, C, JavaScript, Go, Swift, Python, PHP, Erlang, and Rust.

That's a bunch. I believe there is no implementation in C#, otherwise all major languages seem to be included in the list. Not counting Kotlin, since binson-java could be used for that.

For you who don't know, Binson is an exceptionally simple, binary serialization format. It's like JSON, but binary. And actually significantly simpler. Full implementations of a Binson serializer/deserializer typically range between 100 and 1000 lines of code. The complete spec is just two pages long. I suppose that is why there are so many implementations. In general: KISS - keep it short and simple! The most important design principle.

The Cycle Gap

 

 

 

The figure above shows the progress of the speed of computer processors and human brains during the last 40 years. It is reasonable to say that computers have become 10,000 times faster during this period. And human brains have remained the same.

 

We can say that a processor cycle is 10,000 times cheaper then in 1980 while a "brain cycle" costs the same. Because of this, most software code today is not optimized to save processor cycles, but rather to save brain cycles of the developers. The development cost of software is typically much higher than the cost of running the software (energy, hardware). So, in general, we do not optimize code for computers anymore, but for the human authors of it.

With the increasing cycle gap, programming languages have evolved to save brain-cycles, at the expense of computer cycles. However, when it comes to embedded programming for resource-constrained devices, the C language is still the king of the hill. It was developed in the 1970s! Very successful, but hardly the most productive language to program in. Perhaps now it is finally time for a change. I have been reading up on Rust and how it works. It certainly sounds good. It is popular. And I really like the memory model.

Will it have a chance to compete with C for embedded? Well, well. Rust is in many ways technically superior. However, C has such robust support, so many compatible tools and a vast amount of available code that can be reused. C is clearly defined (has a spec) and has multiple implementations and is very stable. A clear advantage of C is that APIs and example code for embedded processors are typically written in C, not Rust or anything else.

If vendors of embedded processors would ship with example code and APIs in Rust, instead of C, then Rust would win! However, as the situation is now, I don't dare to predict the future. Being technically superior is not enough. However, I would love to see a more modern language that will really compete with C. Also in the embedded world.

Powerpinions Kill Decision Making

Let me coin a word: powerpinion. A powerpinion is an opinion of a powerful person on a subject he lacks necessary knowledge of. Often, a powerpinion is delivered through a Power Point presentation.

Powerpinions can completely kill the decision making skills of an organization. It can go so far, that a technical decision can be taken that is obviously wrong to just about any expert on the subject.

So, how to avoid this? Perhaps the following:

• If you are a person with power (formal or informal), please always listen very carefully to those with more knowledge than you on the subject matter.
• Read! Study! Get the knowledge you need before having opinions on something.
• Challenge powerpinions! Ask about the facts. What is that opinion based on? Do you have a reference to that fact? Did we ask the experts? Who is the expert on this in our organization? Can external experts be used?
• Written communication may help. Powerpinions are often delivered orally accompanied with hard-to-interpret Power Point slides that are soon forgotten. If opinions are recorded and can be referenced in the future, it likely makes people more hesitant to have opinions om subjects they lack knowledge in.
• Be careful with topics that seem simple at first, but are not. Cryptography is one example. Those who know the most realize how little they really know, but those who know a little, think they know it all.

Anything else? Comments are appreciated. There is probably relevant research in the area that would be interesting to consume.

Added 2023-03-06. Link to HIPPO effect text: t2informatik.de/en/smartpedia/hippo-effect/.

IoT: WAP all over again?

In 1999, the Wireless Application Protocol (WAP) was introduced. It gained an extreme amount of interest and hype the following years. We know what happened. It failed dramatically.

WAP is a set of protocols focused on the delivery of media to mobile phones. Essentially it is a whole new stack of protocols besides the already established HTTP/(TLS/)TCP/IP stack for content transfer and HTML to express the content. The protocols were motivated with the need for protocols more suited to less capable devices. It was believed that HTML+HTTP was too heavy for mobile phones.

And it was, sort of. Mobiles had bad Internet connectivity and small monochrome screens with a low resolution. However, as you know, this changed rather quickly. Now our mobile phones have megabits of bandwidth to the Internet, high-resolution color displays and very capable multi-core processors. It did not take long until it was realized that: yes, a mobile can handle the ordinary Internet protocols for content distribution: HTTP+HTML and email and so on.

I wonder:

    Is the IoT world in a WAP-phase today?

It is suggested today that the ordinary TCP/IP stack cannot be used for IoT devices because of the limitations they have in processing power, connectivity, energy consumption. Instead, special IoT protocols are suggested. In particular, CoAP/UDP is often suggested.

I don't know, but perhaps we are in a temporary phase (5-10 years) where some 8-bit IoT devices cannot speak the same language as the rest of the Internet. But will that situation last? The vast majority of the protocols that we associate with "Internet" uses TCP/IP. And nowadays and mostly TLS/TCP/IP is used to encrypt the Internet communication. This TLS/TCP/IP stack is used for the World Wide Web (HTTP), for SSH to control computers remotely, for REST to present cloud APIs, for email (IMAP, SMTP) and just about everything else on the Internet. Even Netflix uses TLS/TCP/IP to stream vast amounts of video data to its customers.

So, if we want our physical IoT devices to interact directly with the existing Internet, they should speak the same language. They should speak TLS/TCP/IP. Reusing only IP with, for example, CoAP/UDP/IP is typical for IoT devices today. However, I believe it may be only a matter of time before IoT devices also speak TLS/TCP/IP and thus can interact directly with existing Internet services without translation and with end-to-end security.

Notably, the IoT services: AWS IoT Core and Google IoT Core mandate the TLS/TCP/IP stack. So, to use those services end-to-end, a device must speak that stack. I wonder about Amazon's and Google's choice of not supporting CoAP/UDP/IP, for example. Instead of supporting such protocols for their cloud services, they advocate using a local bridge that translates, for example, CoAP/UDP/IP traffic to TLS/TCP/IP.

We will see. In 2030, we know the answer. No one knows. In the Internet world, the experts are often wrong. Me included. However, I think we should consider whether we can reuse the existing, well-established "big-Internet" protocols also for our smallest devices. Yes, there is some overhead, but it might be worth it. When we send IoT communication on the public Internet, we do have the same need for security. At least. Also, there are efforts to make the existing TLS/TCP/IP stack more efficient. Those efforts include TLS 1.3, TCP Fast Open, efficient TLS implementations, and 6LowPAN. Perhaps we should focus our energy on that instead of building up a separate, incompatible stack of protocols for IoT devices just like we did for mobile phones with WAP.

Delay attacks - the forgotten attack?

The unlock scenario

Together with colleges at ASSA ABLOY, I am working with a secure channel protocol called Salt Channel. It is open source and can be found on Github. One potential application is to control a lock (lock / unlock commands) from a credential in the proximity of the lock (RFID card, mobile phone, fob).

Typical secure channel implementations, like TLS, provide confidentiality and mutual authentication. Data integrity is also provided. They generality protect against attacks such as: replay attacks, various types of man-in-the-middle attacks and more. However, I know of no secure channel protocol that protects against delay attacks.

A delay attack is an attack where the attacker simply delays a packet in the communication. This is definitely in the scope of what an attacker is allowed to do in just about any threat model. Also, in practice, it can be easy to perform. Delaying a packet may not seem like a threat at first. Surely, it did not appear to us while developing Salt Channel v1, that a packet delay could be a security issue. Well, it can!

The figure about shows the scenario. Alice wants to unlock Lock with her phone through a radio communication channel (Bluetooth, Bluetooth Low Energy, NFC) to Lock. Mallory intercepts the communication and function as a man-in-the-middle. Alice establishes a secure channel with Lock. This is successful since Mallory simply forwards all messages between Alice and Lock. Then Alice sends the unlock message to Lock. Mallory recognizes this packet by packets size, packet ordering and so on (based on studying previous communication sessions). Mallory cannot read the contents of the package, nor modify it, however she delays it. Alice detects that she cannot open the door. Something seems to not work. She walks away. Once Alice is gone, Mallory, who is hiding near the door, sends the unlock packet. The Lock unlocks and Mallory can get in through the door without being detected.

Literature

I have not found literature focused on this issue. Perhaps I am just googling wrong, I have not studied this much. Any help is appreciated. I don't even know a name for this, so I invented "delay attack" since I could not find a term for it. Surely, this must be treated in public literature already.

Note, that this is not a replay attack. The packet is not replayed and a delay attack requires completely different counter-measures.

Note, this is not a timing attack. Even though timing is involved, timing attacks is a completely different thing and should therefore not be used for this type of attacks.

Existing delay attacks

There seem to exist practical delay attacks against car key systems.

Protection

Many application layer implementations likely do not consider packet delay attacks and their implications. It can be argued that there should be protection against delay attacks in the secure channel layer.

When Alice sends the unlock command she implicitly wants the door to open now. Not in 60 seconds. We can see this as an integrity protection of her intent to unlock now. Of course, this could be handled by the application layer. But why not put it in the secure channel layer? It sure seems like a general problem to deal with in a general way.

Perhaps another blog post will deal with countermeasures of delay attacks. We need some.

Appended

2020-02-24. These links are of interest. They use the term "delay attack".

https://tools.ietf.org/html/draft-mattsson-core-coap-actuators-06#section-2.2

https://tools.ietf.org/html/draft-liu-core-coap-delay-attacks-01

TestableThread - a Simple Way to Test Multi-Threaded Code

Multi-threaded code is hard to write and hard to test. For years, I have been missing simple tools for testing multi-threaded Java applications. Anyway, for certain types of test situations the TestableThread class can be used. See below and the TestableThread class at the java-cut repo.

The idea is simple. By introducing named "breakpoints" in code run by threads, the test management code can control the execution of a thread by telling it to go to a certain breakpoint. Breakpoints are added to normal code using statements like:

assert TestableThread.breakpoint("breakA");

By using an assert, the breakpoint code will not incur any performance penalty when the software is run in production (the default way to run Java software is without -ea, that is, without enabling assertions).

Given defined breakpoints, test code can let threads execute till they reach a given named breakpoint, for example, the code:

t1.goTo("breakA");

will enable the t1 thread to run until it reaches breakpoint "breakA". When the breakpoint is reached, the t1 thread will stop executing until it gets another goTo() request.


The implementation below is only 50 LOCs or something, but still have been shown to be useful. There are, of course, lots of improvements / additions to be made including conditional breakpoints.

Code:

public class TestableThread extends Thread {

    private final Object sync = new Object();
    private volatile String breakName;
    
    public TestableThread(Runnable r) {
        super(r);
    }
    
    /**
     * Run thread until it hits the named breakpoint or exits.
     */
    public void goTo(String breakName) {
        synchronized (sync) {
            this.breakName = breakName;
            sync.notifyAll();
        }
        
        if (getState() == Thread.State.NEW) {
            start();
        }
    }
    
    /**
     * Run thread, not stopping at any break points.
     */
    public void go() {
        goTo(null);
    }
    
    public static boolean breakpoint(String breakName) {
        if (breakName == null) {
            throw new IllegalArgumentException("breakName == null not allowed");
        }
        
        Thread thread = Thread.currentThread();
        if (thread instanceof TestableThread) {
            TestableThread tt = (TestableThread) thread;
            synchronized (tt.sync) {
                while (tt.breakName != null && tt.breakName.equals(breakName)) {
                    try {
                        tt.sync.wait();
                    } catch (InterruptedException e) {
                        throw new Error("not expected: " + e);
                    }
                }
            }
        }
        
        return true;
    }

 }

The Unsolvable Rubik's Cube?

Introduction

A very puzzling thought has been on my mind for a while now: is it possible to create a mechanical puzzle, something like the Rubik's Cube, that is unsolvable in general, but still demonstrably solvable if one knows the scrambling moves.

Such a puzzle would be truly mind-boggling and incredible frustrating for puzzle-solvers. Imaging a puzzle that starts from the solved state, just like a Rubik’s cube with all sides completed. Then, a long enough sequence of random moves (a scrambling sequence) would make it impossible to go back to the solved state if the scrambling sequence is not known. If the scrambling sequence is known, it is however trivial to reach the solved state by simply applying the inverse of each move in the scrambling sequence in reverse order.

The definition of unsolvable

By impossible to solve or unsolvable, we mean that it is infeasible for a human to reach the solved state given a scrambled puzzle. To be concrete: there should be no general algorithm that solves the puzzle in less than 100 million moves. This roughly corresponds to one move every second for three years. Of course, one could always be lucky and find the solution faster, but on average, there should be no way to solve the puzzle in less than 100 million moves. And this is by my definition "infeasible" for a human to do.

Notation and puzzle properties

Let's go ahead and define this problem more rigorously.

Consider a mechanical puzzle with a finite distinct number of states. From a particular puzzle state, S, another state can be reached by making a move. A move, m, is a mathematical function from one puzzle state to the next.

    Si = mi(S_i-1)

OK, that looks ugly. MathML looks much better:

  ${\displaystyle S_i=m_i\left(S_{i-1}\right) }$

but it is slow to edit and does not work on all browsers (mobile phone browsers in particular). Let's go on using the ugly style.

Every move, m, has a corresponding inverse move, m'. So, for every move, m, and every state, S, there is an inverse move, m', such that:

  S = m'(m(S))

When dealing with long move sequences, the function notation with all the resulting parenthesis is too annoying, instead we will use the following notation:

  S3 = S0 | m1 m2 m3

to mean that when moves m1, m2, and m3 are applied to state S0, the resulting state is S3. So, with the new notation, we have:

  Si = Si-1 | mi

and

  S = S | m m'

Each puzzle state has a corresponding finite set of possible next moves. In the case of the Rubik's Cube, each state has 12 possible next moves (only 90 degree moves are considered, "quarter-turn metrics"). Often they are denoted: F, Fi, B, Bi, U, Ui, D, Di, L, Li, R, Ri.

The puzzle has one particular state called the solved state. Solving the puzzle is equivalent to finding a move sequence that transforms the current state to the solved state.

A scrambling of the puzzle is a random sequence of moves starting from the solved state. At each state, the next move is chosen randomly. Each possible next-move has the same probability of being chosen. A random scrambling of size n, is a random scrambling with n moves.

Now we are ready to summarize the properties of our puzzle. Lets call it an F-puzzle to distinguish it from other puzzles. An F-puzzle is a puzzle with the following properties:

• The puzzle has a finite number of states.
• One puzzle state is called the solved state.
• Each puzzle state has a set of next possible moves. The set is finite and has a size of at least two.
• For any state, S, and any move, m, there is an inverse move, m', such that:
  S = S | m m'.
• A scrambling is a random sequence of moves starting from the solved state. The state after a scramble of size N is:
  S_scrambled = S_solved | m1 m2 m3 ... mN.
• A scrambling is trivial to unscramble given that the scramble sequence is known:
  S_solved = S_solved | m1 m2 m3 ... mN mN' m(N-1)' ... m3' m2' m1'

Hopefully, that is precise enough. Tell me if the F-puzzle definition is not clear.

The Rubik’s Cube is one example of an F-puzzle. However, it is solvable. In particular, any scrambling of the Rubik’s Cube can be solved in 20 moves in half-turn metrics and 26 moves in quarter-turn metrics. See www.cube20.org.

The problem

So, now we can state the problem.

1. Can we create a mathematical unsolvable F-puzzle?

2. Can we create a mechanical unsolvable F-puzzle?

3. Can we create a practical mechanical unsolvable F-puzzle that can be mass-produced with a unit cost below 100 Euro?

To be concrete, we would like a mechanical puzzle that cannot be solved in 100 million moves after a scrambling of size 100 or less (20 or less would be nice). By "practical", we mean a puzzle that can be scrambled or unscrambled within one minute by most humans without training or tools. We also want a solution that is not a "mechanical computer"; it should be more of a Rubik's cube than a mechanical computer where symbols are used. For example, we don't want something like a code lock where digits are used to set a code.

That's the problem. Let's discuss potential solutions some other time.

The flaws of shared-secret authentication

Consider the scenario where Alice wants to authenticate to Bob; that is, prove her identity to Bob. Also, let us limit the discussion to digital communication.

Shared-secret authentication is common. In particular, password-based authentication is still the most common way to authenticate a user to website. Gmail, Twitter, Facebook -- all major Internet services still use some type of password-based login.

Shared-secret authentication is an authentication approach based on sharing secret information between Alice and Bob prior to the start of the authentication. For example a password (or pin code, Mifare UUID, credit card number etc) is shared between Alice and Bob.

The inherent flaws of shared-secret authentication are:

• Impersonation. Since Bob knows the password of Alice, Bob can impersonate Alice if Alice reuses the same shared secret when authenticating with other parties.
• Proliferation of secrets. To avoid the problem with impersonation, Alice may choose to use one password for each party she would like to authenticate with. The obviously leads to a problem of remembering the passwords and having password-recovery mechanisms for all of them.
• No real identity. Shared-secret authentication can only be used among the parties who know the secret. Alice cannot use the same credential to prove her identity to others if she wants to avoid the threat of impersonation. Therefore, she cannot build a single identity between, for example, Internet services. The identity really only exists between Alice and Bob. Alice is not able to prove her identity to some one else using the same credential she is using to authenticate with Bob.

All these problems can be fixed! And, of course, the solution is to use public-key cryptography.

Let's call this public-key authentication. Alice and Bob generates key pairs and exchange their public keys with each other. Bob cannot impersonate Alice, Alice can safely reuse her credential for authenticating with multiple parties, and she can (if she chooses to) maintain a single identity between multiple parties.

The principle is: secret credentials should never be shared! The key pair should be generated by Alice and the private key should not leave the place where it was generated (except for backup purposes).

One could also call this type of authentication: zero-knowledge authentication. This is because Alice proves possession of her private key without revealing any information about the private key itself. She needs to reveal zero information about her secret credential to Bob or any one else.

Conclusion:

If Alice wants real, secure authentication, she should use public-key authentication. This requires a credential that can do public key crypto computations and handle a digital dialogue with Bob. To generate the key pair, a source of random data is also required.

Three fundamental types of identifiers: Local ID, Global ID, and Provable ID

Identifiers are crucial in information technology and in our society in general. There seems to be three fundamentally distinct types of identifiers. Surprisingly, I could not find any prior text on these identifier types, so I will describe them in this blog post.

1. Local ID. Local IDs are unique, but only within a specific context. They require an ID issuer to attain unique IDs within the context. For example, an integer can be used as an ID of a row in a database table (primary key). This ID can be used to pick one row in the specific table. The database manager is the ID issuer that ensures that each row of the table has a unique ID. Uniqness of the ID is not guaranteed outside the ID context (the database table in the example).
   
   Local IDs are common. Examples include: domain names, passport numbers, email addresses, variable names and US social security numbers.
2. Global ID. Global ID schemes require no central ID issuer. An ID can be 16 random bytes for example. Version 4 UUIDs, and GUIDs are other examples of global IDs. A checksum of byte content can be used as a global ID of the content as long as the content is static.
   
   Global IDs are (in practice) globally unique, but they can be forged. Anyone can create a specific global ID and claim that it identifies something.
3. Provable ID. A provable ID is an identifier that in itself can be used to prove what it identifies. The identification (id -> entity) is provable. A provable ID cannot be forged like a global ID or a local ID. No one can create a different ID and claim that it identifies the same thing. Also, no one can use a particular provable ID and claim that it identifies something else.
   
   A provable ID is a cryptographic construction -- a public key or a secure hash or similar. A secure hash can be used to as a provable ID of static content (content-addressable storage [3]). The GIT version control system uses a secure hash (Merkle tree) to identify commits. This is one example of a provable ID.
   
   To identify entities that are "live" (can compute) their public key can be used as a provable ID. An entity identified with its public key can prove possession of the corresponding private key.

Some IDs have other information included in them beyond the data needed to identify an element. Such identifiers are not considered in this blog post.

That is my take on identifiers.

[1] UUID, https://en.wikipedia.org/wiki/Universally_unique_identifier
[2] GUID, https://en.wikipedia.org/wiki/Globally_unique_identifier
[3] Content-addressable storage, https://en.wikipedia.org/wiki/Content-addressable_storage

Blog name change

Today, I am changing the name of my blog from "From Theory To Disk" to "My Take on IT" to reflect a broader blog scope. Will possibly cover just about anything in information technology.

You can reach the blog at: http://blog.franslundberg.com/ as before.

BergDB 2015.1

Released a new version of BergDB today -- BergDB 2015.1. Download it from bergdb.com.

BergDB 2014.1

I made a release of BergDB today. bergdb-2014.1.zip can be downloaded from bergdb.com.

The release is focused on stability, clean code, and an improved API. The software is getting stable. There are no known issues and 650 units tests that say it works (85 per cent code coverage). The API is getter more stable between releases and the binary database file format is not changing much.

So, in my opinion, it is now production ready for many types of development projects.

Database Mathematics

We need mathematical rigor in the theory of databases. The current situation is that we have a very weak foundation for database theory. Not even the basic concepts such as atomicity and durability have generally accepted definitions. Instead some ill-defined (yet often somewhat useful) concepts are taken for granted without clear definitions.

As mentioned before in post ACID Does Not Make Sense, the concept of ACID transactions is ill-defined. This blog also has a post (The CAP Theorem Is Not a Theorem) on the so called CAP Theorem where I agree with Mark Burgess that the so called CAP Theorem is not a theorem at all. Brewers conjecture has not been proven with mathematical rigour.

Data storage is mathematics. I believe it is possible to describe the function of modern databases in rigorous mathematical terms using existing or mostly existing mathematics. I wish I had the resources and the skills myself to develop the much needed database mathematics (or "data storage theory", "data mathematics", "database theory").

The need for more rigor is even more important now when there is a more diverse set of database products available. Yes, I do talk about the NoSQL movement. The relational model of SQL databases has a useful mathematical background. However, a decreasing subset of databases use the relational model introduced by Edgar F. Codd in 1969.

Durability could be defined using probability theory. What is the probability that we can read a value written to a database after after one second, one hour, one day, and after ten years? What is acceptable?

Atomicity would also benefit from a mathematical treatment. With global atomicity and transaction with serializable isolation level (SQL speak), the database state evolves through a sequence of distinct states. A transaction is then a mathematical function that takes the database from one state to the next. I have a draft blog entry on the different types of atomicity that are used in common database products and programming languages. We will see if and when it will be published.

There is so much more to say and think about this. It would be interesting to get in contact with a mathematician who would be interested in making a contribution in this field. And maybe I missed something in the existing literature? Maybe there is significant work on this already?

There Is No "Now"

Let's consider a common database with distributed clients. Often we tend to think about the "current state" of the database or the "now" state. But, really, in general, there is no commonly agreed on global state that all clients would agree on.

There is no now!

Even for a centralized database running on a single server, there is no consistent current state. Clients will not observe a commonly agreed on database state "now". The observers are distributed and there is always a delay until an update has reached a client. And this delay is not deterministic. No matter how short, there is always a delay.

There can be a central consistent view of the state, but not at distributed clients / "observers". This is equivalent to the Theory of Relativity. Information travels with a finite speed. Two observers will in general observe an update at different times.

So, eventual consistency is the only consistency there ever is!

However, all observers of a centralized database can agree on a global history of the database state. If the updates are sent from the central server to the clients in a given order, the whole history of the data up to the time of the last update that has reached a client can be agreed on between all clients that have received the update. All data is old, there is no agreed on now, but the history up until the last update received, can be globally agreed on.

This is one of the reasons why databases should be append-only (called "immutable" by some) and support historic queries. They should remember the history. This is the only thing that can be globally agreed on.


References:

The video: The Value of Values, Rich Hickley

http://markburgess.org/blog_cap.html
The Special Theory of Relativity for distributed systems

NoSQL Distilled - A Good Guide in the NoSQL Jungle

The book NoSQL Distilled is a useful and compact guide when trying to navigate the NoSQL jungle out there. Read it, or at least, read this book review.

The subtitle: A Brief Guide to the Emerging World of Polyglot Persistence says much about the content and how the authors envisions the future of data storage. NoSQL Distilled by Martin Fowler and Pramod J. Sadalage (2013) is divided into two parts. The first treats the concepts that are important when considering choosing a NoSQL database. The second part is focused on how to implement a data storage system with NoSQL.

The book works fine for someone with little prior knowledge of NoSQL, but is still a fruitful read for those with more background knowledge. The text is easy to navigate and it is easy to skip the material that might not be of importance to the reader.

The book starts by describing the value of traditional SQL databases with focus on transactions and the advantage of the standardization that SQL brings to the these databases. The object-relational impedance mismatch is described and is seen as one of the driving forces behind the NoSQL movement. The other highlighted force behind NoSQL is horizontal scalability to be able to handle larger amounts of data.

The book does not offer a precise definition of "NoSQL", but lists some common traits: they do not use the relational model, they can run distributed on a cluster of servers, open-source, are build for the web and are schemaless. The authors simply states that "NoSQL" is very ill-defined. Defining the meaning of NoSQL is tricky, but I would have appreciated an attempt by the authors. At least a definition for how it is used in the book would have been suitable. In general, I would have appreciated a more rigorous definition of important terms and data models. I understand the authors, however. Terms and definitions will change as they slowly get more accepted and standardized, so there is a risk to "be wrong". But on the other hand, the authors miss an opportunity to contribute to the definition and maturity of the concepts.

The chapter "Distribution Models" describes elegantly the different ways the function of a database can be shared between a set of servers (or not shared): single master servers, master-slave replication, peer-to-peer replication (multi-master).

The book contains a chapter on data consistency and treats, among other things, the CAP theorem (which is not a theorem). The CAP concept has been used and misused frequently the last years. The authors have an interesting take on it:

It is usually better to think not about the tradeoff between consistency and availability, but rather between consistency and latency.

The chapter contains fresh thought on durability. Let me quote: “it’s useful for individual calls to indicate what level of durability they need”. I completely agree. In a larger project I ran into the incredibly frustrating problem that the database did not support what I like to call "durability control". At least not on a per-transaction basis. For this actual case, we needed to wait until a transaction (larger payment) had been replicated to a remote location before the transaction is conformed to the user. The lack of durability eventually led is to change database.

The book handles map-reduce in a simple, practical and accessible way. Map-reduce is a way to run database queries in parallel on multiple servers without the need for the client to explicitly divide the task into pieces suitable for each server. This is handled by the database engine completely transparent the the client.

The authors have chosen to divide the NoSQL databases into four categories: key-value, document database, column-family stores, and graph databases. This categorization is reasonable, but not obvious. It would have been interesting to know why the authors chose these specific categories. The chapters on these database categories are well-written and gives the reader a valuable overview. Each chapter contains a section with typical use cases that suits certain types of databases. Very useful.

The chapters "Polyglot Persistence", "Beyond NoSQL", and "Choosing Your Database" finish the book. Polyglot Persistence describes how a heterogeneous collection of databases are growing in fertile soil while the total dominance of SQL databases is fading. Different storage needs are best solved by different database types. The chapter on how to choose a database is short and has no advice on specific database products. Men the book is short and introductory, so this is reasonable. One could easily write a whole book on the topic of how to choose database given specific storage needs.

"Beyond NoSQL" is indeed interesting reading. The authors here describes storage technology that does not fit under the NoSQL umbrella. Among other things, they write something I find fundamental and worth repeating:

When we think of data storage, we tend to think of a single-point-of-time worldview, which is very limiting compared to the complexity supported by a version control system. It’s therefore surprising that data storage tool haven’t borrowed some of the ideas from version control systems. After all, many situations require historic queries and support for multiple views of the world.

I completely agree! The lack of support for historic queries in existing databases is one of the main driving forces for developing BergDB (bergdb.com). BergDB handles historic queries just like a query for the last state of the database. All states (the most current state as well as historic states) are available for queries at the same time.

The book is good and I really enjoyed reading it. But there is one, nearly unforgivable, mistake. The book does not cover consistent hashing (original paper, introduction). Consistent hashing is used by Riak, Cassandra, Memcached and is fundamental to achieving reads and writes that scales horizontally and linearly.

So, read the book. But also read about consistent hashing.

Good luck in the NoSQL jungle out there!

One in a Million, PUT

Here's the performance result for PUT operations. See the previous post for information on the setup. A PUT operations updates the value of an existing key. One million keys are stored. The PUT operations are run one-by-one by a single thread. 10,000 or 100,000 PUT operations (random keys) are made in sequence and timed. The time per PUT is recorded.


This result should be taken with a grain of salt! The default settings are used. For MySQL 5.5 this means that the InnoDB storage engine is used and it flushes to disk for every write (innodb_flush_log_at_trx_commit=1) before it returns to the client. Presumably, this is the case for Riak too, while MongoDB seems to return to the client without flushing data to disk.

It would be interesting to dig further into this... As is always the case with performance testing. My ugly source code is available upon request.

As often is the case, I/O limits performance, not the CPU. When the data is cached and available in-process, a PUT operation only needs to take in the order of 10 us (BergDB, Berkeley, BerkeleyT). Thus, a throughput in the order of 100,000 transactions/s is achieved. Prevayler is a bit slower. This is likely because of the overhead of serializing Java objects.

The in-process databases write data for every transaction, but they do not flush the data all the way to physical disk storage for every transaction. It is impossible to do if one wants to achieve a throughput in the order of 100,000 transactions/s. The default approach by BergDB is to flush data to disk every 0.1 seconds.

There are many important things to say about disk flushing, how to define "durable", and what I like to call durability control. Hopefully, I will be able to address these important topics in future posts.

One in a Million

GET performance of MongoDB, Riak, BergDB, MySQL, and more

Ola Rende (a colleague at Citerus) and I will hold a presentation of a few NoSQL databases on January 21st in Stockholm. Welcome to participate! Contact Citerus for details and to sign-up.

While preparing, I wanted to write some code to test the databases for one specific use case. I chose a simple test that works for any database that can store key-value pairs.

First, the database is populated with one million 4-byte keys with corresponding 4-byte values. The value is the same as the key. The keys are the integers from 0 to 999,999 encoded in binary. They are added in random order. The key set happens to be dense (all non-negative integers < 1,000,000), but this is just a coincidence. The database must store the entries in a way that would allow any set of integers as keys.

Then the GET performance of the database is tested. This is done by accessing 100,000 of the entries selected randomly. This is repeated three times and the best result (best average GET time) is recorded. This means that the cache of the database should be filled and presumably, there is no need to read from disk for the 2nd and 3rd run. The access is made from a Java process on my computer. My setup: Ubuntu 12.04 LTS, Toshiba Z930 laptop, i7 processor, SSD disk, JVM 1.7 from Oracle. The database is either run in-process for the in-processes databases, or as a separate process on localhost. By default, I used the default settings of the databases.

Here is the result:

Conclusions

For a data set that fits into cache, the tested in-process databases are in the order of 100 times faster that the out-of-process databases (MySQL, MongoDB, Riak). This is not surprising. On my computer, I measured the network round-trip (TCP, one byte back and forth) between two processes on localhost to be 50 us.

For many applications, all databases tested can be considered fast. Riak responds in a little more than 1 ms which is acceptable to many applications. Note that the tests are run with client and server on localhost. The network round-trip overhead could of course be 10 ms or something for computers further away from each other. Also, if data would not fit into cache, the disk access time may be as high as 10 ms and it would limit the performance. Consider using SSD disks!

Of, course the result should not be seen as some overall evaluation of the databases. For example, Riak scales horizontally and provides high-availability and BergDB supports historic queries. There is much, much more to these databases then what is tested here.

Other comments:

• IO limits performance. Most likely, the network or the disk IO will limit the performance of your database setup. When data is cached and available in-process, lookups can be done within a few microseconds, while disk and network access times often are in the order of milliseconds.
• Consider an in-process database. If you want an application database, not an integration database, an in-process database may be a performant alternative.
• Little benefits of all-in-memory databases? I question the benefits of all-in-memory databases. The in-process databases Berkeley DB and BergDB perform on par with the all-in-memory solutions (TreeMap, Prevayler). So why use an all-in-memory database with its problem of a slow startup (all data must be read from disk to RAM at startup time which may take a long time)?
• You might need 1000 servers to beat one. Riak and Cassandra may scale horizontally and linearly, but a single server can have a very impressive throughput for some use cases. So, don't get a huge cluster of servers if you only need one server. See The LMAX Architecture by Martin Fowler as an example.
  

Per database comments

TreeMap. This is the java.util.TreeMap class. Not a real database, but included for comparison. Access to it is made in a synchronized block.

Prevayler. Prevayler 2.6. Prevayler is an all-in-memory database. All data is stored in memory and must be read to RAM at startup. The data is stored in one big serializable Java object. Since it is stored as a Java object in the JVM, the performance for random access is optimal. It takes less than one microsecond to get a value given its key. This is the same performance as a TreeMap; actually, a TreeMap is used to store the data for this performance test.

BergDB. BergDB is a database I created. When data is cached, the GET time is on par with what is offered by an all-in-memory solution like Prevayler or TreeMap.

Berkeley. Berkeley DB, Java Edition, 5.0.97 is a stable, high-performance in-process database. "BerkeleyT" is Berkeley DB used with transactions enabled. When comparing performance, note that BergDB and Prevayler always supports transactions (cannot be disabled).

MySQL. MySQL 5.5 with default settings (InnoDB storage engine, isolation level: repeatable read). The officially supported JDBC Java Driver is used. To save time, only 100k keys were used. The actual GET time for 1M keys could be somewhat higher.

MongoDB. MongoDB with their official Java driver. Default settings.

Riak. Latest stable release of Riak with Java client 1.4.2. For this database, I used only 100k key-value entries to save some time. So the actual GET time for 1M keys could be somewhat higher.