首頁  >  文章  >  15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

青灯夜游
青灯夜游轉載
2022-02-21 11:40:264617瀏覽

在面試前多看看有關公司的面試資料,對之後的面試會很有幫助。今天就跟大家分享15道蝦皮服務端的面試真題(附答案解析),快來看看自己的程度到底如何吧,希望能幫助大家!

1. 排序鍊錶

給你鍊錶的頭結點head ,請將其按升序排列並返回排序後的鍊錶 。

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

實例1:

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

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

#實例2:

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

這題可以用雙指標歸併排序演算法解決,主要以下四個步驟

 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.對稱與非對稱加密演算法的差異

#先複習一下相關概念:

  • 明文:指沒有經過加密的資訊/資料。

  • 密文:明文被加密演算法加密之後,會變成密文,以確保資料安全。

  • 金鑰:是一種參數,它是在明文轉換為密文或將密文轉換為明文的演算法中輸入的參數。密鑰分為對稱密鑰與非對稱密鑰。

  • 加密:將明文變成密文的過程。

  • 解密:將密文還原為明文的過程。

對稱加密演算法:加密和解密使用相同金鑰的加密演算法。常見的對稱加密演算法有AES、3DES、DES、RC5、RC6等。

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

非對稱加密演算法:非對稱加密演算法需要兩個金鑰(公開金鑰和私有金鑰)。公鑰與私鑰是成對存在的,如果用公鑰對資料進行加密,只有對應的私鑰才能解密。主要的非對稱加密演算法有:RSA、Elgamal、DSA、D-H、ECC

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

3. TCP如何保證可靠性

  • 首先,TCP的連線是基於三次握手,而斷開則是四次揮手。確保連接和斷開的可靠性。

  • 其次,TCP的可靠性,也體現在有狀態;TCP會記錄哪些資料發送了,哪些資料被接受了,哪些沒有被接受,並且保證資料包按序到達,保證資料傳輸不出差錯。

  • 再次,TCP的可靠性,也體現在可控制。它有報文校驗、ACK應答、逾時重傳(發送方)、失序資料重傳(接收方)、丟棄重複資料、流量控制(滑動視窗)和擁塞控制等機制。

4. 聊聊五種IO模型

#4.1 阻塞IO 模型

假設應用程式的進程發起IO調用,但是如果核心的資料還沒準備好的話,那應用程式進程就一直在阻塞等待,一直等到核心資料準備好了,從核心拷貝到用戶空間,才回傳成功提示,這次IO操作,稱為阻塞IO。

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

4.2 非阻塞IO模型

如果核心資料還沒準備好,可以先回傳錯誤資訊給用戶進程,讓它不需要等待,而是透過輪詢的方式再來請求。這就是非阻塞IO,流程圖如下:

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

4.3 IO多路復用模型

IO多路復用之select

應用程式透過呼叫select函數,可以同時監控多個fd,在select函數監控的fd中,只要有任何一個資料狀態準備就緒了,select函數就會回傳可讀狀態,這時應用程式再發起recvfrom請求去讀取資料。

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

select有幾個缺點:

  • #最大連接數有限,在Linux系統上一般為1024。

  • select函數傳回後,是透過遍歷fdset,找到就緒的描述子fd。

IO多路復用之epoll

#為了解決select存在的問題,多路復用模型epoll誕生,它採用事件驅動來實現,流程圖如下:

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

epoll先透過epoll_ctl()來註冊一個fd(檔案描述子),一旦基於某個fd就緒時,核心會採用回呼機制,迅速啟動這個fd,當進程呼叫epoll_wait()時便得到通知。這裡去掉了遍歷文件描述符的坑爹操作,而是採用監聽事件回呼的機制。這就是epoll的亮點。

4.4 IO模型之訊號驅動模型

訊號驅動IO不再用主動詢問的方式去確認資料是否就緒,而是向核心發送一個訊號(呼叫sigaction的時候建立一個SIGIO的訊號),然後應用使用者進程可以去做別的事,不用阻塞。當核心資料準備好後,再透過SIGIO訊號通知應用進程,資料準備好後的可讀狀態。應用用戶程序收到訊號之後,立即呼叫recvfrom,去讀取資料。

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

4.5 IO 模型之非同步IO(AIO)

AIO實作了IO全流程的非阻塞,就是應用程式發出系統呼叫後,是立即回傳的,但是立即回傳的不是處理結果,而是表示提交成功類似的意思。等核心資料準備好,將資料拷貝到使用者行程緩衝區,發送訊號通知使用者進程IO操作執行完畢。

流程如下:

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

5. hystrix 運作原理

Hystrix 工作流程圖如下:

115道蝦皮服務端面試真題,你能全答對嗎? (附解析)

1、建置指令

Hystrix 提供了兩個指令物件:HystrixCommand和HystrixObservableCommand,它將代表你的一個依賴請求任務,向建構函式中傳入請求依賴所需要的參數。

2、執行指令

