ホームページ  >  記事  >  実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

青灯夜游
青灯夜游転載
2022-02-21 11:40:264603ブラウズ

面接の前に企業の面接資料について詳しく読んでください。これはその後の面接に非常に役立ちます。今日は、Shopee サーバーの実際の面接での 15 の質問 (回答分析付き) を共有します。ぜひ、自分のレベルを確認してください。お役に立てれば幸いです。

1. リンク リストを並べ替える

リンク リストのヘッド ノードを指定して、それを昇順に並べ替えて、並べ替えられたリンク リストを返します。

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

例 1:

输入:head = [4,2,1,3]
输出:[1,2,3,4]

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

例 2:

输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]

この質問では、ポインタ マージ ソート アルゴリズムは、次の 4 つのステップで解決されます。

1. 高速および低速のポインタ方式、リンク リストをトラバースして中間ノードを見つけます。

2. 中間ノードがリンク リストを切断します。

3. それぞれを使用します。左と右のサブリンク リストをマージソートします。

4. サブリンク リストをマージします。

完全なコードは次のとおりです。

class Solution {
    public ListNode sortList(ListNode head) {
        //如果链表为空,或者只有一个节点,直接返回即可,不用排序
        if (head == null || head.next == null)
            return head;
        
        //快慢指针移动,以寻找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null && fast.next.next !=null){
          fast = fast.next.next;
          slow = slow.next;
        }
        //找到中间节点,slow节点的next指针,指向mid
        ListNode mid = slow.next;
        //切断链表
        slow.next = null;
        
        //排序左子链表
        ListNode left = sortList(head);
        //排序左子链表
        ListNode right = sortList(mid);
        
        //合并链表
        return merge(left,right);
    }
    
    public ListNode merge(ListNode left, ListNode right) {
       ListNode head = new ListNode(0);
       ListNode temp = head;
       while (left != null && right != null) {
           if (left.val <= right.val) {
                temp.next = left;
                left = left.next;
            } else {
                temp.next = right;
                right = right.next;
            }
            temp = temp.next;
        }
        if (left != null) {
            temp.next = left;
        } else if (right != null) {
            temp.next = right;
        }
        return head.next;
    }
}

2. 対称暗号化アルゴリズムと非対称暗号化アルゴリズムの違い

最初に関連する概念を確認しましょう:

  • クリア テキスト: 暗号化されていない情報/データを指します。 。

  • 暗号文: 平文が暗号化アルゴリズムによって暗号化された後、データのセキュリティを確保するために暗号文になります。

  • Key: 平文を暗号文に、または暗号文を平文に変換するアルゴリズムに入力されるパラメーターです。鍵は対称鍵と非対称鍵に分けられます。

  • 暗号化: 平文を暗号文に変換するプロセス。

  • 復号化: 暗号文を平文に復元するプロセス。

対称暗号化アルゴリズム: 暗号化と復号化に 同じキーを使用する暗号化アルゴリズム。一般的な対称暗号化アルゴリズムには、AES、3DES、DES、RC5、RC6 などが含まれます。

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

#非対称暗号化アルゴリズム: 非対称暗号化アルゴリズムには 2 つのキー (公開キーと秘密キー) が必要です。公開鍵と秘密鍵はペアで存在し、公開鍵を使用してデータを暗号化した場合、対応する秘密鍵のみで復号化できます。主な非対称暗号化アルゴリズムは、RSA、Elgamal、DSA、D-H、ECC です。

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

3. TCP はどのように信頼性を確保しますか

  • まず、TCP 接続は 3 つの要素に基づいています。 -way ハンドシェイク、切断は 4 波です。確実な接続と切断を保証します。

  • 第 2 に、TCP の信頼性は状態にも反映されます。TCP は、どのデータが送信されたか、どのデータが受け入れられたか、どのデータが受け入れられなかったかを記録し、データ パケットが確実に送信されることを保証します。データ送信にエラーがないことを確認するためです。

  • 第三に、TCP の信頼性はその制御性にも反映されます。メッセージ検証、ACK応答、タイムアウト再送(送信側)、順序外れデータ​​再送(受信側)、重複データの破棄、フロー制御(スライディングウィンドウ)、輻輳制御などのメカニズムを備えています。

#4. 5 つの IO モデルについて話しましょう

##4.1 ブロッキング IO モデル

## アプリケーション プロセスが IO 呼び出しを開始すると仮定しますが、カーネル データの準備がまだ整っていない場合、アプリケーション プロセスはブロックされ、カーネル データの準備ができてカーネルからユーザー空間にコピーされるまで待機します。成功のプロンプトが表示されると、この IO 操作はブロッキング IO と呼ばれます。

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

4.2 ノンブロッキング IO モデル

