CMU.Distributed-System.Lab1

发表于   |   分类于

分布式系统学习笔记

Lab1.Distributed Password Cracker

实验内容:

概述
实现一个基于互联网环境的分布式”密码”暴力破解应用,”密码”由不可逆的Hash函数生成

挑战

  1. 容错:互联网环境不可靠性,丢包,节点失效,网络不可用是常态.
  2. 负载均衡:各个节点的运算性能不一,要为每个节点分配”合适”的运算量

要求

  1. 应用结构包括三部分:请求客户端,服务器,运算客户端
    a. 请求客户端:负责向服务器发送要破解的密码.
    b. 服务器:负责切分运算任务,向运算客户端分配合适的运算任务,向请求客户端返回破解结果
    c. 运算客户端:负责接收运算任务,向服务器反馈运算结果
  2. 底层通信基于UDP,运算客户端和服务器,运算客户端之间可以互相通信
  3. 服务器要求容错,将失效的运算客户端未完成的任务分配给其他运算客户端
  4. 实现基于Golang

服务器描述

  1. 识别不同的客户端
  2. 跟踪每台客户端的进度
  3. 处理超时
  4. 负载均衡:为每台运算客户端分配合适的运算任务.为每个运算请求分配平衡的运算客户端,直到所有已提交的运算请求平均分摊在所有的运算客户端上
  5. 实现server的可执行文件,命令格式: ./server 
    1
    ./server 2222

客户端

运算客户端应用

  1. 基于多线程的工作方式.一个线程执行运算任务,一个线程用于和服务器交互
  2. 独立,通过定义好的协议和交互可以获取所有所需的”数据”
  3. 实现client的可执行文件,命令格式: ./worker_client 
    1
    ./worker_client unix32.andrew.cum.edu 2222

请求客户端应用

  1. 向服务器发送”解密”请求
  2. 定时向服务器发送心跳数据,直到拿到请求结果
  3. 命令格式: ./request_client 
    1
    ./request_client unix32.andrew.cmu.edu 2222 aaHLWHfiLg

使用crypt()

使用手册: man 3 crypt , 调用方式如下:

1
char *crypt(const char *key, const char *salt)

salt用于混淆密文,简单起见,实验使用"aa"作为加盐数据

协议

+——-+——-+——+——+
|MAGIC |
+——-+——-+——+——+
|Version|Commond|Client ID |
+——-+——-+——+——+
|Other Info (any length) |
+——-+——-+——+——+
|Other Info (continued) |
+——-+——-+——+——+

  • MAGIC 魔数,用于标识数据包属于本应用.我们使用15440
  • Version 使用 1

  • Commond

    1. REQUEST_TO_JOIN 运算客户端请求加入

    2. JOB 服务器向运算客户端分配任务,本次通信携带数据域“XXXXX XXXXX HHHHH”,其中XXXXX是数值,他们表示运算客户端要运算检测的范围.HHHHH表示Hash值
      例如:JOB AAAAA ABAAA aas4dfBX3

    3. ACK_JOB 运算客户端收到JOB分配的运算任务,向服务器发送的响应.数据域“XXXXX XXXXX HHHHH”,含义同上.同时还用于服务器响应请求客户端发起的任务请求,此时数据域不带有信息.

    4. PING 请求客户端用于向服务器发送心跳,同时也用于服务器向客户端发送心跳

    5. DONE_NOT_FOUND 运算客户端完成运算任务但是没有破解出密码时向服务器发送,携带数据域“XXXXX XXXXX”.同时用于服务器向请求客户端发送任务失败的信息,携带数据域HHHHH

    6. DONE_FOUND 当运算客户端完成运算任务并找到明文时向服务器发送,同时也用于服务器向请求客户端发送任务成功的信息.格式是:DONE_FOUND "PPPP HHHHH",“PPPP”是找到的明文

    7. NOT_DONE 运算客户端收到服务器的心跳,但还没有完成任务,向服务器回复此信息

    8. SHUTDOWN 服务器关闭时向所有运算服务器发送此信息

    9. HASH 请求客户端向服务器发起破解请求时发送此信息

  • Client_ID

    1. 运算客户端:当运算客户端首次加入系统时向服务器发送Commond:REQUEST_TO_JOIN请求,服务器随机生成一个ID分配给运算客户端.当客户端发送REQUEST_TO_JOIN请求时,ID字段设置0,当服务器回复请求,并在回复中携带分配的任务时,设置ID字段,从这时候起,运算客户端使用这个ID于服务器进行交互.

    2. 请求客户端:当请求客户端第一次向服务器发送Commond:Hash请求时,ID字段设置为0,服务器发送Commond:ACK_JOB的响应,随机生成一个ID写入协议并分配给请求客户端.

实验以服务器为中心,假定服务器不会失效

错误

  1. 分配运算任务时,如果服务器没有收到运算客户端的响应,服务器会继续尝试向该运算客户端分配本任务,直到3次都没有收到回复,则向下一个运算服务器分配本任务,并清除(discard)没有响应的运算客户端的信息.

  2. 当运算客户端完成运算任务,向服务器发送DONE_NOT_FOUND超时,服务器不会察觉,但是服务器会一直向运算客户端发送PING,运算客户端收到PING时,会向服务器回复刚刚完成的运算任务的DONE信息.当运算客户端在处理运算任务时收到PING,向服务器响应NOT_DONE.如果服务器收到NOT_DONE,会重置向该运算客户端发送的PING数量.如果PING超时,尝试3次,还是超时的话,将这个任务交给另外的运算客户端,并清除这个运算客户端的信息

  3. 请求客户端每隔5分钟向服务器发送PING维持心跳,服务器负责监听这些PING,如果15分钟还没有收到请求客户端的PING,则认为该请求客户端失效,移除对应的运算任务.

  4. 所有信息的超时时间设置为3s.服务器分配任务后,在3s中之内等待ACK_JOB的回复,3s内没有收到回复则认为发生超时,并重发.收到ACK_JOB后等待3s再发送PING.

分步实现

Part 1: 本地密码破解

尝试顺序如下:
A - Z a - z 0 - 9
如果范围是 AAAAA ABAAA,则应该测试如下字符串:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
AAAAA
AAAAB
...
AAAAZ
AAAAa
AAAAb
...
AAAAz
AAAA0
AAAA1
...
AAAA9
AAABA
...
ABAAA

Part 2: 实现协议

Part 3: 附加要求

运算客户端只在标准输出中输出运算的正确结果,不输出debug信息.服务器可以收到关机信号(SIGTERM),收到关机信号后向所有运算客户端发送SHUTDOWN.本实验使用的密码始终是5个字符