[發明專利]一種刪除過期鍵的方法和裝置

在審

• 申請號: 201811332078.8
• 申請日: 2018-11-09
• 公開（公告）號: CN111177109A
• 公開（公告）日: 2020-05-19
• 發明（設計）人: 余小龍;張帥
• 申請（專利權）人: 北京京東尚科信息技術有限公司;北京京東世紀貿易有限公司
• 主分類號: G06F16/21
• 分類號: G06F16/21;G06F9/50
• 代理公司: 中原信達知識產權代理有限責任公司 11219
• 代理人: 張一軍;李陽

1.一種刪除過期鍵的方法，其特征在于，包括：

生成n個分桶，所述n個分桶的過期時間戳依次遞增；其中，n為大于1的正整數；

根據各個分桶的過期時間戳和鍵的過期時間戳，分別在所述n個分桶內存放對應的鍵，以使所述鍵的過期時間戳小于等于其所存放的分桶的過期時間戳，大于其所存放的分桶的前一個分桶的過期時間戳；

定時或者定期刪除過期的分桶以及存放在所述分桶內的過期鍵。

2.根據權利要求1所述的方法，其特征在于，生成n個分桶，所述n個分桶的過期時間戳依次遞增，包括：

根據單位時間段和當前時間戳，生成n個分桶，所述n個分桶的過期時間戳基于所述單位時間段依次遞增；

其中，前n-1個分桶的過期時間戳為前一個分桶的過期時間戳加上單位時間段，第n個分桶的過期時間戳為正無窮。

3.根據權利要求2所述的方法，其特征在于，根據各個分桶的過期時間戳和鍵的過期時間戳，分別在所述n個分桶內存放對應的鍵，以使所述鍵的過期時間戳小于等于其所存放的分桶的過期時間戳，大于其所存放的分桶的前一個分桶的過期時間戳，包括：

根據當前時間戳和鍵的過期時長，確定鍵的過期時間戳；

根據各個分桶的過期時間戳和所述鍵的過期時間戳，采用半折查找法查找所述鍵對應的分桶，使得所述鍵的過期時間戳小于等于所述分桶的過期時間戳，并大于所述分桶的前一個分桶的過期時間戳；

判斷所述分桶內存放的鍵的數量是否超過第一數量閾值；若是，則將所述分桶拆分為兩個分桶，將所述鍵存入其中一個分桶內，以使每個分桶內存放的鍵的數量少于等于第一數量閾值；若否，則將所述鍵存入所述分桶內。

4.根據權利要求3所述的方法，其特征在于，將所述分桶拆分為兩個分桶，將所述鍵存入其中一個分桶內，包括：

根據所述分桶的過期時間戳和單位時間段，將所述分桶拆分為兩個分桶，所述兩個分桶的過期時間戳的差值為單位時間段的一半；

根據所述兩個分桶的過期時間戳和所述鍵的過期時間戳，將所述述鍵存入其中一個分桶內。

5.根據權利要求2所述的方法，其特征在于，在根據各個分桶的過期時間戳和鍵的過期時間戳，分別在所述n個分桶內存放對應的鍵之后，還包括：

針對第n個分桶，判斷所述分桶內存放的鍵數量是否超過第二數量閾值，若是，則將所述分桶拆分為兩個分桶；其中一個分桶的過期時間戳為第n-1個分桶的過期時間戳加上單位時間段，另一個分桶的過期時間戳為正無窮；

其中，所述第二數量閾值大于第一數量閾值。

6.根據權利要求1所述的方法，其特征在于，定時刪除過期的分桶以及存放在所述分桶內的過期鍵，包括：

對每個分桶配置定時器，當達到定時器的定時時間戳時，刪除所述定時器對應的分桶以及所述分桶內的過期鍵；

其中，所述定時器的定時時間戳大于等于與其對應的分桶的過期時間戳。

7.根據權利要求1所述的方法，其特征在于，定期刪除過期的分桶以及存放在所述分桶內的過期鍵，包括：

每隔一段時間，查找到過期時間戳小于等于當前時間戳的分桶，從所述分桶內取出指定數量的過期鍵并將其刪除，或者將所述分桶以及存放在所述分桶內的過期鍵刪除。

8.根據權利要求1所述的方法，其特征在于，定時或者定期刪除過期的分桶以及存放在所述分桶內的過期鍵之后，還包括：

判斷當前剩余的分桶的數量是否小于第三數量閾值，若是，則對最后一個分桶進行拆分，以使分桶的數量大于等于第三數量閾值。