カーネル データの準備がまだ整っていない場合は、次のことができます。最初にエラーを返す この情報はユーザー プロセスに与えられるため、ユーザー プロセスは待つ必要がなく、ポーリングを通じて再度要求します。これはノンブロッキング IO です。フローチャートは次のとおりです:

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)##4.3 IO 多重化モデル

IO多重化select

アプリケーションプロセスはselect関数を呼び出すことで複数のfdを同時に監視することができますselect関数で監視しているfdでは、いずれかのデータステータスがreadyである限り、 select 関数は読み取り可能な状態に戻り、その後アプリケーション プロセスはデータを読み取るために recvfrom リクエストを開始します。

select にはいくつかの欠点があります。

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

接続の最大数は制限されており、Linux システムでは通常 1024 です。

  • select 関数が戻った後、fdset を走査することによって準備完了記述子 fd が見つかります。

  • IO 多重化 epoll

select の問題を解決するために、イベント駆動型の多重化モデル epoll が誕生しました。のフローチャートは次のとおりです:

epoll は、最初に epoll_ctl() を通じて fd (ファイル記述子) を登録します。特定の fd の準備が整うと、カーネルはコールバック メカニズムを使用して fd を迅速にアクティブ化します。プロセスが epoll_wait() を呼び出すと、通知されます。ここでは、ファイル記述子をトラバースするという厄介な操作が削除され、イベント コールバックをリッスンするメカニズムが使用されます。これがepollのハイライトです。

4.4 IO モデルの信号駆動型モデル

信号駆動型 IO は、データの準備ができているかどうかを確認するためにアクティブな問い合わせを使用しなくなりましたが、カーネルがシグナルを送信すると (sigaction の呼び出し時に SIGIO シグナルが確立されます)、アプリケーションのユーザー プロセスはブロックせずに他の処理を行うことができます。カーネル データの準備ができると、アプリケーション プロセスは、SIGIO 信号を通じて、データを読み取り可能にする準備ができたことを通知されます。アプリケーション ユーザー プロセスはシグナルを受信すると、すぐに recvfrom を呼び出してデータを読み取ります。

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

4.5 非同期 IO (AIO) の IO モデル

AIO は、非同期 IO の非線形化を実現します。 IOプロセス全体 ブロッキングとは、アプリケーションプロセスがシステムコールを発行した後、すぐに戻ることを意味しますが、すぐに返されるのは処理結果ではなく、サブミット成功のようなものです。カーネル データの準備ができたら、データをユーザー プロセス バッファーにコピーし、IO 操作が完了したことをユーザー プロセスに通知する信号を送信します。

プロセスは次のとおりです:

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

5. Hystrix の動作原理

Hystrix ワークフロー チャートは次のとおりです。以下:

1実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

1. ビルド コマンド

Hystrix は、HystrixCommand と HystrixObservableCommand という 2 つのコマンド オブジェクトを提供します。これらは、依存関係リクエスト タスクの 1 つを表し、それを に渡します。コンストラクター 依存関係を要求するために必要なパラメーター。

2. コマンドの実行

Hystrix コマンドを実行するには 4 つの方法があります。

  • Rexecute(): 同期ブロッキング実行。依存するリクエストから 1 つの応答を受け取ります。

  • Future queue(): 非同期実行。単一の応答を含む Future オブジェクトを返します。

  • Observable observable(): Observable を作成した後、Observable をサブスクライブし、依存するリクエストからの応答を表す Observable オブジェクトを返します

  • Observable toObservable() : cold observable、Observable を返します、Hystrix コマンドはサブスクライブ時にのみ実行され、複数の結果が返される可能性があります

3. 応答がキャッシュされているかどうかを確認します

Hystrix キャッシュを有効にすると、タスクの実行前に、同じコマンドを実行するためのキャッシュがあるかどうかが最初に判断されます。存在する場合、キャッシュされた応答を含む Observable が直接返されます。キャッシュされた結果がなくてもキャッシュが有効になっている場合、実行結果は後で使用するためにキャッシュされます。

4. サーキット ブレーカーが開いているかどうかを確認します。サーキット ブレーカー (サーキット ブレーカー) はヒューズに似ています。ヒューズは危険が発生したときに切れて回路を保護しますが、サーキット ブレーカーは回路を開くことができます。設定したしきい値に達すると、短絡をトリガーし (たとえば、リクエストの失敗率が 50% に達する)、リクエストの実行を拒否します。

ルーパーが開いている場合、Hystrix はコマンドを実行せず、直接フォールバック処理ロジックに入ります。

5. スレッド プール/セマフォ/キューの状況を確認する Hystrix の分離方法には、スレッド プールの分離とセマフォの分離があります。 Hystrix スレッド プールを使用する場合、Hystrix はデフォルトで各依存サービスに 10 個のスレッドを割り当てます。10 個のスレッドすべてがビジー状態の場合、コマンドの実行は拒否され、代わりにフォールバック ロジックの実行にすぐにジャンプします。

