Blogs

Digital Currency without public ledger

A public ledger used by numerous crypto currencies has been a trouble since the very onset of digital money. Be it blockchain or tangle (used by IOTA) – the result is the same. One needs to store transaction data somewhere. In order to store it you need to be sure that the transactions are valid. In other words we need to reach a consensus among the participants that provide and maintain the currency data.

Proof-of-Work and Proof-of-Stake are two common ways to validate transactions. The former burns electricity in vain, the later shifts the equality of participants towards the richest ones which entails a lot of security issues

Why public ledger? Why public or why ledger at all? Public is good. We are sure that there is no central point in the technology and anyone (or almost anyone) may participate. But why do you need to store and record transactions? If we do not need a ledger for the sake of ledger, then its main role is to ensure that the data is valid. And for this purpose we do not need to chain blocks and create the ledger. We only need to be able somehow to say that the data is valid.

Anyone can possess data (or money, because money is data). It is a question about how everyone could be sure that this data is not counterfeit. Some authority is needed who is believed to be entitled to verify the data.

This authority can be centralized: a bank, payment aggregator (like paypal) etc., or decentralized if it has p2p architecture, including distributed database.

So far, it is quite easy to validate someone’s data, but how do you solve a notorious double-spent problem without a public ledger? If you hold valid data it is possible to send it to multiple recipients. Bad.

One approach is to ‘own’ the data after you receive it. The original data becomes invalid after you ‘own’ it. It looks like a digital handover. You transfer the data from hand to hand, but in digital world. There is a short period of time when the sender sent the data and a the recipient did not take it. During this period the data belongs to both sender and recipient.

The example of such technology is RAIDA – Redundant Array of Independent Detection Agents. The Array helps to change data in a way that the previous owner loses control over it. The technology is used as an underlying verification mechanism in Cloud Coins. It is still centralized, so it is not that cool and pretty as it might seem. At the moment, that RAIDA implementation has 25 nodes distributed across the world. It is not P2P, though. Only trusted nodes can be part of RAIDA. However, it is the first step in getting rid of annoying public ledger. RAIDA does not record transactions because it only stores data. And there is no way to track customers transactions, because they are not recorded at all.

Hopefully, the technology will evolve into something really distributed, so that it would earn much more trust from digital community.

Matching MariaDB internal thread ID with OS thread

In order to find a thread id, that would normally be returned by gettid() inside the thread, we might use a simple query:

MariaDB [oap]> show processlist;
+-----+------+-----------+------+---------+------+-------+------------------+----------+
| Id  | User | Host      | db   | Command | Time | State | Info             | Progress |
+-----+------+-----------+------+---------+------+-------+------------------+----------+
| 358 | root | localhost | oap  | Query   |    0 | NULL  | show processlist |    0.000 |
+-----+------+-----------+------+---------+------+-------+------------------+----------+

The Id column has little to do with OS thread ID. You can not match it with any thread you find via ps command.

This might be necessary if we have a long query running and need to examine what a certain thread is doing to make sure everything is fine.

For instance, here is an output of a few MariaDB threads

mysql    11646 10834 11646  0   20  ?     00:00:00 /usr/libexec/mysqld --basedir=/usr --datadir=/var/lib/mysql --plugin-dir=/usr/lib64/mysql/plugin --log-error=/var/log/mariadb/mariadb.log --pid-file=/var/run/mariadb/mariadb.pid --socket=/var/lib/mysql/mysql.sock
mysql    11646 10834 11648  0   20  ?     00:00:28 /usr/libexec/mysqld --basedir=/usr --datadir=/var/lib/mysql --plugin-dir=/usr/lib64/mysql/plugin --log-error=/var/log/mariadb/mariadb.log --pid-file=/var/run/mariadb/mariadb.pid --socket=/var/lib/mysql/mysql.sock
mysql    11646 10834 11649  0   20  ?     00:00:38 /usr/libexec/mysqld --basedir=/usr --datadir=/var/lib/mysql --plugin-dir=/usr/lib64/mysql/plugin --log-error=/var/log/mariadb/mariadb.log --pid-file=/var/run/mariadb/mariadb.pid --socket=/var/lib/mysql/mysql.sock

The third column is an OS thread ID. And it does not match Maria’s internal ID

It is possible to turn on performance schema and examine the threads table in the corresponding database. A field named THREAD_OS_ID of the table will give you an exact OS thread ID.

mysql> SHOW VARIABLES LIKE 'performance_schema';
+--------------------+-------+
| Variable_name      | Value |
+--------------------+-------+
| performance_schema | ON    |
+--------------------+-------+
mysql> SELECT * FROM threads;

But, it requires the server to be restarted and seriously hurts overall performance.

So, there must be another way to find OS thread ID. And it exists.

First off, it works only for InnoDB databases, which usually is not a problem, since it is the most common DB engine nowdays. We need to examine InnoDB status:

mysql>show engine innodb status\G;
...
------------
TRANSACTIONS
------------
Trx id counter 866A5
Purge done for trx's n:o < 866A3 undo n:o < 0
History list length 1058
LIST OF TRANSACTIONS FOR EACH SESSION:
---TRANSACTION 0, not started
MySQL thread id 278, OS thread handle 0x7f7798249700, query id 5180433 localhost root
show engine innodb status
---TRANSACTION 7C82C, not started
MySQL thread id 255, OS thread handle 0x7f7798200700, query id 5014696 localhost root
---TRANSACTION 866A3, ACTIVE 459 sec updating or deleting
mysql tables in use 1, locked 1
27737 lock struct(s), heap size 3029432, 2849739 row lock(s), undo log entries 1444562
MySQL thread id 195, OS thread handle 0x7f77982db700, query id 5137989 localhost root
delete from deliverlines
----------------------------
END OF INNODB MONITOR OUTPUT

