Code Sample: Implement a Persistent Memory Cache-A Simple Find Example

Introduction

In this short article, I show how to improve the user experience by using persistent memory as a cache. The advantage of using persistent memory resides in the unification of the data model, avoiding the need to split data between main memory and storage.

For the persistent memory code, I use the C++ bindings of the libpmemobj library, a high-level transactional library that is part of the Persistent Memory Development Kit (PMDK). To learn more, visit the Intel® Developer Zone Persistent Memory Programming site, where you will find the information needed to get started.

All the code referenced here can be found in the following repository. Follow the instructions there to compile it.

The Volatile Version

This code sample corresponds to a simplified version of the command find in Linux, called find-all. If you go to the repository linked above, you will find that the sample also comes with a script called create_test_tree.sh. This script creates an arbitrary directory structure given three parameters:

tree-root, which is where the root of the directory structure is placed.

tree-depth, which is how many levels of subdirectories we want in the tree.

files-per-level, indicating how many files will be created per level.

The files created will be empty (since find is used to find files by name, we only care about the file name here). The number of subdirectories in each level is fixed to three.

For example, to create a directory tree with six levels and 100 files per level, with the root at ./test_tree, we run:

$ ./create_test_tree.sh test_tree 6 100

If you list the root, you should see something like this:

[sdp@localhost find_all_pm]$ ls test_tree/
acvlhpknswalwbwtnpzggaewqnacpopv  httjlfkrsbjvnydfwkfiekfqkbqtstkq  rgwbefyncedkyvpziijfqgzxcghcbyua
agocrfeblfzeirldzyzyqeqsqecwodio  hxuimxojjfprdmuoqxkeopavhjuldomd  rhafepwdyvoxoxhhfqyybajfhkijkryh
bdpdfdfysqkpilptzfqypldeydiemcel  idvcepykqyvwuthshsopckxkpuxqmdab  
...
[sdp@localhost find_all_pm]$

File names are 32 characters long and generated randomly. Directory names are generated randomly as well, but they are just 5 characters long. For the curious, we have generated 36,400 files in 364 subdirectories.

We can now search for file names containing arbitrary strings. Let’s search for files whose names include the string “aazz”:

$ ./find-all ./test_tree aazz
./test_tree/gzqtl/kwntu/fvecf/tivvl/kuzpl/klwfgiwqenljruorfdupgkmaazzydrik
./test_tree/gzqtl/kwntu/opuci/ktxmi/chisz/enlvjaazzuanuguupnnrrwxgfafekwck
./test_tree/hfibr/fifpu/wtpdt/mgrex/mbrma/sapjhqtpnxaazzkflhbmgtrhqbcxkvuj
$

As it is possible to see, three files are found. How much time does it take to do the search? Let’s find out:

$ time ./find-all ./test_tree aazz
./test_tree/gzqtl/kwntu/fvecf/tivvl/kuzpl/klwfgiwqenljruorfdupgkmaazzydrik
./test_tree/gzqtl/kwntu/opuci/ktxmi/chisz/enlvjaazzuanuguupnnrrwxgfafekwck
./test_tree/hfibr/fifpu/wtpdt/mgrex/mbrma/sapjhqtpnxaazzkflhbmgtrhqbcxkvuj
...
real    0m0.579s
user    0m0.517s
sys    0m0.060s

* see performance disclaimer

Over half a second! That may not seem like a lot of time, but seconds can add up if search queries are required often. Moreover, and as the tree structure becomes more complex (see below), the response time can start to be measured in whole seconds, which can really degrade the user experience.

The Persistent Version

In this version, a persistent data structure is added that mimics the directory structure (that is, a tree) for each pattern. The data structure starts with a root object. The root has a list of patterns that the user has searched for in the past:

class root {
  private:
    pobj::persistent_ptr<pattern> patterns;

  public:
    pattern *find_pattern(const char *patstr, const char *rootstr) {
        ...
    }
    pattern *create_pattern(const char *patstr, const char *rootstr) {
        ...
    }
};

From each pattern, we hang a tree storing all the subdirectories. In the case of files, however, and to keep the data structure efficient, only those files’ names that matched the pattern in previous queries are stored for each subdirectory in the data structure.