6. 特定のタスクを実行する HystrixObservableCommand.construct() または HystrixCommand.run() を使用して、ユーザーの実際のタスクを実行します。

7. ループの健全性を計算します。コマンドの実行が開始されるたび、コマンドの実行が終了するたび、または例外が発生するたびに、成功、失敗、拒否、タイムアウトなどの実行ステータスが記録されます。これらは定期的に処理され、設定された条件に従ってルーパーを開くかどうかを決定します。

8. コマンドが失敗した場合にフォールバック ロジックを実行する コマンドが失敗した場合に、ユーザー指定のフォールバック ロジックを実行します。上図ではサーキットブレーク、スレッドプール拒否、セマフォ拒否、実行実行、実行タイムアウトはすべてフォールバック処理に入ります。

9. 実行結果を返します。元のオブジェクトの結果が Observable の形式で返されます。ユーザーに返される前に、呼び出しメソッドに応じていくつかの処理が行われます。

6. 遅延シナリオの処理

日常の開発では、次のようなビジネス シナリオに遭遇することがよくあります。注文; ユーザーが登録に成功してから 15 分後に、ユーザーに通知するテキスト メッセージが送信されます。これは、遅延タスク処理シナリオです。このようなシナリオに対しては、主に次のソリューションがあります。

  • #JDK の DelayQueue 遅延キュー

  • #タイム ホイール アルゴリズム
  • データベースのスケジュールされたタスク (Quartz など)
  • Redis ZSet の実装
  • MQ 遅延キューの実装

7.https リクエスト プロセス

  • HTTPS = HTTP SSL/TLS、つまり、暗号化と復号化に SSL/TLS を使用します。データ、送信用のHTTP。

  • SSL (Secure Sockets Layer) は、ネットワーク通信のセキュリティとデータの整合性を提供するセキュリティ プロトコルです。

  • TLS、​​Transport Layer Security (Secure Transport Layer Protocol) は、SSL 3.0 の後継バージョンです。

1実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)
http リクエスト プロセス

1. ユーザーはブラウザに https URL を入力し、サーバーの 443 ポートに接続します。

2. サーバーにはデジタル証明書のセットが必要です。サーバー自体で作成することも、組織に適用することもできます。違いは、サーバー自体が発行した証明書はクライアントによって検証される必要があることです。この証明書のセットは、実際には公開鍵と秘密鍵のペアです。

3. サーバーは、独自のデジタル証明書 (公開キーを含む) をクライアントに送信します。

4. クライアントはサーバーからデジタル証明書を受信した後、それをチェックしますが、失敗した場合は、警告ボックスが表示されます。証明書に問題がない場合は、キーが生成され (対称暗号化)、証明書の公開キーで暗号化されます。

5. クライアントは HTTPS で 2 番目の HTTP リクエストを開始し、暗号化されたクライアント キーをサーバーに送信します。

6. サーバーは、クライアントから暗号文を受信した後、独自の秘密キーを使用して非対称的に復号化します。復号化後、クライアント キーを取得し、クライアント キー ペアを使用して暗号文を返します。データを暗号文にするために対称暗号化を実行します。

7. サーバーは暗号化された暗号文をクライアントに返します。

8. クライアントはサーバーから返された暗号文を受信し、独自のキー (クライアント キー) を使用して対称的に復号化し、サーバーから返されたデータを取得します。

##8. トランザクション分離レベルと反復読み取りの実装原則について話しましょう

##8.1 データベースの 4 つの主要な分離レベル 同時トランザクションにおける

ダーティ読み取り、反復不能読み取り、およびファントム読み取り

の問題を解決するために、データベースおじさんは 4 つの分離レベルを設計しました。それらは、Read uncommitted、Read Committed、Repeatable Read、Serializable です。

    コミットされていない分離レベルの読み取り: 2 つのデータを同時に変更できないように制限するだけですが、データが変更されると、トランザクションがコミットされていない場合でも、変更される可能性があります。他のトランザクションによる読み取り。このレベルのトランザクション分離には、ダーティ読み取り、繰り返し読み取り、ファントム読み取りの問題があります。
  • 読み取りコミット分離レベル: 現在のトランザクションは、によって送信されたデータのみを読み取ることができます。このトランザクション分離レベルでは、ダーティ読み取りの問題は解決されますが、繰り返し読み取りとファントム読み取りの問題は依然として残ります。
  • 繰り返し読み取り: データの読み取りが制限されている場合、修正ができないため、繰り返し読み込みの問題は解決しましたが、範囲データを読み込む場合はデータを挿入できるため、ファントム読み込みの問題は残ります;
  • シリアル化:最も高いトランザクション分離レベル。すべてのトランザクションが連続して実行されます。ダーティ読み取り、反復不能読み取り、ファントム読み取りなどの同時実行の問題をすべて回避できます。ただし、このトランザクション分離レベルでは、トランザクションの実行はパフォーマンスに非常に負荷がかかります。
  • 4 つの分離レベルにおける同時実行性の問題は何ですか?
