saidie's log

learning, learning, learning

Handling HashMap with byte-string keys in Rust

Recently, I've tried to create a hash map whose key is a "byte string" in Rust. A naive code would be something like this: letm=HashMap<Vec<u8>,V> Note that using a borrowed type, like &[u8], as key is not a good idea. Of course, this does work but it would little bit inconvenient if you would like to use the key like a "string", e.g., m.get("ascii string") However, it will cause a compilation error.

Introduction to Renoir

About a month ago, I released a “production ready” Redis cluster client library for Ruby. It is named Renoir and was pushed to rubygems.org: https://rubygems.org/gems/renoir. It was surprising that there had been no reliable Redis Cluster client library for Ruby in spite of the fact that Redis 3.0 had been released about two years ago. In fact, there exist several implementations but their README always say like “this library is not yet production ready.

Dijkstra's algorithm by Redis and Lua (2 of 2)

In the previous post, a brief description about running Lua script on Redis and a code snippet to add a graph edge to a hash are given. In this post, an implementation of the Dijkstra’s shortest path algorithm is explained. I will not explain the algorithm itself since there are already so many articles explaining about it, e.g., Wikipedia’s page. Priority Queue A priority queue plays a primary role on the Dijkstra’s algorithm.

Dijkstra's algorithm by Redis and Lua (1 of 2)

Redis provides several kind of data structures and many functions to manipulate those data. But sometimes additional function is required for satisfying some demand. The power of Lua For example, you may need to delete a string only when the string is equal to a specified one but there is no such function. Although this is easy to implement by checking the equality of GET-ed string in client-side program and executing DEL command if necessary, it is difficult to make sure that this operation is atomic and you also have to implement a remote locking mechanism.

Redis code reading: sds

Last weekend, I read and summarized zmalloc.c which provides basic memory allocation mechanisms of Redis. In this weekend, I explored sds.c which implements many functions to manage a dynamic string efficiently; in fact, “sds” stands for Simple Dynamic String. This post describes a core of sds implementations. The version of Redis is 3.0.5. I put some comments on following code snippets. sds is just a char pointer with hidden header As well as zmalloc family, sds implicitly keeps track of available size and length of string by placing them on its (hidden) prefix.

Redis code reading: zmalloc

This post explains some fundamental functions of memory allocation used in Redis. These functions are kind of wrapper to hide architecture-dependent implementations and to keep track of the size of total allocated memory. The version of Redis is 3.0.5. Available Backend Implementations A backend memory allocator of zmalloc can be one of the following: libc malloc Default except Linux. jemmaloc http://www.canonware.com/jemalloc/ It seems less fragmentation than libc malloc.

Visualize rough Redis source code dependencies

Now, I’m getting interested in Redis. The concept of Redis seems to be different from other general purpose database like relational, document, graph databases; each of these employs a one-size-fits-all data model. By no free lunch theorem, these databases cannot store and fetch some kind of data efficiently. Some of this data can be efficiently handled by Redis since it provides specialized and primitive data structures. This specialty attracts me.