####Memcache与Redis的区别都有哪些？

1)、存储方式

Memecache把数据全部存在内存之中，断电后会挂掉，数据不能超过内存大小。

Redis有部份存在硬盘上，这样能保证数据的持久性。

2)、数据支持类型

Memcache对数据类型支持相对简单。

Redis有复杂的数据类型。

3)、使用底层模型不同

它们之间底层实现方式 以及与客户端之间通信的应用协议不一样。

Redis直接自己构建了VM 机制 ，因为一般的系统调用系统函数的话，会浪费一定的时间去移动和请求。

4），value大小

redis最大可以达到1GB，而memcache只有1MB

####redis常见性能问题和解决方案：

(1) Master最好不要做任何持久化工作，如RDB内存快照和AOF日志文件

(2) 如果数据比较重要，某个Slave开启AOF备份数据，策略设置为每秒同步一次

(3) 为了主从复制的速度和连接的稳定性，Master和Slave最好在同一个局域网内

(4) 尽量避免在压力很大的主库上增加从库

(5) 主从复制不要用图状结构，用单向链表结构更为稳定，即：Master <- Slave1 <- Slave2 <- Slave

####redis 最适合的场景

Redis最适合所有数据in-momory的场景，虽然Redis也提供持久化功能，但实际更多的是一个disk-backed的功能。

（1）、会话缓存（Session Cache）

最常用的一种使用Redis的情景是会话缓存（session cache）。用Redis缓存会话比其他存储（如Memcached）的优势在于：Redis提供持久化。当维护一个不是严格要求一致性的缓存时，如果用户的购物车信息全部丢失，大部分人都会不高兴的，现在，他们还会这样吗？

幸运的是，随着 Redis 这些年的改进，很容易找到怎么恰当的使用Redis来缓存会话的文档。甚至广为人知的商业平台Magento也提供Redis的插件。

（2）、全页缓存（FPC）

除基本的会话token之外，Redis还提供很简便的FPC平台。回到一致性问题，即使重启了Redis实例，因为有磁盘的持久化，用户也不会看到页面加载速度的下降，这是一个极大改进，类似PHP本地FPC。

再次以Magento为例，Magento提供一个插件来使用Redis作为全页缓存后端。

此外，对WordPress的用户来说，Pantheon有一个非常好的插件 wp-redis，这个插件能帮助你以最快速度加载你曾浏览过的页面。

（3）、队列

Reids在内存存储引擎领域的一大优点是提供 list 和 set 操作，这使得Redis能作为一个很好的消息队列平台来使用。Redis作为队列使用的操作，就类似于本地程序语言（如Python）对 list 的 push/pop 操作。

如果你快速的在Google中搜索“Redis queues”，你马上就能找到大量的开源项目，这些项目的目的就是利用Redis创建非常好的后端工具，以满足各种队列需求。例如，Celery有一个后台就是使用Redis作为broker，你可以从这里去查看。

（4），排行榜/计数器

Redis在内存中对数字进行递增或递减的操作实现的非常好。集合（Set）和有序集合（Sorted Set）也使得我们在执行这些操作的时候变的非常简单，Redis只是正好提供了这两种数据结构。所以，我们要从排序集合中获取到排名最靠前的10个用户–我们称之为“user_scores”，我们只需要像下面一样执行即可：

当然，这是假定你是根据你用户的分数做递增的排序。如果你想返回用户及用户的分数，你需要这样执行：

ZRANGE user_scores 0 10 WITHSCORES

Agora Games就是一个很好的例子，用Ruby实现的，它的排行榜就是使用Redis来存储数据的，你可以在这里看到。

（5）、发布/订阅

最后（但肯定不是最不重要的）是Redis的发布/订阅功能。发布/订阅的使用场景确实非常多。我已看见人们在社交网络连接中使用，还可作为基于发布/订阅的脚本触发器，甚至用Redis的发布/订阅功能来建立聊天系统！（不，这是真的，你可以去核实）。

####集群间session共享问题

session共享有多重解决办法，常用的有四种：

客户端Cookie保存，

服务器间session同步、

使用集群管理Session、

把session持久化到数据库

集群中session共享解决方案

1. 客户端存储方案

2. 集中式session共享方案

3. session复制方案

4. 把session持久化到数据库

###索引的作用？和它的优点缺点是什么？

数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用B树及其变种B+树。

在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

为表设置索引要付出代价的：一是增加了数据库的存储空间，二是在插入和修改数据时要花费较多的时间(因为索引也要随之变动)。

####创建索引可以大大提高系统的性能（优点）：

第一，通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。

第二，可以大大加快数据的检索速度，这也是创建索引的最主要的原因。

第三，可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。

第四，在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。

第五，通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

####也许会有人要问：增加索引有如此多的优点，为什么不对表中的每一个列创建一个索引呢？因为，增加索引也有许多不利的方面：

第一，创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。

第二，索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。

第三，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

索引是建立在数据库表中的某些列的上面。在创建索引的时候，应该考虑在哪些列上可以创建索引，在哪些列上不能创建索引。

####一般来说，应该在这些列上创建索引：

（1）在经常需要搜索的列上，可以加快搜索的速度；

（2）在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；

（3）在经常用在连接的列上，这些列主要是一些外键，可以加快连接的速度；

（4）在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的；

（5）在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间；

（6）在经常使用在WHERE子句中的列上面创建索引，加快条件的判断速度。

####同样，对于有些列不应该创建索引：

第一，对于那些在查询中很少使用或者参考的列不应该创建索引。这是因为，既然这些列很少使用到，因此有索引或者无索引，并不能提高查询速度。相反，由于增加了索引，反而降低了系统的维护速度和增大了空间需求。

