ARTS第14週|LeetCode 683 K個空き植木鉢|Redis持続化|MySQLインデックス失効

ARTS
ARTSは陳浩(ハンドルネーム左耳ネズミ)が極客時間コラムで始めた活動で、分かち合いを通じて勉強を続けることを目的としている.
1人1週間に1つのARTS:Algorithmはアルゴリズムの問題で、Reviewは英語の文章を読んで、Technique/Tipsは1つの小さい技術を分かち合って、Shareは1つの観点を分かち合います.
今週の内容
Algorithm
今週のアルゴリズムの問題はLeetCode 683 K個の空き植木鉢です.
この問題の最も簡潔な方法は二重ポインタを使うことだ.実現は簡単ですが、理解するのは容易ではありません.中心的な考え方はbulbsの植木鉢へのマッピング->開花日数のdays.タイトル要求の「彼らの間にk輪の花が隔てられていて開放されていない」はdays[i]とdays[i+K+1]の間のすべてのdays[x]がdays[i]とdays[i+K+1]より大きく、つまり開花時間が両側のdays[i]とdays[i+K+1]よりも遅く、days[i]とdays[i+K+1]の間にK個の植木鉢が開花していないことを保証することができる.

func kEmptySlots(bulbs []int, K int) int {
    if len(bulbs) == 0 {
        return -1
    }
    days := make([]int, len(bulbs))
    for i, n := range bulbs {
        days[n-1] = i
    }

    ans, left, right := 1<<31-1, 0, K+1
    for right < len(days) {
        breakFlag := false
        for i := left+1; i < right; i++ {
            if days[i] < days[left] || days[i] < days[right] {
                left, right = i, i+K+1
                breakFlag = true
                break
            }
        }
        if ! breakFlag {
            ans = min(ans, max(days[left], days[right]))
            left, right = right, right+K+1
        }
    }
    if ans == 1<<31-1 {
        return -1
    }
    return ans+1
}

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Review記事推奨
今週の英語の文章はRedis公式のRedis Persistenceで、主にRedisの持続化を紹介しています.

RDBとAFRDBファイルにはRedisデータのスナップショットが保存されており、AOFファイルにはデータが変化するたびの書き込み操作が保存されている.AOFは実行済みの「コマンド」が保存されていると大まかに理解でき,これらの「コマンド」はRedisサービスが起動したときに再生される.Redisの永続化はオプションであり、永続化を行わないか、RDBとAOFの両方のファイルを同時に使用するかを選択できます.

RDB優劣スナップショット式のRDBは、大きな時間のデータを格納および伝送するのにより友好的である.データ量が比較的大きい場合,サーバの起動速度の面では,AOFを用いるよりもRDBを持続化スキームとして用いる方が優れている.スナップショットを作成するには時間間隔を設定する必要があるため、障害が発生すると、必ず1つの時間間隔内のデータが失われます.RDBファイルをメモリにロードするには、Redisサービスforkのサブプロセスが必要であり、極端な数の場合、通常のサービス応答速度に影響を与えるCPUが多すぎる可能性があります.

AOFの優劣がより柔軟(例えば短い)な永続化データ間隔は、故障発生時のデータ損失を低減することができ、例えば毎秒または毎回命令を実行するAOFを追加することができる.append onlyの方式はseekを必要とせず、書き込み障害の処理が容易である.AOFファイルが大きすぎる場合、Redisはファイルを「簡略化」し、冗長な操作記録を捨てることができます.AOFはかなり良い可読性を保持している.AOFは通常RDBファイルよりも大きい.

公式の2つの持続化方式に対する提案が1つしか使われていない場合は、RDBが望ましい.

Tipプログラミングテクニック

インデックスの失効を引き起こす可能性のある使用範囲クエリー、例えばid<10は、連合インデックスに対してlike+%blablaを使用するファジイマッチングを行い、orは2つの条件

