分布式哈希表常用在P2P网络中,如常见的BitTorrent。而Kademlia算法是要解决在网络中的寻找节点问题。

分布式哈希表(Distributed Hash Table)

在介绍Kademlia之前有必要熟悉一下DHT。

分布式哈希表就是将文件的哈希表存储在多个节点中,每个节点存储一部分文件的同时维护一个路由表,即每个节点包含:

  • Hash key(文件哈希值)
  • Hash Value(文件的一部分)
  • 路由表(在kademlia算法中称为k-bucket)

这些节点相互连接组成网络:

具体到P2P的文件共享中,假如要分享1G的电影,可以将1G的文件分割为128KB的小块,并生成小块的哈希值。

分布式哈希表实际上是P2P共享发展史上的第三种技术路线,前两代都存在一定的问题,简单介绍一下:

  1. 第一代 Tracker服务器
    • 这种模式下,文件块是分发到各个节点上的,但是每个节点在获取其他节点的位置时需要连接中央服务器。
    • 这种情况下中央服务器就成为了单点故障,一旦中央服务器出现故障或者被不可抗力ban掉后整个网络就无法运行
  2. 第二代
    • 在看到第一代的不足后,第二代P2P在查找节点时会询问与自身相连的所有节点,如果周边节点不知道目标节点的位置,又回广播一遍查询信息,直到找到目标节点。
    • 显然这种情况很容易催生广播风暴,严重占用网络带宽。即使通过设定TTL、限制查询递归次数也无法解决这个问题。

Kademlia算法

首先声明算法的三个参数:

  1. keyspace
    • 节点ID的位数,默认是160位
    • 决定每个节点的路由表(k-bucket)有几层
  2. k *重要*
    • 路由表里的每层存储k个信息
    • 每次查询时返回k个信息
    • 存储文件时,将文件存储到k个节点
    • 默认值为8
  3. α
    • 向其他节点查询目标节点时,每次向α个节点发送请求

Continue reading “Kademlia算法与分布式哈希表(DHT)”

环境

  • .NET SDK 2.2

参考

步骤

  1. 在项目内使用NuGet添加AspNetCoreRateLimit包
    • 注意.NET Core版本必须为2.2及以上,2.1版本安装会报错
  2. 编辑Startup.cs,DI组件,并启用中间件
    //using ...
    using AspNetCoreRateLimit;
    
    public void ConfigureServices(IServiceCollection services) {
        // ...
        services.AddOptions();
        services.AddMemoryCache();
    
        services.Configure<IpRateLimitOptions>(Configuration.GetSection("IpRateLimiting"));
        services.Configure<IpRateLimitPolicies>(Configuration.GetSection("IpRateLimitPolicies"));
    
        services.AddSingleton<IIpPolicyStore, MemoryCacheIpPolicyStore>();
        services.AddSingleton<IRateLimitCounterStore, MemoryCacheRateLimitCounterStore>();
    
        services.AddSingleton<IHttpContextAccessor, HttpContextAccessor>();
        services.AddSingleton<IRateLimitConfiguration, RateLimitConfiguration>();
    }
    
    public void Configure(IApplicationBuilder app, IHostingEnvironment env) {
        // ...   
        app.UseIpRateLimiting(); //注意在UseMvc()前注册
    
        app.UseMvc();
    }
  3. 编辑appsettings.json,设置具体的IP限制
    {
        ...
        "IpRateLimiting": {
            "EnableEndpointRateLimiting": true, //此字段设定为false则全局有效,会限制所有*的规则。例如:如果频率限制到每秒5次,则会纪录向任何端点的任何HTTP请求
                                                //这里设置为true可以对每个端点分别设置请求频率
            "StackBlockedRequests": false,
            "RealIpHeader": "X-Real-IP",
            "ClientIdHeader": "X-ClientId",
            "HttpStatusCode": 429,
            "GeneralRules": [
                { //设置hello路径的请求频率为每30秒3次请求,"*:"代表任何HTTP VERB,"/*"代表其后的参数
                    "Endpoint": "*:/hello/*",
                    "Period": "30s",
                    "Limit": 3
                }
            ]
        }
    }
    • 可以配置更多功能,例如白名单,更改计数方式,自定义返回内容等等,详细信息可以查看GIthub WIki
  4. 配置Action的路由
    namespace IP_restrict_test.Controllers {
        public class HomeController: Controller {
            //...
    
            [Route("/hello/")]
            public IActionResult Index() {
                return View();
            }
            
            //...
        }
    }
  5. 生成并运行,测试频率限制功能
    • 可以看到,连续打开或者刷新页面3次后,第4次打开页面会提示访问频率过快。