第二，对于那些只有很少数据值的列也不应该增加索引。这是因为，由于这些列的取值很少，例如人事表的性别列，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度。

第三，对于那些定义为text, image和bit数据类型的列不应该增加索引。这是因为，这些列的数据量要么相当大，要么取值很少。

第四，当修改性能远远大于检索性能时，不应该创建索引。这是因为，修改性能和检索性能是互相矛盾的。当增加索引时，会提高检索性能，但是会降低修改性能。当减少索引时，会提高修改性能，降低检索性能。因此，当修改性能远远大于检索性能时，不应该创建索引。

###列举几种表连接方式,有什么区别？

内连接：只有两个元素表相匹配的才能在结果集中显示。

外连接：

左外连接:左边为驱动表，驱动表的数据全部显示，匹配表的不匹配的不会显示。

右外连接:右边为驱动表，驱动表的数据全部显示，匹配表的不匹配的不会显示。

全外连接：连接的表中不匹配的数据全部会显示出来。

交叉连接： 笛卡尔效应，显示的结果是链接表数的乘积

###主键和外键的区别？

主键在本表中是唯一的、不可唯空的，外键可以重复可以唯空；外键和另一张表的主键关联，不能创建对应表中不存在的外键。

###在数据库中查询语句速度很慢，如何优化？

1. 建索引

2. 减少表之间的关联

3. 优化sql，尽量让sql很快定位数据，不要让sql做全表查询，应该走索引,把数据 量大的表排在前面

4. 简化查询字段，没用的字段不要，已经对返回结果的控制，尽量返回少量数据

5. 尽量用PreparedStatement来查询，不要用Statement

###数据库三范式是什么?

第一范式：列不可再分

第二范式：行可以唯一区分，主键约束

第三范式：表的非主属性不能依赖与其他表的非主属性 外键约束

三大范式是一级一级依赖的，第二范式建立在第一范式上，第三范式建立第一第二范式上

###union和union all有什么不同?

UNION在进行表链接后会筛选掉重复的记录，所以在表链接后会对所产生的结果集进行排序运算，删除重复的记录再返回结果。

实际大部分应用中是不会产生重复的记录，最常见的是过程表与历史表UNION。 UNION ALL只是简单的将两个结果合并后就返回。这样，如果返回的两个结果集中有重复的数据，那么返回的结果集就会包含重复的数据了。

从效率上说，UNION ALL 要比UNION快很多，所以，如果可以确认合并的两个结果集中不包含重复的数据的话，那么就使用UNION ALL。

###truncate与 delete区别

TRUNCATE TABLE 在功能上与不带 WHERE 子句的 DELETE 语句相同：二者均删除表中的全部行。但 TRUNCATE TABLE 比 DELETE 速度快，且使用的系统和事务日志资源少。 DELETE 语句每次删除一行，并在事务日志中为所删除的每行记录一项。

TRUNCATE TABLE 通过释放存储表数据所用的数据页来删除数据，并且只在事务日志中记录页的释放。 TRUNCATE,DELETE,DROP 放在一起比较：

TRUNCATE TABLE ：删除内容、释放空间但不删除定义。

DELETE TABLE: 删除内容不删除定义，不释放空间。

DROP TABLE ：删除内容和定义，释放空间。

####innodb引擎的4大特性

1. 插入缓冲（insert buffer)

2. 二次写(double write)

3. 自适应哈希索引(ahi)

4. 预读(read ahead)

####什么情况下设置了索引但无法使用

1. 以“%”开头的LIKE语句，模糊匹配

2. OR语句前后没有同时使用索引

3. 数据类型出现隐式转化（如varchar不加单引号的话可能会自动转换为int型）

####实践中如何优化MySQL

① SQL语句及索引的优化

② 数据库表结构的优化

③ 系统配置的优化

④ 硬件的优化

####简单描述mysql中，索引，主键，唯一索引，联合索引的区别，对数据库的性能有什么影响（从读写两方面）

索引是一种特殊的文件(InnoDB数据表上的索引是表空间的一个组成部分)，它们包含着对数据表里所有记录的引用指针。
普通索引(由关键字KEY或INDEX定义的索引)的唯一任务是加快对数据的访问速度。

普通索引允许被索引的数据列包含重复的值。如果能确定某个数据列将只包含彼此各不相同的值，在为这个数据列创建索引的时候就应该用关键字UNIQUE把它定义为一个唯一索引。也就是说，唯一索引可以保证数据记录的唯一性。

主键，是一种特殊的唯一索引，在一张表中只能定义一个主键索引，主键用于唯一标识一条记录，使用关键字PRIMARY KEY 来创建。
索引可以覆盖多个数据列，如像INDEX(columnA, columnB)索引，这就是联合索引。

索引可以极大的提高数据的查询速度，但是会降低插入、删除、更新表的速度，因为在执行这些写操作时，还要操作索引文件。

###hadoop-mapreduce框架详解

https://www.cnblogs.com/sharpxiajun/p/3151395.html

###Hbase学习笔记

https://www.cnblogs.com/sharpxiajun/p/5107470.html

###分段交换链表
Swap Nodes in Pairs

Given 1->2->3->4, you should return the list as 2->1->4->3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        
        if(head==None):
            return head
        
        trav1 = head
        trav2 = head.next
        
        if(trav2==None):
            return head
        
        head = head.next
        
        while(True):
            trav1.next = trav1.next.next
            trav2.next = trav1
            
            if trav1.next == None or trav2.next==None:
                break            
            
            trav2 = trav1.next
            if trav2.next == None:
                break            
           
            trav1.next = trav2.next
            trav1 = trav2
            trav2 = trav2.next
            
        return head