Here, in the TRANSACTIONS section, we can see a MySQL thread ID and a corresponding OS thread handle, which is nothing else than an address of pthread_t struct of a MariadDB OS thread. The same identifier will be returned by pthread_self()

Now we need to match OS thread handle with OS thread ID. It can be done by attaching MariaDB server process by a debugger. Be careful, the server will be suspended when you attach to it, so do the things fast

# gdb attach 11646
...
(gdb) info threads
 ...
  4    Thread 0x7f779836d700 (LWP 11666) "mysqld" 0x00007f779ee9e101 in sigwait () from /lib64/libpthread.so.0
  3    Thread 0x7f7798249700 (LWP 9613) "mysqld" 0x00007f779ee9d49d in read () from /lib64/libpthread.so.0
  2    Thread 0x7f77982db700 (LWP 10442) "mysqld" 0x00007f779ee9d49d in read () from /lib64/libpthread.so.0
* 1    Thread 0x7f779f2b7840 (LWP 11646) "mysqld" 0x00007f779d704dfd in poll () from /lib64/libc.so.6

Now, it is clear that OS thread handle 0x7f77982db700 has tid with number 10442.

Attach to it and enjoy.

# strace -p 10442

Linux process anonymous memory

A server administrator who tries to detect the most RAM-consuming process in the system may have a fair question: what actually memory consumption is. To address the question one needs to go deeper into the kernel realm trying to avoid, if possible, popular utilites like ps and top. Them merely display information that lives in the kernel.

Every process or task is represented by struct task_struct in the kernel which holds loads of process info. We only intersted in one particular and important field: struct mm_struct. The field represents a process virtual memory layout which has almost nothing to do with physical RAM. A rough view of the layout might be seen in /proc/<pid>/maps file for the process.

So, we have come to the virtual memory of processes. This is all the pages the process has. “To have” pages means that process is allowed to read/write them or execute a code in them. This, in turn, means that kernel will properly respond to page-fault hardware exception by altering process page tables. If the virtual address does not belong to the process, the kernel will send SIGSEGV or other signal to the process, otherwise it will try to map the pages to the virtual address and load the contents of the page from the backend storage (swap), if necessary.

If a process tries to allocate memory it may do this in several ways: extending the stack (push operation), extending the heap (sbrk() call), direct allocation (e.g. mmap()). Functions like malloc() make use of mmap() in most cases. Mmap stands for ‘memory mapping’ which will map pages to the process virtual memory.

# cat /proc/$$/maps
00400000-004dd000 r-xp 00000000 08:01 197198                             /usr/bin/bash
006dc000-006dd000 r--p 000dc000 08:01 197198                             /usr/bin/bash
006dd000-006e6000 rw-p 000dd000 08:01 197198                             /usr/bin/bash
006e6000-006ec000 rw-p 00000000 00:00 0
02610000-02652000 rw-p 00000000 00:00 0                                  [heap]
7f8665bcb000-7f8665bd7000 r-xp 00000000 08:01 198477                     /usr/lib64/libnss_files-2.17.so
7f8665bd7000-7f8665dd6000 ---p 0000c000 08:01 198477                     /usr/lib64/libnss_files-2.17.so
7f8665dd6000-7f8665dd7000 r--p 0000b000 08:01 198477                     /usr/lib64/libnss_files-2.17.so
7f8665dd7000-7f8665dd8000 rw-p 0000c000 08:01 198477                     /usr/lib64/libnss_files-2.17.so
<...trimmed...>

Each mapping line has start and end virtual address, permissions, offset in the mapped file, major-minor device numbers where file resides, inode of the file and file name.

Mapping can represent a file on disk or be anonymous. Anonymous memory is the memory we allocate and use (e.g via malloc()). In the maps file above lines 5 and 6 are anonymous mappings.

Lets create our own anonymous mapping:

#include <stdio.h>
#include <sys/mman.h>

int main(int argc, char *argv[]) {
        char *ptr;

        ptr = (char *) mmap((void *) 0x123000, 2 * getpagesize(), PROT_WRITE|PROT_READ, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
        printf("ptr is %p\n",ptr);

        sleep(100);
}

The first argument is our desired virtual address where we want to map the pages. The second argument is a mapping length; we use two pages. The third one is a bitmask of the permissions of our mapping. The fourth argument defines that our mapping is anonymous and is not backed by any file. We do not need the other arguments for they are only required for file-mapped memory.

Compile and run it:

# ./a.out &
[1] 26140
ptr is 0x123000
# cat /proc/26140/maps
00123000-00125000 rw-p 00000000 00:00 0
00400000-00401000 r-xp 00000000 08:01 1253390                            /root/a.out
<...trimmed...>

We asked to create a two-page mapping from the virtual address 0x1230000. Since memory is allocated in pages, the address should be multiple of the page size. 4096 bytes in our case. The kernel does not guarantee to map the pages at the specified address, so normally we would put 0 as the first argument to mmap() to allow the kernel to choose the address.

Our mapping is the first. The size is exactly two pages 2 * 4096 = 8192 = 0x2000 bytes. It has exactly the start address we asked. The permissions and size, of course, the same as well.