#分離レベルダーティ リード反復不可能な読み取りファントム リード未コミットの読み取り√√√送信済みの読み取り×√√繰り返し読み取りシリアル化
##× #

#8.2 読み取りビューの可視性ルール

##変数m_idsmax_limit_idmin_limit_idcreator_trx_id

読み取りビューの可視性ルールは次のとおりです:

  • データ トランザクション ID trx_id の場合、このバージョンを生成したトランザクションを示します。 <code>Read Before View を生成していますが、送信されているため (トランザクション ID がインクリメントされているため)、現在のトランザクションからこのバージョンにアクセスできます。

  • trx_id>= max_limit_id の場合、このバージョンを生成したトランザクションは Read View が生成された後に生成されたことを示しているため、このバージョンは現在のトランザクション アクセスはできません。

  • min_limit_id = の場合、3 つの状況で議論する必要があります

1)

m_idstrx_id が含まれる場合、Read View が生成された時刻を表します。このトランザクションはまだ送信されていませんが、trx_id がデータの creator_trx_id と等しいことは、データが独自に生成されるため、表示されることを示します。

2)

m_idstrx_id が含まれており、trx_idcreator_trx_id と等しくない場合、Read View生成時に、トランザクションは送信されず、自動的に生成されないため、現在のトランザクションも表示されません;

3)

m_idstrx_id が含まれていない場合, then これは、Read View が生成される前にトランザクションが送信されており、変更の結果が現在のトランザクションで確認できることを意味します。

8.3 反復読み取り実装の原則

データベースは、ロックによって分離レベルを実現します。 , 他の人に邪魔されずに静かに過ごすために、家の中に閉じ込めてドアに鍵を追加することができます。シリアル化分離レベルはロックによって実装されます。ただし、頻繁にロックするとパフォーマンスが低下します。そこでデータベースを設計したおじさんは

MVCC を考えました。

反復可能な読み取りの実装原理は、

MVCC マルチバージョン同時実行制御です。トランザクションのスコープ内で、2 つの同一のクエリが同じレコードを読み取りますが、異なるデータを返します。これは、反復不可能な読み取りです。反復可能な読み取り分離レベルは、non-repeatable read の問題を解決するためのものです。

MVCC に基づいてレコードをクエリします。そのプロセスは何ですか?

  • トランザクションのバージョン番号、つまりトランザクション ID を取得します

  • Get Read View

  • Query 取得されたデータは、読み取りビューのトランザクションのバージョン番号と比較されます。

  • 読み取りビューの可視性ルールが満たされていない場合は、Undo ログの履歴スナップショットが必要です。

  • 最終的に満たすデータを返します。ルール

InnoDB は

MVCC を実装します。これは Read View Undo Log を通じて実装され、Undo Log は履歴スナップショットを保存します。 ,Read View可視性ルールは、現在のバージョンのデータが表示されるかどうかを判断するのに役立ちます。

Repeatable Read (RR) 分離レベル、Non-Repeatable Read の問題を解決するにはどうすればよいですか?

トランザクション A と B があると仮定すると、SQL 実行プロセスは次のとおりです。

1実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

Repeatable Read (RR) 分離レベルでは、トランザクションは次のようになります。

read view がレプリカによって共有された場合にのみ取得され、各クエリのデータが同じであることが保証されます。

現在 core_user テーブルがあると仮定し、次のように初期化データを挿入します。

1実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)##MVCC に基づいて、実行プロセスを見てみましょう

1. A はトランザクションをオープンし、最初にトランザクション ID 100

2 を取得します。B はトランザクションをオープンし、トランザクション ID 101

3 を取得します。トランザクション A は読み取りを生成しますビューと読み取りビューに対応する値は次のとおりです

説明
現在のシステム内のアクティブな (コミットされていない) 読み取りおよび書き込みトランザクション ID。そのデータ構造はリストです。
読み取りビューの生成時にシステム内の次のトランザクションに割り当てる必要がある ID 値を示します。
読み取りビューの生成時に現在のシステムでアクティブな読み取りおよび書き込みトランザクションの中で最小のトランザクション ID、つまり m_ids の最小値を示します。 。
現在の読み取りビューのトランザクション ID を作成します
#変数値##m_idsmax_limit_idmin_limit_id Creator_trx_id

然后回到版本链:开始从版本链中挑选可见的记录:

1実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

由图可以看出,最新版本的列name的内容是孙权,该版本的trx_id值为100。开始执行read view可见性规则校验:

min_limit_id(100)=<trx_id(100)<102;
creator_trx_id = trx_id =100;