###往右移动k个链表

1
2
3
4
5
6
7

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

计算链表长度，用k%len，得到实际移动长度，然后用双箭头，标记新的头和新的结尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        
        if head == None:
            return None
        
        cur = head
        length = 1
        pos = 0
        table = {}
        # count how many steps we need
        while cur and cur.next:
            cur = cur.next
            length += 1
        steps = k % length
        
        n = 0
        lastk = head
        while n < steps:
            lastk = lastk.next
            n+=1
            
        last = head
        while lastk.next != None:
            lastk = lastk.next
            last = last.next
            
        lastk.next = head
        newhead = last.next
        last.next = None
        return newhead

###链表转换二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        tree = []
        while head:
            tree.append(head.val)
            head = head.next
        root = self.constructTree(tree)        
        return root
    
    def constructTree(self, tree):
        if not tree:
            return
        mid = len(tree)/2
        root = TreeNode(tree[mid])
        root.left = self.constructTree(tree[:mid])
        root.right = self.constructTree(tree[mid+1:])
        return root

###深拷贝包含随机指针的链表

第一次遍历使用map存储新的节点，第二次遍历添加随机指针和正常指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        map = {}
        iterNode = head
        while iterNode:
            map[iterNode] = RandomListNode(iterNode.label)
            iterNode = iterNode.next
        
        iterNode = head
        while iterNode:
            map[iterNode].next = map[iterNode.next] if iterNode.next else None
            map[iterNode].random = map[iterNode.random] if iterNode.random else None
            iterNode = iterNode.next
        return map[head] if head else None

###回文字符串

从中间去循环向周围扩散，有两种情况，奇数和偶数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s) <= 0:
            return 0
        mlength = 0
        slen = ''
        for i in range(0,len(s)):
            l = r = i
            temp = self.check(s,l,r)
            if len(temp) > len(slen):
                slen = temp

            l = i
            r = i + 1
            n = 0
            temp = self.check(s,l,r)
            if len(temp) > len(slen):
                slen = temp


        return slen

    def check(self,s,l,r):
        while(l>=0 and r < len(s) and s[l] == s[r]):
            l-=1
            r+=1
        return s[l+1:r]

###字符串正则匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution(object):
    def isMatch(self, text, pattern):
        memo = {}
        def dp(i, j):
            if (i, j) not in memo:
                if j == len(pattern):
                    ans = i == len(text)
                else:
                    first_match = i < len(text) and pattern[j] in {text[i], '.'}
                    if j+1 < len(pattern) and pattern[j+1] == '*':
                        ans = dp(i, j+2) or first_match and dp(i+1, j)
                    else:
                        ans = first_match and dp(i+1, j+1)

                memo[i, j] = ans
            return memo[i, j]

        return dp(0, 0)

###手机键盘数字转换字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

kvmaps = {'1': '*',
          '2': 'abc',
          '3': 'def',
          '4': 'ghi',
          '5': 'jkl',
          '6': 'mno',
          '7': 'pqrs',
          '8': 'tuv',
          '9': 'wxyz',
          '0': ' '
          }
class Solution(object):
    
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits == "":
            return []
        combinations = []
        if len(digits) == 1:
            for x in kvmaps[digits[0]]:
                combinations.append(x)
        else:
            for c in self.letterCombinations(digits[1:]):
                for x in kvmaps[digits[0]]:
                    combinations.append(x + c)
        return combinations

###数字转换成IP地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution(object):
    def helper(self, s, dotnum, ret, rets):
        if dotnum > 4 or (len(s) / 3 > 4-dotnum):
            return
        
        if len(s) == 0:
            if dotnum == 4:
                rets.append(ret)
            return

        for i in range(1, 4):
            tmp = s[:i]
            if (dotnum == 3 and i > len(s)) or (i > 1 and s[0] == '0') or (int(tmp) > 255):
                continue
                #如果超长了，如果包含0，如果数值大于255则跳过
            self.helper(s[i:], dotnum+1, ret+'.'+tmp if len(ret) > 0 else tmp, rets)
                
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        rets = []
        self.helper(s, 0, '', rets)
        return rets

###反转句子，词不反转

I am student->student am I

1
2
3
4
5
6
7

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        return " ".join(s.split()[::-1])

###最长公共子串