For each subdirectory in the tree, we also store the time when the latest search was performed. When the user is searching for the same pattern again, the program will simply iterate this in-memory tree structure. If the modification time for a particular subdirectory in the file system hasn’t changed since the last search (it only changes if new files or directories are added or removed to or from it), we don’t need to re-scan it. We can simply print the cached results and move to the next subdirectory recursively. The following code snippet shows the class pattern:

class pattern {
  private:
    pobj::persistent_ptr<char[]> patstr;
    pobj::persistent_ptr<char[]> rootstr;
    pobj::persistent_ptr<entry> rootdir;
    pobj::persistent_ptr<pattern> next;

  public:
    pattern(const char *patstr, const char *rootstr) {
        NEW_PM_STRING(this->patstr, patstr);
        NEW_PM_STRING(this->rootstr, rootstr);
        this->rootdir = pobj::make_persistent<entry>(nullptr, rootstr, true);
        this->next = nullptr;
    }
    const char *get_patstr(void) { return this->patstr.get(); }
    const char *get_rootstr(void) { return this->rootstr.get(); }
    pobj::persistent_ptr<pattern> get_next(void) { return this->next; }
    void set_next(pobj::persistent_ptr<pattern> pat) { this->next = pat; }
    int find_all(void) {
        return rootdir->process_directory(this->patstr.get());
    }
};

The function find_all() is the one called to scan a tree root with the pattern. This function calls process_directory(), a recursive function from the class entry in charge of scanning all the files and directories under a particular directory root (the first one is always the tree root).