由此可得,trx_id=100的这个记录,当前事务是可见的。所以查到是name为孙权的记录。

4、事务B进行修改操作,把名字改为曹操。把原数据拷贝到undo log,然后对数据进行修改,标记事务ID和上一个数据版本在undo log的地址。

1実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

5、事务B提交事务

6、事务A再次执行查询操作,因为是RR(可重复读)隔离级别,因此会复用老的Read View副本,Read View对应的值如下

100,101
102
100
100
#変数値##m_idsmax_limit_idmin_limit_id Creator_trx_id

然后再次回到版本链:从版本链中挑选可见的记录:

1実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

从图可得,最新版本的列name的内容是曹操,该版本的trx_id值为101。开始执行read view可见性规则校验:

min_limit_id(100)=<trx_id(101)<max_limit_id(102);

因为m_ids{100,101}包含trx_id(101),
并且creator_trx_id (100) 不等于trx_id(101)

所以,trx_id=101这个记录,对于当前事务是不可见的。这时候呢,版本链roll_pointer跳到下一个版本,trx_id=100这个记录,再次校验是否可见:

min_limit_id(100)=<trx_id(100)< max_limit_id(102);

因为m_ids{100,101}包含trx_id(100),
并且creator_trx_id (100) 等于trx_id(100)

所以,trx_id=100这个记录,对于当前事务是可见的,所以两次查询结果,都是name=孙权的那个记录。即在可重复读(RR)隔离级别下,复用老的Read View副本,解决了不可重复读的问题。

9. 聊聊索引在哪些场景下会失效?

1. 查询条件包含or,可能导致索引失效

2. 如何字段类型是字符串,where时一定用引号括起来,否则索引失效

3. like通配符可能导致索引失效。

4. 联合索引,查询时的条件列不是联合索引中的第一个列,索引失效。

5. 在索引列上使用mysql的内置函数,索引失效。

6. 对索引列运算(如,+、-、*、/),索引失效。

7. 索引字段上使用(!= 或者 ,not in)时,可能会导致索引失效。

8. 索引字段上使用is null, is not null,可能导致索引失效。

9. 左连接查询或者右连接查询查询关联的字段编码格式不一样,可能导致索引失效。

10. mysql估计使用全表扫描要比使用索引快,则不使用索引。

10. 什么是虚拟内存

虚拟内存,是虚拟出来的内存,它的核心思想就是确保每个程序拥有自己的地址空间,地址空间被分成多个块,每一块都有连续的地址空间。同时物理空间也分成多个块,块大小和虚拟地址空间的块大小一致,操作系统会自动将虚拟地址空间映射到物理地址空间,程序只需关注虚拟内存,请求的也是虚拟内存,真正使用却是物理内存。

现代操作系统使用虚拟内存,即虚拟地址取代物理地址,使用虚拟内存可以有2个好处:

  • 虚拟内存空间可以远远大于物理内存空间

  • 多个虚拟内存可以指向同一个物理地址

零拷贝实现思想,就利用了虚拟内存这个点:多个虚拟内存可以指向同一个物理地址,可以把内核空间和用户空间的虚拟地址映射到同一个物理地址,这样的话,就可以减少IO的数据拷贝次数啦,示意图如下:

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

11. 排行榜的实现,比如高考成绩排序

排行版的实现,一般使用redis的zset数据类型。

使用格式如下:

zadd key score member [score member ...],zrank key member
  • 层内部编码:ziplist(压缩列表)、skiplist(跳跃表)

  • 使用场景如排行榜,社交需求(如用户点赞)

实现demo如下:

1実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

12.分布式锁实现

分布式锁,是控制分布式系统不同进程共同访问共享资源的一种锁的实现。秒杀下单、抢红包等等业务场景,都需要用到分布式锁,我们项目中经常使用Redis作为分布式锁。

选了Redis分布式锁的几种实现方法,大家来讨论下,看有没有啥问题哈。

  • 命令setnx + expire分开写

  • setnx + value值是过期时间

  • set的扩展命令(set ex px nx)

  • set ex px nx + 校验唯一随机值,再删除

  • Redisson

12.1 命令setnx + expire分开写

if(jedis.setnx(key,lock_value) == 1){ //加锁
    expire(key,100); //设置过期时间
    try {
        do something  //业务请求
    }catch(){
  }
  finally {
       jedis.del(key); //释放锁
    }
}

如果执行完setnx加锁,正要执行expire设置过期时间时,进程crash掉或者要重启维护了,那这个锁就“长生不老”了,别的线程永远获取不到锁啦,所以分布式锁不能这么实现。

12.2 setnx + value值是过期时间

long expires = System.currentTimeMillis() + expireTime; //系统时间+设置的过期时间
String expiresStr = String.valueOf(expires);