两个字符串的最长公共子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution(object):
    def minDistance(self, w1, w2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        if not w1: return len(w2)
        if not w2: return len(w1)
        m,n = len(w1), len(w2)
        dp = [[1]*n for _ in range(m)]
        for i in range(m):
            if w1[i] != w2[0]: dp[i][0] = 0
            else: break
        for j in range(n):
            if w1[0] != w2[j]: dp[0][j] = 0
            else: break

        for i in range(1,m):
            for j in range(1,n):
                if w1[i] == w2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        l = dp[-1][-1]
        return m - l + n - l

简答说一下hadoop的map-reduce编程模型

2、hadoop的TextInputFormat作用是什么，如何自定义实现

3、hadoop和spark的都是并行计算，那么他们有什么相同和区别

4、为什么要用flume导入hdfs，hdfs的构架是怎样的

5、map-reduce程序运行的时候会有什么比较常见的问题

6、简单说一下hadoop和spark的shuffle过程

简答说一下hadoop的map-reduce编程模型

首先map task会从本地文件系统读取数据，转换成key-value形式的键值对集合

使用的是hadoop内置的数据类型，比如longwritable、text等

将键值对集合输入mapper进行业务处理过程，将其转换成需要的key-value在输出

之后会进行一个partition分区操作，默认使用的是hashpartitioner，可以通过重写hashpartitioner的getpartition方法来自定义分区规则

之后会对key进行进行sort排序，grouping分组操作将相同key的value合并分组输出，在这里可以使用自定义的数据类型，重写WritableComparator的Comparator方法来自定义排序规则，重写RawComparator的compara方法来自定义分组规则

之后进行一个combiner归约操作，其实就是一个本地段的reduce预处理，以减小后面shufle和reducer的工作量

reduce task会通过网络将各个数据收集进行reduce处理，最后将数据保存或者显示，结束整个job

hadoop的TextInputFormat作用是什么，如何自定义实现

InputFormat会在map操作之前对数据进行两方面的预处理

1是getSplits，返回的是InputSplit数组，对数据进行split分片，每片交给map操作一次

2是getRecordReader，返回的是RecordReader对象，对每个split分片进行转换为key-value键值对格式传递给map

常用的InputFormat是TextInputFormat，使用的是LineRecordReader对每个分片进行键值对的转换，以行偏移量作为键，行内容作为值

自定义类继承InputFormat接口，重写createRecordReader和isSplitable方法
在createRecordReader中可以自定义分隔符

hadoop和spark的都是并行计算，那么他们有什么相同和区别

两者都是用mr模型来进行并行计算，hadoop的一个作业称为job，job里面分为map task和reduce task，每个task都是在自己的进程中运行的，当task结束时，进程也会结束

spark用户提交的任务成为application，一个application对应一个sparkcontext，app中存在多个job，每触发一次action操作就会产生一个job

这些job可以并行或串行执行，每个job中有多个stage，stage是shuffle过程中DAGSchaduler通过RDD之间的依赖关系划分job而来的，每个stage里面有多个task，组成taskset有TaskSchaduler分发到各个executor中执行，executor的生命周期是和app一样的，即使没有job运行也是存在的，所以task可以快速启动读取内存进行计算

hadoop的job只有map和reduce操作，表达能力比较欠缺而且在mr过程中会重复的读写hdfs，造成大量的io操作，多个job需要自己管理关系

spark的迭代计算都是在内存中进行的，API中提供了大量的RDD操作如join，groupby等，而且通过DAG图可以实现良好的容错

为什么要用flume导入hdfs，hdfs的构架是怎样的

flume可以实时的导入数据到hdfs中，当hdfs上的文件达到一个指定大小的时候会形成一个文件，或者超过指定时间的话也形成一个文件

文件都是存储在datanode上面的，namenode记录着datanode的元数据信息，而namenode的元数据信息是存在内存中的，所以当文件切片很小或者很多的时候会卡死

map-reduce程序运行的时候会有什么比较常见的问题

比如说作业中大部分都完成了，但是总有几个reduce一直在运行

这是因为这几个reduce中的处理的数据要远远大于其他的reduce，可能是因为对键值对任务划分的不均匀造成的数据倾斜

解决的方法可以在分区的时候重新定义分区规则对于value数据很多的key可以进行拆分、均匀打散等处理，或者是在map端的combiner中进行数据预处理的操作

Flume工作机制是什么？

核心概念是agent，里面包括source、chanel和sink三个组件。
source运行在日志收集节点进行日志采集，之后临时存储在chanel中，sink负责将chanel中的数据发送到目的地。

只有成功发送之后chanel中的数据才会被删除。

首先书写flume配置文件，定义agent、source、chanel和sink然后将其组装，执行flume-ng命令。

driver的功能是什么？

1）一个Spark作业运行时包括一个Driver进程，也是作业的主进程，具有main函数，并且有SparkContext的实例，是程序的人口点；

2）功能：负责向集群申请资源，向master注册信息，负责了作业的调度，负责作业的解析、生成Stage并调度Task到Executor上。包括DAGScheduler，TaskScheduler。

hadoop和spark的shuffle相同和差异？

从 high-level 的角度来看，两者并没有大的差别。 都是将 mapper（Spark 里是 ShuffleMapTask）的输出进行 partition，不同的 partition 送到不同的 reducer（Spark 里 reducer 可能是下一个 stage 里的 ShuffleMapTask，也可能是 ResultTask）。Reducer 以内存作缓冲区，边 shuffle 边 aggregate 数据，等到数据 aggregate 好以后进行 reduce() （Spark 里可能是后续的一系列操作）。

2）从 low-level 的角度来看，两者差别不小。 Hadoop MapReduce 是 sort-based，进入 combine() 和 reduce() 的 records 必须先 sort。这样的好处在于 combine/reduce() 可以处理大规模的数据，因为其输入数据可以通过外排得到（mapper 对每段数据先做排序，reducer 的 shuffle 对排好序的每段数据做归并）。目前的 Spark 默认选择的是 hash-based，通常使用 HashMap 来对 shuffle 来的数据进行 aggregate，不会对数据进行提前排序。如果用户需要经过排序的数据，那么需要自己调用类似 sortByKey() 的操作；如果你是Spark 1.1的用户，可以将spark.shuffle.manager设置为sort，则会对数据进行排序。在Spark 1.2中，sort将作为默认的Shuffle实现。

3）从实现角度来看，两者也有不少差别。 Hadoop MapReduce 将处理流程划分出明显的几个阶段：map(), spill, merge, shuffle, sort, reduce() 等。每个阶段各司其职，可以按照过程式的编程思想来逐一实现每个阶段的功能。在 Spark 中，没有这样功能明确的阶段，只有不同的 stage 和一系列的 transformation()，所以 spill, merge, aggregate 等操作需要蕴含在 transformation() 中。如果我们将 map 端划分数据、持久化数据的过程称为 shuffle write，而将 reducer 读入数据、aggregate 数据的过程称为 shuffle read。那么在 Spark 中，问题就变为怎么在 job 的逻辑或者物理执行图中加入 shuffle write 和 shuffle read 的处理逻辑？以及两个处理逻辑应该怎么高效实现？ Shuffle write由于不要求数据有序，shuffle write 的任务很简单：将数据 partition 好，并持久化。之所以要持久化，一方面是要减少内存存储空间压力，另一方面也是为了 fault-tolerance。

Spark中数据的位置是被谁管理的？

每个数据分片都对应具体物理位置，数据的位置是被blockManager，无论数据是在磁盘，内存还是tacyan，都是由blockManager管理

rdd有几种操作类型？

1）transformation，rdd由一种转为另一种rdd

2）action，

3）cronroller，crontroller是控制算子,cache,persist，对性能和效率的有很好的支持三种类型，不要回答只有2中操作

join操作优化经验？

join其实常见的就分为两类： map-side join 和 reduce-side join。当大表和小表join时，用map-side join能显著提高效率。将多份数据进行关联是数据处理过程中非常普遍的用法，不过在分布式计算系统中，这个问题往往会变的非常麻烦，因为框架提供的 join 操作一般会将所有数据根据 key 发送到所有的 reduce 分区中去，也就是 shuffle 的过程。造成大量的网络以及磁盘IO消耗，运行效率极其低下，这个过程一般被称为 reduce-side-join。如果其中有张表较小的话，我们则可以自己实现在 map 端实现数据关联，跳过大量数据进行 shuffle 的过程，运行时间得到大量缩短，根据不同数据可能会有几倍到数十倍的性能提升。

网络层次划分

1）物理层（Physical Layer）

　　该层为上层协议提供了一个传输数据的可靠的物理媒体。

2）数据链路层（Data Link Layer）

　　数据链路层在不可靠的物理介质上提供可靠的传输。该层的作用包括：物理地址寻址、数据的成帧、流量控制、数据的检错、重发等。

　　有关数据链路层的重要知识点：

　　1> 数据链路层为网络层提供可靠的数据传输；

　　2> 基本数据单位为帧；

　　3> 主要的协议：以太网协议；

　　4> 两个重要设备名称：网桥和交换机。

3）网络层（Network Layer）

　　网络层的目的是实现两个端系统之间的数据透明传送，具体功能包括寻址和路由选择、连接的建立、保持和终止等。

有关网络层的重点为：

　　1> 网络层负责对子网间的数据包进行路由选择。此外，网络层还可以实现拥塞控制、网际互连等功能；

　　2> 基本数据单位为IP数据报；

　　3> 包含的主要协议：

　　IP协议（Internet Protocol，因特网互联协议）;

　　ICMP协议（Internet Control Message Protocol，因特网控制报文协议）;

　　ARP协议（Address Resolution Protocol，地址解析协议）;

　　RARP协议（Reverse Address Resolution Protocol，逆地址解析协议）。

　　4> 重要的设备：路由器。

4）传输层（Transport Layer）

　　第一个端到端，即主机到主机的层次。传输层负责将上层数据分段并提供端到端的、可靠的或不可靠的传输。此外，传输层还要处理端到端的差错控制和流量控制问题。

　　有关网络层的重点：
　　
　　1> 传输层负责将上层数据分段并提供端到端的、可靠的或不可靠的传输以及端到端的差错控制和流量控制问题；
　　
　　2> 包含的主要协议：TCP协议（Transmission Control Protocol，传输控制协议）、UDP协议（User Datagram Protocol，用户数据报协议）；
　　
　　3> 重要设备：网关。
　　
5）会话层

　　会话层管理主机之间的会话进程，即负责建立、管理、终止进程之间的会话。会话层还利用在数据中插入校验点来实现数据的同步。

6）表示层

　　表示层对上层数据或信息进行变换以保证一个主机应用层信息可以被另一个主机的应用程序理解。表示层的数据转换包括数据的加密、压缩、格式转换等。

7）应用层

　为操作系统或网络应用程序提供访问网络服务的接口。

　包含的主要协议：FTP（文件传送协议）、Telnet（远程登录协议）、DNS（域名解析协议）、SMTP（邮件传送协议），POP3协议（邮局协议），HTTP协议（Hyper Text Transfer Protocol）。 　

###IP地址

　　各类地址

　　A类地址以0开头，第一个字节作为网络号，地址范围为：0.0.0.0~127.255.255.255；

　　B类地址以10开头，前两个字节作为网络号，地址范围是：128.0.0.0~191.255.255.255;

　　C类地址以110开头，前三个字节作为网络号，地址范围是：192.0.0.0~223.255.255.255。

　　D类地址以1110开头，地址范围是224.0.0.0~239.255.255.255，D类地址作为组播地址（一对多的通信）；

　　E类地址以1111开头，地址范围是240.0.0.0~255.255.255.255，E类地址为保留地址，供以后使用。

　　注：只有A,B,C有网络号和主机号之分，D类地址和E类地址没有划分网络号和主机号

　　A、B、C类私有地址

　　私有地址(private address)也叫专用地址，它们不会在全球使用，只具有本地意义。

　　A类私有地址：10.0.0.0/8，范围是：10.0.0.0~10.255.255.255

　　B类私有地址：172.16.0.0/12，范围是：172.16.0.0~172.31.255.255

　　C类私有地址：192.168.0.0/16，范围是：192.168.0.0~192.168.255.255 　　

###子网掩码及网络划分

子网掩码的计算：

　　对于无须再划分成子网的IP地址来说，其子网掩码非常简单，即按照其定义即可写出：如某B类IP地址为 10.12.3.0，无须再分割子网，则该IP地址的子网掩码255.255.0.0。如果它是一个C类地址，则其子网掩码为 255.255.255.0。其它类推，不再详述。下面我们关键要介绍的是一个IP地址，还需要将其高位主机位再作为划分出的子网网络号，剩下的是每个子网的主机号，这时该如何进行每个子网的掩码计算。

　　下面总结一下有关子网掩码和网络划分常见的面试考题：

　　1）利用子网数来计算

　　在求子网掩码之前必须先搞清楚要划分的子网数目，以及每个子网内的所需主机数目。

　　(1) 将子网数目转化为二进制来表示;

　　如欲将B类IP地址168.195.0.0划分成27个子网：27=11011；

　　(2) 取得该二进制的位数，为N；

　　该二进制为五位数，N = 5

　　(3) 取得该IP地址的类子网掩码，将其主机地址部分的的前N位置1即得出该IP地址划分子网的子网掩码。

　　将B类地址的子网掩码255.255.0.0的主机地址前5位置 1，得到 255.255.248.0

　　2）利用主机数来计算

　　如欲将B类IP地址168.195.0.0划分成若干子网，每个子网内有主机700台：

　　(1) 将主机数目转化为二进制来表示；

　　700=1010111100；

　　(2) 如果主机数小于或等于254（注意去掉保留的两个IP地址），则取得该主机的二进制位数，为N，这里肯定 N<8。如果大于254，则 n="">8，这就是说主机地址将占据不止8位；

　　该二进制为十位数，N=10；

　　(3) 使用255.255.255.255来将该类IP地址的主机地址位数全部置1，然后从后向前的将N位全部置为 0，即为子网掩码值。

　　将该B类地址的子网掩码255.255.0.0的主机地址全部置1，得到255.255.255.255，然后再从后向前将后 10位置0,即为：11111111.11111111.11111100.00000000，即255.255.252.0。这就是该欲划分成主机为700台的B类IP地址 168.195.0.0的子网掩码。

　　3）还有一种题型，要你根据每个网络的主机数量进行子网地址的规划和计算子网掩码。这也可按上述原则进行计算。

　　比如一个子网有10台主机，那么对于这个子网需要的IP地址是：

　　10＋1＋1＋1＝13

　　注意：加的第一个1是指这个网络连接时所需的网关地址，接着的两个1分别是指网络地址和广播地址。

　　因为13小于16（16等于2的4次方），所以主机位为4位。而256－16＝240，所以该子网掩码为255.255.255.240。

　　如果一个子网有14台主机，不少人常犯的错误是：依然分配具有16个地址空间的子网，而忘记了给网关分配地址。这样就错误了，因为14＋1＋1＋1＝17，17大于16，所以我们只能分配具有32个地址（32等于2的5次方）空间的子网。这时子网掩码为：255.255.255.224。

#linux命令

###查看端口号占用

lsof -i:端口号

netstat -tunlp | grep 端口号

###系统信息

arch 显示机器的处理器架构(1)

uname -m 显示机器的处理器架构(2)

uname -r 显示正在使用的内核版本

cat /proc/cpuinfo 显示CPU info的信息
系统管理命令

stat 显示指定文件的详细信息，比ls更详细

who 显示在线登陆用户

whoami 显示当前操作用户

hostname 显示主机名

uname 显示系统信息

top 动态显示当前耗费资源最多进程信息

ps 显示瞬间进程状态 ps -aux

du 查看目录大小 du -h /home带有单位显示目录信息

df 查看磁盘大小 df -h 带有单位显示磁盘信息

ifconfig 查看网络情况

ping 测试网络连通

netstat 显示网络状态信息

man 命令不会用了，找男人 如：man ls

clear 清屏

kill 杀死进程，可以先用ps 或 top命令查看进程的id，然后再用kill命令杀死进程。

###目录结构

/bin：大部分的系统命令

/boot：启动相关目录

/dev：设备文件目录，linux下一切设备皆文件

/etc：配置文件目录

/home：普通用户的家目录，一个用户对应一个文件夹

/lib：库文件

/lib64：64位库文件

/lost+found：系统异常时临时保存数据，用于恢复等操作

/media：媒体目录

/mnt：挂载目录，通用挂载点

/opt：安装系统非必须软件目录

/proc：虚拟文件系统，会映射硬件信息

/root：root用户的家目录

/sbin：超级用户才能执行的命令目录

/selinux：linux一套安全机制，非常复杂，通常不用

/srv：存放本机或本机服务器的数据或服务

/sys：类似于/proc，也是虚拟文件系统，可以映射系统信息

/tmp：临时文件，可能随时销毁

/usr：存放用户安装的应用程序

/var：系统产生的不可自动销毁的文件，如：日志、缓存等

###Vim编辑器

• 常用操作：

vim filename +n 打开文件，定位到第n行

vim filename + 打开文件，定位到末尾

gg 定位到首行

G 定位到尾行

ngg 定位到第n行

^ 定位到行首

$ 定位到行尾

yy 复制光标所在行

p 粘贴

nyy 复制光标开始的n行

dd 删除光标所在行

ndd 删除光标开始的n行

u 撤销操作

ctrl + r 反撤销操作

插入模式：就是可以编辑文件内容的模式，在正常模式下输入以下字符进入：

i：在光标处插入

I：在行首插入

a：在光标下一个字符处插入

A：在行尾插入

o：下光标下一行插入空行

O：下光标上一行插入空行

s：删除光标所在字符并插入

S：删除光标所在行并插入

编辑模式：是对整个文件进行的操作，如：保存，退出

在正常模式下输入’:’即可进入编辑模式

:w 保存

:q 退出

:wq 保存退出，等价于 shift + zz

:x 保存退出，等价于:wq

:q! 强制退出

:set nu 显示行号

:set nonu 隐藏行号

:行号 定位到指定行号

/内容 查找指定内容，n下翻，N上翻

:%s/原内容/新内容 使用新内容替换原内容，全部替换

:m,ns/原内容/新内容 使用新内容替换原内容，替换m到n行

友情提醒：若非正常关闭vim，则会生成临时文件(隐藏的)，需要删除

###文件及文件夹

touch：创建普通文件

rm：删除文件，-f表示强制删除，-r表示递归删除

cp：拷贝文件，若目标目录写上文件名可以顺便把名字改了，-r可以操作目录

mv：移动文件，若目标目录写上文件名可以顺便把名字改了

mkdir：创建文件夹，-p创建中间目录

rmdir：删除文件夹，只能删除空目录

###查看文件

cat：从上到下查看文件，全部内容

tac：从下到上查看文件，全部内容

head：查看开头的指定行内容，默认10行，head -3 1.txt

tail：查看末尾的指定行内容，默认10行，tail -5 1.txt

more：逐渐查看文件，回车下翻一行，空格下翻一屏，看到结尾会自动结束，q退出查看

less：逐渐查看文件，回车下翻一行，空格下翻一屏，看到结尾不会自动结束，可以上下翻

nl：功能同cat，会多显示行号

wc：统计文件信息，显示结果：行数 | 单词数 | 字节数

###用户及用户组

whoami：查看当前用户

useradd：创建用户

passwd：设置指定用户的密码，若不指定设置当前用户的密码

userdel：删除用户，-rf删除用户相关目录，否则需要手动删除

groupadd：创建用户组

groupdel：删除用户组

gpasswd：将用户添加到某个组，从某个组删除
gpasswd -a test hello 将test用户添加到hello组
gpasswd -d test hello 将test用户从hello组中删除

chgrp：改变文件所属组，chgrp hello 1.txt

chown：改变文件拥有者[及组]，chown root[:root] 1.txt

chsh：修改用户的shell解释器，chsh test -s /sbin/nologin

su - : 切换到指定用户，若不加’-‘，只会切换目录及用户身份，不会切换执行环境
若不指定用户。默认切换到root用户

涉及文件：

/etc/passwd：存放用户信息

/etc/group：存放用户组信息

/etc/shadow：存放用户密码

###文件查找

tree：查看目录结构，-L指定层级深度，tree / -L 2

find：查找文件

-name：指定名字，find / -name 1.txt

-type：指定类型，(b/c/d/p/l)

-size：指定大小，单位K/M/G，+表示大于，-表示小于，find / -size
+1G

-perm：指定权限

-user：指定用户

-group：指定组

-maxdepth：指定最大层级深度

whereis：查找程序，不要使用find(效率太低)

which：专门用来查找命令

alias：给某个命令起别名，alias ls=’ls –color=auto’

unalias：取消别名

grep：正则匹配查找

类结构

1
2
3
4

ReentrantLock-->Lock
NonfairSync/FairSync-->Sync-->AbstractQueuedSynchronizer-->AbstractOwnableSynchronizer
NonfairSync/FairSync-->Sync是ReentrantLock的三个内部类
Node是AbstractQueuedSynchronizer的内部类

非公平锁与非公平锁的创建

非公平锁：
ReentrantLock()或ReentrantLock(false)

1

final ReentrantLock lock = new ReentrantLock();

公平锁：ReentrantLock(true)

1

final ReentrantLock lock = new ReentrantLock(true)

简化版的步骤：（非公平锁的核心）

基于CAS尝试将state（锁数量）从0设置为1

A、如果设置成功，设置当前线程为独占锁的线程；

B、如果设置失败，还会再获取一次锁数量，

B1、如果锁数量为0，再基于CAS尝试将state（锁数量）从0设置为1一次，如果设置成功，设置当前线程为独占锁的线程；

B2、如果锁数量不为0或者上边的尝试又失败了，查看当前线程是不是已经是独占锁的线程了，如果是，则将当前的锁数量+1；如果不是，则将该线程封装在一个Node内，并加入到等待队列中去。等待被其前一个线程节点唤醒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/**
     *获取一个锁
     *三种情况：
     *1、如果当下这个锁没有被任何线程（包括当前线程）持有，则立即获取锁，锁数量==1，之后再执行相应的业务逻辑
     *2、如果当前线程正在持有这个锁，那么锁数量+1，之后再执行相应的业务逻辑
     *3、如果当下锁被另一个线程所持有，则当前线程处于休眠状态，直到获得锁之后，当前线程被唤醒，锁数量==1，再执行相应的业务逻辑
     */
    public void lock() {
        sync.lock();//调用NonfairSync（非公平锁）或FairSync（公平锁）的lock()方法
    }
复制代码
3.2、NonfairSync：lock()


        /**
         * 1）首先基于CAS将state（锁数量）从0设置为1，如果设置成功，设置当前线程为独占锁的线程；-->请求成功-->第一次插队
         * 2）如果设置失败(即当前的锁数量可能已经为1了，即在尝试的过程中，已经被其他线程先一步占有了锁)，这个时候当前线程执行acquire(1)方法
         * 2.1）acquire(1)方法首先调用下边的tryAcquire(1)方法，在该方法中，首先获取锁数量状态，
         * 2.1.1）如果为0(证明该独占锁已被释放，当下没有线程在使用)，这个时候我们继续使用CAS将state（锁数量）从0设置为1，如果设置成功，当前线程独占锁；-->请求成功-->第二次插队；当然，如果设置不成功，直接返回false
         * 2.2.2）如果不为0，就去判断当前的线程是不是就是当下独占锁的线程，如果是，就将当前的锁数量状态值+1（这也就是可重入锁的名称的来源）-->请求成功
         * 
         * 下边的流程一句话：请求失败后，将当前线程链入队尾并挂起，之后等待被唤醒。
         * 
         * 2.2.3）如果最后在tryAcquire(1)方法中上述的执行都没成功，即请求没有成功，则返回false，继续执行acquireQueued(addWaiter(Node.EXCLUSIVE), arg)方法
         * 2.2）在上述方法中，首先会使用addWaiter(Node.EXCLUSIVE)将当前线程封装进Node节点node，然后将该节点加入等待队列（先快速入队，如果快速入队不成功，其使用正常入队方法无限循环一直到Node节点入队为止）
         * 2.2.1）快速入队：如果同步等待队列存在尾节点，将使用CAS尝试将尾节点设置为node，并将之前的尾节点插入到node之前
         * 2.2.2）正常入队：如果同步等待队列不存在尾节点或者上述CAS尝试不成功的话，就执行正常入队（该方法是一个无限循环的过程，即直到入队为止）-->第一次阻塞
         * 2.2.2.1）如果尾节点为空（初始化同步等待队列），创建一个dummy节点，并将该节点通过CAS尝试设置到头节点上去，设置成功的话，将尾节点也指向该dummy节点（即头节点和尾节点都指向该dummy节点）
         * 2.2.2.1）如果尾节点不为空，执行与快速入队相同的逻辑，即使用CAS尝试将尾节点设置为node，并将之前的尾节点插入到node之前
         * 最后，如果顺利入队的话，就返回入队的节点node，如果不顺利的话，无限循环去执行2.2)下边的流程，直到入队为止
         * 2.3）node节点入队之后，就去执行acquireQueued(final Node node, int arg)（这又是一个无限循环的过程，这里需要注意的是，无限循环等于阻塞，多个线程可以同时无限循环--每个线程都可以执行自己的循环，这样才能使在后边排队的节点不断前进）
         * 2.3.1）获取node的前驱节点p，如果p是头节点，就继续使用tryAcquire(1)方法去尝试请求成功，-->第三次插队（当然，这次插队不一定不会使其获得执行权，请看下边一条），
         * 2.3.1.1）如果第一次请求就成功，不用中断自己的线程，如果是之后的循环中将线程挂起之后又请求成功了，使用selfInterrupt()中断自己
         * （注意p==head&&tryAcquire(1)成功是唯一跳出循环的方法，在这之前会一直阻塞在这里，直到其他线程在执行的过程中，不断的将p的前边的节点减少，直到p成为了head且node请求成功了--即node被唤醒了，才退出循环）
         * 2.3.1.2）如果p不是头节点，或者tryAcquire(1)请求不成功，就去执行shouldParkAfterFailedAcquire(Node pred, Node node)来检测当前节点是不是可以安全的被挂起，
         * 2.3.1.2.1）如果node的前驱节点pred的等待状态是SIGNAL（即可以唤醒下一个节点的线程），则node节点的线程可以安全挂起，执行2.3.1.3）
         * 2.3.1.2.2）如果node的前驱节点pred的等待状态是CANCELLED，则pred的线程被取消了，我们会将pred之前的连续几个被取消的前驱节点从队列中剔除，返回false（即不能挂起），之后继续执行2.3）中上述的代码
         * 2.3.1.2.3）如果node的前驱节点pred的等待状态是除了上述两种的其他状态，则使用CAS尝试将前驱节点的等待状态设为SIGNAL，并返回false（因为CAS可能会失败，这里不管失败与否，都返回false，下一次执行该方法的之后，pred的等待状态就是SIGNAL了），之后继续执行2.3）中上述的代码
         * 2.3.1.3）如果可以安全挂起，就执行parkAndCheckInterrupt()挂起当前线程，之后，继续执行2.3）中之前的代码
         * 最后，直到该节点的前驱节点p之前的所有节点都执行完毕为止，我们的p成为了头节点，并且tryAcquire(1)请求成功，跳出循环，去执行。
         * （在p变为头节点之前的整个过程中，我们发现这个过程是不会被中断的）
         * 2.3.2）当然在2.3.1）中产生了异常，我们就会执行cancelAcquire(Node node)取消node的获取锁的意图。
         */

简化版的步骤：（公平锁的核心）

获取一次锁数量，

B1、如果锁数量为0，如果当前线程是等待队列中的头节点，基于CAS尝试将state（锁数量）从0设置为1一次，如果设置成功，设置当前线程为独占锁的线程；

B2、如果锁数量不为0或者当前线程不是等待队列中的头节点或者上边的尝试又失败了，查看当前线程是不是已经是独占锁的线程了，如果是，则将当前的锁数量+1；如果不是，则将该线程封装在一个Node内，并加入到等待队列中去。等待被其前一个线程节点唤醒。

1
2
3
4
5
6
7

/**
     *获取一个锁
     *三种情况：
     *1、如果当下这个锁没有被任何线程（包括当前线程）持有，则立即获取锁，锁数量==1，之后被唤醒再执行相应的业务逻辑
     *2、如果当前线程正在持有这个锁，那么锁数量+1，之后被唤醒再执行相应的业务逻辑
     *3、如果当下锁被另一个线程所持有，则当前线程处于休眠状态，直到获得锁之后，当前线程被唤醒，锁数量==1，再执行相应的业务逻辑
     */