I previously wrote about inverted indexes, but since it was implemented in Python, performance was pretty rough, and as a demo, many details were completely ignored. Recently, on and off, I finally wrote a slightly better program (or rather, a half-finished one) in C++. If you're interested, please fork & star.

[github_widget repo="yuikns/argcv-index"]

Lately, my habit is to prepare a relatively unified C++ library and then wrap a concrete business project around it. This project is the same; much of its underlying content is implemented in the following project.

[github_widget repo="yuikns/argcv"]

In principle, it is no different from the previous inverted index. Although I have many ideas that I thought were brilliant, unfortunately I don't have time right now, so I can only hurriedly produce a result first.

The goal of the index is to serve as a backend for business-level services (usually Java, Scala, Python, etc.), so externally it uses program interfaces rather than HTTP-based RESTful APIs. As a simple program, it roughly needs three parts from front to back:

  • TCP connection service. As a backend for backends, it still needs a channel for external interaction.
    • <li>Indexing logic. Inverted index data storage needs special formats to facilitate queries.</li>

<li>Storage service. Low-level data access (mainly various key-value pairs).</li>

It finally seems to work end to end, so I'd like to share some experience, hoping to better avoid these pitfalls next time. If it miraculously helps a passerby, that would be a pleasant surprise.

Project Organization

First, a project is needed to organize the whole system. As a C++ project, I personally particularly like CMake because it can easily handle dependencies. Many times, you can write a lot of general code, and later dependency management is also very convenient. This project is the same; you only need to add a few lines to easily reuse yuikns/argcv, my slowly growing collection of wheels (utilities).
Bash
ADD_SUBDIRECTORY(lib/argcv) # 添加子工程
INCLUDE_DIRECTORIES(${ARGCV_INCLUDE_DIR}) # 将子工程头文件加入搜寻路径
LINK_DIRECTORIES(${ARGCV_LIB_DIR}) # 将子工程库文件加入搜寻路径

When you need to depend on open-source projects like LevelDB, it's also easy to use them with CMake scripts—debug once, use many times.

But it's occasionally unreliable; if there's no network, it's a huge hassle.

TCP Service

TCP service is a very simple and convenient thing. The code can be seen here; as you can see, it basically just calls the library file tcp_listen.hh, which I introduced before. It was basically adapted from the ideas in a blog post by Cloud Wu, tweaked along the way. This time is just a simple application of that code.

In actual use, to ensure the client can interact normally, I set it to first send the length, then send the actual content. If the content is not fully received, the next step doesn't begin.

For the data format used in interaction, I originally wanted to use JSON, but unfortunately I didn't find a good library; from the C++ perspective, neither efficiency nor code writing was satisfactory. So I used Protobuf for the content. Protobuf isn't difficult to work with in CMake; although using CMake's built-in scripts directly sometimes seems a bit problematic, some simple improvements can fix it. You can refer to this example. And in an SBT-managed Scala project, some simple plugins can also make things very easy. (I'll come back to fill this pit later.)

Indexing Logic

The index itself is a TF-IDF-based implementation; the formula is also simple, and it has many variants. I just picked a simple one.

First, given a piece of text, perform stemm, tokenlize, and analyze on it. Then store the results.

When storing, I encode the information. Because the final storage uses LevelDB, which has a nice property: it's lexicographically ordered, so it's easy to do things like "find entries starting with xxx". Therefore we can use terms, field names, etc. as prefixes, and later we can locate targets very quickly. Second, I put multiple pieces of information into one key, so that no additional query is needed to get the information. For example, a UUID is two uint64_t values, so I just append them to the end of the key, and later I can recover the data by reading backwards.

For plain text, I use '\0' as a separator. This effectively identifies text without having to bother recording the length before the content.

Storage Service

The system uses leveldb as the actual storage backend, but I wrapped it with a few wrappers. Mainly, I want to be able to plug in other underlying data services later, and things like load balancing still matter a lot.

TODO

  • First, class tcp_listen is well suited for multithreading, and the relevant code is not hard to write either. I also kept thread safety in mind while coding; it’s just that debugging multithreading is troublesome, and time was limited, so this will have to wait.
    • <li>Second, the analyzer is currently extremely simple—it doesn’t even have stop words prepared, and only strips out some punctuation. I don’t think that’s good. Besides, Chinese word segmentation is an interesting problem: 52nlp has <a href="http://www.52nlp.cn/%E4%B8%AD%E6%96%87%E5%88%86%E8%AF%8D%E5%85%A5%E9%97%A8%E4%B9%8B%E6%9C%80%E5%A4%A7%E5%8C%B9%E9%85%8D%E6%B3%95%E6%89%A9%E5%B1%951" target="_blank" rel="noopener">an introductory article</a> about it, and there are <a href="https://github.com/ling0322/webdict" target="_blank" rel="noopener">some entries</a> compiled by others that can be used as resources. It’s actually not hard to implement, so I plan to tackle it first.</li>

<li>Third, matching is currently based only on text similarity. The scoring formula should really be more sophisticated. For example, this time I stored some papers; I could easily have included citation counts in the calculation—but I didn’t. Also, when searching for “data mining”, the analyzer splits it into “data” and “mining”, searches them separately, and merges the results. I stored the positions of “data” and “mining” in the original text, but I never actually used them.</li>

<li>Fourth, as I mentioned before, things like load balancing were started but not carried through. It’ll have to wait until I have some free time.</li>