Sunday, May 8, 2016

Replicated Object. Part 7: Masterless Consensus Algorithm

1 Abstract

The article introduces the new generation of consensus algorithms: masterless consensus algorithm. The core part consists of less than 30 lines of C++ code. Thus it is the simplest consensus algorithm that contains several outstanding features allowing to easily developing complex fault-tolerant distributed services.

2 Introduction

There are only two hard problems in distributed systems:
2. Exactly-once delivery.
1. Guaranteed order of messages.
2. Exactly-once delivery.

Mathias Verraes.

Distributed programming is hard. The main reason that you should not rely on the common assumptions about timings, possible failures, devices reliability and operation sequences.

Tuesday, November 10, 2015

Replicated Object. Part 2: God Adapter

1 Annotation

The article introduces a special adapter that allows developers to wrap any object into another one with additional features you want to include. Adapted objects have the same interface thus they are completely transparent from the usage point of view. The generic concept will be introduced step-by-step using simple but powerful examples.

2 Introduction

Disclaimer. If you are not tolerant to C++ perversions please stop reading this article.

The term god adapter is originated from god object meaning that it implements many features. The same idea is applicable for god adapter as well. Such adapter has outstanding responsibility and includes features that you can or even cannot imagine.

Sunday, September 20, 2015

Replicated Object. Part 1: Introduction

1 Abstract

The present article explains an early prototype that introduces the concept of replicated object or replob. Such object is a further rethinking how to deal with complexity related to distributed systems development. Replob eliminates the dependency on the external reliable service and incorporates the consistent data manipulation into the user-defined objects representing data and related functionality. The idea is based on using the power of C++ language and object-oriented programming that allows complex logic utilization within distributed transactions and significantly simplifies development of the reliable applications and services. Subsequent articles will explain presented approach in detail step-by-step.

2 Introduction

Disclaimer. Almost all methods specified in the article contain dirty memory hacks and abnormal usage of C++ language. So if you are not tolerant to system and C++ perversions please stop reading this article.

Today, topics related to distributed systems are one of the most interesting and attract many people including developers and computer scientists. The popularity can be explained in a simple manner: we need to create robust fault-tolerant systems that provide safe environment to perform execution of operations and data storing.

Along with that, the consistency of distributed system plays important role. It comes with a price if you want to have stronger notion of consistency level. There are a set of systems provides a weakest form of consistency: so called eventual consistency. While those systems have relatively good performance they cannot be used in many areas where you need to have transactional semantics for your operations. The thing is that it is much simpler to meditate and reason about a system under consideration using one of the strong forms of consistency like strict consistency or linearizability. Due to those consistency levels, it is much easier to develop reliable application with safe semantics of operations.

Wednesday, August 12, 2015

New Language Paradigm Philosophy

Rules

  1. Simple things must be simple.
  2. Complex things must be as simple as possible.

Meaning that the implementation should be the simplest.

Four Noble Truths

The approach is like a buddhism:

  1. There is a complexity.
  2. There is a root cause of the complexity.
  3. There is an absence of complexity.
  4. There is a way to avoid complexity.

Complexity

API depends on the model you choose: actor, callback-style, subscription, future/promise, RPC-style etc. But the model should be implementation details: you should change it if you wish. Currently, it’s not the case.

The idea is to transform the code in such way to have flexibility in the model and approaches. One should consider the model as a low-level (implementation details) architecture.

Building Blocks

You should build the application from top to bottom (from architecture to implementation), not from bottom to top (from classes and libraries to satisfy the requirements/architecture).

Monday, December 8, 2014

C++ User Group in Saratov, October 2014

On 25th, October 2014 the regular C++ meeting conference was held. It was planned to be 5 speakers but one of them could not attend due to family circumstances. Thus the total amount of presentations were equal to 4:

  1. Vasiliy Sorokin: Google C++ Mocking and Test Frameworks
  2. Grigory Demchenko: Asynchronicity And Coroutines: Data Processing
  3. Rainer Grimm: Functional Programming in C++11
  4. Mikhail Matrosov: C++ Without new and delete

Below you may find small description related to each presentation.

Monday, August 4, 2014

Memory Model: Brief Description

Introduction

My previous post was related to discussion about memory model in C++11. Now let’s talk about memory model itself briefly.

So, memory model contains 3 different use cases. It can be classified differently. Let’s use the following criteria: how many threads are affected on atomic operation:

  1. One thread, known as relaxed atomic operations.
  2. Two threads, known as acquire-release operations.
  3. More than two threads, the strongest guarantee, known as sequentially consistent operations.

One Thread: Relaxed Atomics

It’s quite simple: if you just need to have eventual atomic consistency you may use relaxed atomics. It has the best performance but it guarantees only atomic operation for that value. Other threads may read old values, but eventually updated value will appear. It’s useful, e.g., for statistics, debugging flags etc, or during intermediate atomic operations in some complex scenarios.

Friday, July 18, 2014

C++11 Memory Model

What is the most interesting and promising feature in C++11? Many of you might say it's the rvalue semantics including move and perfect forward concepts. But I don't think so.

Let me clarify what I mean. Definitely, rvalue semantics is a step forward. But it's not the most advanced and interesting part of the standard. The reason is that it doesn't contain something new. Forwarding is like a syntactic sugar, it allows avoiding unnecessary usage of overloaded functions. Move semantics had been introduced before C++11, for example, in Ultimate++ framework, transfer semantics. So, it's like a syntax evolution to deeper improve performance when return value optimization cannot be applied.

Meanwhile the memory model is another story. It resolves one of the most sophisticated problems: how to obtain common denominator for very different hardware processor models with different assembler instructions. It's very complicated problem. You have to know about every platform to create such denominator. And I would say that it has been resolved perfectly.

Wait, wait, wait. Most of readers might raise an objection against "perfect solution". It's the most complex part of the standard. It's true. But the problem itself is much more complicated. So solution from the problem statement point of view is much simpler.

Solution is great indeed. It provides an abstraction that allows to create highly portable and still very efficient applications using appropriate atomic instructions on any platform: from x86 to modern ARM and DEC Alpha (with special consume/release semantics, as if DEC and ARM platforms like relaxing). Finally, memory model of next generation of ARM processor is going to have special atomic sequential consistency instructions providing better performance in most cases. It's the case when hardware pays attention to software needs. It's fundamental model that has far-reaching consequences. And it's amazing!

I'm very expecting that in the nearest future any lock-free and wait-free articles will contain detailed description of memory ordering for all involved atomic operations.