有四種方式執行Hystrix指令。分別是:

  • R execute():同步阻塞執行的,從依賴請求中接收到單一回應。

  • Future queue():非同步執行,傳回一個包含單一回應的Future物件。

  • Observable observe():在建立Observable後會訂閱Observable,從依賴請求傳回代表回應的Observable物件

  • #Observable toObservable() :cold observable,回傳一個Observable,只有訂閱時才會執行Hystrix指令,可以傳回多個結果

3、檢查回應是否被快取

如果啟用了Hystrix緩存,任務執行前會先判斷是否有相同指令執行的快取。如果有則直接傳回包含快取回應的Observable;如果沒有快取的結果,但啟動了緩存,將快取本次執行結果以供後續使用。

4、檢查迴路器是否開啟迴路器(circuit-breaker)和保險絲類似,保險絲在發生危險時將會燒斷以保護電路,而迴路器可以在達到我們設定的閥值時觸發短路(例如請求失敗率達50%),拒絕執行任何請求。

如果迴路器被打開,Hystrix將不會執行指令,直接進入Fallback處理邏輯。

5、檢查執行緒池/信號量/佇列情況 Hystrix 隔離方式有執行緒池隔離和信號量隔離。當使用Hystrix線程池時,Hystrix 預設為每個依賴服務分配10個線程,當10個線程都繁忙時,將拒絕執行命令,,而是立即跳到執行fallback邏輯。

6、執行具體的任務 透過HystrixObservableCommand.construct() 或 HystrixCommand.run() 來執行使用者真正的任務。

7、計算迴路健康每次開始執行command、結束執行command以及發生異常等情況時,都會記錄執行情況,例如:成功、失敗、拒絕和超時等指標情況,會定期處理這些數據,再根據設定的條件來判斷是否開啟迴路器。

8、指令失敗時執行Fallback邏輯 在指令失敗時執行使用者指定的 Fallback 邏輯。上圖中的斷路、執行緒池拒絕、信號量拒絕、執行執行、執行逾時都會進入Fallback處理。

9、傳回執行結果 原始物件結果將以Observable形式傳回,在傳回給使用者之前,會根據呼叫方式的不同做一些處理。

6. 延時場景處理

日常開發中,我們經常遇到這種業務場景,如:外帶訂單超30分鐘未支付,則自動取消訂單;用戶註冊成功15分鐘後,發送簡訊通知用戶等等。這就是延時任務處理場景。針對這類場景我們主要有以下幾個處理方案:

  • JDK的DelayQueue延遲佇列

  • 時間輪演算法

  • 資料庫定時任務(如Quartz)

  • Redis ZSet 實作

  • MQ 延時佇列實作

7.https請求程序

  • #HTTPS = HTTP SSL/TLS,即用SSL/TLS對資料進行加密與解密,Http進行傳輸。

  • SSL,即Secure Sockets Layer(安全通訊端協定),是網路通訊提供安全及資料完整性的一種安全協定。

  • TLS,即Transport Layer Security(安全傳輸層協定),它是SSL 3.0的後續版本。

115道蝦皮服務端面試真題,你能全答對嗎? (附解析)
http請求流程

1、使用者在瀏覽器輸入一個https網址,然後連接到server的443埠。

2、伺服器必須要有一套數位證書,可以自己製作,也可以向組織申請,差別就是自己頒發的證書需要客戶端驗證通過。這套憑證其實就是一對公鑰和私鑰。

3、伺服器將自己的數位憑證(含有公鑰)傳送給客戶端。

4、用戶端收到伺服器端的數位憑證之後,會對其進行檢查,如果不通過,則會彈出警告框。如果憑證沒問題,則產生一個金鑰(對稱加密),用憑證的公鑰對它加密。

5、客戶端會發起HTTPS中的第二個HTTP請求,將加密之後的客戶端金鑰傳送給伺服器。

6、伺服器接收到客戶端發來的密文之後,會用自己的私鑰對其進行非對稱解密,解密之後得到客戶端密鑰,然後用客戶端密鑰對返回數據進行對稱加密,這樣資料就變成了密文。

7、伺服器將加密後的密文回傳給客戶端。

8、客戶端收到伺服器發送回傳的密文,用自己的金鑰(客戶端金鑰)對其進行對稱解密,得到伺服器傳回的資料。

8. 聊聊交易隔離級別,以及可重複讀取實現原理

#8.1 資料庫四大隔離級別

為了解決並發交易存在的髒讀、不可重複讀取、幻讀等問題,資料庫大叔設計了四種隔離等級。分別是讀取未提交,讀取已提交,可重複讀取,串行化(Serializable)

  • 讀取未提交隔離等級:只限制了兩個資料不能同時修改,但是修改資料的時候,即使事務未提交,都是可以被別的事務讀取到的,這層級的交易隔離有髒讀、重複讀取、幻讀的問題;

  • #已提交隔離等級:目前交易只能讀取到其他交易提交的數據,所以這種交易的隔離等級解決了髒讀問題,但還是會存在重複讀取、幻讀問題;

  • #可重複讀取:限制了讀取資料的時候,不可以進行修改,所以解決了重複讀取的問題,但是讀取範圍數據的時候,是可以插入數據,所以還會存在幻讀問題;

  • ##串行化:事務最高的隔離級別,在該級別下,所有事務都是進行串行化順序執行的。可以避免髒讀、不可重複讀與幻讀所有並發問題。但是這種事務隔離等級下,事務執行很耗效能。