// 如果当前锁不存在,返回加锁成功
if (jedis.setnx(key, expiresStr) == 1) {
        return true;
} 
// 如果锁已经存在,获取锁的过期时间
String currentValueStr = jedis.get(key);

// 如果获取到的过期时间,小于系统当前时间,表示已经过期
if (currentValueStr != null && Long.parseLong(currentValueStr) < System.currentTimeMillis()) {

     // 锁已过期,获取上一个锁的过期时间,并设置现在锁的过期时间(不了解redis的getSet命令的小伙伴,可以去官网看下哈)
    String oldValueStr = jedis.getSet(key_resource_id, expiresStr);
    
    if (oldValueStr != null && oldValueStr.equals(currentValueStr)) {
         // 考虑多线程并发的情况,只有一个线程的设置值和当前值相同,它才可以加锁
         return true;
    }
}
        
//其他情况,均返回加锁失败
return false;
}

笔者看过有开发小伙伴就是这么实现分布式锁的,但是这种方案也有这些缺点:

  • 过期时间是客户端自己生成的,分布式环境下,每个客户端的时间必须同步。

  • 没有保存持有者的唯一标识,可能被别的客户端释放/解锁。

  • 锁过期的时候,并发多个客户端同时请求过来,都执行了jedis.getSet(),最终只能有一个客户端加锁成功,但是该客户端锁的过期时间,可能被别的客户端覆盖。

12.3 set的扩展命令(set ex px nx)(注意可能存在的问题)

if(jedis.set(key, lock_value, "NX", "EX", 100s) == 1){ //加锁
    try {
        do something  //业务处理
    }catch(){
  }
  finally {
       jedis.del(key); //释放锁
    }
}

这个方案可能存在这样的问题:

  • 锁过期释放了,业务还没执行完。

  • 锁被别的线程误删。

12.4 set ex px nx + 校验唯一随机值,再删除

if(jedis.set(key, uni_request_id, "NX", "EX", 100s) == 1){ //加锁
    try {
        do something  //业务处理
    }catch(){
  }
  finally {
       //判断是不是当前线程加的锁,是才释放
       if (uni_request_id.equals(jedis.get(key))) {
        jedis.del(key); //释放锁
        }
    }
}

在这里,判断当前线程加的锁和释放锁是不是一个原子操作。如果调用jedis.del()释放锁的时候,可能这把锁已经不属于当前客户端,会解除他人加的锁。

一般也是用lua脚本代替。lua脚本如下:

