15 soalan temuduga pelayan Shopee sebenar, bolehkah anda menjawab semuanya dengan betul? (dengan analisis)

Baca lebih lanjut tentang bahan temu duga syarikat sebelum temu duga, yang akan sangat membantu untuk temu duga seterusnya. Hari ini saya akan berkongsi dengan anda 15 soalan temuduga pelayan Shopee yang sebenar (dengan analisis jawapan Datang dan lihat tahap anda, saya harap ia dapat membantu anda!

1. Isih senarai terpaut

memberi anda nod kepala senarai terpaut, sila isikannya dalam tertib menaik dan kembalikan senarai terpaut yang diisih.

Contoh 1:

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

Contoh 2:

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

Ini masalah boleh diselesaikan menggunakan algoritma isihan gabungan dua penuding, yang terutamanya melibatkan empat langkah berikut

1. Kaedah penuding pantas dan perlahan, melintasi senarai terpaut untuk mencari nod perantaraan

2 . Potong senarai terpaut di nod perantaraan

3. Gunakan isihan gabungan untuk mengisih senarai subpautan kiri dan kanan masing-masing

4. Cantumkan senarai subpautan

Kod lengkap adalah seperti berikut:

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. Perbezaan antara algoritma penyulitan simetri dan asimetri

Mari kita semak konsep yang berkaitan dahulu:

• Teks kosong: merujuk kepada maklumat/data yang belum disulitkan.

• Sifirteks: Selepas teks biasa disulitkan oleh algoritma penyulitan, ia akan menjadi teks sifir untuk memastikan keselamatan data.

• Kunci: ialah parameter yang dimasukkan dalam algoritma yang menukar teks biasa kepada teks sifir atau teks sifir kepada teks biasa. Kekunci dibahagikan kepada kekunci simetri dan kekunci tidak simetri.

• Penyulitan: Proses menukar teks biasa kepada teks sifir.

• Penyahsulitan: Proses mengurangkan teks sifir kepada teks biasa.

Algoritma penyulitan simetri: Algoritma penyulitan yang menggunakan kunci yang sama untuk penyulitan dan penyahsulitan. Algoritma penyulitan simetri biasa termasuk AES, 3DES, DES, RC5, RC6, dsb.

Algoritma penyulitan asimetri : Algoritma penyulitan asimetri memerlukan dua kekunci (kunci awam dan kunci persendirian). Kunci awam dan kunci persendirian wujud secara berpasangan Jika kunci awam digunakan untuk menyulitkan data, hanya kunci persendirian yang sepadan boleh menyahsulitnya. Algoritma penyulitan asimetri utama ialah: RSA, Elgamal, DSA, D-H, ECC.

3 Bagaimana TCP memastikan kebolehpercayaan

• Pertama sekali, sambungan TCP adalah berdasarkan tiga. -cara berjabat tangan Dan pemotongan adalah empat gelombang. Pastikan sambungan dan pemutusan sambungan yang boleh dipercayai.

• Kedua, kebolehpercayaan TCP juga ditunjukkan dalam keadaan; adalah dalam rangka Ketibaan untuk memastikan tiada ralat dalam penghantaran data.

• Ketiga, kebolehpercayaan TCP juga ditunjukkan dalam kebolehkawalannya. Ia mempunyai mekanisme seperti pengesahan mesej, respons ACK, penghantaran semula tamat masa (penghantar), penghantaran semula data di luar urutan (penerima), membuang data pendua, kawalan aliran (tetingkap gelongsor) dan kawalan kesesakan.

4.1 Menyekat model IO

Andaikan proses aplikasi memulakan panggilan IO, tetapi jika data kernel belum sedia, proses aplikasi akan disekat dan menunggu sehingga data kernel sedia dan disalin dari kernel ke ruang pengguna Mengembalikan gesaan yang berjaya , operasi IO ini dipanggil menyekat IO.

4.2 Model IO tidak menyekat

Jika data kernel belum sedia, anda boleh kembalikan ralat dahulu Maklumat diberikan kepada proses pengguna supaya ia tidak perlu menunggu, tetapi meminta semula melalui pengundian. Ini ialah IO tidak menyekat dan carta alir adalah seperti berikut:

4.3 model pemultipleksan IO

Pilih pemultipleksan IO

Proses aplikasi boleh memantau berbilang fd pada masa yang sama dengan memanggil fungsi pilih Dalam fd yang dipantau oleh fungsi pilih, asalkan sebarang status data ready , fungsi pilih akan kembali ke keadaan boleh dibaca, dan kemudian proses permohonan akan memulakan permintaan recvfrom untuk membaca data.

pilih mempunyai beberapa kelemahan:

Bilangan maksimum sambungan adalah terhad, biasanya 1024 pada sistem Linux.

• Selepas fungsi pilih kembali, ia merentasi fdset untuk mencari deskriptor fd sedia.

• epoll untuk pemultipleksan IO

Untuk menyelesaikan masalah pemilihan, epoll model pemultipleksan telah dilahirkan, yang didorong oleh peristiwa Kepada laksanakan, carta alir adalah seperti berikut:

epoll mula-mula mendaftarkan fd (deskriptor fail) melalui epoll_ctl(). Setelah fd tertentu sudah siap, kernel akan menggunakan mekanisme panggil balik untuk mengaktifkan fd dengan cepat Apabila proses memanggil epoll_wait(), ia akan dimaklumkan. Operasi rumit untuk melintasi deskriptor fail dialih keluar di sini dan mekanisme mendengar panggilan balik acara digunakan. Ini adalah kemuncak epoll.

4.4 Model dipacu isyarat model IO

IO dipacu isyarat tidak lagi menggunakan pertanyaan aktif untuk mengesahkan sama ada data sedia, tetapi kepada Kernel menghantar isyarat (isyarat SIGIO ditubuhkan apabila memanggil sigaction), dan kemudian proses pengguna aplikasi boleh melakukan perkara lain tanpa menyekat. Apabila data kernel sedia, proses aplikasi dimaklumkan melalui isyarat SIGIO bahawa data sedia untuk dibaca. Selepas proses pengguna aplikasi menerima isyarat, ia segera memanggil recvfrom untuk membaca data.

4.5 IO model asynchronous IO (AIO)

AIO menyedari ketidak-linearan keseluruhan Penyekatan proses IO bermaksud bahawa selepas proses aplikasi mengeluarkan panggilan sistem, ia kembali serta-merta, tetapi apa yang dikembalikan serta-merta bukanlah hasil pemprosesan, tetapi sesuatu seperti penyerahan yang berjaya. Apabila data kernel sedia, salin data ke penimbal proses pengguna, dan hantar isyarat untuk memberitahu proses pengguna bahawa operasi IO telah selesai.

Prosesnya adalah seperti berikut:

5 Prinsip kerja Hystrix

Rajah aliran kerja Hystrix adalah seperti berikut. :

1. Bina arahan

Hystrix menyediakan dua objek arahan: HystrixCommand dan HystrixObservableCommand, yang akan mewakili salah satu tugas permintaan pergantungan anda dan menghantarnya ke dalam Parameter pembina yang diperlukan untuk meminta kebergantungan.

2. Laksanakan arahan

Terdapat empat cara untuk melaksanakan arahan Hystrix. Ia adalah:

• R execute(): pelaksanaan penyekatan segerak, menerima satu respons daripada permintaan bergantung.

• Future queue(): Pelaksanaan tak segerak, mengembalikan objek Masa Depan yang mengandungi satu respons.

• Observable observe(): Selepas mencipta Observable, ia akan melanggan Observable dan mengembalikan objek Observable yang mewakili respons daripada permintaan bergantung

• Observable toObservable() : cold observable, mengembalikan perintah Observable, Hystrix hanya akan dilaksanakan apabila melanggan dan berbilang hasil boleh dikembalikan

3 Periksa sama ada respons dicache

jika cache Hystrix didayakan, sebelum pelaksanaan tugas, ia akan terlebih dahulu menentukan sama ada terdapat cache untuk pelaksanaan arahan yang sama. Jika ada, Observable yang mengandungi respons cache dikembalikan secara langsung jika tiada hasil cache tetapi caching didayakan, hasil pelaksanaan akan dicache untuk kegunaan seterusnya.

4. Periksa sama ada pemutus litar terbuka Pemutus litar (pemutus litar) adalah serupa dengan fius litar apabila ia mencapai ambang yang kami tetapkan Cetuskan litar pintas (contohnya, kadar kegagalan permintaan mencapai 50%) dan enggan melaksanakan sebarang permintaan.

Jika gelung dibuka, Hystrix tidak akan melaksanakan arahan dan terus memasuki logik pemprosesan Fallback.

5. Semak situasi kumpulan benang/semaphore/baris gilir termasuk pengasingan kumpulan benang dan pengasingan semaphore. Apabila menggunakan kumpulan benang Hystrix, Hystrix memperuntukkan 10 utas kepada setiap perkhidmatan bergantung secara lalai Apabila semua 10 utas sibuk, pelaksanaan arahan akan ditolak, dan sebaliknya ia akan segera melompat ke pelaksanaan logik sandaran.

6. Laksanakan tugasan tertentu melalui HystrixObservableCommand.construct() atau HystrixCommand.run() untuk menjalankan tugas sebenar pengguna.

7 Kira kesihatan gelung Setiap kali anda mula melaksanakan perintah, menamatkan pelaksanaan perintah atau pengecualian berlaku, status pelaksanaan akan direkodkan, seperti: kejayaan, kegagalan, penolakan, tamat masa dan penunjuk lain. , dan ini akan diproses dengan kerap, dan kemudian menentukan sama ada untuk membuka gelung mengikut syarat yang ditetapkan.

8. Laksanakan logik Fallback apabila arahan gagal. Dalam rajah di atas, pemutus litar, penolakan kumpulan benang, penolakan semaphore, pelaksanaan pelaksanaan dan tamat masa pelaksanaan semuanya akan memasuki pemprosesan Fallback.

9. Kembalikan hasil perlaksanaan Hasil objek asal akan dikembalikan dalam bentuk Observable Sebelum dikembalikan kepada pengguna, beberapa pemprosesan akan dilakukan bergantung pada kaedah panggilan.

6. Kelewatan pemprosesan senario

Dalam pembangunan harian, kami sering menghadapi senario perniagaan seperti ini, seperti: jika pesanan bawa pulang tidak dibayar lebih daripada 30 minit, ia akan dibatalkan secara automatik Pesanan 15 minit selepas pengguna berjaya mendaftar, mesej teks akan dihantar untuk memberitahu pengguna, dsb. Ini ialah senario pemprosesan tugas yang tertangguh. Kami terutamanya mempunyai penyelesaian berikut untuk senario sedemikian:

• Baris gilir kelewatan DelayQueue JDK

• Algoritma roda masa

• Tugas berjadual pangkalan data (seperti Kuarza)

• Pelaksanaan Redis ZSet

• Pelaksanaan baris gilir kelewatan MQ

7.proses permintaan https

• HTTPS = HTTP SSL/TLS, iaitu menggunakan SSL/TLS untuk menyulitkan dan menyahsulit data , HTTP untuk penghantaran.

• SSL, atau Secure Sockets Layer, ialah protokol keselamatan yang menyediakan keselamatan dan integriti data untuk komunikasi rangkaian.

• TLS, Transport Layer Security (Secure Transport Layer Protocol), ialah versi SSL 3.0 yang seterusnya.

proses permintaan http

1. Pengguna memasukkan URL https dalam penyemak imbas, dan kemudian menyambung ke port 443 pelayan.

2. Pelayan mesti mempunyai satu set sijil digital Anda boleh membuatnya sendiri atau memohon kepada organisasi. Set sijil ini sebenarnya adalah sepasang kunci awam dan peribadi.

3. Pelayan menghantar sijil digitalnya sendiri (mengandungi kunci awam) kepada pelanggan.

4. Selepas pelanggan menerima sijil digital daripada pelayan, ia akan menyemaknya Jika gagal, kotak amaran akan muncul. Jika sijil OK, kunci dijana (penyulitan simetri) dan disulitkan dengan kunci awam sijil.

5 Pelanggan akan memulakan permintaan HTTP kedua dalam HTTPS dan menghantar kunci klien yang disulitkan ke pelayan.

6 Selepas menerima teks sifir daripada klien, pelayan akan menggunakan kunci peribadinya sendiri untuk menyahsulitnya secara tidak simetri Selepas penyahsulitan, ia akan memperoleh kunci klien, dan kemudian menggunakan pasangan kunci klien untuk mengembalikan data . Lakukan penyulitan simetri supaya data menjadi teks sifir.

7. Pelayan mengembalikan teks sifir yang disulitkan kepada klien.

8 Pelanggan menerima teks sifir yang dikembalikan oleh pelayan, menggunakan kuncinya sendiri (kunci pelanggan) untuk menyahsulitnya secara simetri dan mendapatkan data yang dikembalikan oleh pelayan.

8 Mari kita bincangkan tentang tahap pengasingan transaksi dan prinsip pelaksanaan bacaan boleh berulang

8.1 Empat tahap pengasingan utama pangkalan data

Untuk menyelesaikan masalah bacaan kotor, bacaan tidak boleh diulang dan bacaan hantu dalam urus niaga serentak, pakcik pangkalan data mereka empat tahap pengasingan. Mereka dibaca tanpa komitmen, dibaca komited, dibaca berulang dan boleh disirikan .

• Baca tahap pengasingan tanpa komitmen: Ia hanya mengehadkan bahawa dua data tidak boleh diubah suai pada masa yang sama, tetapi apabila data diubah suai, walaupun transaksi tidak diserahkan, ia boleh dibaca oleh urus niaga lain , tahap pengasingan transaksi ini mempunyai masalah dengan bacaan kotor, bacaan berulang dan bacaan hantu

• Baca tahap pengasingan yang diserahkan: urus niaga semasa hanya boleh membaca data yang diserahkan oleh orang lain. transaksi, jadi Tahap pengasingan transaksi ini menyelesaikan masalah bacaan kotor, tetapi masih terdapat masalah dengan bacaan berulang dan bacaan hantu

• Bacaan berulang: tidak boleh dilakukan apabila membaca data dihadkan. Pengubahsuaian, jadi masalah pembacaan berulang diselesaikan, tetapi apabila membaca data julat, data boleh dimasukkan, jadi masih akan ada masalah bacaan hantu; tahap, di mana semua urus niaga dilaksanakan secara bersiri. Ia boleh mengelakkan semua masalah konkurensi bacaan kotor, bacaan tidak berulang dan bacaan hantu. Walau bagaimanapun, di bawah tahap pengasingan urus niaga ini, pelaksanaan transaksi adalah sangat intensif prestasi.

• Apakah masalah konkurensi antara empat tahap pengasingan

  隔离级别	脏读	不可重复读	幻读
  读未提交	√	√	√
  读已提交	×	√	√
  可重复读	×	×	√
  串行化	×	×	×

  8.2 Peraturan Keterlihatan Paparan Baca

  变量	描述
  m_ids	当前系统中那些活跃(未提交)的读写事务ID, 它数据结构为一个List。
  max_limit_id	表示生成Read View时，系统中应该分配给下一个事务的id值。
  min_limit_id	表示在生成Read View时，当前系统中活跃的读写事务中最小的事务id，即m_ids中的最小值。
  creator_trx_id	创建当前Read View的事务ID

  Peraturan keterlihatan Read View adalah seperti berikut:

  • Jika ID transaksi data ialah trx_id < min_limit_id, ini menunjukkan bahawa transaksi yang menjana versi ini telah dilakukan sebelum menjana Read View (kerana ID transaksi dinaikkan), jadi versi ini boleh diakses oleh transaksi semasa.

  • Jika trx_id>= max_limit_id, ini bermakna transaksi yang menjana versi ini dijana selepas Read View dijana, jadi versi ini tidak boleh diakses oleh transaksi semasa.

  • Jika min_limit_id =<trx_id< max_limit_id, kita perlu membincangkannya dalam tiga situasi

  1) Jika m_ids mengandungi trx_id , kemudian Mewakili saat Read View dijana Transaksi ini masih belum dilakukan, tetapi jika trx_id data adalah sama dengan creator_trx_id, ia menunjukkan bahawa data telah dijana dengan sendirinya, jadi ia boleh dilihat. .

  2) Jika m_ids mengandungi trx_id, dan trx_id tidak sama dengan creator_trx_id, maka apabila Read View dijana, transaksi tidak dilakukan dan tidak dihasilkan dengan sendirinya, jadi transaksi semasa juga tidak kelihatan ;

  3) Jika m_ids tidak mengandungi trx_id, ini bermakna transaksi anda telah diserahkan sebelum Read View dihasilkan, dan hasil pengubahsuaian boleh dilihat oleh transaksi semasa.

  8.3 Prinsip Pelaksanaan Bacaan Berulang

  Pangkalan data mencapai tahap pengasingan melalui penguncian Contohnya, jika anda mahu bersendirian Untuk senyap dan tidak diganggu orang lain, anda boleh mengunci diri di dalam rumah dan menambah kunci pada pintu! Tahap pengasingan bersiri dilaksanakan dengan mengunci. Tetapi jika anda kerap mengunci, prestasi akan menurun. Jadi pakcik yang reka pangkalan data memikirkan MVCC.

  Prinsip pelaksanaan bacaan boleh ulang ialah kawalan pertukaran mata wang berbilang versi MVCC. Dalam skop transaksi, dua pertanyaan yang sama membaca rekod yang sama, tetapi mengembalikan data yang berbeza Ini dibaca tidak boleh diulang . Tahap pengasingan bacaan boleh berulang adalah untuk menyelesaikan masalah bacaan tidak boleh berulang .

  Tanya rekod berdasarkan MVCC Apakah prosesnya?

  • Dapatkan nombor versi transaksi, iaitu ID transaksi

  • Dapatkan Paparan Baca

  • Pertanyaan Data yang diperoleh kemudian dibandingkan dengan nombor versi transaksi dalam Pandangan Baca.

  • Jika peraturan keterlihatan Read View tidak dipenuhi, petikan sejarah dalam log Buat asal diperlukan; memenuhi peraturan

  • InnoDB melaksanakan

    MVCC
  melalui
  menyimpan petikan sejarah

  peraturan keterlihatan membantu menentukan sama ada versi data semasa nampak. Bagaimanakah tahap pengasingan bacaan boleh berulang (RR) menyelesaikan masalah bacaan tidak boleh berulang? Read View Undo LogUndo LogDengan mengandaikan terdapat transaksi A dan B, aliran pelaksanaan SQL adalah seperti berikut Read View

  Di bawah tahap pengasingan baca berulang (RR), transaksi hanya akan diperoleh sekali

  , dikongsi oleh replika, dengan itu memastikan bahawa data untuk setiap pertanyaan adalah sama.

  Anggap bahawa pada masa ini terdapat jadual pengguna_teras dan masukkan data permulaan seperti berikut:

  read view

  Berdasarkan MVCC, mari kita lihat proses pelaksanaan

  1. A memulakan transaksi dan mula-mula mendapat ID transaksi 100

  2. B memulakan transaksi dan mendapat ID transaksi 101
  3 Paparan Baca dan nilai yang sepadan dengan paparan baca Seperti berikut

  变量	值
  m_ids	100，101
  max_limit_id	102
  min_limit_id	100
  creator_trx_id	100

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

  

  由图可以看出，最新版本的列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的地址。

  

  5、事务B提交事务

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

  变量	值
  m_ids	100，101
  max_limit_id	102
  min_limit_id	100
  creator_trx_id	100

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

  

  从图可得，最新版本的列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的数据拷贝次数啦，示意图如下：

  

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

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

  使用格式如下：

  zadd key score member [score member ...]，zrank key member

  • 层内部编码：ziplist（压缩列表）、skiplist（跳跃表）

  • 使用场景如排行榜，社交需求（如用户点赞）

  实现demo如下：

  

  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('get',KEYS[1]) == ARGV[1] then 
     return redis.call('del',KEYS[1]) 
  else
     return 0
  end;

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

  12.5 Redisson

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

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

  

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

  13. 零拷贝

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

  传统IO流程

  • 零拷贝实现之mmap+write

  • 零拷贝实现之sendfile

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

  13.1 传统IO流程

  流程图如下：

  

  • 用户应用进程调用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实现的零拷贝流程如下：

  

  • 用户进程通过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实现的零拷贝流程如下：

  
  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实现的零拷贝流程如下：

  

  • 用户进程发起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是它的原理实现。

  

  在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中几个关键字段的含义如图所示：

  

  14.3 Java Monitor 的工作机理

  

  • 想要获取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关联

  

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

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

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

  

  重量级锁，指向互斥量的指针。其实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。

  
  雪花算法

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

  【面试题专题】

  Hadapan: [Soalan temuduga hadapan][soalan temuduga js][ soalan temuduga vue][soalan temuduga ajax 】Backend: [

  soalan temuduga PHP

  ][thinkphp soalan temuduga][soalan temuduga python][ soalan temuduga java 】【

  soalan temuduga android

  】