• 面试题总结 20231024

    1.桶排序的应用案例：上亿元素排行榜

     step1: 桶排序本质是一种分治算法

    step2:每个桶都代表了一个元素的范围

    step3:每个桶中的元素都排好序后，取出来，这样子就有序了

    2.简述你们框架中用到的线程模型

    1.actor思想(单线程处理)

    2.xdb加锁(类似的还有mysql的锁机制)

    3.解释下你们xdb中get方法拿锁的流程 和 拿锁是tryLock还是lock，业务执行过长怎么办？时用到的锁是什么？(以秘宝为例子)

    1.首先是GatewayHandler收到玩家请求

    1. public void channelRead(ChannelHandlerContext ctx, Object msg) {
    2.         try {
    3.             if(msg == null) {
    4.                 return;
    5.             }
    6.  
    7.             if(GameServer.isServerClosed()) {
    8.                 return;
    9.             }
    10.  
    11.             ProtobufMessage message = (ProtobufMessage) msg;
    12.             session.parseAndDispatchMessage(message);
    13. }

    2.ClientSession是绑定了根据userId，玩家登录后就也确定了roleId。 所以将上一步的请求和这个玩家信息封装为上下文如：OnlineMsgParam，然后嵌套Instance，扔到xdb线程池中执行

    1.  // 这个是使用xdb.Executor.getInstance()是单例类，是支持了Timeout
    2.         xdb.Executor.getInstance().execute(() ->
    3.                 client2LogicMsgInstance.handle(message, "userId", userId));

    其中这个xdb.Executor.getInstance()是一个支持超时的线程池TimeoutExecutor

    execute方法：

    1. 	public void execute(Runnable command) {
    2. 		super.execute(xdb.Angel.decorateRunnable(command, defaultTimeout));
    3. 	}

    可见这是一个被包装为支持超时的任务了。

    3.这个任务中很可能是一个修改操作，比如：领奖，那么这个业务Task被执行时，里面肯定是触发了一个submit的提交，咱们看下实现：

    1.     @MsgReceiver(MsgArtifact.CSAddPositionExp.class)
    2.     public static void onCSAddPositionExp(OnlineMsgParam param) {
    3.          
    4.         // 这个业务体肯定是在xdb线程中，同时也接收了超时检测，但是我想这个超时检测仅仅是：
    5.         // 这个方法体的，毕竟submit的执行还是异步的。所以一般不会超时，除非带有select这种超时了
    6.  
    7.         new PAddArtifactBaseExp(param.getHumanId(), equips).submit();
    8.     }

    submit的实现如下：

    1.     public final Future<Procedure> submit() {
    2.         // 首先验证下是不是已经在事务内了，在事务内了是不能submit了
    3.         verify();
    5.         // 看着是new了一个ProcedureFuture对象，实际还是任务的提交
    6.         return new ProcedureFuture(this);
    7.     }

    看下构造方法：

    1.     public ProcedureFuture(P p) {
    2.         // 保存下事务
    3.         this.p = p;
    4.  
    5.         // 扔到带有超时检测的线程池中
    6.         // 实现的是Future接口
    7.         future = Xdb.executor().getProcedureTimeoutExecutor()
    8.                 .submit(this, p, p.getConf().getMaxExecutionTime());
    9.  
    10.         // 默认情况下，啥都不干
    11.         this.done = null;
    12.     }

    可见是把当前事务又包装了下，这个submit是自己写的，注意：主角Angle登场了。

    其实还是调用的java线程池的submit，只不过是多了一层Angle的包装：

    1. 	public  Future submit(Runnable task, T result, long timeout) {
    2. 		xdb.Worker.debugHunger(this);
    3. 		return super.submit(xdb.Angel.decorate(task, result, timeout));
    4. 	}

    这个Angle包装下是为了啥呢，接下来看：

    1.   public static <V> Callable<V> decorate(Runnable task, V result, long timeout) {
    2.         // 将Runnable包装为Callable
    3.         final Callable<V> callable = Executors.callable(task, result);
    4.  
    5.         // 默认肯定是有超时检测的，因此这里就是：TimeoutCallable
    6.         return timeout > 0 ? new TimeoutCallable<>(callable, timeout) : callable;
    7.     }

    可见是为了这个TimeoutCallable又进行了包装（又使用TimeoutManager带上了超时检测）

    1.     @Override
    2.     public V call() throws Exception {
    3.         if (timeout > 0) {
    4.             runner = Thread.currentThread();
    5.  
    6.             // 将此任务开始执行前扔到TimeoutManager中，如果到时候没移除，则说明此任务执行超时
    7.             final TimeoutManager tm = TimeoutManager.getInstance();
    8.             tm.schedule(this, timeout);
    9.  
    10.             try {
    11.                 // 任务真正开始执行
    12.                 return inner.call();
    13.             } finally {
    14.                 // 执行完毕后，移除
    15.                 tm.remove(this);
    16.                 runner = null;
    17.             }
    18.         } else {
    19.             return inner.call();
    20.         }
    21.     }

    至此，是不是有点迷糊了，再次后头看一下，其实这个inner.call()执行的实际是啥呢？其实就是：

    ProcedureFuture的方法体，也就是最初：new ProcedureFuture的地方，我们看下这个执行体(只不过这个执行体又被包装了支持了超时检测)

    1. @Override
    2.     public void run() {
    3.         // 存储过程开始执行，执行次数+1
    4.         ++ranTimes;
    5.  
    6.         try {
    7.             // 创建事务和执行存储过程。
    8.             try {
    9.                 // 核心方法：所以这个里面调用的还是call方法
    10.                 Transaction.create().perform(p);
    11.             } finally {
    12.                 // safe if create fail
    13.                 Transaction.destroy();
    14.             }
    15.  
    16.             // 正常存储过程执行结束
    17.             // 但是目前看done变量为空，等于这句啥也没做
    18.             done();
    19.         } catch (XLockDead e) { // 这个异常何时被抛出来呢？其实就是：Lockkey中的无参lock方法使用的是lockInterruptibly，在被超时打断的时候会跑出来
    20.             /** @see Lockey#lock() */
    21.  
    22.             // 重试次数过多
    23.             if (ranTimes >= p.getConf().getRetryTimes()) {
    24.                 done();
    25.  
    26.                 // 达到最大重复次数.报告最终错误.
    27.                 throw new XAngelError();
    28.             }
    29.  
    30.             // 下面是发生死锁了，随机一个时间，进行重试
    31.             int delay = Xdb.random().nextInt(p.getConf().getRetryDelay());
    32.  
    33.             // 再次提交任务到线程池
    34.             future = Xdb.executor().getScheduledTimeoutExecutor().schedule(
    35.                     Executors.callable(this, p),
    36.                     delay,
    37.                     TimeUnit.MILLISECONDS,
    38.                     p.getConf().getMaxExecutionTime());
    39.  
    40.             // 报告死锁错误，future打断当前的监视对象，重新监视。
    41.             throw e;
    42.         } catch (Error error) {
    43.             done();
    44.             throw error;
    45.         } catch (Throwable e) {
    46.             done();
    47.             // 有其他方法,不需要包装一下,直接扔出去吗?
    48.             throw new XError(e);
    49.         }
    50.     }

    我们看下Transaction的perform方法干了啥？其实最重要的就是调用了call方法，从而创建事务，

    并且执行我们的process方法

    1.  public void perform(Procedure p) throws Throwable {
    2.         try {
    3.             // 总数 = .True(未统计此项) + .False + .Exception
    4.             //counter.increment(p.getClass().getName());
    5.             totalCount.incrementAndGet();
    6.  
    7.             // flush lock . MEMORY类型的表本来不需要这个锁，为了不复杂化流程，不做特殊处理。
    8.             Lock flushLock = Xdb.getInstance().getTables().flushReadLock();
    9.             flushLock.lockInterruptibly();
    10.             try {
    11.                 // 重点方法call！！！
    12.                 if (p.call()) {
    13.                     if (_real_commit_() > 0) {
    14.                         logNotify(p);
    15.                         // else : 没有修改，不需要logNotify。至此过程处理已经完成了。
    16.                     }
    17.                 } else {
    18.                     // 执行逻辑返回false统计
    19.                     //counter.increment(p.getClass().getName() + ".False");
    20.                     totalFalse.incrementAndGet();
    21.                     _last_rollback_(); // 应用返回 false，回滚
    22.                 }
    23.             } catch (Throwable e) {
    24.                 // 未处理的异常，回滚
    25.                 _last_rollback_();
    26.                 throw e;
    27.             } finally {
    28.                 // 有多把锁
    29.                 if (deadLockDetection && lockList.size() > 1) {
    30.                     //死锁风险检测
    31.                     deadlockDetection(p.getClass().getName());
    32.                 }
    33.  
    34.                 this.doneRunAllTask();
    35.                 this.finish();
    36.                 flushLock.unlock();
    37.             }
    38.  
    39.         } catch (Throwable e) {
    40.             p.setException(e);
    41.             p.setSuccess(false);
    42.             // 执行异常统计
    43.             //counter.increment(p.getClass().getName() + ".Exception");
    44.             totalException.incrementAndGet();
    45.             // 所有的异常错误都应该处理，尽量不抛到这里。这里仅记录日志。
    46.             Trace.error("Transaction Perform Exception " + p.getClass().getName(), e);
    47.             throw e;
    48.         }
    49.     }

    然后进入到高潮部分，也就call方法，也就是调用我们业务层的process，从而真正业务执行部分(同时在业务异常或者返回false时将本地缓存回滚，也就是log删除掉)

    1. public boolean call() {
    2.         // 当前如果不在事务内
    3.         if (Transaction.current() == null) {
    4.             try {
    5.                 // perform 将回调本函数,然后执行事务已经存在的分支。
    6.                 // 何时被加上事务的呢？其实就是这个Transaction.create()中执行的，当前ThreadLocal没存，则设置下
    7.                 Transaction.create().perform(this);
    8.             } catch (Throwable e) {
    9.                 // this.setException(e); 在 Transaction.perform 里面会保存异常。这里没什么事可做了。
    10.             } finally {
    11.                 Transaction.destroy();
    12.                 this.fetchTasks();
    13.             }
    14.             return this.isSuccess();
    15.         }
    16.  
    17.         // 执行到这里必然是处于事务中了，则记录下保存点
    18.         int savepoint = beginAndSavepoint();
    19.  
    20.         // 捕捉所有异常，在发生异常和process返回false时，回滚到过程开始的保存点。
    21.         // 不捕捉错误，所有的错误抛到外层。
    22.         try {
    23.             if (process()) {
    24.                 commit();
    25.                 this.setSuccess(true);
    26.                 return true;
    27.             }
    28.         } catch (Exception ex) {
    29.             this.setException(ex);
    30.             logErrorFunc.accept(ex);
    31.         }
    32.  
    33.         // 进行业务的回滚
    34.         rollback(savepoint);
    35.  
    36.         return false;
    37.     }

    4.理解xdb中怎么拿锁的

    经过上面的分析，我们看出来，其实就是业务的执行时，仅仅是使用ThreadLocal保存了当前new出来的事务对象，然后接着执行我们的process方法了，里面就是我们游戏层的业务实现了，我们分析下process方法如何拿锁的，我们直接看秘宝的process方法：

    1.映入眼帘的肯定是这一句

    ArtifactBean artifactBean = Artifact.get(humanId);

    2.看一下get方法

    1. 	public static xbean.ArtifactBean get(Long key) throws Exception {
    2. 		return _Tables_.getInstance().artifact.get(key);
    3. 	}

    3.这个方法是重载的

    1. public final V get(K key) throws Exception {
    2.         return get(key, true);
    3.     }

    4.接下来看实现

    1.     public final V get(K key, boolean holdNull) throws Exception {
    2.         if (null == key) {
    3.             throw new NullPointerException("key is null");
    4.         }
    5.  
    6.         countGet.incrementAndGet();
    7.  
    8.         // 从事务本身里先进行查询，也就是在事务内拿过一次锁之后，以后不会再重复拿了
    9.         final Transaction currentT = Transaction.current();
    10.  
    11.         // 先从本地事务哪个普通的Map对象中拿缓存.这段代码算是优化了
    12.         TRecord<K, V> rCached = currentT.getCachedTRecord(this, key);
    13.         if (rCached != null) {
    14.             return rCached.getValue();
    15.         }
    16.  
    17.         // 事务缓存中没拿到，就生成一把锁
    18.         Lockey lockey = Lockeys.get(this, key);
    19.  
    20.         // 这里调用的是：lockInterruptibly方法
    21.         lockey.lock();
    22.         try {
    23.             // 这个是实现LRU算法的，从本地缓存取数据，对应的类是：TTableCacheLRU，取缓存会有一次synchronized的调用，所以上面还有一份事务内的缓存加快访问
    24.             // LRU底层是：包装的LinkedHashMap实现，删除策略是自己实现的
    25.             TRecord<K, V> r = cache.get(key);
    26.  
    27.             // 缓存中不存在
    28.             if (null == r) {
    29.                 // 记录下缓存miss了
    30.                 countGetMiss.incrementAndGet();
    31.  
    32.                 // 缓存中也没有，那就查询sql了
    33.                 V value = _find(key);
    34.  
    35.                 // sql也没查询到
    36.                 if (null == value) {
    37.                     countGetStorageMiss.incrementAndGet();
    38.                     if (holdNull) {
    39.                         currentT.add(lockey);
    40.                     }
    41.                     return null;
    42.                 }
    43.  
    44.                 // sql查询到了
    45.                 r = new TRecord<K, V>(this, value, lockey, TRecord.State.INDB_GET);
    46.  
    47.                 // 先记录数据到LRU缓存中
    48.                 cache.addNoLog(key, r);
    49.             }
    50.  
    51.             // 下面其实是记录一次缓存到本地事务中，这样子不是每次都从LRU cache中取，可以减少一次锁的访问
    52.             // 重点：记录当前事务拿到的锁！ 死锁检测就从这里入手了
    53.             // 注意： 里面还是有一次lock。 所以下面finally会先unlock一次
    54.             currentT.add(lockey);
    55.  
    56.             // 记录下本次事务用过的缓存
    57.             currentT.addCachedTRecord(this, r);
    58.  
    59.             // 返回取到的值
    60.             return r.getValue();
    61.         } finally {
    62.             lockey.unlock();
    63.         }
    64.     }

    分析：

    可以看出来，当前缓存的话，是根据Transaction中一个普通的Map中拿到的，首先根据当前的表名字和key取缓存，毕竟会涉及到多张表，所以是要传入表对象的。

    这样子其实有2份缓存：1份是事务内的缓存，一份是：根据表+synchronized。

    这样子拿过缓存后，就不会再加锁了直接取缓存。否则会查询缓存。

    缓存查询不到，查sql，查到了，则记录到本地事务中

    前面分析了，何时释放所有的锁呢？

    Transaction.java

    1.     /**
    2.      * 结束事务，释放所有锁并且清除，清除wrapper。
    3.      */
    4.     private void finish() {
    5.         wrappers.clear();
    6.  
    7.         // 没有按照lock的顺序unlock。
    8.         for (Lockey lockey : locks.values()) {
    9.             // Trace.debug("unlock " + lockey);
    10.             try {
    11.                 lockey.unlock();
    12.             } catch (Throwable e) {
    13.                 Trace.fatal("unlock " + lockey, e);
    14.             }
    15.         }
    16.         locks.clear();
    17.         cachedTRecord.clear();
    18.     }

    5.理解xdb中的超时检测机制

    如何进行超时检测呢？

    在Exector初始化的时候，就负责开启了一个定时器进行超时检测的处理

    1.       this.scheduled.scheduleWithFixedDelay(
    2.                 // 执行超时检测
    3.                 xdb.util.TimeoutManager.getInstance(),
    4.  
    5.                 timeoutPeriod,
    6.                 timeoutPeriod,
    7.                 TimeUnit.MILLISECONDS);

    检测到超时后，进行打断，咱们的Xdb线程池中的线程都是Worker线程：

    1.  @Override
    2.     public void onTimeout() {
    3.         final Thread r = runner;
    4.  
    5.         // 如果这个r为null，则说明已经执行完了
    6.         if (r != null) {
    7.             if (r instanceof Worker) {
    8.                 ((Worker) r).angelInterrupt();
    9.             } else {
    10.                 r.interrupt();
    11.             }
    12.         }
    13.     }

    打断方法实现如下：

    1.    /**
    2.      * 这个是Worker被打断时，多执行一个标记
    3.      */
    4.     public void angelInterrupt() {
    5.         angel.set(true);
    6.         super.interrupt();
    7.     }

    Lockey中使用的是可被打断的lockInterruptibly：

    1.     /**
    2.      * 这个非常的重要，
    3.      */
    4.     public final void lock() {
    5.         try {
    6.             lock.lockInterruptibly();
    7.         } catch (InterruptedException ex) {
    8.             // 这里我认为其实未必就是真的死锁，有可能业务执行繁忙超时后，也会被打断？
    9.             if (Worker.angelInterrupted()) {
    10.                 throw new XLockDead();
    11.             }
    12.  
    13.             throw new XLockInterrupted(this.toString());
    14.         }
    15.     }

    3.这样子在ArtifactMsgHandler的一个方法处理器中，就会到一个xdb线程池中执行。

    6.简述Recast Nav中障碍的实现

    1.

    7.简述技能系统的实现

    1.

    8.压测都发现了什么问题？

    1.

  • 相关阅读:
    org.postgresql.util.PSQLException: Bad value for type long
    mavenj解决依赖冲突
    C标准文档
    网课答题查题公众号助手搭建教程
    【座位调整】Python 实现-附ChatGPT解析
    数商云：日化用品行业采购智能管理平台整合供应闭环，实现企业端到端寻源采购
    c++学生成绩管理系统
    【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
    Python基础复习-面向对象的编程
    【LeetCode】图解算法数据结构+java代码实现（数据结构篇）
  • 原文地址：https://blog.csdn.net/themagickeyjianan/article/details/134003947