if redis.call(&#39;get&#39;,KEYS[1]) == ARGV[1] then 
   return redis.call(&#39;del&#39;,KEYS[1]) 
else
   return 0
end;

这种方式比较不错了,一般情况下,已经可以使用这种实现方式。但是存在锁过期释放了,业务还没执行完的问题(实际上,估算个业务处理的时间,一般没啥问题了)。

12.5 Redisson

分布式锁可能存在锁过期释放,业务没执行完的问题。有些小伙伴认为,稍微把锁过期时间设置长一些就可以啦。其实我们设想一下,是否可以给获得锁的线程,开启一个定时守护线程,每隔一段时间检查锁是否还存在,存在则对锁的过期时间延长,防止锁过期提前释放。

当前开源框架Redisson就解决了这个分布式锁问题。我们一起来看下Redisson底层原理是怎样的吧:

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

只要线程一加锁成功,就会启动一个watch dog看门狗,它是一个后台线程,会每隔10秒检查一下,如果线程1还持有锁,那么就会不断的延长锁key的生存时间。因此,Redisson就是使用Redisson解决了锁过期释放,业务没执行完问题。

13. 零拷贝

零拷贝就是不需要将数据从一个存储区域复制到另一个存储区域。它是指在传统IO模型中,指CPU拷贝的次数为0。它是IO的优化方案

传统IO流程

  • 零拷贝实现之mmap+write

  • 零拷贝实现之sendfile

  • 零拷贝实现之带有DMA收集拷贝功能的sendfile

13.1 传统IO流程

流程图如下:

2実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

  • 用户应用进程调用read函数,向操作系统发起IO调用,上下文从用户态转为内核态(切换1)

  • DMA控制器把数据从磁盘中,读取到内核缓冲区。

  • CPU把内核缓冲区数据,拷贝到用户应用缓冲区,上下文从内核态转为用户态(切换2),read函数返回

  • 用户应用进程通过write函数,发起IO调用,上下文从用户态转为内核态(切换3)

  • CPU将应用缓冲区中的数据,拷贝到socket缓冲区

  • DMA控制器把数据从socket缓冲区,拷贝到网卡设备,上下文从内核态切换回用户态(切换4),write函数返回

从流程图可以看出,传统IO的读写流程,包括了4次上下文切换(4次用户态和内核态的切换),4次数据拷贝(两次CPU拷贝以及两次的DMA拷贝)。

13.2 mmap+write实现的零拷贝

mmap 的函数原型如下:

void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
  • addr:指定映射的虚拟内存地址

  • length:映射的长度

  • prot:映射内存的保护模式

  • flags:指定映射的类型

  • fd:进行映射的文件句柄

  • offset:文件偏移量

  • mmap使用了虚拟内存,可以把内核空间和用户空间的虚拟地址映射到同一个物理地址,从而减少数据拷贝次数!

mmap+write实现的零拷贝流程如下:

2実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

  • 用户进程通过mmap方法向操作系统内核发起IO调用,上下文从用户态切换为内核态。

  • CPU利用DMA控制器,把数据从硬盘中拷贝到内核缓冲区。

  • 上下文从内核态切换回用户态,mmap方法返回。

  • 用户进程通过write方法向操作系统内核发起IO调用,上下文从用户态切换为内核态。

  • CPU将内核缓冲区的数据拷贝到的socket缓冲区。

  • CPU利用DMA控制器,把数据从socket缓冲区拷贝到网卡,上下文从内核态切换回用户态,write调用返回。

可以发现,mmap+write实现的零拷贝,I/O发生了4次用户空间与内核空间的上下文切换,以及3次数据拷贝。其中3次数据拷贝中,包括了2次DMA拷贝和1次CPU拷贝。

mmap是将读缓冲区的地址和用户缓冲区的地址进行映射,内核缓冲区和应用缓冲区共享,所以节省了一次CPU拷贝‘’并且用户进程内存是虚拟的,只是映射到内核的读缓冲区,可以节省一半的内存空间。

sendfile实现的零拷贝

sendfile是Linux2.1内核版本后引入的一个系统调用函数,API如下:

ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);
  • out_fd:为待写入内容的文件描述符,一个socket描述符。,

  • in_fd:为待读出内容的文件描述符,必须是真实的文件,不能是socket和管道。

  • offset:指定从读入文件的哪个位置开始读,如果为NULL,表示文件的默认起始位置。

  • count:指定在fdout和fdin之间传输的字节数。

  • sendfile表示在两个文件描述符之间传输数据,它是在操作系统内核中操作的,避免了数据从内核缓冲区和用户缓冲区之间的拷贝操作,因此可以使用它来实现零拷贝。

sendfile实现的零拷贝流程如下:

2実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)
sendfile实现的零拷贝

  • 用户进程发起sendfile系统调用,上下文(切换1)从用户态转向内核态

  • DMA控制器,把数据从硬盘中拷贝到内核缓冲区。

  • CPU将读缓冲区中数据拷贝到socket缓冲区

  • DMA控制器,异步把数据从socket缓冲区拷贝到网卡,

  • 上下文(切换2)从内核态切换回用户态,sendfile调用返回。

可以发现,sendfile实现的零拷贝,I/O发生了2次用户空间与内核空间的上下文切换,以及3次数据拷贝。其中3次数据拷贝中,包括了2次DMA拷贝和1次CPU拷贝。那能不能把CPU拷贝的次数减少到0次呢?有的,即带有DMA收集拷贝功能的sendfile

sendfile+DMA scatter/gather实现的零拷贝

linux 2.4版本之后,对sendfile做了优化升级,引入SG-DMA技术,其实就是对DMA拷贝加入了scatter/gather操作,它可以直接从内核空间缓冲区中将数据读取到网卡。使用这个特点搞零拷贝,即还可以多省去一次CPU拷贝。

sendfile+DMA scatter/gather实现的零拷贝流程如下:

2実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

  • 用户进程发起sendfile系统调用,上下文(切换1)从用户态转向内核态

  • DMA控制器,把数据从硬盘中拷贝到内核缓冲区。

  • CPU把内核缓冲区中的文件描述符信息(包括内核缓冲区的内存地址和偏移量)发送到socket缓冲区

  • DMA控制器根据文件描述符信息,直接把数据从内核缓冲区拷贝到网卡

  • 上下文(切换2)从内核态切换回用户态,sendfile调用返回。

可以发现,sendfile+DMA scatter/gather实现的零拷贝,I/O发生了2次用户空间与内核空间的上下文切换,以及2次数据拷贝。其中2次数据拷贝都是包DMA拷贝。这就是真正的 零拷贝(Zero-copy) 技术,全程都没有通过CPU来搬运数据,所有的数据都是通过DMA来进行传输的。

14. synchronized

synchronized是Java中的关键字,是一种同步锁。synchronized关键字可以作用于方法或者代码块。

一般面试时。可以这么回答:

  • 反编译后,monitorenter、monitorexit、ACC_SYNCHRONIZED

  • monitor监视器

  • Java Monitor 的工作机理

  • 对象与monitor关联

14.1 monitorenter、monitorexit、ACC_SYNCHRONIZED

