C#中通過LRU實(shí)現(xiàn)通用高效的超時連接探測

2019-10-29 19:41:24

字體：大中小

供稿：網(wǎng)友

編寫網(wǎng)絡(luò)通訊都要面對一個問題，就是要把很久不存活的死連接清除，如果不這樣做那死連接最終會占用大量內(nèi)存影響服務(wù)運(yùn)作！在實(shí)現(xiàn)過程中一般都會使用ping,pong原理，通過ping,pong來更新連接的時效性，最后通過掃描連接列表來清除掉。雖然這種做法比較簡單，但很難抽取出通用性的封裝，掃描整個列表復(fù)雜度也比較高。以下講解如何通過LRU算法實(shí)現(xiàn)一個通用高效的探測超時連接功能類。

什么是LRU

在這里還是要大概介紹一下LRU，LRU算法的設(shè)計原則是：如果一個數(shù)據(jù)在最近一段時間沒有被訪問到，那么在將來它被訪問的可能性也很小.也就是說，當(dāng)限定的空間已存滿數(shù)據(jù)時，應(yīng)當(dāng)把最久沒有被訪問到的數(shù)據(jù)淘汰.當(dāng)然在這里并不需要使用到自動淘汰機(jī)制，只需要把未位到達(dá)超時的連接清除即可。

在C#中如何實(shí)現(xiàn)LRU

C#并不存在這樣的數(shù)據(jù)結(jié)構(gòu)，不過有一個結(jié)構(gòu)很適合實(shí)現(xiàn)LRU，這個結(jié)構(gòu)就是LinkedList雙向鏈表，通過以下結(jié)構(gòu)圖就容易理解通過LinkedList實(shí)現(xiàn)LRU

C#,LRU,超時,連接

通過LinkedList的功能我們可以把活越項先移出來，然后再把項移到頭部。在這里需要注意LinkedList的Remove方法，它有兩個重載版本，兩個版本的復(fù)雜度不一樣。一個是O(n)一個是O(1)所以使用上一定要注意，否則在數(shù)據(jù)多的情況下效率差別巨大(這些細(xì)節(jié)都可以通過源代碼來查看)！

代碼實(shí)現(xiàn)

前面已經(jīng)大概講述的原理，接下來要做的就是代碼實(shí)現(xiàn)了。第一步需要制訂一個基礎(chǔ)可控測對象規(guī)則接口，這樣就可以讓現(xiàn)有的已經(jīng)實(shí)現(xiàn)的功能實(shí)現(xiàn)它并可得到相關(guān)功能的支持。

public interface IDetector  {    double ActiveTime    { get; set; }    LinkedListNode<IDetector> DetectorNode    {      get;      set;    }  }

接口定義了兩個屬性，一個是最近活越時間，另一個就是LinkedListNode<IDetector>這個屬性比交關(guān)鍵，通過LinkedListNode<IDetector>可以讓LinkedList在Remove時復(fù)雜度為O(1).接下來就要針對基于LRU算法處理超時制定一個應(yīng)用規(guī)則

 public interface ILRUDetector  {    void Update(IDetector item);    void Detection(int timeout);    double GetTime();    Action<IList<IDetector>> Timeout { get; set; }  }

規(guī)則也是比較簡單，Update用于更新跟蹤對象，一般在處理接受ping或pong包后進(jìn)行調(diào)用；Detection方法是探測超出指定時間的對象，時間當(dāng)位是毫秒，如果存在有超時的對象則觸發(fā)Timeout事件；GetTime是獲取探測器已經(jīng)運(yùn)行的時間單位毫秒！規(guī)則定好了那接著要做的事實(shí)就是要實(shí)現(xiàn)它:

 class LRUDetector : ILRUDetector, IDisposable  {    public LRUDetector()    {      mTimeWatch = new System.Diagnostics.Stopwatch();      mTimeWatch.Restart();    }    private Buffers.XSpinLock xSpinLock = new Buffers.XSpinLock();    private System.Diagnostics.Stopwatch mTimeWatch;    private LinkedList<IDetector> mItems = new LinkedList<IDetector>();    public Action<IList<IDetector>> Timeout    {      get; set;    }    public void Detection(int timeout)    {      double time = GetTime();      List<IDetector> result = new List<IDetector>();      using (xSpinLock.Enter())      {        LinkedListNode<IDetector> last = mItems.Last;        while (last != null && (time - last.Value.ActiveTime) > timeout)        {          mItems.Remove(last);          result.Add(last.Value);          last.Value.DetectorNode = null;          last = mItems.Last;        }      }      if (Timeout != null && result.Count > 0)        Timeout(result);    }    public void Update(IDetector item)    {      using (xSpinLock.Enter())      {        if (item.DetectorNode == null)          item.DetectorNode = new LinkedListNode<IDetector>(item);        item.ActiveTime = GetTime();        if (item.DetectorNode.List == mItems)          mItems.Remove(item.DetectorNode);        mItems.AddFirst(item);      }    }    public void Dispose()    {      mItems.Clear();    }    public double GetTime()    {      return mTimeWatch.Elapsed.TotalMilliseconds;    }  }

代碼并不復(fù)雜，相信不用過多解釋也能看懂相關(guān)操作原理。

測試

既然功能已經(jīng)實(shí)現(xiàn)，接下來就要對代碼進(jìn)行測試看運(yùn)行效果。測試代碼比較簡單首先開啟一個Timer定時執(zhí)行Detection,另外開一個線程去調(diào)用Update方法

class Program  {    public class TestDetector : IDetector    {      public double ActiveTime { get; set; }      public string Name { get; set; }      public LinkedListNode<IDetector> DetectorNode { get; set; }    }    static void Main(string[] args)    {      LRUDetector lRUDetector = new LRUDetector();      lRUDetector.Timeout = (items) =>      {        foreach (TestDetector item in items)          Console.WriteLine($"{(item.Name)} timeout {lRUDetector.GetTime() - item.ActiveTime}ms");      };      System.Threading.Timer timer = null;      timer = new System.Threading.Timer(o =>      {        timer.Change(-1, -1);        lRUDetector.Detection(5000);        timer.Change(5000, 5000);      }, null, 5000, 5000);      System.Threading.ThreadPool.QueueUserWorkItem(o =>      {        int i = 0;        while (true)        {          System.Threading.Thread.Sleep(500);          i++;          TestDetector testDetector = new TestDetector();          testDetector.Name = "my name is " + i;          lRUDetector.Update(testDetector);        }      });      Console.Read();    }  }

運(yùn)行效果:

C#,LRU,超時,連接