Entries can be directories or files. File entries (cached from previous searches) are simply printed out as results, while directories are processed recursively by calling process_directory(). As mentioned before, in the case where the modification time of a directory has changed since the last search, the directory’s contents need to be re-scanned again from the file system:

        ...
        /* Let's get current 'last modif time' */
        stat(path, &st);
        time_t new_mtime = st.st_mtime;
        if (difftime(new_mtime, this->mtime) != 0) {
            /* dir content has changed, we need
             * to re-scan it
             * */

            while ((dirp = readdir(dp)) != NULL) {
                ...

These are the variables of the class entry:

class entry {
  private:
    pobj::persistent_ptr<char[]> parent;
    pobj::persistent_ptr<char[]> name;
    pobj::p<bool> isdir;
    pobj::p<time_t> mtime;
    pobj::persistent_ptr<entry> entries;
    pobj::persistent_ptr<entry> next;
    ...
};

The persistent program is called find-all-pm. To run it, we need to indicate the location of the persistent memory pool (if the pool does not exist, the program will create it) in addition to the other parameters. In my case, the pool resides in /mnt/pmem/pool:

$ time ./find-all-pm /mnt/pmem/pool ./test_tree aazz
./test_tree/hfibr/fifpu/wtpdt/mgrex/mbrma/sapjhqtpnxaazzkflhbmgtrhqbcxkvuj
./test_tree/gzqtl/kwntu/opuci/ktxmi/chisz/enlvjaazzuanuguupnnrrwxgfafekwck
./test_tree/gzqtl/kwntu/fvecf/tivvl/kuzpl/klwfgiwqenljruorfdupgkmaazzydrik
...
real	0m0.699s
user	0m0.020s
sys	    0m0.038s

* see performance disclaimer

As you can see, the execution is slower the first time we run it with a new pattern; in this case, 0.120 seconds slower compared with the volatile version (0.579 versus 0.699). However, if we run it again:

$ time ./find-all-pm /mnt/pmem/pool ./test_tree aazz
./test_tree/hfibr/fifpu/wtpdt/mgrex/mbrma/sapjhqtpnxaazzkflhbmgtrhqbcxkvuj
./test_tree/gzqtl/kwntu/opuci/ktxmi/chisz/enlvjaazzuanuguupnnrrwxgfafekwck
./test_tree/gzqtl/kwntu/fvecf/tivvl/kuzpl/klwfgiwqenljruorfdupgkmaazzydrik
...
real	0m0.058s
user	0m0.020s
sys	    0m0.038s

* see performance disclaimer

We get the results in just over 50 milliseconds! In other words, the volatile version is 10x slower.

A Bigger Tree

What happens with a bigger tree? Let’s try increasing the number of files by 10x:

$ ./create_test_tree.sh test_tree1 6 1000

Running the volatile version:

$ time ./find-all test_tree1 aazz
test_tree1/npkhu/egzez/qyixsuqzfywemoaazzgdwququodezchy
test_tree1/npkhu/egzez/fpvee/sbkue/vupmb/xptjsqiqtuchcspywsjaazzxceuaokfa
test_tree1/npkhu/egzez/fpvee/zrrhb/agera/hcxhbztjmfmedzbytkgdwxeaazzygnnp
test_tree1/mgwwl/tsjzb/xuojd/wsjzw/iittr/icaazzzwzmdaevemdkjsybtegxccrjqq

...
real    0m5.531s
user    0m5.042s
sys     0m0.476s

* see performance disclaimer

We find our answers in 5.5 seconds. Let’s run the persistent version:

$ time ./find-all-pm /mnt/pmem/pool test_tree1 aazz
test_tree1/mgwwl/tsjzb/xuojd/wsjzw/iittr/icaazzzwzmdaevemdkjsybtegxccrjqq
test_tree1/mgwwl/tsjzb/xuojd/isplz/jlqje/gwalshqfqlopanbutlcduuaazznziwle
test_tree1/mgwwl/tsjzb/xuojd/isplz/fpcpaectvcipoaazzuhvfltrcrxrqvnz
test_tree1/mgwwl/tsjzb/thybd/elaga/uczjzwoywatubaazzcktnsmlfvgbxoal
...
real    0m5.568s
user    0m5.001s
sys     0m0.531s

* see performance disclaimer

We get 5.7 seconds, which is almost identical to the volatile version. This indicates that the major bottleneck in this program is not writing to persistent memory. Rather, it is reading file metadata from the file system and doing pattern matching.

Searching the same pattern again:

$ time ./find-all-pm /mnt/pmem/pool test_tree1 aazz
test_tree1/mgwwl/tsjzb/xuojd/wsjzw/iittr/icaazzzwzmdaevemdkjsybtegxccrjqq
test_tree1/mgwwl/tsjzb/xuojd/isplz/jlqje/gwalshqfqlopanbutlcduuaazznziwle
test_tree1/mgwwl/tsjzb/xuojd/isplz/fpcpaectvcipoaazzuhvfltrcrxrqvnz
test_tree1/mgwwl/tsjzb/thybd/elaga/uczjzwoywatubaazzcktnsmlfvgbxoal
...
real    0m0.058s
user    0m0.022s
sys     0m0.036s

* see performance disclaimer

We get the same 58 milliseconds that we got before. In relative terms, however, the volatile version is almost 100x slower! In general, the more files we have in our tree, the bigger the incentive is to use a persistent memory cache.

Summary

In this short article, I showed how you can improve the user experience by using persistent memory as a cache. More specifically, the performance of a small code sample corresponding to a simplified version of the find command in Linux is improved by 10x for 36,400 files, and 100x for 364,000 files, using a persistent memory cache. All the code referenced here can be found in the following repository.

Disclaimer

* Performance results are based on testing as of May 10, 2019, and may not reflect all publicly available security updates. See configuration disclosure for details. No product can be absolutely secure. Software and workloads used in performance tests may have been optimized for performance only on Intel microprocessors. Performance tests, such as SYSmark* and MobileMark*, are measured using specific computer systems, components, software, operations and functions. Any change to any of those factors may cause the results to vary. You should consult other information and performance tests to assist you in fully evaluating your contemplated purchases, including the performance of that product when combined with other products.

Configuration disclosure: Testing by Intel as of May 10, 2019. 1-node, 2x Intel® Xeon® Platinum 8260 processors, Wolfpass platform, Total memory 192 GB, 12 slots / 16GB / 2667 MT/s DDR4 RDIMM, Total persistent memory 1.5 TB, 12 slots / 128GB / 2667 MT/s Intel® Optane™ Persistent Memory Modules (DCPMM), Intel® Hyper-Threading Technology : Enable, Storage (boot): 1x TB P4500, ucode: 0x400001C, OS: CentOS* Linux* 7.6, Kernel: 3.10.0-957.12.2.el7.x86_64

Security mitigations for the following vulnerabilities: CVE-2017-5753, CVE-2017-5715, CVE-2017-5754, CVE-2018-3640, CVE-2018-3639, CVE-2018-3615, CVE-2018-3620, CVE-2018-3646, CVE-2018-12126, CVE-2018-12130, CVE-2018-12127, CVE-2019-11091