如果synchronized作用于代码块,反编译可以看到两个指令:monitorenter、monitorexit,JVM使用monitorenter和monitorexit两个指令实现同步;如果作用synchronized作用于方法,反编译可以看到ACCSYNCHRONIZED标记,JVM通过在方法访问标识符(flags)中加入ACCSYNCHRONIZED来实现同步功能。

  • 同步代码块是通过monitorenter和monitorexit来实现,当线程执行到monitorenter的时候要先获得monitor锁,才能执行后面的方法。当线程执行到monitorexit的时候则要释放锁。

  • 同步方法是通过中设置ACCSYNCHRONIZED标志来实现,当线程执行有ACCSYNCHRONIZED标志的方法,需要获得monitor锁。每个对象都与一个monitor相关联,线程可以占有或者释放monitor。

14.2 monitor监视器

monitor是什么呢?操作系统的管程(monitors)是概念原理,ObjectMonitor是它的原理实现。

2実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

在Java虚拟机(HotSpot)中,Monitor(管程)是由ObjectMonitor实现的,其主要数据结构如下:

 ObjectMonitor() {
    _header       = NULL;
    _count        = 0; // 记录个数
    _waiters      = 0,
    _recursions   = 0;
    _object       = NULL;
    _owner        = NULL;
    _WaitSet      = NULL;  // 处于wait状态的线程,会被加入到_WaitSet
    _WaitSetLock  = 0 ;
    _Responsible  = NULL ;
    _succ         = NULL ;
    _cxq          = NULL ;
    FreeNext      = NULL ;
    _EntryList    = NULL ;  // 处于等待锁block状态的线程,会被加入到该列表
    _SpinFreq     = 0 ;
    _SpinClock    = 0 ;
    OwnerIsThread = 0 ;
  }

ObjectMonitor中几个关键字段的含义如图所示:

2実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

14.3 Java Monitor 的工作机理

2実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

  • 想要获取monitor的线程,首先会进入_EntryList队列。

  • 当某个线程获取到对象的monitor后,进入Owner区域,设置为当前线程,同时计数器count加1。

  • 如果线程调用了wait()方法,则会进入WaitSet队列。它会释放monitor锁,即将owner赋值为null,count自减1,进入WaitSet队列阻塞等待。

  • 如果其他线程调用 notify() / notifyAll() ,会唤醒WaitSet中的某个线程,该线程再次尝试获取monitor锁,成功即进入Owner区域。

  • 同步方法执行完毕了,线程退出临界区,会将monitor的owner设为null,并释放监视锁。

14.4 对象与monitor关联

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

  • 在HotSpot虚拟机中,对象在内存中存储的布局可以分为3块区域:对象头(Header),实例数据(Instance Data)和对象填充(Padding)。

  • 对象头主要包括两部分数据:Mark Word(标记字段)、Class Pointer(类型指针)。

Mark Word 是用于存储对象自身的运行时数据,如哈希码(HashCode)、GC分代年龄、锁状态标志、线程持有的锁、偏向线程 ID、偏向时间戳等。

2実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)

重量级锁,指向互斥量的指针。其实synchronized是重量级锁,也就是说Synchronized的对象锁,Mark Word锁标识位为10,其中指针指向的是Monitor对象的起始地址。

15. 分布式id生成方案有哪些?什么是雪花算法?

分布式id生成方案主要有:

  • UUID

  • 数据库自增ID

  • 基于雪花算法(Snowflake)实现

  • 百度 (Uidgenerator)

  • 美团(Leaf)

什么是雪花算法?

雪花算法是一种生成分布式全局唯一ID的算法,生成的ID称为Snowflake IDs。这种算法由Twitter创建,并用于推文的ID。

一个Snowflake ID有64位。

  • 第1位:Java中long的最高位是符号位代表正负,正数是0,负数是1,一般生成ID都为正数,所以默认为0。

  • 接下来前41位是时间戳,表示了自选定的时期以来的毫秒数。

  • 接下来的10位代表计算机ID,防止冲突。

  • 其余12位代表每台机器上生成ID的序列号,这允许在同一毫秒内创建多个Snowflake ID。

実際の Shopee サーバーのインタビューで 15 の質問があります。すべて正しく答えることができますか? (分析あり)
雪花算法

最后PHP中文网祝大家找到一份满意的工作!!!

【面试题专题】

フロントエンド: [フロントエンドのインタビューの質問][js インタビューの質問][ vue インタビューの質問][ajax インタビューの質問][ react インタビューの質問 ]

データベース:【mysql インタビューの質問】【redis インタビューの質問】[oracle インタビュー質問 ]

バックエンド:【PHP面接の質問】【thinkphp面接の質問】【Python面接の質問】【 Java の面接の質問 ]【Android の面接の質問

100,101
102
100
100
声明:
この記事は微信公众号で複製されています。侵害がある場合は、admin@php.cn までご連絡ください。