を接続する.
インデックスの失効を引き起こす可能性のあるシーン:すべてのフィールドに関数、タイプ変換、プリアンブルブラーマッチング(like"%blabla")、where句の多条件の組み合わせが適切ではありません(orを使用したり、id<10などの結合インデックスの非終了フィールドに範囲検索を使用したりします).ps後置ブラーマッチング(like「blabla%」)は、プレフィックスインデックスを使用できます.
Shareキラキラ
人が群れをなす本質は「軽蔑チェーン」が構築したアイデンティティではないか.
今週の読書リスト

Optimizing OR (union) operations in MySQLでは、inner joinを使用して2つのテーブルをクエリーし、そのうちの1つのテーブルのフィルタ条件をorで接続するときにインデックスを使用してクエリーの最適化を行う方法について詳しく説明しています.ここでは、unionが元のor接続を分割する2つの条件をそれぞれ使用し、クエリー・オプティマイザがindex merge機能を使用できるように、他の並列where条件を最適化します.プロセスは詳細ですが、これらの操作の原因を説明していないのは気まずいです.だから、上記のorキーワードの最適化原理はいったい何なのでしょうか.

パフォーマンス分析ツールを使用してSQLの実行が遅い理由を特定する方法は、まずMySQLクエリーの最適化の全体的な考え方と、遅いSQLの一般的なコマンドとパラメータを紹介します.次に、typeフィールドの各値が表す意味を含むEXPLAINの使い方を紹介します.以下はtypeに関するまとめです.allは全表スキャン方式を採用しているため、最悪の場合です.indexとallの差は多くありませんが、indexがインデックステーブルをフルスキャンするメリットは、データのソートを必要としないことですが、オーバーヘッドは依然として大きいです.Extral列にUsing indexが表示されている場合は、インデックスオーバーライドが使用されていることを示します.つまり、インデックスが必要なSELECTフィールドをオーバーライドすることができ、リターンテーブルを必要とせず、データ検索のオーバーヘッドを削減できます.rangeはインデックス範囲スキャンを採用していることを示しています.ここでは例を挙げません.このレベルからインデックスの役割はますます明らかになります.そのため、SQLクエリーがrangeというレベル以上のtypeアクセス方式を使用できるようにする必要があります.refタイプは、一意でないインデックスが使用されているか、一意のインデックスの非一意性接頭辞が使用されていることを示し、ref列にconstが表示され、接続整合条件が定数であることを示し、インデックス列の検索に使用されます.eq_refタイプは、プライマリ・キーまたは一意のインデックスを使用する場合に発生するアクセス方法であり、通常はマルチテーブル・クエリーで使用されます.constタイプは、プライマリ・キーまたはユニーク・インデックス(すべての部分)を使用して定数値と比較したことを示します.しかし、接続方式によって効率が異なり、効率が低いものから高いものまでall

オペレーティングシステムモデルとレゴ積み木・OSDI 2018本稿で紹介するのは、OSDI 2018の論文であるLegoOS:A Disseminated、Distributed OS for Hardware Resource Disaggregation 1であり、OSDI 2018の最適な論文(Awarded Best Paper)であり、この論文で実現されたLegoOSオペレーティングシステムは、データセンター内の単体サーバをネットワーク接続を介した分散ハードウェアに分割することができる.各ハードウェアは独立したコントローラによって管理されます.既存のオペレーティングシステムでは同様のシナリオを処理できないため,本論文では,下位層のハードウェアリソースを管理し制御するためにカーネルを分離するオペレーティングシステムモデルを提案した.

なぜシステム呼び出しは多くのリソースを消費するのかこの文章を読み直し,著者らは詳細なシステム呼び出し実装方式を列挙した.しかし、その実現にかかわらず、比較的複雑なプロセスに関連しています.

Go言語設計と実装4.2インタフェース Goの2つの「インタフェース」、すなわちGo interface{}とtype xxx interface{}の内部実装はifaceとeface構造体に依存する必要があり、前者はオブジェクトの属性のみを保存し、後者はオブジェクトのメソッドセットも保存する.メモリ内の2つの構造の分散方式も紹介し,直接タイプ推定を行ってからオブジェクトを呼び出す方法と,マルチステートを用いたDynamic Dispatchの性能の違い(マルチステート方式は性能が劣るが,開発の利便性をもたらす)を比較した.