四大隔離級別,都會存在哪些並發問題呢

讀取未提交√√√讀取已提交×√√可重複讀取##×#√序列化××##×
隔離等級 髒讀 無法重複讀取 幻讀
##×
##### #

8.2 Read View可見性規則

##描述m_ids目前系統中那些活躍(未提交)的讀寫事務ID, 它資料結構為一個List。 max_limit_id表示產生Read View時,系統中應該指派給下一個交易的id值。 min_limit_id表示在產生Read View時,目前系統中活躍的讀寫事務中最小的交易id,即m_ids中的最小值。 creator_trx_id建立目前Read View的事務ID

Read View的可見性規則如下:

  • 如果資料事務ID trx_id #,表示產生該版本的交易正在產生<code>Read View前,已經提交(因為事務ID是遞增的),所以該版本可以被目前事務存取。

  • 如果trx_id>= max_limit_id,表示產生該版本的事務在生成Read View後才生成,所以該版本不可以被目前事務存取。

  • 如果min_limit_id =<trx_id max_limit_id>,需要分3種情況討論</trx_id>

##1)如果m_ids包含trx_id,則代表Read View產生時刻,這個交易還未提交,但是如果資料的trx_id#等於creator_trx_id的話,表示資料是自己產生的,因此是可見的。

2)如果m_ids包含trx_id,且trx_id不等於creator_trx_id,則Read View生成時,事務未提交,且不是自己生產的,所以當前事務也是看不見的;

3)如果m_ids不包含trx_id,則說明你這個事務在Read View生成之前就已經提交了,修改的結果,當前事務是能看見的。

8.3 可重複讀取實現原理

#資料庫是透過加鎖實現隔離等級的,例如,你想一個人靜靜,不被別人打擾,你可以把自己關在房子,並在房門上加上一把鎖!串行化隔離等級就是加鎖實現的。但是如果頻繁加鎖,效能會下降。因此設計資料庫的大叔想到了MVCC

可重複讀取的實作原理就是MVCC多版本並發控制。在一個事務範圍內,兩個相同的查詢,讀取同一筆記錄,卻回傳了不同的數據,這就是不可重複讀取。可重複讀取隔離級別,就是為了解決不可重複讀取問題。

查詢一筆記錄,基於MVCC,是怎樣的流程呢?

  • 取得事務自己的版本號,即事務ID

  • #取得Read View

  • ##查詢得到的數據,然後Read View中的交易版本號進行比較。

  • 如果不符合Read View的可見性規則,即就需要Undo log中歷史快照;

  • 最後傳回符合規則的資料

InnoDB 實作

MVCC,是透過Read View Undo Log實現的,Undo Log儲存了歷史快照,Read View可見性規則可協助判斷目前版本的資料是否可見。

可重複讀取(RR)隔離級別,是如何解決不可重複讀取問題的?

假設存在交易A和B,SQL執行流程如下

115道蝦皮服務端面試真題,你能全答對嗎? (附解析)

#在可重複讀取(RR)隔離等級下,一個交易只會取得一次

read view,都是副本共用的,從而保證每次查詢的資料都是一樣的。

假設目前有一張core_user表,插入一條初始化資料,如下:

115道蝦皮服務端面試真題,你能全答對嗎? (附解析)

基於MVCC,我們來看看執行流程

1.A開啟事務,首先得到一個事務ID為100

2、B開啟事務,得到事務ID為101

3、事務A產生一個Read View,read view對應的值如下

#變數
變數
#m_ids 100,101
max_limit_id 102
#min_limit_id #100
# creator_trx_id 100

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

115道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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

115道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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

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

115道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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

115道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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

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

使用格式如下:

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

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

实现demo如下:

115道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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底层原理是怎样的吧:

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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

13. 零拷贝

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

传统IO流程

  • 零拷贝实现之mmap+write

  • 零拷贝实现之sendfile

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

13.1 传统IO流程

流程图如下:

215道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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

215道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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

215道蝦皮服務端面試真題,你能全答對嗎? (附解析)
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实现的零拷贝流程如下:

215道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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

215道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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

215道蝦皮服務端面試真題,你能全答對嗎? (附解析)

14.3 Java Monitor 的工作机理

215道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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

215道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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

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

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

215道蝦皮服務端面試真題,你能全答對嗎? (附解析)

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

15道蝦皮服務端面試真題,你能全答對嗎? (附解析)
雪花算法

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

【面试题专题】

前端:【前端面試題】【js面試題 】【 vue面試題】【ajax面試題】【 react面試題

資料庫:【mysql面試題】【redis面試題】【oracle面試題

後端:【PHP面試題】【thinkphp面試題】【python面試題】【java面試題】【android面試題

陳述:
本文轉載於:微信公众号。如有侵權,請聯絡admin@php.cn刪除