Computer Programming, Volume 3: Sorting and Searching The Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences $ grep $ awk $ sed 正規表現
10,320件 30,483件 500,020件 UNIX BSD mmap kernel Linux 520件 1 1 1 2 3 3 4 5 5 6 6 7 S. Ding and T. Suel. Faster top-k document retrieval using block-max indexes. In Proceedings of the 34th Annual International ACM SIGIR Conference on Research and development in Information Retrieval, pages 993-1002, 2011. ↑の成果は Lucene 8 (2019/3/14 リリース) で実装 • https://fosdem.org/2019/schedule/event/apache_lucene_solr_8/attachments/slides/3325/export/events/attachments/apache_lucene_so lr_8/slides/3325/SchindlerLucene8Slides.pdf • https://medium.com/@mocobeta/lucene-8-%E3%81%AE-top-k- %E3%82%AF%E3%82%A8%E3%83%AA%E3%83%97%E3%83%AD%E3%82%BB%E3%83%83%E3%82%B7%E3%83%B3%E3%82 %B0%E6%9C%80%E9%81%A9%E5%8C%96-1-%E5%B0%8E%E5%85%A5%E7%B7%A8-5a6387076e8e 今でも効率的なアルゴリズムの研究が続いている
2021. 55 • https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/codecs/MultiLevelSkipListWriter.java • https://github.com/apache/lucene/blob/main/lucene/core/src/java/org/apache/lucene/codecs/MultiLevelSkipListReader.java * Example for skipInterval = 3: * c (skip level 2) * c c c (skip level 1) * x x x x x x x x x x (skip level 0) * d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d (posting list) * 3 6 9 12 15 18 21 24 27 30 (df) * * d – document * x - skip data * c - skip data with child pointer
recommendation is to give 50% of the available memory to Elasticsearch heap, while leaving the other 50% free. It won’t go unused; Lucene will happily gobble up whatever is left over.” 【注意】Java の世界から逸脱している(Java のヒープ外でアロケートされてる)
Balance) • ドキュメント単位でルーティング • どのシャードに格納するのかは、あなた次第! シャード A, B, C 全部が生存 欠損なしで 検索続行 分散検索: 可用性(Availability) 104 A Shard C Shard B Shard C Shard A Shard B Shard ✗
Balance) • ドキュメント単位でルーティング • どのシャードに格納するのかは、あなた次第! シャード A と B に関する 検索 シャード A と B に関する 検索 シャード A と B に関する 検索 105 A Shard C Shard B Shard C Shard A Shard B Shard 分散検索: 負荷分散(Load Balance)
Balance) • ドキュメント単位でルーティング • どのシャードに格納するのかは、あなた次第! hash(XXX) mod (# of Shard) = C Doc ID: XXX 106 A Shard C Shard B Shard C Shard A Shard B Shard 分散検索: ルーティング
扱う index は Practice②と同じ • 通信は http • 分散検索は • /and?term=AAAAA,BBBBBで AND 検索 • /or?term=AAAA,BBBBBで OR 検索 • 分散させずに、ローカルで解決する検索は • /_and?term=AAAAA,BBBBBで AND 検索 • /_or?term=AAAA,BBBBBで OR 検索 • マージ処理(実際の AND と OR の処理)はリク エストを受け取ったサーバーで OK • 分散検索時には、各ノードで一つの term に対す る処理(単に Posting List を返すだけの処理)だ け行えば OK(_and でも _or でもどちらを使っ ても構わない) • term に従ってサーバーを固定してみる Index