跳至主要内容

Elasticsearch Introduction Speech Note

Concepts

node, cluster

master: creating or deleting an index, or adding or removing a node from the cluster

index, mapping/type, document

Term Elasticsearch Equivalent in RDMS
Index collection of different type of documents and document properties database
Shards the horizontal separation of a index X
Type/Mapping collection of dicuments sharing a set of common fields table
Document collection of fields defined in JSON row
ID Every document is associated with ID primary key

Example

-------        --------          --------
 Node0          Node1             Node2
 shard0         shard1              
 shard1                           shard0
--------       --------          --------
  • one copy of replicas
  • two copy of data & two shards (shard0, shard1)
  • three nodes

Application

clients

Java
Restful
curl -XGET 'localhost:9200/my_index/my_type/_search' -d'
{
    "query": {
        "match": {
            "title": "BROWN DOG!"
        }
    }
}

Nature

  • use
  • debug
  • opt
  • binary search
  • hashmap
  • skiplist
  • tree: binary tree, red-black tree, B+ tree
  • heap

Another data structure: Inverted index

Example
  1. The quick brown fox jumped over the lazy dog
  2. Quick brown foxes leap over lazy dogs in summer

A simple inverted index may looks like:

Term      Doc_1  Doc_2
-------------------------
Quick   |       |  X
The     |   X   |
brown   |   X   |  X
dog     |   X   |
dogs    |       |  X
fox     |   X   |
foxes   |       |  X
in      |       |  X
jumped  |   X   |
lazy    |   X   |  X
leap    |       |  X
over    |   X   |  X
quick   |   X   |
summer  |       |  X
the     |   X   |
------------------------

If we search for quick brown， we will get the following results:

Term      Doc_1  Doc_2
-------------------------
brown   |   X   |  X
quick   |   X   |
------------------------
Total   |   2   |  1

Store

Two design choice

  • Immutable

    • No need of locking
      • programmer
      • performance: avoid distributed lock
    • Cache friendly
      • file system cache

  • Updatable: multiple version index, example.

    • Segments: fsync
    • Memory buffer
    • Disk cache: refresh – write new entry into disk cache, which is the lightweight way to make new documents visible to search
    • Transaction log

Inverted Index + NoSQL

Algorithm

Three core algorithm

  • routing: search for id=1
    • which shard: distributed hash table
    • which node: round robin
  • analyzer: inverted index revisit
    • character filter: could be used to strip out HTML, or to convert & characters to the word and
    • tokenizer
    • token filter: change/add/remove term
Term      Doc_1  Doc_2
-------------------------
brown   |   X   |  X
dog     |   X   |  X
fox     |   X   |  X
in      |       |  X
jump    |   X   |  X
lazy    |   X   |  X
over    |   X   |  X
quick   |   X   |  X
summer  |       |  X
the     |   X   |  X
------------------------
  • scoring
    • term frequency: “test” – “a test in test” vs “test in”
    • field length: “title” vs “content”
    • inverse document frequency: across multiple documents

Questions

Document Deletion

When a document is “deleted,” it is actually just marked as deleted in the .del file. A document that has been marked as deleted can still match a query, but it is removed from the results list before the final query results are returned.

version-1 version-2
a a’
b
c
version-1.del version-2.del
b
a

Master election

Once a node joins, it will send a join request to the master.

There are two fault detection processes running. The first is by the master, to ping all the other nodes in the cluster and verify that they are alive. And on the other end, each node pings to master to verify if its still alive or an election process needs to be initiated.

ZenDiscovery service elect like this:

  • Each node calculates the lowest known node id and sends a vote for leadership to this node
  • If a node receives sufficiently many votes and the node also voted for itself, then it takes on the role of leader and starts publishing cluster state.

Update collision

  • document has version number
  • optimistic locking: CAS like, compare version and update if version match
  • auto retry
curl -XPOST 'http://localhost:9200/designs/shirt/1/_update?retry_on_conflict=5' -d'
{
   "script" : "ctx._source.votes += 1"
}'

Ref

标签：

评论

发表评论

此博客中的热门博文

Spring Boot: Customize Environment

Spring Boot: Customize Environment Environment variable is a very commonly used feature in daily programming: used in init script used in startup configuration used by logging etc In Spring Boot, all environment variables are a part of properties in Spring context and managed by Environment abstraction. Because Spring Boot can handle the parse of configuration files, when we want to implement a project which uses yml file as a separate config file, we choose the Spring Boot. The following is the problems we met when we implementing the parse of yml file and it is recorded for future reader. Bind to Class Property values can be injected directly into your beans using the @Value annotation, accessed via Spring’s Environment abstraction or bound to structured objects via @ConfigurationProperties. As the document says, there exists three ways to access properties in *.properties or *.yml : @Value : access single value Environment : can access multi
5 条评论
阅读全文

Elasticsearch: Join and SubQuery

Elasticsearch: Join and SubQuery Tony was bothered by the recent change of search engine requirement: they want the functionality of SQL-like join in Elasticsearch! “They are crazy! How can they think like that. Didn’t they understand that Elasticsearch is kind-of NoSQL 1 in which every index should be independent and self-contained? In this way, every index can work independently and scale as they like without considering other indexes, so the performance can boost. Following this design principle, Elasticsearch has little related supports.” Tony thought, after listening their requirements. Leader notice tony’s unwillingness and said, “Maybe it is hard to do, but the requirement is reasonable. We need to search person by his friends, didn’t we? What’s more, the harder to implement, the more you can learn from it, right?” Tony thought leader’s word does make sense so he set out to do the related implementations Application-Side Join “The first implementation
发表评论
阅读全文

Implement isdigit

It is seems very easy to implement c library function isdigit , but for a library code, performance is very important. So we will try to implement it and make it faster. Function So, first we make it right. int isdigit ( char c) { return c >= '0' && c <= '9' ; } Improvements One – Macro When it comes to performance for c code, macro can always be tried. #define isdigit (c) c >= '0' && c <= '9' Two – Table Upper version use two comparison and one logical operation, but we can do better with more space: # define isdigit(c) table[c] This works and faster, but somewhat wasteful. We need only one bit to represent true or false, but we use a int. So what to do? There are many similar functions like isalpha(), isupper ... in c header file, so we can combine them into one int and get result by table[c]&SOME_BIT , which is what source do. Source code of ctype.h : # define _ISbit(bit) (1 << (
发表评论
阅读全文